2.5k citations · 4.7k across the 60 of their papers we have counts for
3 papers · 1 filter
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…