新论文 · v1arXiv:2610.37869
Hardness of Coloring $2$-Colorable $3$-Uniform Hypergraphs with $\log^{Ω(1)} n$ Colors
Amey Bhangale, Krishna Priya KM, Simon Rubin-Toles
We show that it is quasi-NP-hard to color a $2$-colorable $3$-uniform hypergraph on $n$ vertices using $O((\log n)^{1/8})$ colors. This exponentially improves the result of Dinur, Regev, and Smyth [Combinatorica'2005], which showed it is quasi-NP-hard to color a $2$-colorable $3$-uniform hypergraph on $n$ vertices using $O((\log \log n)^{1/3})$ colors.
尚无 AI 解读，展示原文摘要
cs.CC