Towards sharp inapproximability for any 2-CSP

DOI10.1137/070711670MaRDI QIDQ3068639zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

semidefinite programmingapproximation algorithmsCSPconstraint satisfaction problemsunique games conjecture

Mathematics Subject Classification ID

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

Recommendations

• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Approximation of non-Boolean 2CSP
• Every 2-CSP allows nontrivial approximation
• Every 2-CSP allows nontrivial approximation
• Near-optimal UGC-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)

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?
• Enumerating homomorphisms
• ETH-hardness of approximating 2-CSPs and directed Steiner network
• Every 2-CSP allows nontrivial approximation
• 2 -Way vs.d -Way Branching for CSP
• Simple approximation algorithms for balanced MAX~2SAT
• scientific article; zbMATH DE number 7758361 (Why is no real title available?)
• Noise stability of functions with low influences: invariance and optimality
• Gaussian bounds for noise correlation of resilient functions
• Lower bounds for the graph homomorphism problem
• Approximation Algorithms for CSPs
• Oblivious algorithms for the maximum directed cut problem
• Every 2-CSP allows nontrivial approximation
• 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)