2 citations · 2 across the 3 of their papers we have counts for
3 papers
Bounded Independence Fools Halfspaces
Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal +2
We show that any distribution on {-1,1}^n that is k-wise independent fools any halfspace h with error \eps for k = O(\log^2(1/\eps) /\eps^2). Up to logarithmic factors, our result…
List Decoding Tensor Products and Interleaved Codes
Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra
We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes. We show that for {\em every} code, the…
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva +1
Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics and threshold phenomena. Recent work on heuristics, and the satisf…