scientific article; zbMATH DE number 7413504

DOI10.4086/toc.2021.v017a009OpenAlexW3202012722MaRDI QIDQ5158503

Tselil Schramm, Ryan O'Donnell

Publication date: 25 October 2021

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1812.09967

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

combinatorial optimizationhierarchiesSherali-Adams

Mathematics Subject Classification ID

Approximation algorithms (68W25) Complexity of proofs (03F20) Theory of computing (68Qxx)

Related Items

Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem ⋮ A \(7 / 3\)-approximation algorithm for feedback vertex set in tournaments via Sherali-Adams

Uses Software

• Outward rotations

Cites Work

• 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
• Outward rotations
• 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
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
• On the cut polytope
• Max Cut and the Smallest Eigenvalue
• 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
• Integrality gaps for Sherali-Adams relaxations
• Spectral techniques applied to sparse random graphs
• Recognizing More Unsatisfiable Random k-SAT Instances Efficiently
• The RPR2 rounding technique for semidefinite programs
• Rounding Semidefinite Programming Hierarchies via Global Correlation
• An Introduction to Matrix Concentration Inequalities
• Geometry of cuts and metrics
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity