Document Open Access Logo

Minimum Circuit Size, Graph Isomorphism, and Related Problems

Authors Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.20.pdf
  • Filesize: 0.57 MB
  • 20 pages

Document Identifiers

Author Details

Eric Allender
Joshua A. Grochow
Dieter van Melkebeek
Cristopher Moore
Andrew Morgan

Cite As Get BibTex

Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, and Andrew Morgan. Minimum Circuit Size, Graph Isomorphism, and Related Problems. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ITCS.2018.20

Abstract

We study the computational power of deciding whether a given truth-table can be described by a circuit of a given size (the Minimum Circuit Size Problem, or MCSP for short), and of the variant denoted MKTP where circuit size is replaced by a polynomially-related Kolmogorov measure. All prior reductions from supposedly-intractable problems to MCSP / MKTP hinged on the power of MCSP / MKTP to distinguish random distributions from distributions produced by hardness-based pseudorandom generator constructions. We develop a fundamentally different approach inspired by the well-known interactive proof system for the complement of Graph Isomorphism (GI). It yields a randomized reduction with zero-sided error from GI to MKTP. We generalize the result and show that GI can be replaced by any isomorphism problem for which the underlying group satisfies some elementary properties. Instantiations include Linear Code Equivalence, Permutation Group Conjugacy, and Matrix Subspace Conjugacy. Along the way we develop encodings of isomorphism classes that are efficiently decodable and achieve compression that is at or near the information-theoretic optimum; those encodings may be of independent interest.

Subject Classification

Keywords
  • Reductions between NP-intermediate problems
  • Graph Isomorphism
  • Minimum Circuit Size Problem
  • time-bounded Kolmogorov complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger. Power from random strings. SIAM Journal on Computing, 35:1467-1493, 2006. Google Scholar
  2. Eric Allender and Bireswar Das. Zero knowledge and circuit minimization. In Mathematical Foundations of Computer Science 2014, pages 25-32, 2014. Google Scholar
  3. Eric Allender, Joshua Grochow, Dieter van Melkebeek, Cristopher Moore, and Andrew Morgan. Minimum circuit size, graph isomorphism, and related problems. Technical Report TR17-158, Electronic Colloquium on Computational Complexity, 2017. Google Scholar
  4. Eric Allender and Shuichi Hirahara. New insights on the (non)-hardness of circuit minimization and related problems. In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017. To appear. Google Scholar
  5. Eric Allender, Michal Koucký, Detlef Ronneburger, and Sambuddha Roy. The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. Journal of Computer and System Sciences, 77:14-40, 2010. Google Scholar
  6. László Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the 48th annual ACM Symposium on Theory of Computing, pages 684-697, 2016. Google Scholar
  7. László Babai, Paolo Codenotti, and Youming Qiao. Polynomial-time isomorphism test for groups with no abelian normal subgroups. In Automata, Languages, and Programming, pages 51-62, 2012. Google Scholar
  8. László Babai. Local Expansion of Vertex-transitive Graphs and Random Generation in Finite Groups. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 164-174, 1991. Google Scholar
  9. Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Algorithms from natural lower bounds. In Proceedings of the 31st Computational Complexity Conference, pages 10:1-10:24, 2016. Google Scholar
  10. Gudmund Skovbjerg Frandsen and Peter Bro Miltersen. Reviewing bounds on the circuit size of the hardest functions. Information Processing Letters, 95(2):354-357, 2005. Google Scholar
  11. Oded Goldreich, Silvio Micali, and Avi Wigderson. 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. Google Scholar
  12. Oded Goldreich, Amit Sahai, and Salil Vadhan. Can statistical zero knowledge be made non-interactive? or on the relationship of SZK and NISZK. In Advances in Cryptology - CRYPTO '99, pages 467-484, 1999. Google Scholar
  13. Oded Goldreich and Salil Vadhan. Comparing entropies in statistical zero knowledge with applications to the structure of SZK. In Proceedings of the 14th Annual IEEE Conference on Computational Complexity, pages 54-73, 1999. Google Scholar
  14. Oded Goldreich and Salil Vadhan. On the complexity of computational problems regarding distributions. In Oded Goldreich, editor, Studies in Complexity and Cryptography - Miscellanea on the Interplay between Randomness and Computation, pages 13-29. Springer, 2011. Google Scholar
  15. Joshua A. Grochow. Matrix Lie algebra isomorphism. In Proceedings of the 2012 IEEE Conference on Computational Complexity, pages 203-213, 2012. Google Scholar
  16. Johan Håstad, Russell Impagliazzo, Leonid Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28:1364-1396, 1999. Google Scholar
  17. Shuichi Hirahara and Rahul Santhanam. On the average-case complexity of MCSP and its variants. In Proceedings of the 32nd Computational Complexity Conference, pages 7:1-7:20, 2017. Google Scholar
  18. Shuichi Hirahara and Osamu Watanabe. Limits of minimum circuit size problem as oracle. In Proceedings of the 31st Conference on Computational Complexity, pages 18:1-18:20, 2016. Google Scholar
  19. Derek F. Holt, Bettina Eick, and Eamonn A. O'Brien. Handbook of Computational Group Theory. Discrete Mathematics and its Applications. Chapman &Hall/CRC, 2005. Google Scholar
  20. Valentine Kabanets and Jin-Yi Cai. Circuit minimization problem. In Proceedings of the 32nd ACM Symposium on Theory of Computing, pages 73-79, 2000. Google Scholar
  21. Donald E. Knuth. The Art of Computer Programming, volume 3: Sorting and Searching. Addison-Wesley, 1973. Google Scholar
  22. Johannes Köbler, Uwe Schöning, and Jacobo Torán. The Graph Isomorphism Problem: Its Structural Complexity. Birkhauser Verlag, Basel, Switzerland, Switzerland, 1993. Google Scholar
  23. Cody D. Murray and R. Ryan Williams. On the (Non) NP-Hardness of Computing Circuit Complexity. Theory of Computing, 13:1-22, 2017. Google Scholar
  24. Noam Nisan and Avi Wigderson. Hardness vs randomness. Journal of Computer and System Sciences, 49(2):149-167, 1994. Google Scholar
  25. Igor C. Carboni Oliveira and Rahul Santhanam. Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness. In Proceedings of the 32nd Computational Complexity Conference, pages 18:1-18:49, 2017. Google Scholar
  26. Erez Petrank and Ron M. Roth. Is code equivalence easy to decide? IEEE Transactions on Information Theory, 43:1602-1604, 1997. Google Scholar
  27. Michael Rudow. Discrete logarithm and minimum circuit size. Information Processing Letters, 128:1-4, 2017. Google Scholar
  28. Amit Sahai and Salil Vadhan. A complete problem for statistical zero knowledge. Journal of the ACM, 50(2):196-249, 2003. Google Scholar
  29. Ákos Seress. Permutation group algorithms, volume 152 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2003. Google Scholar
  30. Boris A. Trakhtenbrot. A survey of Russian approaches to perebor (brute-force searches) algorithms. IEEE Annals of the History of Computing, 6(4):384-400, 1984. Google Scholar
  31. Masaki Yamamoto. A tighter lower bound on the circuit size of the hardest Boolean functions. Technical Report TR11-086, Electronic Colloquium on Computational Complexity, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact