Algebraic proofs over noncommutative formulas
From MaRDI portal
Publication:642520
DOI10.1016/j.ic.2011.07.004zbMath1251.03072MaRDI QIDQ642520
Publication date: 27 October 2011
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2011.07.004
lower bounds; polynomial calculus; algebraic proof systems; proof complexity; Frege proofs; noncommutative formulas
03F20: Complexity of proofs
Related Items
Characterizing Propositional Proofs as Noncommutative Formulas, Witnessing matrix identities and proof complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Random CNF's are hard for the polynomial calculus
- Exponential lower bounds for the pigeonhole principle
- Resolution over linear equations and multilinear proofs
- The strength of multilinear proofs
- Lower bounds for the polynomial calculus
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Algebraic proof systems over formulas.
- Deterministic polynomial identity testing in non-commutative models
- Monotone simulations of non-monotone proofs.
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- Deterministic Black-Box Identity Testing $pi$-Ordered Algebraic Branching Programs
- Space Complexity in Propositional Calculus
- The relative efficiency of propositional proof systems
- Pseudorandom Generators in Propositional Proof Complexity
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- On the descriptive and algorithmic power of parity ordered binary decision diagrams
- An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- Principles and Practice of Constraint Programming – CP 2004
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
