Staff View
Minimum Circuit Size, Graph Isomorphism, and Related Problems

Descriptive

TypeOfResource
Text
TitleInfo
Title
Minimum Circuit Size, Graph Isomorphism, and Related Problems
Name (type = personal); (authority = orcid); (authorityURI = http://id.loc.gov/vocabulary/identifiers/orcid.html); (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 (type = text); (authority = marcrt)
author
Name (type = personal)
NamePart (type = family)
Grochow
NamePart (type = given)
Joshua A.
Affiliation
University of Colorado Boulder
Role
RoleTerm (type = text); (authority = marcrt)
author
Name (type = personal)
NamePart (type = family)
van Melkebeek
NamePart (type = given)
Dieter
Affiliation
University of Wisconsin--Madison
Role
RoleTerm (type = text); (authority = marcrt)
author
Name (type = personal)
NamePart (type = family)
Moore
NamePart (type = given)
Cristopher
Affiliation
Santa Fe Institute (Santa Fe, N.M.)
Role
RoleTerm (type = text); (authority = marcrt)
author
Name (type = personal)
NamePart (type = family)
Morgan
NamePart (type = given)
Andrew
Affiliation
University of Wisconsin--Madison
Role
RoleTerm (type = text); (authority = marcrt)
author
Name (type = corporate); (authority = RutgersOrg-Department)
NamePart
Computer Science (New Brunswick)
Name (type = corporate); (authority = RutgersOrg-School)
NamePart
School of Arts and Sciences (SAS) (New Brunswick)
Genre (authority = RULIB-FS)
Article, Refereed
Genre (authority = NISO JAV)
Accepted Manuscript (AM)
Note (type = peerReview)
Peer reviewed
OriginInfo
DateCreated (encoding = w3cdtf); (qualifier = exact); (keyDate = yes)
2018
Abstract (type = Abstract)
We study the computational power of deciding whether a given truth-table can be described by a circuit of a given size (the Minimum Circuit Size Problem, or MCSP for short), and of the variant denoted MKTP where circuit size is replaced by a polynomially-related Kolmogorov measure. Prior to our work, all reductions from supposedly-intractable problems to MCSP / MKTP hinged on the power of MCSP / MKTP to distinguish random distributions from distributions produced by hardness-based pseudorandom generator constructions. We develop a fundamentally different approach inspired by the well-known interactive proof system for the complement of Graph Isomorphism (GI). It yields a randomized reduction with zero-sided error from GI to MKTP. We generalize the result and show that GI can be replaced by any isomorphism problem for which the underlying group satises some elementary properties. Instantiations include Linear Code Equivalence, Permutation Group Conjugacy, and Matrix Subspace Conjugacy. Along the way we develop encodings of isomorphism classes that are efficiently decodable and achieve compression that is at or near the information-theoretic optimum; those encodings may be of independent interest.
Language
LanguageTerm (authority = ISO 639-3:2007); (type = text)
English
PhysicalDescription
InternetMediaType
application/pdf
Extent
36 p.
Subject (authority = local)
Topic
Reductions between NP-intermediate problems
Subject (authority = local)
Topic
Graph Isomorphism
Subject (authority = local)
Topic
Minimum Circuit Size Problem
Subject (authority = local)
Topic
Time-bounded Kolmogorov complexity
Extension
DescriptiveEvent
Type
Citation
DateTime (encoding = w3cdtf)
2018
AssociatedObject
Name
SIAM Journal on Computing
Type
Journal
Relationship
Has part
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Funder
Name
National Science Foundation
AssociatedEntity
Role
Originator
Name
Eric Allender
AssociatedObject
Type
Grant number
Name
CCF-1555409
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
Joshua A. Grochow
AssociatedObject
Type
Grant number
Name
DMS-1620484
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Funder
Name
National Science Foundation
AssociatedEntity
Role
Originator
Name
Joshua A. Grochow
AssociatedObject
Type
Grant number
Name
DMS-1750319
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Funder
Name
National Science Foundation
AssociatedEntity
Role
Originator
Name
Dieter van Melkebeek
AssociatedObject
Type
Grant number
Name
CCF-1319822
Note (type = special display note)
An extended abstract of this paper appeared in the Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS’18).
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/T3HH6PBZ
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
ApplicationName
pdfTeX-1.40.16
DateCreated (point = end); (encoding = w3cdtf); (qualifier = exact)
2018-04-21T06:05:40
DateCreated (point = end); (encoding = w3cdtf); (qualifier = exact)
2018-04-21T06:05:40
Back to the top
Version 8.3.10
Rutgers University Libraries - Copyright ©2019