Tata Institute of Fundamental Research
Hardness of Hypergraph Coloring
Seminar
Speaker:
Girish Varma
Organiser:
Girish Varma
Date:
Friday, 23 May 2014, 10:00 to 11:00
Venue:
AG-80
(Scan to add to calendar)
Abstract:
Abstract: The Graph Coloring problem is to efficiently color the vertices of a graph on n vertices using as few colors as possible such that no edge is monochromatic. All known efficient algorithms till date, only guarantee a $n^\delta$ coloring, when the input is promised to be 3 colorable. However what is known is that it is NP Hard to 4 color a 3 colorable graph. Improving the hardness result to match the algorithms has been an open question for long. However progress had been made in the hypergraph version: Given a 2 colorable hypergraph, prove that its hard to color it using Q colors. The results currently known only give hardness for upto $Q= log^c n$. We give the first results that crosses the log^c barrier using the low-degree polynomial code (aka, the 'short code' of Barak et. al. [FOCS 2012]) and the techniques proposed by Dinur and Guruswami [FOCS 2013] to incorporate this code for inapproximability results. In particular, we prove quasi-NP-hardness of the following problems on n-vertex hyper-graphs:
* Coloring a 2-colorable 8-uniform hypergraph with 2^2^Ω(√loglogn) colors.
* Coloring a 4-colorable 4-uniform hypergraph with 2^2^Ω(√loglogn) colors.
* Coloring a 3-colorable 3-uniform hypergraph with (logn)^Ω(1/logloglogn) colors.
Reference : http://arxiv.org/abs/1311.7407
| Speaker: | Girish Varma |
| Organiser: | Girish Varma |
| Date: | Friday, 23 May 2014, 10:00 to 11:00 |
| Venue: | AG-80 |
(Scan to add to calendar)
Abstract:
Abstract: The Graph Coloring problem is to efficiently color the vertices of a graph on n vertices using as few colors as possible such that no edge is monochromatic. All known efficient algorithms till date, only guarantee a $n^\delta$ coloring, when the input is promised to be 3 colorable. However what is known is that it is NP Hard to 4 color a 3 colorable graph. Improving the hardness result to match the algorithms has been an open question for long. However progress had been made in the hypergraph version: Given a 2 colorable hypergraph, prove that its hard to color it using Q colors. The results currently known only give hardness for upto $Q= log^c n$. We give the first results that crosses the log^c barrier using the low-degree polynomial code (aka, the 'short code' of Barak et. al. [FOCS 2012]) and the techniques proposed by Dinur and Guruswami [FOCS 2013] to incorporate this code for inapproximability results. In particular, we prove quasi-NP-hardness of the following problems on n-vertex hyper-graphs:
* Coloring a 2-colorable 8-uniform hypergraph with 2^2^Ω(√loglogn) colors.
* Coloring a 4-colorable 4-uniform hypergraph with 2^2^Ω(√loglogn) colors.
* Coloring a 3-colorable 3-uniform hypergraph with (logn)^Ω(1/logloglogn) colors.
Reference : http://arxiv.org/abs/1311.7407
* Coloring a 2-colorable 8-uniform hypergraph with 2^2^Ω(√loglogn) colors.
* Coloring a 4-colorable 4-uniform hypergraph with 2^2^Ω(√loglogn) colors.
* Coloring a 3-colorable 3-uniform hypergraph with (logn)^Ω(1/logloglogn) colors.
Reference : http://arxiv.org/abs/1311.7407