| dc.contributor.author |
Allender, Eric |
|
| dc.contributor.author |
Das, Bireswar |
|
| dc.date.accessioned |
2018-02-12T10:37:31Z |
|
| dc.date.available |
2018-02-12T10:37:31Z |
|
| dc.date.issued |
2017-10 |
|
| dc.identifier.citation |
Allender, Eric and Das, Bireswar, “Zero knowledge and circuit minimization”, Information and Computation, DOI: 10.1016/j.ic.2017.04.004, vol. 256, pp. 2-8, Oct. 2017. |
en_US |
| dc.identifier.issn |
0890-5401 |
|
| dc.identifier.issn |
1090-2651 |
|
| dc.identifier.uri |
https://repository.iitgn.ac.in/handle/123456789/3443 |
|
| dc.identifier.uri |
http://dx.doi.org/10.1016/B978-0-12-812808-4.00006-7 |
|
| dc.description.abstract |
We show that every problem in the complexity class (Statistical Zero Knowledge) is efficiently reducible to the Minimum Circuit Size Problem (). In particular Graph Isomorphism lies in .
This is the first theorem relating the computational power of Graph Isomorphism and , despite the long history these problems share, as candidate -intermediate problems. |
en_US |
| dc.description.statementofresponsibility |
by Eric Allendera and Bireswar Dash |
|
| dc.format.extent |
Vol. 256, pp. 2-8, |
|
| dc.language.iso |
en |
en_US |
| dc.publisher |
Elsevier |
en_US |
| dc.subject |
Graph Isomorphism |
en_US |
| dc.subject |
Minimum Circuit Size Problem |
en_US |
| dc.subject |
NP-intermediate problem |
en_US |
| dc.subject |
Statistical Zero Knowledge |
en_US |
| dc.title |
Zero knowledge and circuit minimization |
en_US |
| dc.type |
Article |
en_US |
| dc.relation.journal |
Information and Computation |
|