Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes
From MaRDI portal
Publication:2968149
DOI10.1137/140995520zbMath1359.68104arXiv1311.7407WikidataQ56958759 ScholiaQ56958759MaRDI QIDQ2968149
Prahladh Harsha, Venkatesan Guruswami, Girish Varma, Srikanth Srinivasan, Johan T. Håstad
Publication date: 10 March 2017
Published in: SIAM Journal on Computing, Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.7407
05C65: Hypergraphs
05C15: Coloring of graphs and hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Uses Software