101 citations · 161 across the 15 of their papers we have counts for
Showing 2014 · cs.CCShow all
3 papers · 2 filters
cs.CC2014
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]…
cs.CC2014★ 1 cited
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…
cs.CC2014★ 1 cited
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…