Publications

Publications and Preprints by Topic

Algorithms    —    Machine Learning    —    Computational Biology

Algorithms

Linear-Sized Spectral Sparsi cation in Almost Quadratic Time and
Regret Minimization Beyond Matrix Multiplicative Weight Updates

With Zeyuan Allen-Zhu and Zhenyu Liao.
Manuscript available upon request.

Nearly-Linear Time Packing and Covering LP Solver with Faster Convergence Rate Than O (1/\varepsilon^2)
With Zeyuan Allen-Zhu.
[ArXiv]

A Novel, Simple Interpretation of Nesterov’s Accelerated Method as a Combination of Gradient and Mirror Descent
With Zeyuan Allen-Zhu.
[ArXiv]

Using Optimization to Break the Epsilon Barrier: A Faster and Simpler Width-Independent Algorithm for Solving Positive Linear Programs in Parallel
With Zeyuan Allen-Zhu.
To appear in SODA’15.
[ArXiv]

Flow-Based Algorithms for Local Graph Clustering
With Zeyuan Allen-Zhu.
SODA’14: Proc. Symp. on Discrete Algorithms, pp. 1267–1286, 2014.
[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.
SODA’14: Proc. Symp. on Discrete Algorithms, pp. 217–226, 2014. 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 Allen-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 Semidefinite-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.