Approximation Resistance from Pairwise-Independent Subgroups
From MaRDI portal
Publication:3177800
DOI10.1145/2873054zbMath1426.68115OpenAlexW2514739098MaRDI QIDQ3177800
Publication date: 2 August 2018
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2873054
probabilistically checkable proofsinapproximabilityintegrality gapsmaximum constraint satisfaction problems
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (19)
On regularity of Max-CSPs and Min-CSPs ⋮ Max-3-Lin over non-abelian groups with universal factor graphs ⋮ Proof Complexity Meets Algebra ⋮ Unnamed Item ⋮ A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems ⋮ On the Approximability of Presidential Type Predicates ⋮ Unnamed Item ⋮ Unnamed Item ⋮ New tools and connections for exponential-time approximation ⋮ Unnamed Item ⋮ Simple and local independent set approximation ⋮ Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs ⋮ Approximation in (Poly-) logarithmic space ⋮ Parameterized inapproximability of independent set in \(H\)-free graphs ⋮ Gaussian bounds for noise correlation of resilient functions ⋮ Multitasking Capacity: Hardness Results and Improved Constructions ⋮ Approximation in (Poly-) Logarithmic Space ⋮ UG-hardness to NP-hardness by losing half ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness
This page was built for publication: Approximation Resistance from Pairwise-Independent Subgroups
