## Webpage:

## Time:

## Venue:

- AG-80

## Organisers:

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:

**Reference :**http://arxiv.org/abs/1311.7407