Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
From MaRDI portal
Publication:1377580
Recommendations
- The polynomial bounds of proof complexity in Frege systems
- scientific article; zbMATH DE number 1114025
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- scientific article; zbMATH DE number 2196511
- Complexity of semialgebraic proofs with restricted degree of falsity
- Complexity of Semialgebraic Proofs with Restricted Degree of Falsity
- scientific article; zbMATH DE number 1916823
- scientific article; zbMATH DE number 2086404
- Theories for subexponential-size bounded-depth Frege proofs
- scientific article; zbMATH DE number 1070621
Cites work
- scientific article; zbMATH DE number 440485 (Why is no real title available?)
- scientific article; zbMATH DE number 3583767 (Why is no real title available?)
- scientific article; zbMATH DE number 1256733 (Why is no real title available?)
- scientific article; zbMATH DE number 1263206 (Why is no real title available?)
- scientific article; zbMATH DE number 1263234 (Why is no real title available?)
- scientific article; zbMATH DE number 524142 (Why is no real title available?)
- scientific article; zbMATH DE number 1114015 (Why is no real title available?)
- scientific article; zbMATH DE number 1163984 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- scientific article; zbMATH DE number 910748 (Why is no real title available?)
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Approximation and Small-Depth Frege Proofs
- Exponential lower bounds for the pigeonhole principle
- Hard examples for resolution
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- Lower bounds for the polynomial calculus
- Lower bounds to the size of constant-depth propositional proofs
- Many hard examples for resolution
- Provability of the pigeonhole principle and the existence of infinitely many primes
- Some remarks on lengths of propositional proofs
- The Complexity of Propositional Proofs
- The independence of the modulo \(p\) counting principles
- The intractability of resolution
- The relative efficiency of propositional proof systems
- \(\text{Count}(q)\) does not imply \(\text{Count}(p)\)
Cited in
(38)- Algebraic proofs over noncommutative formulas
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- scientific article; zbMATH DE number 5901621 (Why is no real title available?)
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- Randomized feasible interpolation and monotone circuits with a local oracle
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- Algebraic proof systems over formulas.
- Propositional proofs and reductions between NP search problems
- Nullstellensatz size-degree trade-offs from reversible pebbling
- scientific article; zbMATH DE number 2086623 (Why is no real title available?)
- Hard examples for the bounded depth Frege proof system
- Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations
- A framework for space complexity in algebraic proof systems
- Characterizing propositional proofs as noncommutative formulas
- On the Complexity of Verifying Regular Properties on Flat Counter Systems,
- Nullstellensatz size-degree trade-offs from reversible pebbling
- Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies
- Towards NP-P via proof complexity and search
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- First-order reasoning and efficient semi-algebraic proofs
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Phase transition of multivariate polynomial systems
- A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- Uniformly generated submodules of permutation modules over fields of characteristic 0.
- Discretely ordered modules as a first-order extension of the cutting planes proof system
- scientific article; zbMATH DE number 1559592 (Why is no real title available?)
- scientific article; zbMATH DE number 7471587 (Why is no real title available?)
- Semialgebraic proofs, IPS lower bounds, and the \(\tau\)-conjecture: can a natural number be negative?
- Propositional proof complexity
- On the degree of ideal membership proofs from uniform families of polynomials over a finite field
- Complexity of Null- and Positivstellensatz proofs
- A bounded arithmetic AID for Frege systems
- The surprising power of constant depth algebraic proofs
- Approximation and Small-Depth Frege Proofs
- Random resolution refutations
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- Extended Nullstellensatz proof systems
This page was built for publication: Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377580)
