All reports by Author Sai Sandeep:

__
TR19-094
| 16th July 2019
__

Venkatesan Guruswami, Sai Sandeep#### Rainbow coloring hardness via low sensitivity polymorphisms

__
TR19-092
| 9th July 2019
__

Venkatesan Guruswami, Jakub OprÅ¡al, Sai Sandeep#### Revisiting Alphabet Reduction in Dinur's PCP

Venkatesan Guruswami, Sai Sandeep

A $k$-uniform hypergraph is said to be $r$-rainbow colorable if there is an $r$-coloring of its vertices such that every hyperedge intersects all $r$ color classes. Given as input such a hypergraph, finding a $r$-rainbow coloring of it is NP-hard for all $k \ge 3$ and $r \ge 2$. ... more >>>

Venkatesan Guruswami, Jakub OprÅ¡al, Sai Sandeep

Dinur's celebrated proof of the PCP theorem alternates two main steps in several iterations: gap amplification to increase the soundness gap by a large constant factor (at the expense of much larger alphabet size), and a composition step that brings back the alphabet size to an absolute constant (at the ... more >>>