101 citations · 161 across the 15 of their papers we have counts for
4 papers · 1 filter
A Characterization of hard-to-cover CSPs
Amey Bhangale, Prahladh Harsha, Girish Varma
We continue the study of the covering complexity of constraint satisfaction problems (CSPs) initiated by Guruswami, Håstad and Sudan [SIAM J. Comp. 2002] and Dinur and Kol [CCC'13]…
Derandomized Graph Product Results using the Low Degree Long Code
Irit Dinur, Prahladh Harsha, Srikanth Srinivasan +1
In this paper, we address the question of whether the recent derandomization results obtained by the use of the low-degree long code can be extended to other product settings. We c…
Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions
Girish Varma
In a recent result, Khot and Saket [FOCS 2014] proved the quasi-NP-hardness of coloring a 2-colorable 12-uniform hypergraph with colors. This result was prove…
Playing games in an uncertain world
Manoj Gopalkrishnan, Girish Varma
Traditional game theory assumes that the players in the game are aware of the rules of the game. However, in practice, often the players are unaware or have only partial knowledge…