Towards sharp inapproximability for any 2-CSP
DOI10.1137/070711670zbMATH Open1206.68135OpenAlexW2789043785MaRDI QIDQ3068639FDOQ3068639
Authors: 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
Recommendations
semidefinite programmingapproximation algorithmsCSPconstraint satisfaction problemsunique games conjecture
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cited In (20)
- On LP-based approximability for strict CSPs
- Improved NP-inapproximability for 2-variable linear equations
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- ETH-hardness of approximating 2-CSPs and directed Steiner network
- Enumerating homomorphisms
- Every 2-CSP allows nontrivial approximation
- 2 -Way vs.d -Way Branching for CSP
- Simple approximation algorithms for balanced MAX~2SAT
- Title not available (Why is that?)
- Noise stability of functions with low influences: invariance and optimality
- Gaussian bounds for noise correlation of resilient functions
- Approximation Algorithms for CSPs
- Lower bounds for the graph homomorphism problem
- Every 2-CSP allows nontrivial approximation
- Oblivious algorithms for the maximum directed cut problem
- Spectral algorithms for unique games
- Maximally stable Gaussian partitions with discrete applications
- Robust optimality of Gaussian noise stability
- SDP gaps for 2-to-1 and other Label-Cover variants
This page was built for publication: Towards sharp inapproximability for any 2-CSP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3068639)
