The Quest for Strong Inapproximability Results with Perfect Completeness

DOI10.1145/3459668OpenAlexW3185022466WikidataQ130978307 ScholiaQ130978307MaRDI QIDQ5032036FDOQ5032036

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/

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

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)

Cited In (2)

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