Publications

On Acceleration with Noise-Corrupted Gradients
With Jelena Diakonikolas. To appear in ICML'18. [ArXiv]
Last updated on Oct 26, 2021
Alternating Randomized Block Coordinate Descent
With Jelena Diakonikolas. To appear in ICML'18. [ArXiv]
Last updated on Oct 26, 2021
Connected Subgraph Detection with Mirror Descent on SDPs
With Cem Aksoylar and Venkatesh Saligrama. ICML’17. [Proceedings]
Last updated on Oct 26, 2021
Nearly linear-time packing and covering LP solvers
With Zeyuan Allen-Zhu. In Mathematical Programming 2018. [Journal]
Last updated on Oct 26, 2021
The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
With Jelena Diakonikolas. In Submission. [ArXiv]
Last updated on Oct 26, 2021
Solving Packing and Covering LPs in Õ(1ε2) Distributed Iterations with a Single Algorithm and Simpler Analysis
With Jelena Diakonikolas [ArXiv]
Oct 24, 2017
Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method
With Jelena Diakonikolas. ITCS'18. [ArXiv]
Last updated on Oct 26, 2021
Expanders Using Local Edge Flips
With Zeyuan Allen-Zhu, Aditya Bhaskara, Silvio Lattanzi and Vahab Mirrokni. SODA’16: Proc. Symp. Discrete Algorithms, pp. 1-15, 2016. [ArXiv]
Last updated on Oct 26, 2021
Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver
With Zeyuan Allen-Zhu and YinTat Lee. SODA’16: Proc. Symp. Discrete Algorithms, pp. 1824-1831, 2016. [ArXiv]
Last updated on Oct 26, 2021
Linear-Sized Spectral Sparsification in Almost Quadratic Time and Regret Minimization Beyond Matrix Multiplicative Weight Updates
With Zeyuan Allen-Zhu and Zhenyu Liao. STOC’15: Proc. Symp. Theory Computing, pp. 237-245, 2015. [ArXiv]
Last updated on Oct 26, 2021
Nearly-Linear Time Packing and Covering LP Solver with Faster Convergence Rate
With Zeyuan Allen-Zhu. STOC’15: Proc. Symp. Theory Computing, pp. 229-236, 2015. [ArXiv]
Last updated on Oct 26, 2021
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. SODA'15: Proc. Symp. Discrete Algorithms, pp.~1439-1456, 2015. [ArXiv] [Proceedings]
Last updated on Oct 26, 2021
Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent
With Zeyuan Allen-Zhu. ICML’17. [ArXiv]
Last updated on Oct 26, 2021
Flow-Based Algorithms for Local Graph Clustering
With Zeyuan Allen-Zhu. SODA’14: Proc. Symp. Discrete Algorithms, pp. 1267–1286, 2014. [ArXiv] [Proceedings]
Last updated on Oct 26, 2021
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] [Proceedings]
Last updated on Oct 26, 2021
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] [Proceedings]
Last updated on Oct 26, 2021
Approximating the Exponential, the Lanczos Method and an ilde{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. [ArXiv] [Conference Version] [Poster]
Last updated on Oct 26, 2021
Fast Approximation Algorithms for Graph Partitioning Using Spectral and Semidefinite-Programming Techniques
UC Berkeley Dissertation, May 2011. [UC Berkeley Tech Report]
Last updated on Oct 26, 2021
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]
Last updated on Oct 26, 2021
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]
Last updated on Oct 26, 2021
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]
Last updated on Oct 26, 2021
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
Last updated on Oct 26, 2021
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]
Last updated on Oct 26, 2021

Publications

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]
Last updated on Oct 26, 2021
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]
Last updated on Oct 26, 2021

Publications

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.
Last updated on Oct 26, 2021

Fundings

Continuous Perspectives on Accelerated Methods for Combinatorial Optimization (2017-2020) with Alina Ene
NSF CCF Algorithmic Foundations Mar 2018
New Perspectives on Spectral Methods for Graph Algorithms (2013-2016)
NSF CCF Algorithmic Foundations Mar 2018