Approximation Resistance from Pairwise-Independent Subgroups
DOI10.1145/2873054zbMATH Open1426.68115OpenAlexW2514739098MaRDI QIDQ3177800FDOQ3177800
Authors: Siu On Chan 
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
Recommendations
- Approximation resistance from pairwise independent subgroups
- Approximation resistant predicates from pairwise independence
- Approximate subgroups and super-strong approximation
- A characterization of strong approximation resistance
- Approximate subgroups
- Approximate subgroups of residually nilpotent groups
- An approximation principle for congruence subgroups
- Approximation by group invariant subspaces
- Schlichting's theorem for approximate subgroups
- scientific article
inapproximabilityprobabilistically checkable proofsintegrality gapsmaximum constraint satisfaction problems
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (27)
- Proof Complexity Meets Algebra
- A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems
- On regularity of Max-CSPs and Min-CSPs
- SDP gaps from pairwise independence
- Title not available (Why is that?)
- Ultimate greedy approximation of independent sets in subcubic graphs
- Parity is positively useless
- Parameterized inapproximability of independent set in \(H\)-free graphs
- Multitasking capacity: hardness results and improved constructions
- Max-3-Lin over non-abelian groups with universal factor graphs
- On the Approximability of Presidential Type Predicates
- Gaussian bounds for noise correlation of resilient functions
- The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
- Bilu-Linial stability, certified algorithms and the independent set problem
- Simple and local independent set approximation
- Approximation in (Poly-) Logarithmic Space
- Approximation resistant predicates from pairwise independence
- A characterization of approximation resistance for even \(k\)-partite CSPs
- New tools and connections for exponential-time approximation
- Approximation resistance from pairwise independent subgroups
- Approximate graph colouring and the hollow shadow
- The quest for strong inapproximability results with perfect completeness
- Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
- Sum of squares lower bounds from pairwise independence (extended abstract)
- Robust algorithms with polynomial loss for near-unanimity CSPs
- UG-hardness to NP-hardness by losing half
- Approximation in (poly-) logarithmic space
This page was built for publication: Approximation Resistance from Pairwise-Independent Subgroups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177800)
