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 satisfactioninapproximabilityhardness of approximationhypergraph coloringdictatorship testing

Mathematics Subject Classification ID

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

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

(2)

• scientific article; zbMATH DE number 7716602 (Why is no real title available?)
• Topology and Adjunction in Promise Constraint Satisfaction

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)