Complexity of Positivstellensatz proofs for the knapsack

DOI10.1007/S00037-001-8192-0zbMATH Open0992.68077OpenAlexW2012805418MaRDI QIDQ5957725FDOQ5957725

Authors: Dima 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

Recommendations

• Complexity of Null- and Positivstellensatz proofs
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• scientific article; zbMATH DE number 1559524
• scientific article; zbMATH DE number 1916823
• Lower bounds for the polynomial calculus

zbMATH Keywords

algebraic proof systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (35)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems
• Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
• Title not available (Why is that?)
• Semialgebraic proofs, IPS lower bounds, and the \(\tau\)-conjecture: can a natural number be negative?
• Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
• Fair colorful \(k\)-center clustering
• Fair colorful \(k\)-center clustering
• On the complexity of Hilbert refutations for partition
• On the hardest problem formulations for the \(0/1\) Lasserre hierarchy
• Symmetric sums of squares over \(k\)-subset hypercubes
• An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs
• On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
• First-order reasoning and efficient semi-algebraic proofs
• Complexity of Null- and Positivstellensatz proofs
• The Spectrum of the Grigoriev–Laurent Pseudomoments
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• On the hardest problem formulations for the 0/1 Lasserre hierarchy
• Title not available (Why is that?)
• Query complexity in expectation
• Sum of Squares Bounds for the Empty Integral Hull Problem
• Breaking symmetries to rescue sum of squares: the case of makespan scheduling
• Tight size-degree bounds for sums-of-squares proofs
• A Lasserre lower bound for the min-sum single machine scheduling problem
• An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
• Approximating rectangles by juntas and weakly exponential lower bounds for LP relaxations of CSPs
• NLTS Hamiltonians from good quantum codes
• Sum-of-squares lower bounds for densest \(k\)-subgraph
• Disordered systems insights on computational hardness
• SOS is not obviously automatizable, even approximately
• Sum-of-squares hierarchy lower bounds for symmetric formulations
• Algebraic proof systems over formulas.
• Generalization of the subset sum problem and cubic forms
• Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5957725)