scientific article; zbMATH DE number 7204388
From MaRDI portal
Publication:5111269
DOI10.4230/LIPIcs.MFCS.2017.54zbMath1441.68082MaRDI QIDQ5111269
Shuichi Hirahara, Eric W. Allender
Publication date: 26 May 2020
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)
Related Items
Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ Unnamed Item ⋮ Hardness of sparse sets and minimal circuit size problem ⋮ Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Average-case linear matrix factorization and reconstruction of low width algebraic branching programs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Circuit lower bounds from NP-hardness of MCSP under turing reductions
Cites Work
- The isomorphism conjecture for constant depth reductions
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Reductions in circuit complexity: An isomorphism theorem and a gap theorem
- Discrete logarithm and minimum circuit size
- The minimum oracle circuit size problem
- Zero Knowledge and Circuit Minimization
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Circuit minimization problem
- Amplifying lower bounds by means of self-reducibility
- On the Structure of Polynomial Time Reducibility
- On the Hardness of Graph Isomorphism
- Minimum Circuit Size, Graph Isomorphism, and Related Problems
- Power from Random Strings
- An Unconditional Study of Computational Zero Knowledge
- Natural proofs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication:
