Complexity of Positivstellensatz proofs for the knapsack

DOI10.1007/S00037-001-8192-0zbMath0992.68077OpenAlexW2012805418MaRDI QIDQ5957725

Dima Yu. Grigoriev

Publication date: 13 March 2002

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-001-8192-0

zbMATH Keywords

algebraic proof systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (31)

Fair Colorful k-Center Clustering ⋮ Query Complexity in Expectation ⋮ On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy ⋮ SOS Is Not Obviously Automatizable, Even Approximately ⋮ A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem ⋮ Disordered systems insights on computational hardness ⋮ Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials ⋮ An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs ⋮ An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem ⋮ Generalization of the subset sum problem and cubic forms ⋮ 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 ⋮ Algebraic proof systems over formulas. ⋮ Breaking symmetries to rescue sum of squares in the case of makespan scheduling ⋮ On vanishing sums of roots of unity in polynomial calculus and sum-of-squares ⋮ The Spectrum of the Grigoriev–Laurent Pseudomoments ⋮ Unnamed Item ⋮ Symmetric sums of squares over \(k\)-subset hypercubes ⋮ On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy ⋮ A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ On the complexity of Hilbert refutations for partition ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ NLTS Hamiltonians from good quantum codes ⋮ Complexity of Null- and Positivstellensatz proofs ⋮ Size-degree trade-offs for sums-of-squares and positivstellensatz proofs ⋮ Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs ⋮ Fair colorful \(k\)-center clustering

This page was built for publication: Complexity of Positivstellensatz proofs for the knapsack