Simultaneous max-cut is harder to approximate than max-cut

DOI10.4230/LIPIcs.CCC.2020.9OpenAlexW3046392294MaRDI QIDQ5092456

Subhash A. Khot, Amey Bhangale

Publication date: 21 July 2022

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

zbMATH Keywords

max-cutunique games hardnesssimultaneous CSPs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Gaussian bounds for noise correlation of functions
• Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
• Simultaneous Approximation of Constraint Satisfaction Problems
• Conditional Hardness for Approximate Coloring
• On the power of unique 2-prover 1-round games
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Better Balance by Being Biased
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder

This page was built for publication: Simultaneous max-cut is harder to approximate than max-cut