Super-polylogarithmic hypergraph coloring hardness via low-degree long codes

DOI10.1145/2591796.2591882MaRDI QIDQ6829111zbMATH OpenFDO

Authors Venkatesan Guruswami, Prahladh Harsha, Johan Hastad, Srikanth Srinivasan, Girish Varma

Publication date 26 June 2015

Published in Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

zbMATH Keywords

hardness of approximationhypergraph coloringshort code

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

This page was built for publication: Super-polylogarithmic hypergraph coloring hardness via low-degree long codes

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