Recommendations
Cites work
- scientific article; zbMATH DE number 4066875 (Why is no real title available?)
- scientific article; zbMATH DE number 65749 (Why is no real title available?)
- scientific article; zbMATH DE number 65757 (Why is no real title available?)
- scientific article; zbMATH DE number 3557241 (Why is no real title available?)
- scientific article; zbMATH DE number 1113991 (Why is no real title available?)
- scientific article; zbMATH DE number 1136103 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- An arithmetical characterization of NP
- Approximate counting in bounded arithmetic
- Bounded arithmetic and the polynomial hierarchy
- Complete sets and the polynomial-time hierarchy
- Consequences of the provability of NP ⊆ P/poly
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Hardness vs randomness
- Logical foundations of proof complexity
- ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- The polynomial-time hierarchy
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
Cited in
(24)- Unprovability of circuit upper bounds in Cook's theory PV
- On defining integers and proving arithmetic circuit lower bounds
- Lower bounds for modular counting by circuits with modular gates
- Lower bounds: from circuits to QBF proof systems
- Hardness magnification near state-of-the-art lower bounds
- scientific article; zbMATH DE number 4125345 (Why is no real title available?)
- Mathematical Foundations of Computer Science 2004
- Circuits in bounded arithmetic. I
- Indistinguishability obfuscation, range avoidance, and bounded arithmetic
- Unprovability of strong complexity lower bounds in bounded arithmetic
- A remark on pseudo proof systems and hard instances of the satisfiability problem
- 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
- Bounded algebra and current-mode digital circuits
- Constructive separations and their consequences
- On uniformity and circuit lower bounds
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Amplifying lower bounds by means of self-reducibility
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- On theories of bounded arithmetic for \(\mathrm{NC}^1\)
- Topological lower bounds for arithmetic networks
- On Lower Bounds for Constant Width Arithmetic Circuits
- Polynomial time ultrapowers and the consistency of circuit lower bounds
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)
