Zero Knowledge and Circuit Minimization

Eric Allender; Bireswar Das

doi:10.7282/T38K7CJT

Back

Accepted manuscript

Open access

Peer reviewed

Zero Knowledge and Circuit Minimization

Eric Allender and Bireswar Das

Information and Computation, Vol.256, pp.2-8

2017

DOI:

https://doi.org/10.7282/T38K7CJT

Abstract

Graph Isomorphism

Minimum Circuit Size Problem

NP-Intermediate Problem

Statistical Zero Knowledge

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^MCSP. 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

Files and links (3)

pdf

szk.mcsp224.74 kBDownload View

Accepted Manuscript (AM) Open Access

url

https://doi.org/10.1016/j.ic.2017.04.004View

Version of Record (VoR) Information and Computation

url

Report an accessibility issueView

Please complete a content remediation request to report an accessibility issue with a library electronic resource, website, or service.

Metrics

170 File downloads

111 Record Views

Details

Title: Subtitle: Zero Knowledge and Circuit Minimization
Creators: Eric Allender (Author) - Computer Science (New Brunswick), Rutgers University
Bireswar Das (Author) - Indian Institute of Technology, Gandhinagar
Publication Details: Information and Computation, Vol.256, pp.2-8
Date published: 2017
Publisher: Rutgers University
Number of pages: 10 p.
Grant note: National Science Foundation - CCF-0832787 ; National Science Foundation - CCF-1064785 ; National Science Foundation - CCF-1555409
Academic Unit: School of Arts and Sciences; Computer Science (SAS)
Language: English
Resource Type: Accepted manuscript
Identifiers: 991031549895304646