Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Sai Sandeep:

TR20-167 | 9th November 2020
Venkatesan Guruswami, Sai Sandeep

Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture

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

TR19-116 | 9th September 2019
Venkatesan Guruswami, Sai Sandeep

$d$-to-$1$ Hardness of Coloring $4$-colorable Graphs with $O(1)$ colors

Revisions: 1

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

ISSN 1433-8092 | Imprint