On the Bit Complexity of Sum-of-Squares Proofs
From MaRDI portal
Publication:5111411
DOI10.4230/LIPIcs.ICALP.2017.80zbMath1441.68100arXiv1702.05139OpenAlexW2594565427MaRDI QIDQ5111411
Benjamin Weitz, Prasad Raghavendra
Publication date: 27 May 2020
Full work available at URL: https://arxiv.org/abs/1702.05139
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Complexity of proofs (03F20)
Related Items (15)
Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting) ⋮ 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 ⋮ 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 ⋮ Mean estimation with sub-Gaussian rates in polynomial time ⋮ The Spectrum of the Grigoriev–Laurent Pseudomoments ⋮ 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 ⋮ Sum-of-squares hierarchies for binary polynomial optimization ⋮ Harmonicity and invariance on slices of the Boolean cube
This page was built for publication: On the Bit Complexity of Sum-of-Squares Proofs
