scientific article; zbMATH DE number 806753
From MaRDI portal
Publication:4850554
zbMATH Open0838.03044MaRDI QIDQ4850554FDOQ4850554
Publication date: 6 June 1996
Title of this publication is not available (Why is that?)
Analysis of algorithms and problem complexity (68Q25) First-order arithmetic and fragments (03F30) Complexity of computation (including implicit computational complexity) (03D15)
Cited In (33)
- NP search problems in low fragments of bounded arithmetic
- Upper Bounds on Boolean-Width with Applications to Exact Algorithms
- Mining circuit lower bound proofs for meta-algorithms
- An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
- Circuit complexity before the dawn of the new millennium
- Lower bounds on the area complexity of Boolean circuits
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Bounded arithmetic for NC, ALogTIME, L and NL
- Multifunction algebras and the provability of \(PH\downarrow\)
- Complexity barriers as independence
- Title not available (Why is that?)
- A proof of the Kahn–Kalai conjecture
- On parallel hierarchies and R ki
- Exact lower time bounds for computing Boolean functions on CREW PRAMs
- Unifying known lower bounds via geometric complexity theory
- Circuit principles and weak pigeonhole variants
- Boolean complexity classes vs. their arithmetic analogs
- Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity
- Forcing in Finite Structures
- Relating the bounded arithmetic and polynomial time hierarchies
- Polynomial time ultrapowers and the consistency of circuit lower bounds
- Improved bounds for the sunflower lemma
- Feebly secure cryptographic primitives
- Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
- Unprovability of strong complexity lower bounds in bounded arithmetic
- Some lower bound results for set-multilinear arithmetic computations
- Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
- Title not available (Why is that?)
- \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly
- Bounded arithmetic, proof complexity and two papers of Parikh
- Simplified lower bounds for propositional proofs
- Algebraic methods and bounded formulas
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
Recommendations
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)
