Minimum Circuit Size, Graph Isomorphism, and Related Problems

DOI10.1137/17M1157970zbMath1397.68082arXiv1710.09806OpenAlexW2884885487WikidataQ129516864 ScholiaQ129516864MaRDI QIDQ3176189

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

Publication date: 19 July 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1710.09806

zbMATH Keywords

graph isomorphismminimum circuit size problemtime-bounded Kolmogorov complexityreductions between NP-intermediate problems

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (10)

Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ The Complexity of Complexity ⋮ Cryptographic hardness under projections for time-bounded Kolmogorov complexity ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ Unnamed Item ⋮ The non-hardness of approximating circuit size ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ Circuit lower bounds from NP-hardness of MCSP under turing reductions ⋮ The hidden subgroup problem and MKTP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Black box exceptional groups of Lie type. II.
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• Complexity classes of equivalence problems revisited
• Reviewing bounds on the circuit size of the hardest functions
• Universal classes of hash functions
• Hardness vs randomness
• Discrete logarithm and minimum circuit size
• Zero knowledge and circuit minimization
• Graph Isomorphism is in SPP
• Probabilistic methods in group theory
• Recognition of finite exceptional groups of Lie type
• Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups
• Black box exceptional groups of Lie type
• On the complexity of circuit satisfiability
• Minimum Circuit Size, Graph Isomorphism, and Related Problems
• Circuit minimization problem
• Equivalence Relations, Invariants, and Normal Forms
• A complete problem for statistical zero knowledge
• A Pseudorandom Generator from any One-way Function
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• Is code equivalence easy to decide?
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• Polynomial-time theory of matrix groups
• Graph isomorphism in quasipolynomial time [extended abstract]
• Learning algorithms from natural proofs
• Power from Random Strings

This page was built for publication: Minimum Circuit Size, Graph Isomorphism, and Related Problems