Richard Peng

Richard Peng

Auto-generated profile, based on publicly available information

Richard Peng

Computer Science, Carnegie Mellon University

Research Focus & Metrics

Academic Career Length

5Years (2022-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
14 May 2025 in Journal of the ACM
Verified
Journal Article
Open access
LCLi Chen
Li Chen
RKRasmus Kyng
Rasmus Kyng
YLYang Liu
Yang Liu
RPRichard Peng
Richard Peng
MGMaximilian Probst Gutenberg
Maximilian Probst Gutenberg
SSSushant Sachdeva
Sushant Sachdeva
We present an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities in \(m^{1+o(1)}\) time. Our algorithm builds the flow through a sequence of \(m^{1+o(1)}\) approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized \(m^{o(1)}\) time using a new dynamic graph data structure. Our framework extends to algorithms running in \(m^{1+o(1)}\) time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives almost-linear time algorithms for several problems including entropy-regularized optimal transport, matrix scaling, p -norm flows, and p -norm isotonic regression on arbitrary directed acyclic graphs.

1 August 2023 in Algorithmica
Verified
Journal Article
Closed access
PDF file
MHMonika Henzinger
Monika Henzinger
BJBilly Jin
Billy Jin
RPRichard Peng
Richard Peng
DWDavid P. Williamson
David P. Williamson

24 August 2024
Verified
Conference Paper
Open access
JCJingbang Chen
Jingbang Chen
QMQiuyang Mang
Qiuyang Mang
HZHangrui Zhou
Hangrui Zhou
RPRichard Peng
Richard Peng
YGYu Gao
Yu Gao
Chenhao MaChenhao Ma
Chenhao Ma
Signed networks, characterized by edges labeled as either positive or negative, offer nuanced insights into interaction dynamics beyond the capabilities of unsigned graphs. Central to this is the task of identifying the maximum balanced subgraph, crucial for applications like polarized community detection in social networks and portfolio analysis in finance. Traditional models, however, are limited by an assumption of perfect partitioning, which fails to mirror the complexities of real-world data. Addressing this gap, we introduce an innovative generalized balanced subgraph model that incorporates tolerance for imbalance. Our proposed region-based heuristic algorithm, tailored for this NP -hard problem, strikes a balance between low time complexity and high-quality outcomes. Comparative experiments validate its superior performance against leading solutions, delivering enhanced effectiveness (notably larger subgraph sizes) and efficiency (achieving up to 100× speedup) in both traditional and generalized contexts.

22 April 2022 in arXiv
Verified
Preprint
Open access
PDF file
LCLi Chen
Li Chen
RKRasmus Kyng
Rasmus Kyng
YLYang P. Liu
Yang P. Liu
RPRichard Peng
Richard Peng
MGMaximilian Probst Gutenberg
Maximilian Probst Gutenberg
SSSushant Sachdeva
Sushant Sachdeva
We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with $m$ edges and polynomially bounded integral demands, costs, and capacities in $m^{1+o(1)}$ time. Our algorithm builds the flow through a sequence of $m^{1+o(1)}$ approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized $m^{o(1)}$ time using a new dynamic graph data structure. Our framework extends to algorithms running in $m^{1+o(1)}$ time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives almost-linear time algorithms for several problems including entropy-regularized optimal transport, matrix scaling, $p$-norm flows, and $p$-norm isotonic regression on arbitrary directed acyclic graphs.

5 October 2024 in Journal of the ACM
Verified
Journal Article
Open access
DADeeksha Adil
Deeksha Adil
RKRasmus Kyng
Rasmus Kyng
RPRichard Peng
Richard Peng
SSSushant Sachdeva
Sushant Sachdeva
The \(\ell _p\) -norm regression problem is a classic problem in optimization with wide ranging applications in machine learning and theoretical computer science. The goal is to compute \(\boldsymbol {\mathit {x}}^{\star } =\arg \min _{\boldsymbol {\mathit {A}}\boldsymbol {\mathit {x}}=\boldsymbol {\mathit {b}}}\Vert \boldsymbol {\mathit {x}}\Vert _p^p\) , where \(\boldsymbol {\mathit {x}}^{\star }\in \mathbb {R}^n,\boldsymbol {\mathit {A}}\in \mathbb {R}^{d\times n},\boldsymbol {\mathit {b}}\in \mathbb {R}^d\) and \(d\le n\) . Efficient high-accuracy algorithms for the problem have been challenging both in theory and practice and the state-of-the-art algorithms require \(poly(p)\cdot n^{\frac{1}{2}-\frac{1}{p}}\) linear system solves for \(p\ge 2\) . In this article, we provide new algorithms for \(\ell _p\) -regression (and a more general formulation of the problem) that obtain a high-accuracy solution in \(O(p n^{ {(p-2)}{(3p-2)}})\) linear system solves. We further propose a new inverse maintenance procedure that speeds-up our algorithm to \(\widetilde{O}(n^{\omega })\) total runtime, where \(O(n^{\omega })\) denotes the running time for multiplying \(n \times n\) matrices. Additionally, we give the first Iteratively Reweighted Least Squares (IRLS) algorithm that is guaranteed to converge to an optimum in a few iterations. Our IRLS algorithm has shown exceptional practical performance, beating the currently available implementations in MATLAB/CVX by 10–50×.

26 July 2025 in Journal of the ACM
Verified
Journal Article
Open access
SDSally Dong
Sally Dong
YGYu Gao
Yu Gao
GGGramoz Goranci
Gramoz Goranci
YLYin Tat Lee
Yin Tat Lee
SSSushant Sachdeva
Sushant Sachdeva
GYGuanghao Ye
Guanghao Ye
We present a nearly-linear time algorithm for finding a minimum-cost flow in planar graphs with polynomially-bounded integer costs and capacities. The previous fastest algorithm for this problem is based on interior point methods (IPMs) and works for general sparse graphs in O ( n 1.5 ⋅ poly (log n )) time [Daitch-Spielman, STOC’08]. Intuitively, Ω ( n 1.5 ) is a natural runtime barrier for IPM-based methods, since they require \(\sqrt {n}\) iterations, each routing a possibly-dense electrical flow. To break this barrier, we develop a new implicit representation for flows based on generalized nested dissection [Lipton-Rose-Tarjan, SINUM’79] and approximate Schur complements [Kyng-Sachdeva, FOCS’16]. This implicit representation permits us to design a data structure to route an electrical flow with sparse demands in roughly \(\sqrt {n}\) update time, resulting in a total runtime of O ( n ⋅ poly (log n )). Our results immediately extend to all families of separable graphs.