The non-hardness of approximating circuit size
From MaRDI portal
Publication:5918358
DOI10.1007/s00224-020-10004-xOpenAlexW2955383056MaRDI QIDQ5918358
Rahul Ilango, Eric W. Allender, Neekon Vafa
Publication date: 3 August 2021
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1721.1/133146.2
Related Items (2)
Cryptographic hardness under projections for time-bounded Kolmogorov complexity ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Reductions in circuit complexity: An isomorphism theorem and a gap theorem
- Discrete logarithm and minimum circuit size
- Zero knowledge and circuit minimization
- The minimum oracle circuit size problem
- Minimum Circuit Size, Graph Isomorphism, and Related Problems
- Circuit minimization problem
- Parity, circuits, and the polynomial-time hierarchy
- Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
- A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
- Hardness magnification near state-of-the-art lower bounds
- New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems
- Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
- On the NP-Completeness of the Minimum Circuit Size Problem.
- Some optimal inapproximability results
- Power from Random Strings
- Natural proofs
- The non-hardness of approximating circuit size
This page was built for publication: The non-hardness of approximating circuit size
