Complexity of Positivstellensatz proofs for the knapsack
From MaRDI portal
Publication:5957725
Recommendations
Cited in
(33)- On the hardest problem formulations for the 0/1 Lasserre hierarchy
- Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems
- On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
- Algebraic proof systems over formulas.
- Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
- Fair colorful \(k\)-center clustering
- Disordered systems insights on computational hardness
- Sum-of-squares bounds via Boolean function analysis
- On the complexity of Hilbert refutations for partition
- Fair colorful \(k\)-center clustering
- NLTS Hamiltonians from good quantum codes
- Sum-of-squares lower bounds for densest \(k\)-subgraph
- A Lasserre lower bound for the min-sum single machine scheduling problem
- First-order reasoning and efficient semi-algebraic proofs
- Generalization of the subset sum problem and cubic forms
- scientific article; zbMATH DE number 7378399 (Why is no real title available?)
- Symmetric sums of squares over \(k\)-subset hypercubes
- An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
- Semialgebraic proofs, IPS lower bounds, and the \(\tau\)-conjecture: can a natural number be negative?
- Query complexity in expectation
- A nearly tight sum-of-squares lower bound for the planted clique problem
- An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs
- Tight size-degree bounds for sums-of-squares proofs
- scientific article; zbMATH DE number 7559092 (Why is no real title available?)
- Sum of Squares Bounds for the Empty Integral Hull Problem
- SOS is not obviously automatizable, even approximately
- Approximating rectangles by juntas and weakly exponential lower bounds for LP relaxations of CSPs
- Complexity of Null- and Positivstellensatz proofs
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- On the hardest problem formulations for the \(0/1\) Lasserre hierarchy
- Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
- The Spectrum of the Grigoriev–Laurent Pseudomoments
- Sum of squares lower bounds from symmetry and a good story
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)
