scientific article; zbMATH DE number 806753
From MaRDI portal
Publication:4850554
Recommendations
Cited in
(43)- Bounded arithmetic for NC, ALogTIME, L and NL
- Lower bounds on the area complexity of Boolean circuits
- Bounded arithmetic, proof complexity and two papers of Parikh
- Exact lower time bounds for computing Boolean functions on CREW PRAMs
- Simplified lower bounds for propositional proofs
- Algebraic methods and bounded formulas
- Multifunction algebras and the provability of PH
- Relating the bounded arithmetic and polynomial time hierarchies
- Feebly secure cryptographic primitives
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Improved bounds for the sunflower lemma
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Polynomial time ultrapowers and the consistency of circuit lower bounds
- Mining circuit lower bound proofs for meta-algorithms
- Unifying known lower bounds via geometric complexity theory
- Circuit principles and weak pigeonhole variants
- Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
- Some lower bound results for set-multilinear arithmetic computations
- Upper Bounds on Boolean-Width with Applications to Exact Algorithms
- Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
- Recent topics on bounded arithmetic and complexity theory
- scientific article; zbMATH DE number 4059392 (Why is no real title available?)
- An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
- Forcing in Finite Structures
- scientific article; zbMATH DE number 2102736 (Why is no real title available?)
- Boolean complexity classes vs. their arithmetic analogs
- NP search problems in low fragments of bounded arithmetic
- Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity
- A satisfiability algorithm for \(\mathrm{AC}^0\)
- A proof of the Kahn–Kalai conjecture
- On parallel hierarchies and R ki
- Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
- Unprovability of strong complexity lower bounds in bounded arithmetic
- Circuit complexity before the dawn of the new millennium
- Complexity barriers as independence
- On small-depth frege proofs for \textsf{PHP}
- From proof complexity to circuit complexity via interactive protocols
- On the consistency of circuit lower bounds for non-deterministic time
- On bounded depth proofs for Tseitin formulas on the grid; revisited
- New bounds on families without large sunflowers
- Lifting for constant-depth circuits and applications to MCSP
- Towards PNP from extended Frege lower bounds
- \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4850554)
