41 citations · 45 across the 3 of their papers we have counts for
4 papers
Optimal Hitting Sets for Combinatorial Shapes
Aditya Bhaskara, Devendra Desai, Srikanth Srinivasan
We consider the problem of constructing explicit Hitting sets for Combinatorial Shapes, a class of statistical tests first studied by Gopalan, Meka, Reingold, and Zuckerman (STOC 2…
On a Connection Between Small Set Expansions and Modularity Clustering in Social Networks
Bhaskar DasGupta, Devendra Desai
In this paper we explore a connection between two seemingly different problems from two different domains: the small-set expansion problem studied in unique games conjecture, and a…
On the Complexity of Newman's Community Finding Approach for Biological and Social Networks
Bhaskar DasGupta, Devendra Desai
Given a graph of interactions, a module (also called a community or cluster) is a subset of nodes whose fitness is a function of the statistical significance of the pairwise intera…
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
Prahladh Harsha, Moses Charikar, Matthew Andrews +14
These are the lecture notes for the DIMACS Tutorial "Limits of Approximation Algorithms: PCPs and Unique Games" held at the DIMACS Center, CoRE Building, Rutgers University on 20-2…