Publications

Publications and Preprints by Topic

Algorithms    —    Machine Learning    —    Computational Biology

Algorithms

Flow-Based Algorithms for Local Graph Clustering
With Zeyuan A. Zhu.
Accepted at SODA’14.
[ArXiv]

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.
Accepted at SODA’14. Co-winner of Best Paper Award.
[ArXiv]

A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time
With Jonathan A. Kelner, Aaron Sidford and Zeyuan A. Zhu.
STOC’13: Proc. Symp. Theory Computing, pp. 911–920, 2013.
[ArXiv]

Approximating the Exponential, the Lanczos Method and an {\bf \tilde{O}(m)}-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]

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]

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]

 

Machine Learning

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]

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]

 

Computational Biology

A Compact, In Vivo Screen of All 6-mers Reveals Drivers of Tissue-Specific Expression and Guides Synthetic Regulatory Element Design.
With Smith RP*, Riesenfeld SJ*, Holloway AK, Li Q, Murphy KK, Feliciano NM, Oksenberg N, Pollard KS, Ahituv N (2013).
Genome Biology, 2013.
In press.

 

* denotes first author when present.