Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
From MaRDI portal
Publication:5941296
DOI10.1016/S0304-3975(00)00157-2zbMath0974.68192OpenAlexW2022749269WikidataQ126570468 ScholiaQ126570468MaRDI QIDQ5941296
Publication date: 20 August 2001
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00157-2
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (39)
Narrow Proofs May Be Maximally Long ⋮ On space and depth in resolution ⋮ Limitations of Algebraic Approaches to Graph Isomorphism Testing ⋮ On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy ⋮ Sum-of-squares rank upper bounds for matching problems ⋮ A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem ⋮ Disordered systems insights on computational hardness ⋮ Noisy tensor completion via the sum-of-squares hierarchy ⋮ Communication Lower Bounds via Critical Block Sensitivity ⋮ An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs ⋮ The matching problem has no small symmetric SDP ⋮ An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Tight size-degree bounds for sums-of-squares proofs ⋮ Sum of Squares Bounds for the Empty Integral Hull Problem ⋮ Sum-of-squares hierarchy lower bounds for symmetric formulations ⋮ Pseudorandom sets in Grassmann graph have near-perfect expansion ⋮ Circular (Yet Sound) Proofs in Propositional Logic ⋮ Breaking symmetries to rescue sum of squares in the case of makespan scheduling ⋮ The Spectrum of the Grigoriev–Laurent Pseudomoments ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Unnamed Item ⋮ On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy ⋮ Proof Complexity Meets Algebra ⋮ Unnamed Item ⋮ Limitations of semidefinite programs for separable states and entangled games ⋮ Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Complexity of Null- and Positivstellensatz proofs ⋮ Propositional proof complexity ⋮ Size-degree trade-offs for sums-of-squares and positivstellensatz proofs ⋮ Sherali-adams strikes back ⋮ Sum-of-Squares Rank Upper Bounds for Matching Problems ⋮ Unnamed Item ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio ⋮ Efficient algorithms for privately releasing marginals via convex relaxations ⋮ Reflections on Proof Complexity and Counting Principles
Cites Work
- Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
- Bounds for the degrees in the Nullstellensatz
- Ramanujan graphs
- Lower bounds for the polynomial calculus
- Stable sets and polynomials
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
- Cones of Matrices and Set-Functions and 0–1 Optimization
- The Complexity of Propositional Proofs
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- Complexity of Null- and Positivstellensatz proofs
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
