SOS Is Not Obviously Automatizable, Even Approximately
From MaRDI portal
Publication:4638114
DOI10.4230/LIPIcs.ITCS.2017.59zbMath1402.90116OpenAlexW2773609948MaRDI QIDQ4638114
Publication date: 3 May 2018
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8198/pdf/LIPIcs-ITCS-2017-59.pdf/
Related Items
Disordered systems insights on computational hardness, Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials, Ideal Membership Problem over 3-Element CSPs with Dual Discriminator Polymorphism, Tight size-degree bounds for sums-of-squares proofs, Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem, A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization, A simplified treatment of Ramana's exact dual for semidefinite programming, The Spectrum of the Grigoriev–Laurent Pseudomoments, How Do Exponential Size Solutions Arise in Semidefinite Programming?, A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian, Lift \& project systems performing on the partial-vertex-cover polytope, Unnamed Item, Unnamed Item, Sum-of-squares hierarchies for binary polynomial optimization, Complexity, exactness, and rationality in polynomial optimization, Sum-of-squares hierarchies for binary polynomial optimization, Complexity, exactness, and rationality in polynomial optimization, High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sums of squares of polynomials with rational coefficients
- Semidefinite programming and arithmetic circuit evaluation
- The ellipsoid method and its consequences in combinatorial optimization
- Geometric algorithms and combinatorial optimization
- Laplacian eigenvalues and the maximum cut problem
- On the complexity of semidefinite programs
- An exact duality theory for semidefinite programming and its complexity implications
- Global Optimization with Polynomials and the Problem of Moments
- Hypercontractive inequalities via SOS, and the Frankl--Rödl graph
- SHARPER COMPLEXITY BOUNDS FOR ZERO-DIMENSIONAL GRÖBNER BASES AND POLYNOMIAL SYSTEM SOLVING
- Class of global minimum bounds of polynomial functions
- Polynomial algorithms in linear programming
- Sum-of-squares proofs and the quest toward optimal algorithms
- Optimisation globale et théorie des moments
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Systems of distinct representatives and linear algebra
- Approximability and proof complexity
- Complexity of Positivstellensatz proofs for the knapsack
- Complexity of Null- and Positivstellensatz proofs
- Strong duality in lasserre's hierarchy for polynomial optimization
