The Quest for Strong Inapproximability Results with Perfect Completeness

DOI10.1145/3459668MaRDI QIDQ5032036zbMATH OpenOpenAlexWikidataFDO

Authors Joshua Brakensiek, Venkatesan Guruswami

Publication date 16 February 2022

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2017/7553/

zbMATH Keywords

constraint satisfactiondictatorship testinghardness of approximationhypergraph coloringinapproximability

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07) Approximation algorithms (68W25)

Recommendations

• The quest for strong inapproximability results with perfect completeness
• Near-optimal UGC-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
• UG-hardness to NP-hardness by losing half
• Conditional Hardness of Approximating Satisfiable Max 3CSP-q
• Near-optimal algorithms for unique games

Cited in

(4)

• Topology and Adjunction in Promise Constraint Satisfaction
• scientific article; zbMATH DE number 7716602 (Why is no real title available?)
• Linearly ordered colourings of hypergraphs
• On the complexity of symmetric vs. functional PCSPs

This page was built for publication: The Quest for Strong Inapproximability Results with Perfect Completeness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5032036)