Zero knowledge and circuit minimization

Show simple item record Allender, Eric Das, Bireswar 2018-02-12T10:37:31Z 2018-02-12T10:37:31Z 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.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

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


My Account