Near-optimal NP-hardness of approximating \textsc{Max} k-CSP_R

DOI10.4086/TOC.2022.V018A003zbMATH Open1500.68006OpenAlexW4226060934MaRDI QIDQ5077145FDOQ5077145

Authors: Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan 

Publication date: 18 May 2022

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2022.v018a003

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

zbMATH Keywords

approximation algorithmsconstraint satisfaction problemshardness of approximationunique gamesMax-CSPdictatorship testingnon-Boolean domain

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Analysis of Boolean Functions
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• On the power of unique 2-prover 1-round games
• Noise stability of functions with low influences: invariance and optimality
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
• A PCP characterization of NP with optimal amortized query complexity
• Approximation resistant predicates from pairwise independence
• On weighted vs unweighted versions of combinatorial optimization problems
• Improved approximation algorithms for label cover problems
• The Nonapproximability of Non-Boolean Predicates
• Gowers Uniformity, Influence of Variables, and PCPs
• Parallel approximation algorithms by positive linear programming
• Near-optimal algorithms for maximum constraint satisfaction problems
• Approximation Resistance from Pairwise-Independent Subgroups
• Approximation of non-Boolean 2CSP
• More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
• Towards a proof of the 2-to-1 games conjecture?
• On non-optimally expanding sets in Grassmann graphs
• Small-set expansion in shortcode graph and the 2-to-2 conjecture
• Approximating CSPs using LP relaxation
• Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness
• Approximation algorithm for non-Boolean \textsc{Max}-\(k\)-CSP
• Near-optimal UGC-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)

Cited In (7)

• 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
• Title not available (Why is that?)

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)