Zero Knowledge and Circuit Minimization

1. Allender, E., Buhrman, H., Koucký, M., van Melkebeek, D., Ronneburger, D.: Power from random strings. SIAM Journal on Computing 35, 1467–1493 (2006)

   Article  MATH  MathSciNet  Google Scholar 

2. Arvind, V., Das, B.: SZK proofs for black-box group problems. Theory Comput. Syst. 43(2), 100–117 (2008)

   Article  MATH  MathSciNet  Google Scholar 

3. Arvind, V., Torán, J.: Isomorphism testing: Perspective and open problems. Bulletin of the EATCS 86 (2005)

   Google Scholar 

4. Boppana, R.B., Håstad, J., Zachos, S.: Does co-NP have short interactive proofs? Information Processing Letters 25(2), 127–132 (1987)

   Article  MATH  MathSciNet  Google Scholar 

5. Ben-Or, M., Gutfreund, D.: Trading help for interaction in statistical zero-knowledge proofs. J. Cryptology 16(2), 95–116 (2003)

   Article  MATH  MathSciNet  Google Scholar 

6. Chailloux, A., Ciocan, D.F., Kerenidis, I., Vadhan, S.P.: Interactive and noninteractive zero knowledge are equivalent in the help model. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 501–534. Springer, Heidelberg (2008)

   Chapter  Google Scholar 

7. Cook, S.A.: The complexity of theorem-proving procedures. In: ACM Symposium on Theory of Computing (STOC), pp. 151–158 (1971)

   Google Scholar 

8. Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems. Journal of the ACM 38(3), 691–729 (1991)

   Article  MATH  MathSciNet  Google Scholar 

9. Håstad, J., Impagliazzo, R., Levin, L., Luby, M.: A pseudorandom generator from any one-way function. SIAM Journal on Computing 28, 1364–1396 (1999)

   Article  MATH  MathSciNet  Google Scholar 

10. Kabanets, V., Cai, J.-Y.: Circuit minimization problem. In: ACM Symposium on Theory of Computing (STOC), pp. 73–79 (2000)

    Google Scholar 

11. Kapron, B., Malka, L., Srinivasan, V.: A characterization of non-interactive instance-dependent commitment-schemes (NIC). In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 328–339. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

12. Krajíček, J.: Forcing with Random Variables and Proof Complexity. Cambridge University Press (2011)

    Google Scholar 

13. Köbler, J., Schöning, U., Torán, J.: The Graph Isomorphism Problem: Its Structural Complexity. Birkhauser Verlag, Basel (1993)

    Book  MATH  Google Scholar 

14. Levin, L.A.: Universal sequential search problems. Problems of Information Transmission 9, 265–266 (1973)

    Google Scholar 

15. Levin, L.: Personal communication (2003)

    Google Scholar 

16. Pemmaraju, S., Skiena, S.: Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge University Press, New York (2003)

    Book  Google Scholar 

17. Razborov, A., Rudich, S.: Natural proofs. Journal of Computer and System Sciences 55, 24–35 (1997)

    Article  MATH  MathSciNet  Google Scholar 

18. Trakhtenbrot, B.A.: A survey of Russian approaches to perebor (brute-force searches) algorithms. IEEE Annals of the History of Computing 6(4), 384–400 (1984)

    Article  MATH  MathSciNet  Google Scholar 

19. Variyam, V.N.: Nondeterministic circuit minimization problem and derandomizing Arthur-Merlin games. Int. J. Found. Comput. Sci. 16(6), 1297–1308 (2005)

    Article  Google Scholar 

20. Wikipedia (2014), http://en.wikipedia.org/wiki/NP-intermediate

Download references