Approximation Resistance from Pairwise-Independent Subgroups
From MaRDI portal
Publication:3177800
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; zbMATH DE number 6538164
Cited in
(27)- 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
- Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
- New tools and connections for exponential-time approximation
- Ultimate greedy approximation of independent sets in subcubic graphs
- Robust algorithms with polynomial loss for near-unanimity CSPs
- Approximate graph colouring and the hollow shadow
- Proof Complexity Meets Algebra
- UG-hardness to NP-hardness by losing half
- A characterization of approximation resistance for even \(k\)-partite CSPs
- Bilu-Linial stability, certified algorithms and the independent set problem
- Approximation resistance from pairwise independent subgroups
- On the Approximability of Presidential Type Predicates
- Max-3-Lin over non-abelian groups with universal factor graphs
- Parameterized inapproximability of independent set in \(H\)-free graphs
- The quest for strong inapproximability results with perfect completeness
- Approximation in (Poly-) Logarithmic Space
- scientific article; zbMATH DE number 7716602 (Why is no real title available?)
- Simple and local independent set approximation
- Multitasking capacity: hardness results and improved constructions
- Approximation in (poly-) logarithmic space
- Sum of squares lower bounds from pairwise independence (extended abstract)
- Gaussian bounds for noise correlation of resilient functions
- SDP gaps from pairwise independence
- Parity is positively useless
- Approximation resistant predicates from pairwise independence
- The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
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)
