Chi-Leung Wong, Zehra Sura, et al.
I-SPAN 2002
We show that it is quasi-NP-hard to color 2-colorable 12-uniform hypergraphs with 2(log n)ω(1) colors where n is the number of vertices. Previously, Guruswami Harsha, Håstad, Srinivasan, and Varma showed that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with {equation presented} colors. Their result is obtained by composing a standard outer probabilistically checkable proof (PCP) with an inner PCP based on the short code of superconstant degree. Our result is instead obtained by composing a new outer PCP with an inner PCP based on the short code of degree two.
Chi-Leung Wong, Zehra Sura, et al.
I-SPAN 2002
Anupam Gupta, Viswanath Nagarajan, et al.
Operations Research
Chidanand Apté, Fred Damerau, et al.
ACM Transactions on Information Systems (TOIS)
Kafai Lai, Alan E. Rosenbluth, et al.
SPIE Advanced Lithography 2007