Circuit lower bounds in bounded arithmetics
DOI10.1016/J.APAL.2014.08.004zbMATH Open1341.03088OpenAlexW2054191060MaRDI QIDQ466447FDOQ466447
Authors: Ján Pich 
Publication date: 27 October 2014
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.apal.2014.08.004
Recommendations
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic in computer science (03B70) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Title not available (Why is that?)
- Hardness vs randomness
- Title not available (Why is that?)
- Logical foundations of proof complexity
- The polynomial-time hierarchy
- Title not available (Why is that?)
- Title not available (Why is that?)
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- Complete sets and the polynomial-time hierarchy
- Consequences of the provability of NP ⊆ P/poly
- Title not available (Why is that?)
- An arithmetical characterization of NP
- Bounded arithmetic and the polynomial hierarchy
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximate counting in bounded arithmetic
Cited In (24)
- Title not available (Why is that?)
- Constructive separations and their consequences
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Circuits in bounded arithmetic. I
- On Lower Bounds for Constant Width Arithmetic Circuits
- Amplifying lower bounds by means of self-reducibility
- Unprovability of circuit upper bounds in Cook's theory PV
- On defining integers and proving arithmetic circuit lower bounds
- Mathematical Foundations of Computer Science 2004
- Hardness magnification near state-of-the-art lower bounds
- Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity
- Proving Circuit Lower Bounds in High Uniform Classes
- On uniformity and circuit lower bounds
- On theories of bounded arithmetic for \(\mathrm{NC}^1\)
- Polynomial time ultrapowers and the consistency of circuit lower bounds
- Lower bounds for modular counting by circuits with modular gates
- Lower bounds: from circuits to QBF proof systems
- Indistinguishability obfuscation, range avoidance, and bounded arithmetic
- Unprovability of strong complexity lower bounds in bounded arithmetic
- Topological lower bounds for arithmetic networks
- Hardness magnification near state-of-the-art lower bounds
- A remark on pseudo proof systems and hard instances of the satisfiability problem
- Bounded algebra and current-mode digital circuits
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
This page was built for publication: Circuit lower bounds in bounded arithmetics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q466447)
