Proof Complexity Meets Algebra
From MaRDI portal
Publication:4617977
DOI10.1145/3265985zbMath1407.03070arXiv1711.07320OpenAlexW2905780568MaRDI QIDQ4617977
Joanna Ochremiak, Albert Atserias
Publication date: 7 February 2019
Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1711.07320
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Complexity of proofs (03F20)
Related Items
Nullstellensatz size-degree trade-offs from reversible pebbling, Nullstellensatz size-degree trade-offs from reversible pebbling, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Affine systems of equations and counting infinitary logic
- Algebraic proof systems over formulas.
- The wonderland of reflections
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- A combinatorial characterization of resolution width
- On the weak pigeonhole principle
- THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA
- Space Complexity in Propositional Calculus
- Approximation Resistance from Pairwise-Independent Subgroups
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Expander graphs and their applications
- Hard examples for bounded depth frege
- Cones of Matrices and Set-Functions and 0–1 Optimization
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- 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
- Proof complexity meets algebra
- A Proof of the CSP Dichotomy Conjecture
- CSP gaps and reductions in the lasserre hierarchy
- Narrow Proofs May Be Maximally Long
- Classifying the Complexity of Constraints Using Finite Algebras
- The Power of Sherali--Adams Relaxations for General-Valued CSPs
- Tractability and Learnability Arising from Algebras with Few Subpowers
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Principles and Practice of Constraint Programming – CP 2004
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
