Under the auspices of the Computational Complexity Foundation (CCF)

LATEST > REPORTS:
Next

TR19-095 | 18th July 2019
Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

#### Unambiguous Catalytic Computation

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

TR19-094 | 16th July 2019
Venkatesan Guruswami, Sai Sandeep

#### Rainbow coloring hardness via low sensitivity polymorphisms

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

TR19-093 | 15th July 2019
Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari

#### Improved 3LIN Hardness via Linear Label Cover

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

ISSN 1433-8092 | Imprint