All reports by Author Sai Sandeep:

__
TR21-007
| 14th January 2021
__

Sai Sandeep#### Almost Optimal Inapproximability of Multidimensional Packing Problems

__
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

__
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

Sai Sandeep

Multidimensional packing problems generalize the classical packing problems such as Bin Packing, Multiprocessor Scheduling by allowing the jobs to be $d$-dimensional vectors. While the approximability of the scalar problems is well understood, there has been a significant gap between the approximation algorithms and the hardness results for the multidimensional variants. ... more >>>

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

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