52 citations · 60 across the 7 of their papers we have counts for
8 papers · 1 filter
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…
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…