2.5k citations · 4.7k across the 60 of their papers we have counts for
10 papers · 1 filter
Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li +2
We propose a new second-order method for geodesically convex optimization on the natural hyperbolic metric over positive definite matrices. We apply it to solve the operator scalin…
Much Faster Algorithms for Matrix Scaling
Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira +1
We develop several efficient algorithms for the classical \emph{Matrix Scaling} problem, which is used in many diverse areas, from preconditioning linear systems to approximation o…
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…
Restricted Isometry Property for General p-Norms
Zeyuan Allen-Zhu, Rati Gelashvili, Ilya Razenshteyn
The Restricted Isometry Property (RIP) is a fundamental property of a matrix which enables sparse recovery. Informally, an matrix satisfies RIP of order for the $\…
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…
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…
Local Graph Clustering Beyond Cheeger's Inequality
Zeyuan Allen Zhu, Silvio Lattanzi, Vahab Mirrokni
Motivated by applications of large-scale graph clustering, we study random-walk-based LOCAL algorithms whose running times depend only on the size of the output cluster, rather tha…
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…