Publications

Deven Mithal, Lorenzo Orecchia. Geometry and Duality of Alternating Markov Chains. 2024.
ArXiv
Konstantinos Ameranis, Adela Frances DePavia, Lorenzo Orecchia, Erasmo Tani. Fast Algorithms for Hypergraph PageRank with Applications to Semi-Supervised Learning. ICML, 2024.
ICML Poster PMLR
Yuepeng Yang, Antares Chen, Lorenzo Orecchia, Cong Ma. Top-K ranking with a monotone adversary. COLT, 2024.
ArXiv PMLR
Konstantinos Ameranis, Antares Chen, Lorenzo Orecchia, Erasmo Tani. Submodular Hypergraph Partitioning: Metric Relaxations and Fast Algorithms via an Improved Cut-Matching Game. 2023.
ArXiv
Konstantinos Ameranis, Antares Chen, Adela Frances DePavia, Lorenzo Orecchia, Erasmo Tani. Hypergraph Diffusions and Resolvents for Norm-Based Hypergraph Laplacians. 2023.
ArXiv
Lorenzo Orecchia, Konstantinos Ameranis, Kunal Talwar, Charalampos Tsourakakis. Practical Almost-Linear-Time Approximation Algorithms for Hybrid and Overlapping Graph Clustering. ICML, 2022.
ICML Slides PMLR
Jelena Diakonikolas, Maryam Fazel, Lorenzo Orecchia. Fair Packing and Covering on a Relative Scale. SIOPT, 2020.
ArXiv SIOPT
Zeyuan Allen-Zhu, Lorenzo Orecchia. Nearly Linear-Time Packing and Covering LP Solvers. Math. Program., 2019.
ACM
Jelena Diakonikolas, Lorenzo Orecchia. The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods. SIOPT, 2019.
ArXiv SIOPT
Jelena Diakonikolas, Lorenzo Orecchia. Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method. ITCS, 2018.
ArXiv ITCS
Michael Cohen, Jelena Diakonikolas, Lorenzo Orecchia. On Acceleration with Noise-Corrupted Gradients. ICML, 2018.
ArXiv PMLR
Jelena Diakonikolas, Lorenzo Orecchia. Alternating Randomized Block Coordinate Descent. ICML, 2018.
ArXiv PMLR
Zeyuan Allen-Zhu, Lorenzo Orecchia. Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent. ITCS, 2017.
ArXiv ITCS
Jelena Diakonikolas, Lorenzo Orecchia. Solving Packing and Covering LPs in $Õ(1ε2)$ Distributed Iterations with a Single Algorithm and Simpler Analysis. ArXiv, 2017.
ArXiv
Cem Aksoylar, Lorenzo Orecchia, Venkatesh Saligrama. Connected Subgraph Detection with Mirror Descent on SDPs. ICML, 2017.
PMLR
Zeyuan Allen-Zhu, Yin Tat Lee, Lorenzo Orecchia. Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver. SODA, 2016.
ArXiv SIAM
Zeyuan Allen-Zhu, Aditya Bhaskara, Silvio Lattanzi, Vahab Mirrokni, Lorenzo Orecchia. Expanders via Local Edge Flips. SODA, 2016.
ArXiv ACM
Zeyuan Allen-Zhu, Lorenzo Orecchia. Using Optimization to Break the Epsilon Barrier: A Faster and Simpler Width-Independent Algorithm for Solving Positive Linear Programs in Parallel. SODA, 2015.
ArXiv ACM
Zeyuan Allen-Zhu, Lorenzo Orecchia. Nearly-Linear Time Packing and Covering LP Solver with Faster Convergence Rate. STOC, 2015.
ACM ArXiv
Jonathan A. Kelner, YinTat Lee, Lorenzo Orecchia, Aaron Sidford. An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations. SODA, 2014.
DOI ArXiv SIAM
Zeyuan Allen-Zhu, Lorenzo Orecchia. Flow-Based Algorithms for Local Graph Clustering. SODA, 2013.
ArXiv SIAM
Jonathan A. Kelner, , Aaron Sidford, Zeyuan Allen-Zhu. A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time. STOC, 2013.
ArXiv ACM
Smith RP*, Riesenfeld SJ*, Holloway AK, Li Q, Murphy KK, Feliciano NM, Oksenberg N, Pollard KS, Ahituv N. A Compact, In Vivo Screen of All 6-mers Reveals Drivers of Tissue-Specific Expression and Guides Synthetic Regulatory Element Design.. Genome Biology, 2013.
BMC
Sushant Sachdeva, Nisheeth K. Vishnoi. Approximating the Exponential, the Lanczos Method and an ilde{O}(m)-Time Spectral Algorithm for Balanced Separator. STOC, 2012.
ArXiv
Michael W. Mahoney, Nisheeth K. Vishnoi, Lorenzo Orecchia. A Local Spectral Method for Graphs: With Applications to Improving Graph Partitions and Exploring Data Graphs Locally. JMLR, 2012.
ArXiv JMLR
Zeyuan Allen-Zhu, Zhenyu Liao, . Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates. STOC, 2011.
ArXiv ACM
. Fast Approximation Algorithms for Graph Partitioning Using Spectral and Semidefinite-Programming Techniques. UC Berkeley Dissertation, 2011.
UCB TR
Lorenzo Orecchia, Nisheeth K. Vishnoi. Towards an SDP-Based Approach to Spectral Methods: A Nearly-Linear Time Algorithm for Graph Partitioning and Decomposition. SODA, 2011.
ACM
Michael W. Mahoney, . Implementing Regularization Implicitly Via Approximate Eigenvector Computation. ICML, 2010.
ArXiv ACM
Kevin J. Lang, Michael W. Mahoney, . Empirical Evaluation of Graph Partitioning Using Spectral Embeddings and Flow. SEA, 2009.
Springer LNTCS
Lorenzo Orecchia, Leonard Schulman, Umesh V. Vazirani, Nisheeth K. Vishnoi. On Partitioning Graphs via Single Commodity Flows. STOC, 2008.
ACM
Devdatt Dubhashi, Olle Häggström, Lorenzo Orecchia, Alessandro Panconesi, Chiara Petrioli, Andrea Vitaletti. Localized Techniques for Broadcasting in Wireless Sensor Networks. Algorithmica, 2007.
Algorithmica
Rohit Khandekar, Subhash A. Khot, Nisheeth K. Vishnoi, Lorenzo Orecchia. On a Cut-Matching Game for the Sparsest Cut Problem. UC Berkeley TR, 2007.
UCB TR