Publications and Preprints
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
With Jonathan A. Kelner, YinTat Lee and Aaron Sidford.
[ArXiv]
A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time
With Jonathan A. Kelner, Aaron Sidford and Zeyuan Allen Zhu.
Accepted to STOC’2013.
[ArXiv]
Approximating the Exponential, the Lanczos Method and an 
-Time Spectral Algorithm for Balanced Separator
With Sushant Sachdeva and Nisheeth K. Vishnoi.
STOC’12: Proc. Symp. Theory Computing, pp. 1141–1160, 2012.
[Conference Version] [Full Version on Arxiv]
[STOC Poster]
A Spectral Algorithm with Applications to Exploring Data Graphs Locally
With Michael W. Mahoney and Nisheeth K. Vishnoi.
J. Machine Learning Research, 13, 2339-2365, 2012.
[JMLR Article]
Fast Approximation Algorithms for Graph Partitioning Using Spectral and Semidenite-Programming Techniques
UC Berkeley Dissertation, May 2011.
[UC Berkeley Tech Report]
Towards an SDP-Based Approach to Spectral Methods: A Nearly-Linear Time Algorithm for Graph Partitioning and Decomposition
With Nisheeth K. Vishnoi.
SODA’11: Proc. Symp. on Discrete Algorithms, pp. 532-545, 2011.
[Conference Version]
[Soda Talk]
Implementing Regularization Implicitly Via Approximate Eigenvector Computation
With Michael W. Mahoney.
ICML’11: Proc. 28th Intl. Conf. Machine Learning, pp. 121-128, 2011.
[Conference Version][Full Version on Arxiv]
[ICML Talk][ICML Poster]
Empirical Evaluation of Graph Partitioning Using Spectral Embeddings and Flow
With Kevin J. Lang and Michael W. Mahoney.
SEA’09: Proc. Intl. Symp. Experimental Algorithms, pp. 197-208, 2009.
[Conference Version]
On Partitioning Graphs via Single Commodity Flows
With Leonard Schulman, Umesh V. Vazirani, and Nisheeth K. Vishnoi.
STOC’08: : Proc. Symp. Theory of Computing, pp. 461-470, 2008.
[Conference Version]
[STOC Talk]
On a Cut-Matching Game for the Sparsest Cut Problem
With Rohit Khandekar, Subhash A. Khot, and Nisheeth K. Vishnoi.
EECS Dept., UC Berkeley, Tech. Rep. UCB/EECS-2007-177, 2007.
[UC Berkeley Tech Report]
Localized Techniques for Broadcasting in Wireless Sensor Networks
With Devidatt Dubhashi, Olle Häggström, Alessandro Panconesi, Chiara Petrioli, and Andrea Vitaletti.
DIALM-POMC Workshop on the Foundations of Mobile Computing, Philadelphia, 2004.
[Conference Version]
Algorithmica, 49-4, 2007.
[Journal Version]