Towards Sharp Inapproximability for Any 2-CSP

DOI10.1137/070711670zbMath1206.68135OpenAlexW2789043785MaRDI QIDQ3068639

Per Austrin

Publication date: 17 January 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/070711670

zbMATH Keywords

semidefinite programmingCSPapproximation algorithmsconstraint satisfaction problemsunique games conjecture

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

Lower Bounds for the Graph Homomorphism Problem ⋮ Enumerating homomorphisms ⋮ Unnamed Item ⋮ Spectral algorithms for unique games ⋮ Approximation Algorithms for CSPs ⋮ Simple approximation algorithms for balanced MAX~2SAT ⋮ Maximally stable Gaussian partitions with discrete applications ⋮ Noise stability of functions with low influences: invariance and optimality ⋮ Robust optimality of Gaussian noise stability ⋮ Gaussian bounds for noise correlation of resilient functions ⋮ Oblivious algorithms for the maximum directed cut problem ⋮ Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds

This page was built for publication: Towards Sharp Inapproximability for Any 2-CSP