85 citations · 294 across the 35 of their papers we have counts for
Showing 2014Show all
2 papers · 1 filter
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…