All reports by Author Sai Sandeep:

__
TR20-167
| 9th November 2020
__

Venkatesan Guruswami, Sai Sandeep#### Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture

__
TR19-116
| 9th September 2019
__

Venkatesan Guruswami, Sai Sandeep#### $d$-to-$1$ Hardness of Coloring $4$-colorable Graphs with $O(1)$ colors

Revisions: 1

Venkatesan Guruswami, Sai Sandeep

A famous conjecture of Tuza states that the minimum number of edges needed to cover all the triangles in a graph is at most twice the maximum number of edge-disjoint triangles. This conjecture was couched in a broader setting by Aharoni and Zerbib who proposed a hypergraph version of this ... more >>>

Venkatesan Guruswami, Sai Sandeep

The $d$-to-$1$ conjecture of Khot asserts that it is hard to satisfy an $\epsilon$ fraction of constraints of a satisfiable $d$-to-$1$ Label Cover instance, for arbitrarily small $\epsilon > 0$. We prove that the $d$-to-$1$ conjecture for any fixed $d$ implies the hardness of coloring a $4$-colorable graph with $C$ ... more >>>