Articles under category:
Constraint Satisfaction
Vol 18, Article 3 (pp 1-29) [APRX-RND16 Spec Issue]
Near-Optimal NP-Hardness of Approximating Max $k$-CSP$_R$
by Pasin Manurangsi, Preetum Nakkiran, and Luca Trevisan
Vol 14, Article 15 (pp 1-24)
Quantum-Walk Speedup of Backtracking Algorithms
by Ashley Montanaro
Vol 14, Article 10 (pp 1-33) [CCC17 Spec Issue]
From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems
by Mrinalkanti Ghosh and Madhur Tulsiani
Vol 13, Article 3 (pp 1-24) [APRX-RND15 Spec Issue]
Towards a Characterization of Approximation Resistance for Symmetric CSPs
by Venkatesan Guruswami and Euiwoong Lee
Vol 11, Article 10 (pp 257-283) [APRX-RND13 Spec Issue]
On the NP-Hardness of Approximating Ordering-Constraint Satisfaction Problems
by Per Austrin, Rajsekar Manokaran, and Cenny Wenner
Vol 10, Article 14 (pp 359-388)
Approximation Resistance on Satisfiable Instances for Sparse Predicates
by Sangxia Huang
Vol 10, Article 13 (pp 341-358) [APRX-RND12 Spec Issue]
Approximation Algorithm for Non-Boolean Max-$k$-CSP
by Konstantin Makarychev and Yury Makarychev
Vol 9, Article 27 (pp 845-862) [Boolean Spec Issue]
Satisfying Degree-$d$ Equations over $GF[2]^n$
by Johan Håstad
Vol 9, Article 23 (pp 703-757) [APRX-RND12 Spec Issue]
Circumventing $d$-to-$1$ for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four
by Cenny Wenner
Vol 9, Article 19 (pp 617-651)
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
by Uriel Feige, Elchanan Mossel, and Dan Vilenchik
Vol 9, Article 11 (pp 413-435)
Improved Inapproximability Results for Maximum $k$-Colorable Subgraph
by Venkatesan Guruswami and Ali Kemal Sinop
Vol 8, Article 12 (pp 269-289)
SDP Gaps from Pairwise Independence
by Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani
Vol 6, Article 5 (pp 85-112)
Can You Beat Treewidth?
by Dániel Marx
Vol 4, Article 5 (pp 111-128)
Approximation Algorithms for Unique Games
by Luca Trevisan