Sherali-adams strikes back

DOI10.4230/LIPIcs.CCC.2019.8OpenAlexW2966742103MaRDI QIDQ5091758

Tselil Schramm, Ryan O'Donnell

Publication date: 27 July 2022

Full work available at URL: https://doi.org/10.4230/lipics.ccc.2019.8

zbMATH Keywords

linear programminggraph eigenvaluessum-of-squaresmax-cutSherali-Adams

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
• Laplacian eigenvalues and the maximum cut problem
• The spectral gap of dense random regular graphs
• Size biased couplings and the spectral gap for random regular graphs
• The expected relative error of the polyhedral approximation of the max- cut problem
• Local Versus Global Properties of Metric Spaces
• Local Global Tradeoffs in Metric Embeddings
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Counting Walks and Graph Homomorphisms via Markov Chains and Importance Sampling
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
• On the cut polytope
• Strongly refuting random CSPs below the spectral threshold
• Sum of squares lower bounds for refuting any CSP
• Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
• HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
• Integrality gaps for Sherali-Adams relaxations
• Spectral techniques applied to sparse random graphs
• Recognizing More Unsatisfiable Random k-SAT Instances Efficiently
• Rounding Semidefinite Programming Hierarchies via Global Correlation
• Geometry of cuts and metrics
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• Analysis 1.