The Quest for Strong Inapproximability Results with Perfect Completeness

DOI10.1145/3459668OpenAlexW3185022466WikidataQ130978307 ScholiaQ130978307MaRDI QIDQ5032036

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 satisfactionhardness of approximationinapproximabilityhypergraph coloringdictatorship testing

Mathematics Subject Classification ID

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

Related Items (2)

Topology and Adjunction in Promise Constraint Satisfaction ⋮ Unnamed Item

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