Sign in
Back
Zero Knowledge and Circuit Minimization
Accepted manuscript   Open access   Peer reviewed

Zero Knowledge and Circuit Minimization

Eric Allender and Bireswar Das
Lecture Notes in Computer Science, Vol.8635, pp.25-32
MFCS 2014 (Budapest, Hungary, 2014)
2014
DOI:
https://doi.org/10.7282/T3WS8W37

Abstract

Graph isomorphism Isomorphisms (Mathematics) Minimum circuit size problem NP-intermediate problem Statistical zero knowledge Zero-knowledge proofs
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.
pdf
szk.mcsp162.78 kBDownloadView
Accepted Manuscript (AM) Open Access
url
http://dx.doi.org/10.1007/978-3-662-44465-8_3View
Version of Record (VoR)Lecture Notes in Computer Science

Metrics

642 File downloads
110 Record Views

Details