An optimal sdp algorithm for max-cut, and equally optimal long code tests

No abstract is available for this paper.

• Publication year

  2008

• Venue

  Symposium on the Theory of Computing

• Publication date

  2008-05-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1374376.1374425
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Balanced max 2-sat might not be the hardest

  2007cited by this paper
• A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations

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

  2007cited by this paper
• SDP gaps and UGC-hardness for MAXCUTGAIN

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

  2005cited by this paper
• Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT

  2005cited by this paper
• On non-approximability for quadratic programs

  2005cited by this paper
• A dozen de Finetti-style results in search of a theory

  2005cited by this paper
• Quadratic forms on graphs

  2005cited by this paper
• Noise stability of functions with low influences: Invariance and optimality

  2005cited by this paper
• Computing over the Reals: Foundations for Scientific Computing

  2005cited by this paper
• Approximating the cut-norm via Grothendieck's inequality

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

  2004influential reference
• Maximizing quadratic programs: extending Grothendieck's inequality

  2004influential reference
• On the optimality of the random hyperplane rounding technique for MAX CUT

  2002influential reference
• On the advantage over a random assignment

  2002cited by this paper
• MAX CUT in cubic graphs

  2002cited by this paper
• Derandomized dimensionality reduction with applications

  2002cited by this paper
• Improved approximation of Max-Cut on graphs of bounded degree

  2002cited by this paper
• Correlation Clustering

  2002cited by this paper
• Constructing worst case instances for semidefinite programming based approximation algorithms

  2001influential reference
• Some optimal inapproximability results

  2001cited by this paper
• The RPR2 rounding technique for semidefinite programs

  2001influential reference
• On Weighted vs Unweighted Versions of Combinatorial Optimization Problems

  2001cited by this paper
• Bipartite Subgraphs and the Smallest Eigenvalue

  2000influential reference
• Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems

  1999cited by this paper
• Derandomizing Approximation Algorithms Based on Semidefinite Programming

  1999cited by this paper
• Résumé de la théorie métrique des produits tensoriels topologiques

  1996cited by this paper
• Gadgets, approximation, and linear programming

  1996cited by this paper
• How good is the Goemans-Williamson MAX CUT algorithm?

  1996influential reference
• Free bits, PCPs and non-approximability-towards tight results

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

  1995influential reference
• Nonpolyhedral Relaxations of Graph-Bisection Problems

  1995cited by this paper
• Combinatorial Properties and the Complexity of a Max-cut Approximation

  1993cited by this paper
• Laplacian eigenvalues and the maximum cut problem

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

  1992cited by this paper
• Sobolev inequalities, the Poisson semigroup, and analysis on the sphere Sn.

  1992cited by this paper
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design

  1988cited by this paper
• A new upper bound for the complex Grothendieck constant

  1987cited by this paper
• Geometric bounds on the Ornstein-Uhlenbeck velocity process

  1985cited by this paper
• P-Complete Approximation Problems

  1976cited by this paper
• Reducibility Among Combinatorial Problems

  1972cited by this paper
• The Value of G

  1936cited by this paper

• RoS-Guard: Robust and Scalable Online Change Detection with Delay-Optimal Guarantees

  2025cites this paper
• MAX BISECTION might be harder to approximate than MAX CUT

  2025influential citation
• Triangles Improve 0.878 Approximation for Maxcut

  2025cites this paper
• On the NP-Hardness Approximation Curve for Max-2Lin(2)

  2024influential citation
• Bounding large-scale Bell inequalities

  2024cites this paper
• Generating mobility networks with generative adversarial networks

  2022cites this paper
• A characterization of approximability for biased CSPs

  2022cites this paper
• Generating Synthetic Mobility Networks with Generative Adversarial Networks

  2022cites this paper
• Proving Lower Bounds Using the Unique Game Conjecture

  2022cites this paper
• Voting algorithms for unique games on complete graphs

  2021cites this paper
• An explicit vector algorithm for high-girth MaxCut

  2021cites this paper
• Quantum entanglement, symmetric nonnegative quadratic polynomials and moment problems

  2020cites this paper
• On the Mysteries of MAX NAE-SAT

  2020influential citation
• Lower Bounds for Max-Cut via Semidefinite Programming

  2020cites this paper
• Max-Cut in Degenerate H-Free Graphs

  2019cites this paper
• Near-optimal approximation algorithm for simultaneous Max-Cut

  2018cites this paper
• Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems

  2018cites this paper
• A Ramsey-type Theorem on the Max-Cut Value of d-Regular Graphs

  2018cites this paper
• Lower Bounds for Max-Cut in H-Free Graphs via Semidefinite Programming

  2018cites this paper
• Memristive Boltzmann machine: A hardware accelerator for combinatorial optimization and deep learning

  2017cites this paper
• Learning the best algorithm for max-cut, clustering, and other partitioning problems

  2016cites this paper
• Memristive Boltzmann machine: A hardware accelerator for combinatorial optimization and deep learning

  2016cites this paper
• Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems

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

  2014cites this paper
• Analysis of Boolean Functions

  2014cites this paper
• A Complete Bibliography of The Bell System Technical Journal , 1960 – 1969

  2013cites this paper
• A characterization of strong approximation resistance

  2013cites this paper
• A Characterization of Approximation Resistance

  2013cites this paper
• Approximation Algorithms and Semidefinite Programming

  2012cites this paper
• On the Usefulness of Predicates

  2012cites this paper
• A new point of NP-hardness for unique games

  2012cites this paper
• A gradient-based randomised heuristic for the maximum cut problem

  2012cites this paper
• A hybridization between memetic algorithm and semidefinite relaxation for the max-cut problem

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

  2012cites this paper
• Approximation Resistance on Satisfiable Instances for Predicates Strictly Dominating Parity

  2012cites this paper
• Strengthened Hardness for Approximating Minimum Unique Game and Small Set Expansion

  2012cites this paper
• Better Balance by Being Biased

  2012cites this paper
• Finding Almost-Perfect Graph Bisections

  2011cites this paper
• Parameterized algorithms on digraph and constraint satisfaction problems

  2010cites this paper
• Improved Parameterized Algorithms for Constraint Satisfaction

  2010cites this paper
• Approximating Linear Threshold Predicates

  2010influential citation
• The Approximability of Learning and Constraint Satisfaction Problems

  2010influential citation
• 3-bit Dictator Testing: 1 vs. 5/8

  2009cites this paper
• Maximally stable Gaussian partitions with discrete applications

  2009cites this paper
• Conditional hardness for satisfiable 3-CSPs

  2009cites this paper
• How to Round Any CSP

  2009cites this paper
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES

  2009cites this paper
• Approximating np-hard problems efficient algorithms and their limits

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

  2009influential citation
• Integrality Gaps for Strong SDP Relaxations of U G

  2009cites this paper
• New Maximally Stable Gaussian Partitions with Discrete Applications

  2009cites this paper
• Max cut and the smallest eigenvalue

  2008cites this paper
• On the Optimality of Some Semidefinite Programming-Based Approximation Algorithms under the Unique Games Conjecture

  2008cites this paper
• Project plan: Approximation of NP-hard optimization problems European Research Council Advanced Grant

  2008influential citation
• Conditional Inapproximability and Limited Independence

  2008influential citation
• Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling

  2008cites this paper
• Approximation Resistant Predicates from Pairwise Independence

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

  2008cites this paper
• Towards Sharp Inapproximability For Any 2-CSP

  2007cites this paper
• SDP gaps and UGC-hardness for MAXCUTGAIN

  2006cites this paper
• On the Unique Games Conjecture (Invited Survey)

  2005cites this paper
• The Unique Games and Sum of Squares: A love hate relation- ship

  year unknowncites this paper