Xinyi Su, Guangyu He, et al.
Dianli Xitong Zidonghua/Automation of Electric Power Systems
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.
Xinyi Su, Guangyu He, et al.
Dianli Xitong Zidonghua/Automation of Electric Power Systems
Israel Cidon, Leonidas Georgiadis, et al.
IEEE/ACM Transactions on Networking
Preeti Malakar, Thomas George, et al.
SC 2012
A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990