Next

__
TR19-095
| 18th July 2019
__

Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari#### Unambiguous Catalytic Computation

__
TR19-094
| 16th July 2019
__

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

__
TR19-093
| 15th July 2019
__

Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari#### Improved 3LIN Hardness via Linear Label Cover

Next

Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

The catalytic Turing machine is a model of computation defined by Buhrman, Cleve,

Kouck, Loff, and Speelman (STOC 2014). Compared to the classical space-bounded Turing

machine, this model has an extra space which is filled with arbitrary content in addition

to the clean space. In such a model we study ...
more >>>

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 >>>

Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari

We prove that for every constant $c$ and $\epsilon = (\log n)^{-c}$, there is no polynomial time algorithm that when given an instance of 3LIN with $n$ variables where an $(1 - \epsilon)$-fraction of the clauses are satisfiable, finds an assignment that satisfies at least $(\frac{1}{2} + \epsilon)$-fraction of clauses ... more >>>

Next