52 citations · 60 across the 7 of their papers we have counts for
9 papers
Expanders via Local Edge Flips
Zeyuan Allen-Zhu, Aditya Bhaskara, Silvio Lattanzi +2
Designing distributed and scalable algorithms to improve network connectivity is a central topic in peer-to-peer networks. In this paper we focus on the following well-known proble…
Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver
Zeyuan Allen-Zhu, Yin Tat Lee, Lorenzo Orecchia
We study the design of polylogarithmic depth algorithms for approximately solving packing and covering semidefinite programs (or positive SDPs for short). This is a natural SDP gen…
Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates
Zeyuan Allen-Zhu, Zhenyu Liao, Lorenzo Orecchia
In this paper, we provide a novel construction of the linear-sized spectral sparsifiers of Batson, Spielman and Srivastava [BSS14]. While previous constructions required r…
Nearly Linear-Time Packing and Covering LP Solvers
Zeyuan Allen-Zhu, Lorenzo Orecchia
Packing and covering linear programs (PC-LPs) form an important class of linear programs (LPs) across computer science, operations research, and optimization. In 1993, Luby and Nis…
Using Optimization to Solve Positive LPs Faster in Parallel
Zeyuan Allen-Zhu, Lorenzo Orecchia
Positive linear programs (LP), also known as packing and covering linear programs, are an important class of problems that bridges computer science, operations research, and optimi…
Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent
Zeyuan Allen-Zhu, Lorenzo Orecchia
First-order methods play a central role in large-scale machine learning. Even though many variations exist, each suited to a particular problem, almost all such methods fundamental…
Flow-Based Algorithms for Local Graph Clustering
Lorenzo Orecchia, Zeyuan Allen Zhu
Given a subset S of vertices of an undirected graph G, the cut-improvement problem asks us to find a subset S that is similar to A but has smaller conductance. A very elegant algor…
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia +1
In this paper, we introduce a new framework for approximately solving flow problems in capacitated, undirected graphs and apply it to provide asymptotically faster algorithms for t…
A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time
Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford +1
In this paper, we present a simple combinatorial algorithm that solves symmetric diagonally dominant (SDD) linear systems in nearly-linear time. It uses very little of the machiner…