## Speaker:

## Affiliation:

Dept. of Applied Math and Computer Science

The Weizmann Institute of Science

Ziskind building, Room 246

Rehovot, 76100 ISRAEL

## Webpage:

## Time:

## Venue:

- A-201 (STCS Seminar Room)

## Organisers:

A k-uniform hypergraph is defined to be q-rainbow colorable (q\leq k) if there exists a coloring of the vertex set with q colors such that every hyperedge contains all the q colors. Given a k-uniform hypergraph which is q rainbow colorable for some q, can we at least find a 2 coloring in polynomial time? This problem comes under the so called *promise* constraint satisfaction problems.

We show that given a k-uniform hypergraph which is (k - 2\sqrt{k})-rainbow colorable, it is NP-hard to find a 2-coloring of it. This improves the result of Guruswami-Lee. We also show NP-hardness of finding a c-coloring of an approximate rainbow colorable (a slightly weaker notion than the rainbow coloring) hypergraph for large c (joint work with Per Austrin and Aditya Potukuchi).