Sherali-adams strikes back
From MaRDI portal
Publication:5091758
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
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.