16 citations · 45 across the 22 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.DS2014★ 1 cited
Simultaneous Approximation of Constraint Satisfaction Problems
Amey Bhangale, Swastik Kopparty, Sushant Sachdeva
Given collections of 2SAT clauses on the same set of variables , can we find one assignment that satisfies a large fraction of clauses from each collection? We consider such…