Near-optimal NP-hardness of approximating \textsc{Max} k-CSP_R
From MaRDI portal
Publication:5077145
Recommendations
- Near-optimal UGC-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
- Near-optimal algorithms for maximum constraint satisfaction problems
- scientific article; zbMATH DE number 6381632
- Approximation algorithm for non-Boolean \textsc{Max}-\(k\)-CSP
- Approximation algorithm for non-Boolean MAX \(k\)-CSP
Cites work
- A PCP characterization of NP with optimal amortized query complexity
- Analysis of Boolean Functions
- Approximating CSPs using LP relaxation
- Approximation Resistance from Pairwise-Independent Subgroups
- Approximation algorithm for non-Boolean \textsc{Max}-\(k\)-CSP
- Approximation of non-Boolean 2CSP
- Approximation resistant predicates from pairwise independence
- Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness
- Gowers Uniformity, Influence of Variables, and PCPs
- Improved approximation algorithms for label cover problems
- More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
- Near-optimal UGC-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
- Near-optimal algorithms for maximum constraint satisfaction problems
- Noise stability of functions with low influences: invariance and optimality
- On non-optimally expanding sets in Grassmann graphs
- On the power of unique 2-prover 1-round games
- On weighted vs unweighted versions of combinatorial optimization problems
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Parallel approximation algorithms by positive linear programming
- Small-set expansion in shortcode graph and the 2-to-2 conjecture
- The Nonapproximability of Non-Boolean Predicates
- Towards a proof of the 2-to-1 games conjecture?
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
Cited in
(7)- scientific article; zbMATH DE number 1833417 (Why is no real title available?)
- Conditional Hardness of Approximating Satisfiable Max 3CSP-q
- Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness
- Automata, Languages and Programming
- The Nonapproximability of Non-Boolean Predicates
- Near-optimal UGC-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
- A toolbox for barriers on interactive oracle proofs
This page was built for publication: Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5077145)
