b'Richard Peng'

research

∙ 08/17/2023

Simpler Analyses of Union-Find

We analyze union-find using potential functions motivated by continuous ...

0 Zhiyi Huang, et al. ∙

research

∙ 06/02/2023

An Empirical Study on Challenging Math Problem Solving with GPT-4

Employing Large Language Models (LLMs) to address mathematical problems ...

0 Yiran Wu, et al. ∙

research

∙ 04/04/2023

The Bit Complexity of Efficient Continuous Optimization

We analyze the bit complexity of efficient algorithms for fundamental op...

0 Mehrdad Ghadiri, et al. ∙

research

∙ 11/08/2022

Fast Algorithms for ℓ_p-Regression

The ℓ_p-norm regression problem is a classic problem in optimization wit...

0 Deeksha Adil, et al. ∙

research

∙ 07/02/2022

Exponential Convergence of Sinkhorn Under Regularization Scheduling

The optimal transport (OT) problem or earth mover's distance has wide ap...

0 Jingbang Chen, et al. ∙

research

∙ 05/03/2022

Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time

We present a nearly-linear time algorithm for finding a minimum-cost flo...

0 Sally Dong, et al. ∙

research

∙ 03/01/2022

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

We give an algorithm that computes exact maximum flows and minimum-cost ...

0 Li Chen, et al. ∙

research

∙ 12/01/2021

Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers

We make several advances broadly related to the maintenance of electrica...

0 Jan van den Brand, et al. ∙

research

∙ 11/19/2021

Sparsified Block Elimination for Directed Laplacians

We show that the sparsified block elimination algorithm for solving undi...

0 Richard Peng, et al. ∙

research

∙ 09/27/2021

Unit-Weight Laplacians are Complete for Linear Systems Modulo p

In this paper, we prove that over finite fields modulo primes, solving g...

0 Yufan Huang, et al. ∙

research

∙ 09/23/2021

Sparse Regression Faster than d^ω

The current complexity of regression is nearly linear in the complexity ...

0 Mehrdad Ghadiri, et al. ∙

research

∙ 09/02/2021

Cut-Toggling and Cycle-Toggling for Electrical Flow and Other p-Norm Flows

We study the problem of finding flows in undirected graphs so as to mini...

0 Monika Henzinger, et al. ∙

research

∙ 05/30/2021

ℓ_2-norm Flow Diffusion in Near-Linear Time

Diffusion is a fundamental graph procedure and has been a basic building...

0 Li Chen, et al. ∙

research

∙ 01/18/2021

Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao

We give an algorithm for computing exact maximum flows on graphs with m ...

0 Yu Gao, et al. ∙

research

∙ 12/31/2020

Minor Sparsifiers and the Distributed Laplacian Paradigm

We study distributed algorithms built around edge contraction based vert...

0 Sebastian Forster, et al. ∙

research

∙ 09/03/2020

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs

We present an Õ(m+n^1.5)-time randomized algorithm for maximum cardinali...

0 Jan van den Brand, et al. ∙

research

∙ 08/06/2020

Concentration Bounds for Co-occurrence Matrices of Markov Chains

Co-occurrence statistics for sequential data are common and important da...

0 Jiezhong Qiu, et al. ∙

research

∙ 07/20/2020

Solving Sparse Linear Systems Faster than Matrix Multiplication

Can linear systems be solved faster than matrix multiplication? While th...

0 Richard Peng, et al. ∙

research

∙ 07/15/2020

Vertex Sparsification for Edge Connectivity

Graph compression or sparsification is a basic information-theoretic and...

0 Parinya Chalermsook, et al. ∙

research

∙ 07/06/2020

Faster Graph Embeddings via Coarsening

Graph embeddings are a ubiquitous tool for machine learning tasks, such ...

2 Matthew Fahrbach, et al. ∙

research

∙ 05/05/2020

Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers

We present a general framework of designing efficient dynamic approximat...

0 Li Chen, et al. ∙

research

∙ 05/03/2020

A Study of Performance of Optimal Transport

We investigate the problem of efficiently computing optimal transport (O...

0 Yihe Dong, et al. ∙

research

∙ 10/23/2019

Vertex Sparsifiers for c-Edge Connectivity

We show the existence of O(f(c)k) sized vertex sparsifiers that preserve...

0 Yang P. Liu, et al. ∙

research

∙ 10/17/2019

A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond

We consider the classical Minimum Balanced Cut problem: given a graph G,...

0 Julia Chuzhoy, et al. ∙

research

∙ 10/17/2019

Deterministic Graph Cuts in Subquadratic Time: Sparse, Balanced, and k-Vertex

We study deterministic algorithms for computing graph cuts, with focus o...

0 Yu Gao, et al. ∙

research

∙ 10/15/2019

Flowless: Extracting Densest Subgraphs Without Flow Computations

We propose a simple and computationally efficient method for dense subgr...

0 Digvijay Boob, et al. ∙

research

∙ 08/06/2019

Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds

In this paper we study the problem of dynamically maintaining graph prop...

0 David Durfee, et al. ∙

research

∙ 08/01/2019

Dynamic Optimality Refuted -- For Tournament Heaps

We prove a separation between offline and online algorithms for finger-b...

0 J. Ian Munro, et al. ∙

research

∙ 07/16/2019

Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression

Linear regression in ℓ_p-norm is a canonical optimization problem that a...

0 Deeksha Adil, et al. ∙

research

∙ 06/25/2019

Flows in Almost Linear Time via Adaptive Preconditioning

We present algorithms for solving a large class of flow and regression p...

0 Rasmus Kyng, et al. ∙

research

∙ 06/24/2019

Fully Dynamic Spectral Vertex Sparsifiers and Applications

We study dynamic algorithms for maintaining spectral vertex sparsifiers ...

0 David Durfee, et al. ∙

research

∙ 06/04/2019

Higher-Order Accelerated Methods for Faster Non-Smooth Optimization

We provide improved convergence rates for various non-smooth optimizatio...

0 Brian Bullins, et al. ∙

research

∙ 01/21/2019

Iterative Refinement for ℓ_p-norm Regression

We give improved algorithms for the ℓ_p-regression problem, _xx_p such t...

0 Deeksha Adil, et al. ∙

research

∙ 11/26/2018

Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations

We show how to solve directed Laplacian systems in nearly-linear time. G...

0 Michael B. Cohen, et al. ∙

research

∙ 08/16/2018

Constant Arboricity Spectral Sparsifiers

We show that every graph is spectrally similar to the union of a constan...

0 Timothy Chu, et al. ∙

research

∙ 05/30/2018

Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions

We develop a framework for graph sparsification and sketching, based on ...

0 Timothy Chu, et al. ∙

research

∙ 05/23/2018

Incomplete Nested Dissection

We present an asymptotically faster algorithm for solving linear systems...

0 Rasmus Kyng, et al. ∙

research

∙ 04/11/2018

Graph Sketching Against Adaptive Adversaries Applied to the Minimum Degree Algorithm

Motivated by the study of matrix elimination orderings in combinatorial ...

0 Matthew Fahrbach, et al. ∙

research

∙ 04/11/2018

Fully Dynamic Effective Resistances

In this paper we consider the fully-dynamic All-Pairs Effective Resistan...

0 David Durfee, et al. ∙

research

∙ 02/07/2018

Current Flow Group Closeness Centrality for Complex Networks

Current flow closeness centrality (CFCC) has a better discriminating abi...

0 Huan Li, et al. ∙

research

∙ 11/22/2017

On Computing Min-Degree Elimination Orderings

We study faster algorithms for producing the minimum degree ordering use...

0 Matthew Fahrbach, et al. ∙

research

∙ 02/12/2015

Spectral Sparsification of Random-Walk Matrix Polynomials

We consider a fundamental algorithmic question in spectral graph theory:...

0 Dehua Cheng, et al. ∙

research

∙ 10/20/2014

Scalable Parallel Factorizations of SDD Matrices and Efficient Sampling for Gaussian Graphical Models

Motivated by a sampling problem basic to computational statistical infer...

0 Dehua Cheng, et al. ∙

research

∙ 10/06/2011

Runtime Guarantees for Regression Problems

We study theoretical runtime guarantees for a class of optimization prob...

0 Hui Han Chin, et al. ∙

Richard Peng

Featured Co-authors