> Details

Allender, Eric [Author]; Grochow, Joshua A. [Author]; van Melkebeek, Dieter [Author]; Moore, Cristopher [Author]; Morgan, Andrew [Author] ; Eric Allender and Joshua A. Grochow and Dieter van Melkebeek and Cristopher Moore and Andrew Morgan [Contributor]

Minimum Circuit Size, Graph Isomorphism, and Related Problems

Reference
management

Bookmarks

Remove from
bookmarks

Share this on Whatsapp

Close

Bookmarks



You can manage bookmarks using lists, please log in to your user account for this.
  • Media type: Text; E-Article; Electronic Conference Proceeding
  • Title: Minimum Circuit Size, Graph Isomorphism, and Related Problems
  • Contributor: Allender, Eric [Author]; Grochow, Joshua A. [Author]; van Melkebeek, Dieter [Author]; Moore, Cristopher [Author]; Morgan, Andrew [Author]
  • Published: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018
  • Language: English
  • DOI: https://doi.org/10.4230/LIPIcs.ITCS.2018.20
  • Keywords: Reductions between NP-intermediate problems ; time-bounded Kolmogorov complexity ; Minimum Circuit Size Problem ; Graph Isomorphism
  • Origination:
  • Footnote: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Description: 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.
  • Access State: Open Access