@inproceedings{d04171f242c6423293743b70cf6cbcb3,

title = "Zero knowledge and circuit minimization",

abstract = "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.",

author = "Eric Allender and Bireswar Das",

year = "2014",

month = jan,

day = "1",

doi = "10.1007/978-3-662-44465-8_3",

language = "English (US)",

isbn = "9783662444641",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

number = "PART 2",

pages = "25--32",

booktitle = "Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Proceedings",

address = "Germany",

edition = "PART 2",

note = "39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014 ; Conference date: 25-08-2014 Through 29-08-2014",

}