Zero knowledge and circuit minimization

Show simple item record

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


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


Browse

My Account