27 citations · 63 across the 8 of their papers we have counts for
7 papers · 1 filter
Localization of Electrical Flows
Aaron Schild, Satish Rao, Nikhil Srivastava
We show that in any graph, the average length of a flow path in an electrical flow between the endpoints of a random edge is . This is a consequence of a more general…
Capacity Releasing Diffusion for Speed and Locality
Di Wang, Kimon Fountoulakis, Monika Henzinger +2
Diffusions and related random walk procedures are of central importance in many areas of machine learning, data analysis, and applied mathematics. Because they spread mass agnostic…
Strongly Refuting Random CSPs Below the Spectral Threshold
Prasad Raghavendra, Satish Rao, Tselil Schramm
Random constraint satisfaction problems (CSPs) are known to exhibit threshold phenomena: given a uniformly random instance of a CSP with variables and clauses, there is a v…
Faster Parallel Solver for Positive Linear Programs via Dynamically-Bucketed Selective Coordinate Descent
Di Wang, Michael Mahoney, Nishanth Mohan +1
We provide improved parallel approximation algorithms for the important class of packing and covering linear programs. In particular, we present new parallel -approximate packin…
Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction
Di Wang, Satish Rao, Michael W. Mahoney
The linear coupling method was introduced recently by Allen-Zhu and Orecchia for solving convex optimization problems with first order methods, and it provides a conceptually simpl…
Fast phylogeny reconstruction through learning of ancestral sequences
Radu Mihaescu, Cameron Hill, Satish Rao
Given natural limitations on the length DNA sequences, designing phylogenetic reconstruction methods which are reliable under limited information is a crucial endeavor. There have…