Characterizing Propositional Proofs as Noncommutative Formulas
DOI10.1137/16M1107632zbMath1426.03037arXiv1412.8746OpenAlexW2963930882WikidataQ113779130 ScholiaQ113779130MaRDI QIDQ4577770
Iddo Tzameret, Fu Li, Zheng Yu Wang
Publication date: 3 August 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1412.8746
Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Algebraic proofs over noncommutative formulas
- Exponential lower bounds for the pigeonhole principle
- Resolution over linear equations and multilinear proofs
- The strength of multilinear proofs
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Unsolvable systems of equations and proof complexity
- 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
- Untersuchungen über das logische Schliessen. II
- Monotone simulations of non-monotone proofs.
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Non-commutative arithmetic circuits with division
- QUASIPOLYNOMIAL SIZE FREGE PROOFS OF FRANKL’S THEOREM ON THE TRACE OF SETS
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- The relative efficiency of propositional proof systems
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- The Parallel Evaluation of General Arithmetic Expressions
- On Interpolation and Automatization for Frege Systems
- Circuit Complexity, Proof Complexity, and Polynomial Identity Testing
- Witnessing matrix identities and proof complexity
- Pseudorandom Generators in Propositional Proof Complexity
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- Short Proofs for the Determinant Identities
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams
- Tensor-Rank and Lower Bounds for Arithmetic Formulas
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- Principles and Practice of Constraint Programming – CP 2004
This page was built for publication: Characterizing Propositional Proofs as Noncommutative Formulas
