Approximation resistance from pairwise independent subgroups

DOI10.1145/2488608.2488665zbMath1293.68163OpenAlexW2125534993MaRDI QIDQ5495815

Siu-On Chan

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2488608.2488665

zbMATH Keywords

probabilistically checkable proofsinapproximabilitymaximum constraint satisfaction problemintegrality gaps

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (15)

Simultaneous Approximation of Constraint Satisfaction Problems ⋮ Approximating CSPs Using LP Relaxation ⋮ Combinatorial Auctions with Conflict-Based Externalities ⋮ Combinatorial optimization. Abstracts from the workshop held November 9--15, 2014. ⋮ On the Lovász Theta Function for Independent Sets in Sparse Graphs ⋮ Inapproximability of $H$-Transversal/Packing ⋮ Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors ⋮ Affine reductions for LPs and SDPs ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network ⋮ Approximation Algorithms for CSPs ⋮ Unnamed Item ⋮ Imperfect gaps in Gap-ETH and PCPs ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness ⋮ An Improved Dictatorship Test with Perfect Completeness ⋮ Direct Sum Testing

This page was built for publication: Approximation resistance from pairwise independent subgroups