Approximability and proof complexity
From MaRDI portal
Publication:5741820
DOI10.1137/1.9781611973105.111zbMath1422.68132arXiv1211.1958OpenAlexW2950706437MaRDI QIDQ5741820
Publication date: 15 May 2019
Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1211.1958
Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Complexity of proofs (03F20)
Related Items (12)
Quantum de Finetti theorems under local measurements with applications ⋮ On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy ⋮ Sum-of-squares rank upper bounds for matching problems ⋮ SOS Is Not Obviously Automatizable, Even Approximately ⋮ Communication Lower Bounds via Critical Block Sensitivity ⋮ An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem ⋮ Tight size-degree bounds for sums-of-squares proofs ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ Lift-and-project methods for set cover and knapsack ⋮ Size-degree trade-offs for sums-of-squares and positivstellensatz proofs ⋮ Hypercontractive inequalities via SOS, and the Frankl--Rödl graph ⋮ Efficient algorithms for privately releasing marginals via convex relaxations
This page was built for publication: Approximability and proof complexity
