Staff View
The non-hardness of approximating circuit size

Descriptive

TypeOfResource
Text
TitleInfo
Title
The non-hardness of approximating circuit size
Name (authority = orcid); (authorityURI = http://id.loc.gov/vocabulary/identifiers/orcid.html); (type = personal); (valueURI = http://orcid.org/0000-0002-0650-028X)
NamePart (type = family)
Allender
NamePart (type = given)
Eric
Affiliation
Computer Science (New Brunswick), Rutgers University
Role
RoleTerm (authority = marcrt); (type = text)
author
Name (type = personal)
NamePart (type = family)
Ilango
NamePart (type = given)
Rahul
Affiliation
Computer Science (New Brunswick), Rutgers University
Role
RoleTerm (authority = marcrt); (type = text)
author
Name (type = personal)
NamePart (type = family)
Vafa
NamePart (type = given)
Neekon
Affiliation
Harvard University
Role
RoleTerm (authority = marcrt); (type = text)
author
Name (authority = RutgersOrg-Department); (type = corporate)
NamePart
Computer Science (New Brunswick)
Name (authority = RutgersOrg-School); (type = corporate)
NamePart
School of Arts and Sciences (SAS) (New Brunswick)
Genre (authority = RULIB-FS)
Conference Paper or Lecture
Genre (authority = NISO JAV)
Corrected Version of Record (CVoR)
Note (type = peerReview)
Peer reviewed
OriginInfo
DateCreated (encoding = w3cdtf); (keyDate = yes); (qualifier = exact)
2019
Publisher
Springer-Verlag
Abstract (type = Abstract)
The Minimum Circuit Size Problem (MCSP) has been the focus of intense study recently; MCSP is hard for SZK under rather powerful reductions, and is provably not hard under “local” reductions computable in TIME(n^0.49). The question of whether MCSP is NP-hard (or indeed, hard even for small subclasses of P) under some of the more familiar notions of reducibility (such as many-one or Turing reductions computable in polynomial time or in AC0) is closely related to many of the longstanding open questions in complexity theory.
All prior hardness results for MCSP hold also for computing somewhat weak approximations to the circuit complexity of a function. Some of these results were proved by exploiting a connection to a notion of time-bounded Kolmogorov complexity (KT) and the corresponding decision problem (MKTP). More recently, a new approach for proving improved hardness results for MKTP was developed, but this approach establishes only hardness of extremely good approximations of the form 1+o(1), and these improved hardness results are not yet known to hold for MCSP. In particular, it is known that MKTP is hard for the complexity class DET under nonuniform AC0 many-one reductions, implying MKTP is not in AC0[p] for any prime p. It was still open if similar circuit lower bounds hold for MCSP. One possible avenue for proving a similar hardness result for MCSP would be to improve the hardness
of approximation for MKTP beyond 1 + o(1) to omega(1), as KT-complexity and circuit size are
polynomially-related. In this paper, we show that this approach cannot succeed.
More specifically, we prove that PARITY does not reduce to the problem of computing superlinear approximations to KT-complexity or circuit size via AC0-Turing reductions that make O(1) queries. This is significant, since approximating any set in P/poly AC0-reduces to just one query of a much worse approximation of circuit size or KT-complexity. For weaker approximations, we also prove non-hardness under more powerful reductions. Our non-hardness results are unconditional, in contrast to conditional results presented in [7] (for more powerful reductions, but for much worse approximations). This highlights obstacles that would have to be overcome by any proof that MKTP or MCSP is hard for NP under AC0 reductions. It may also be a step toward confirming a conjecture of Murray and Williams, that MCSP is not NP-complete under logtime-uniform AC0 many-one reductions.
Language
LanguageTerm (authority = ISO 639-3:2007); (type = text)
English
PhysicalDescription
InternetMediaType
application/pdf
Extent
1 online resource (16 pages)
Subject (authority = local)
Topic
Minimum circuit size problem
Subject (authority = local)
Topic
Reductions
Subject (authority = local)
Topic
NP-completeness
Subject (authority = local)
Topic
Time-bounded Kolmogorov complexity
Extension
DescriptiveEvent
Type
Citation
AssociatedEntity
Role
Publisher
Name
Springer-Verlag
DateTime (encoding = w3cdtf)
2019-07
AssociatedObject
Name
Computer Science – Theory and Applications. 14th International Computer Science Symposium in Russia, (CSR)
Type
Journal
Relationship
Has part
Reference (type = url)
http://dx.doi.org/10.1007/978-3-030-19955-5_2
Extension
DescriptiveEvent
Type
Conference
AssociatedObject
Name
Computer Science in Russia (CSR)
Type
Conference
Detail
14
Place
Novosibirsk, Russia
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Funder
Name
National Science Foundation
AssociatedEntity
Role
Originator
Name
Eric Allender
AssociatedObject
Type
Grant number
Name
CCF-1514164
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Funder
Name
National Science Foundation
AssociatedEntity
Role
Originator
Name
Rahul Ilango
AssociatedObject
Type
Grant number
Name
CCF-1559855
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Funder
Name
National Science Foundation
AssociatedEntity
Role
Originator
Name
Neekon Vafa
AssociatedObject
Type
Grant number
Name
CCF-1559855
RelatedItem (type = host)
TitleInfo
Title
Allender, Eric
Identifier (type = local)
rucore30165700001
Location
PhysicalLocation (authority = marcorg); (displayLabel = Rutgers, The State University of New Jersey)
NjNbRU
Identifier (type = doi)
doi:10.7282/t3-za19-d168
Genre (authority = ExL-Esploro)
Journal Article
Back to the top

Rights

RightsDeclaration (AUTHORITY = FS); (TYPE = [FS] statement #1); (ID = rulibRdec0004)
Copyright for scholarly resources published in RUcore is retained by the copyright holder. By virtue of its appearance in this open access medium, you are free to use this resource, with proper attribution, in educational and other non-commercial settings. Other uses, such as reproduction or republication, may require the permission of the copyright holder.
Copyright
Status
Copyright protected
Availability
Status
Open
Reason
Permission or license
RightsEvent
Type
Permission or license
AssociatedObject
Type
License
Name
Multiple author license v. 1
Detail
I hereby grant to Rutgers, The State University of New Jersey (Rutgers) the non-exclusive right to retain, reproduce, and distribute the deposited work (Work) in whole or in part, in and from its electronic format, without fee. This agreement does not represent a transfer of copyright to Rutgers.Rutgers may make and keep more than one copy of the Work for purposes of security, backup, preservation, and access and may migrate the Work to any medium or format for the purpose of preservation and access in the future. Rutgers will not make any alteration, other than as allowed by this agreement, to the Work.I represent and warrant to Rutgers that the Work is my original work. I also represent that the Work does not, to the best of my knowledge, infringe or violate any rights of others.I further represent and warrant that I have obtained all necessary rights to permit Rutgers to reproduce and distribute the Work and that any third-party owned content is clearly identified and acknowledged within the Work.By granting this license, I acknowledge that I have read and agreed to the terms of this agreement and all related RUcore and Rutgers policies.
Back to the top

Technical

RULTechMD (ID = TECHNICAL1)
ContentModel
Document
CreatingApplication
Version
1.5
DateCreated (point = start); (encoding = w3cdtf); (qualifier = exact)
2019-03-21T16:50:54
DateCreated (point = start); (encoding = w3cdtf); (qualifier = exact)
2019-03-21T16:50:54
ApplicationName
itext-paulo-155 (itextpdf.sf.net-lowagie.com)
Back to the top
Version 8.3.13
Rutgers University Libraries - Copyright ©2020