Lorenzo Orecchia - Publications

The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
With Jelena Diakonikolas.
In submission.
[ArXiv]

Solving Packing and Covering LPs in Distributed Iterations with a Single Algorithm and Simpler Analysis
With Jelena Diakonikolas.
Manuscript.
[ArXiv]

On Acceleration with Noise-Corrupted Gradients
With Jelena Diakonikolas.
To appear in ICML’18.
[ArXiv]

Alternating Randomized Block Coordinate Descent
With Jelena Diakonikolas.
To appear in ICML’18.
[ArXiv]

Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method
With Jelena Diakonikolas.
ITCS’18.
[ArXiv]

Nearly linear-time packing and covering LP solvers
With Zeyuan Allen-Zhu.
In Mathematical Programming 2018.
[Journal]

Connected Subgraph Detection with Mirror Descent on SDPs
With Cem Aksoylar and Venkatesh Saligrama.
ICML’17.
[Proceedings]

Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent
With Zeyuan Allen-Zhu.
ITCS’17.
[ArXiv]

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]

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]

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]

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]

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]

Flow-Based Algorithms for Local Graph Clustering
With Zeyuan Allen-Zhu.
SODA’14: Proc. Symp. Discrete Algorithms, pp. 1267–1286, 2014.
[ArXiv] [Proceedings]

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]

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]

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] [ArXiv]
[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.