Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES

No abstract is available for this paper.

• Publication year

  2009

• Venue

  2009 50th Annual IEEE Symposium on Foundations of Computer Science

• Publication date

  2009-10-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/FOCS.2009.73
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• SDP Integrality Gaps with Local ell_1-Embeddability

  2009cited by this paper
• SDP Integrality Gaps with Local̀ 1-Embeddability Subhash Khot

  2009cited by this paper
• Integrality gaps for Sherali-Adams relaxations

  2009cited by this paper
• How to Round Any CSP

  2009cited by this paper
• Towards computing the Grothendieck constant

  2009influential reference
• CSP gaps and reductions in the lasserre hierarchy

  2009influential reference
• Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph

  2008cited by this paper
• Optimal algorithms and inapproximability results for every CSP?

  2008cited by this paper
• Improved Approximation Guarantees through Higher Levels of SDP Hierarchies

  2008cited by this paper
• SDP Gaps and UGC Hardness for Multiway Cut , 0-Extension and Metric Labelling

  2008cited by this paper
• An optimal sdp algorithm for max-cut, and equally optimal long code tests

  2008cited by this paper
• Linear Level Lasserre Lower Bounds for Certain k-CSPs

  2008cited by this paper
• Unique games on expanding constraint graphs are easy: extended abstract

  2008cited by this paper
• A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover

  2007cited by this paper
• Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut

  2007influential reference
• Intrusion-Resilient Secret Sharing

  2007cited by this paper
• Towards Sharp Inapproximability For Any 2-CSP

  2007cited by this paper
• One-way multiparty communication lower bound for pointer jumping with applications

  2007cited by this paper
• Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations

  2007cited by this paper
• New Lower Bounds for Vertex Cover in the Lovasz-Schrijver Hierarchy

  2006cited by this paper
• New approximation guarantee for chromatic number

  2006cited by this paper
• Integrality gaps for sparsest cut and minimum linear arrangement problems

  2006cited by this paper
• Near-optimal algorithms for unique games

  2006cited by this paper
• ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUT

  2005cited by this paper
• Approximation algorithms for unique games

  2005influential reference
• Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy

  2005cited by this paper
• Gowers uniformity, influence of variables, and PCPs

  2005influential reference
• The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l/sub 1/

  2005cited by this paper
• The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into 1 (Extended Abstract)

  2005influential reference
• Noise stability of functions with low influences: Invariance and optimality

  2005cited by this paper
• Expander flows, geometric embeddings and graph partitioning

  2004cited by this paper
• Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?

  2004influential reference
• Vertex cover might be hard to approximate to within 2-/spl epsiv/

  2003cited by this paper
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0-1 Programming

  2003cited by this paper
• Rank bounds and integrality gaps for cutting planes procedures

  2003cited by this paper
• On the power of unique 2-prover 1-round games

  2002cited by this paper
• On the distribution of the fourier spectrum of Boolean functions

  2002cited by this paper
• Proving integrality gaps without knowing the linear program

  2002cited by this paper
• An Explicit Exact SDP Relaxation for Nonlinear 0-1 Programs

  2001cited by this paper
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

  1995cited by this paper
• A Geometric Approach to Betweenness

  1995cited by this paper
• Two-prover one-round proof systems: their power and their problems (extended abstract)

  1992cited by this paper
• Cones of Matrices and Set-Functions and 0-1 Optimization

  1991cited by this paper
• A hierarchy of relaxation between the continuous and convex hull representations

  1990cited by this paper
• A Hierarchy of Relaxations Between the Continuous and Convex Hull Representations for Zero-One Programming Problems

  1990cited by this paper

• On Semi-Algebraic Proofs and Algorithms

  2022cites this paper
• On L1-Embeddability of Unions of L1-Embeddable Metric Spaces and of Twisted Unions of Hypercubes

  2021cites this paper
• Superlinear Integrality Gaps for the Minimum Majority Problem

  2021cites this paper
• A stress-free sum-of-squares lower bound for coloring

  2021cites this paper
• Approximation Algorithms and Hardness for Strong Unique Games

  2020cites this paper
• Playing unique games on certified small-set expanders

  2020cites this paper
• Subexponential LPs Approximate Max-Cut

  2019influential citation
• On Local Testability in the Non-Signaling Setting

  2019cites this paper
• C C ] 21 M ay 2 01 2 Hypercontractivity , Sum-of-Squares Proofs , and their Applications

  2018cites this paper
• Small Set Expansion in The Johnson Graph

  2018cites this paper
• Testing Linearity against Non-signaling Strategies

  2018cites this paper
• Polynomial Proof Systems, Effective Derivations, and their Applications in the Sum-of-Squares Hierarchy

  2017cites this paper
• A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover

  2017cites this paper
• Treewidth, Extended Formulations of CSP and MSO Polytopes, and their Algorithmic Applications

  2017cites this paper
• Strengths and Limitations of Linear Programming Relaxations

  2017cites this paper
• Hardness of Approximation

  2016cites this paper
• Bypassing UGC from Some Optimal Geometric Inapproximability Results

  2016cites this paper
• Optimal Approximabilities beyond CSPs : Thesis Proposal

  2016cites this paper
• From Weak to Strong LP Gaps for All CSPs

  2016cites this paper
• On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique

  2016cites this paper
• Candidate hard unique game

  2016cites this paper
• No Small Linear Program Approximates Vertex Cover within a Factor 2 -- e

  2015cites this paper
• Extended Formulation for CSP that is Compact for Instances of Bounded Treewidth

  2015cites this paper
• Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program

  2015cites this paper
• On the Integrality Gap of Directed Steiner Tree Problem

  2014cites this paper
• Locally Testable Codes and Small-Set Expanders Guru Guruganesh December 8 , 2014 A report based on the paper “ Making the Long Code Shorter , with applications to the Unique Games Conjecture

  2014cites this paper
• Sum-of-squares proofs and the quest toward optimal algorithms

  2014cites this paper
• Unique Games on the Hypercube

  2014cites this paper
• Goldreich's PRG: Evidence for Near-Optimal Polynomial Stretch

  2014cites this paper
• Candidate Lasserre Integrality Gap For Unique Games

  2014cites this paper
• Unique Games Conjecture : the Boolean Hypercube and connections to graph lifts

  2014cites this paper
• Hardness of Graph Pricing Through Generalized Max-Dicut

  2014cites this paper
• Social choice, computational complexity, Gaussian geometry, and Boolean functions

  2014cites this paper
• On expansion and spectral properties of simplicial complexes

  2013cites this paper
• Rounding Lasserre SDPs using column selection and spectrum-based approximation schemes for graph partitioning and Quadratic IPs

  2013cites this paper
• 2 Np-hardness

  2013cites this paper
• A Characterization of Approximation Resistance

  2013influential citation
• Lecture 24: Hardness Assumptions

  2013cites this paper
• Sparsest cut on bounded treewidth graphs: algorithms and hardness results

  2013cites this paper
• Integer Programming and Combinatorial Optimization

  2013cites this paper
• Inapproximability Reductions and Integrality Gaps

  2013cites this paper
• Cones of multipowers and combinatorial optimization problems

  2013cites this paper
• A characterization of strong approximation resistance

  2013influential citation
• New Results in the Theory of Approximation: Fast Graph Algorithms and Inapproximability

  2013cites this paper
• Beyond Worst Case Analysis in Approximation Algorithms

  2012cites this paper
• Approximation Algorithms and Semidefinite Programming

  2012cites this paper
• Hypercontractive inequalities via SOS, with an application to Vertex-Cover

  2012cites this paper
• Truth vs. Proof in Computational Complexity

  2012cites this paper
• Semidefinite Programming and Constraint Programming

  2012cites this paper
• Convex Relaxations and Integrality Gaps

  2012cites this paper
• SDP Gaps from Pairwise Independence

  2012cites this paper
• Hypercontractive inequalities via SOS, and the Frankl-Rödl graph

  2012cites this paper
• Hypercontractivity, sum-of-squares proofs, and their applications

  2012cites this paper
• Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems

  2012cites this paper
• Faster SDP Hierarchy Solvers for Local Rounding Algorithms

  2012cites this paper
• Approximability and proof complexity

  2012cites this paper
• A PRG for lipschitz functions of polynomials with applications to sparsest cut

  2012influential citation
• On Hierarchies of Strong SDP Relaxations for Combinatorial Optimization Problems

  2012cites this paper
• Hypercontractivity, sum-of-squares proofs, and their applications

  2012cites this paper
• Majority is stablest: discrete and SoS

  2012influential citation
• Making the Long Code Shorter

  2012influential citation
• A New Approach Towards Graph Coloring

  2012cites this paper
• An introduction to the Ribe program

  2012cites this paper
• An introduction to the Ribe program

  2012cites this paper
• Finding Dense Structures in Graphs and Matrices

  2012cites this paper
• On LP-based approximability for strict CSPs

  2011cites this paper
• Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph

  2011cites this paper
• Rounding Semidefinite Programming Hierarchies via Global Correlation

  2011cites this paper
• Some Problems in Proof Complexity and Combinatorial Optimization

  2011cites this paper
• Making the long code shorter, with applications to the Unique Games Conjecture

  2011cites this paper
• Approximating CSPs with global cardinality constraints using SDP hierarchies

  2011cites this paper
• Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy

  2011cites this paper
• Sparsest Cut on Quotients of the Hypercube

  2011cites this paper
• Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry

  2011influential citation
• Graph Partitioning and Semi-definite Programming Hierarchies

  2011cites this paper
• Subexponential Algorithms for Unique Games and Related Problems

  2010cites this paper
• Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain

  2010influential citation
• The Sherali-Adams System Applied to Vertex Cover: Why Borsuk Graphs Fool Strong LPs and some Tight Integrality Gaps for SDPs

  2010cites this paper
• Subexponential Algorithms for dto-1 Two-Prover Games and for Certifying Almost Perfect Expansion

  2010cites this paper
• Fast SDP algorithms for constraint satisfaction problems

  2010cites this paper
• Reductions between Expansion Problems

  2010cites this paper
• O Lp- A  S Csp

  2010cites this paper
• Approximate Lasserre Integrality Gap for Unique Games

  2010influential citation
• Graph expansion and the unique games conjecture

  2010influential citation
• SDP Gaps for 2-to-1 and Other Label-Cover Variants

  2010cites this paper
• Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack

  2010cites this paper
• Semidefinite Programming and Approximation Algorithms: A Survey

  2010cites this paper
• Subexponential Algorithms for U  G  and Related Problems

  2010cites this paper
• On the complexity of unique games and graph expansion

  2010cites this paper
• Approximating Sparsest Cut in Graphs of Bounded Treewidth

  2010cites this paper
• Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations

  2010influential citation
• Improved Algorithms for Unique Games via Divide and Conquer

  2010cites this paper
• Improving Integrality Gaps via Chvátal-Gomory Rounding

  2010cites this paper
• Spectral Algorithms for Unique Games

  2010cites this paper
• On the Optimality of a Class of LP-based Algorithms

  2009influential citation
• Hardness amplification in proof complexity

  2009cites this paper
• Local Constraints in Combinatorial Optimization

  2009cites this paper
• The Approximability of Some NP-hard Problems Thesis proposal

  2009cites this paper
• Subsampling Semidefinite Programs and Max-Cut on the Sphere

  2009cites this paper
• Intractability results for problems in computational learning and approximation

  2009influential citation