Minimum Circuit Size, Graph Isomorphism, and Related Problems

DOI10.4230/LIPIcs.ITCS.2018.20zbMath1462.68045OpenAlexW2963858417MaRDI QIDQ4993283

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

Publication date: 15 June 2021

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8345/pdf/LIPIcs-ITCS-2018-20.pdf/

zbMATH Keywords

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (1)

Unnamed Item

Cites Work

• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• Reviewing bounds on the circuit size of the hardest functions
• Hardness vs randomness
• Discrete logarithm and minimum circuit size
• Zero Knowledge and Circuit Minimization
• On the Complexity of Computational Problems Regarding Distributions
• Circuit minimization problem
• 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
• Graph isomorphism in quasipolynomial time [extended abstract]
• Learning algorithms from natural proofs
• Power from Random Strings
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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