Prahladh Harsha: Improved Inapproximability results for Hypergraph Coloring

Practicalities

Lunch is served at 12:00 noon (register at this doodle by Sunday March 23 at 8 pm). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for ca two hours of more technical discussions.

Abstract

Despite the tremendous progress in understanding the approximability of several problems, the status of approximate coloring of constant colorable (hyper)graphs is not resolved and in fact, there is an exponential (if not doubly exponential) gap between the best known approximation algorithms and inapproximability results. The best known approximation algorithms which are a combination of combinatorial and semi-definite programming methods, require at least n^delta colors to color a 2 colorable 4-uniform hypergraph for some constant delta in (0,1). On the contrary, till recently, the best known hardness results could rule out at best coloring a 2-colorable hypergraph with polylog n colors (if not polyloglog n colors in some cases).

Recently, with the discovery of the low-degree polynomial long code (aka short code of Barak et al [FOCS 2012]), there has been a super-polynomial (and in some cases, exponential) improvement in the inapproximability results. In particular, we prove quasi-NP-hardness of the following problems on n-vertex hypergraphs:

• Coloring a 2-colorable 8-uniform hypergraph with 2^{2^{\sqrt{log log n}} colors.
• Coloring a 4-colorable 4-uniform hypergraph with 2^{2^{\sqrt{log log n}} colors
• Coloring a 3-colorable 3-uniform hypergraph with (log n)^{1/log log log n} colors.

These results are obtained using the low-degree polynomial code and the techniques proposed by Dinur and Guruswami [FOCS 2013] to incorporate this code for inapproximability results.

In this talk, I'll explain the bottleneck in obtaining improved coloring inapproximability results using the long code and how derandomizations of the long code (the short code in our setting) can be used to improve the inapproximability factors.

Joint work with V. Guruswami, J. Håstad, S. Srinivasan, G. Varma.