Staff View
Zero Knowledge and Circuit Minimization

Descriptive

TypeOfResource
Text
TitleInfo
Title
Zero Knowledge and Circuit Minimization
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)
Das
NamePart (type = given)
Bireswar
Affiliation
Indian Institute of Technology, Gandhinagar
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)
Article, Refereed
Genre (authority = NISO JAV)
Accepted Manuscript (AM)
Note (type = peerReview)
Peer reviewed
OriginInfo
DateIssued (encoding = w3cdtf); (keyDate = yes); (qualifier = exact)
2017
Abstract (type = Abstract)
We show that every problem in the complexity class SZK (Statistical Zero Knowledge) is efficiently reducible to the Minimum Circuit Size Problem (MCSP). In particular Graph Isomorphism lies in RP<sup>MCSP</sup>.

This is the first theorem relating the computational power of Graph Isomorphism and MCSP, despite the
long history these problems share, as candidate NP-intermediate problems
Language
LanguageTerm (authority = ISO 639-3:2007); (type = text)
English
PhysicalDescription
InternetMediaType
application/pdf
Extent
10 p.
Subject (authority = local)
Topic
Graph Isomorphism
Subject (authority = local)
Topic
Minimum Circuit Size Problem
Subject (authority = local)
Topic
NP-Intermediate Problem
Subject (authority = local)
Topic
Statistical
Zero Knowledge
Extension
DescriptiveEvent
Type
Citation
AssociatedObject
Name
Information and Computation
Type
Journal
Relationship
Has part
Reference (type = url)
https://doi.org/10.1016/j.ic.2017.04.004
Identifier (type = volume and issue)
256
Detail
2-8
DateTime (encoding = w3cdtf)
2017
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Funder
Name
National Science Foundation
AssociatedEntity
Role
Originator
Name
Eric Allender
AssociatedObject
Type
Grant number
Name
CCF-0832787
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Funder
Name
National Science Foundation
AssociatedEntity
Role
Originator
Name
Eric Allender
AssociatedObject
Type
Grant number
Name
CCF-1064785
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
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/T38K7CJT
Back to the top

Rights

RightsDeclaration (AUTHORITY = Creative Commons); (ID = https://creativecommons.org/licenses/by-nc-nd/4.0/); (TYPE = Attribution-NonCommercial-NoDerivs (CC BY-NC-ND))
This work has been licensed by the rightsholder under a Creative Commons Attribution-NonCommercial-NoDerivs (CC BY-NC-ND) 4.0 International License (https://creativecommons.org/licenses/by-nc-nd/4.0/).
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.
RightsEvent
Type
Embargo
DateTime (encoding = w3cdtf); (point = end)
2018-04-26
Detail
Access to this PDF has been restricted at the publisher's request. It will be publicly available after April 26, 2018.
RightsEvent
Type
Permission or license
AssociatedObject
Type
License
Name
Creative Commons Attribution-NonCommercial-NoDerivs (CC BY-NC-ND) license
Reference (type = digital)
https://creativecommons.org/licenses/by-nc-nd/4.0/
Back to the top

Technical

RULTechMD (ID = TECHNICAL1)
ContentModel
Document
DateCreated (point = end); (encoding = w3cdtf); (qualifier = exact)
2017-04-27T22:37:23
CreatingApplication
Version
1.4
ApplicationName
pdfeTeX-1.21a
DateCreated (point = start); (encoding = w3cdtf); (qualifier = exact)
2017-04-27T22:26:49
Back to the top
Version 8.3.10
Rutgers University Libraries - Copyright ©2019