research
∙
08/17/2023
Simpler Analyses of Union-Find
We analyze union-find using potential functions motivated by continuous ...
share
research
∙
06/02/2023
An Empirical Study on Challenging Math Problem Solving with GPT-4
Employing Large Language Models (LLMs) to address mathematical problems ...
research
∙
04/04/2023
The Bit Complexity of Efficient Continuous Optimization
We analyze the bit complexity of efficient algorithms for fundamental op...
research
∙
11/08/2022
Fast Algorithms for ℓ_p-Regression
The ℓ_p-norm regression problem is a classic problem in optimization wit...
research
∙
07/02/2022
Exponential Convergence of Sinkhorn Under Regularization Scheduling
The optimal transport (OT) problem or earth mover's distance has wide ap...
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...
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 ...
research
∙
12/01/2021
Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers
We make several advances broadly related to the maintenance of electrica...
research
∙
11/19/2021
Sparsified Block Elimination for Directed Laplacians
We show that the sparsified block elimination algorithm for solving undi...
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...
research
∙
09/23/2021
Sparse Regression Faster than d^ω
The current complexity of regression is nearly linear in the complexity ...
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...
research
∙
05/30/2021
ℓ_2-norm Flow Diffusion in Near-Linear Time
Diffusion is a fundamental graph procedure and has been a basic building...
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 ...
research
∙
12/31/2020
Minor Sparsifiers and the Distributed Laplacian Paradigm
We study distributed algorithms built around edge contraction based vert...
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...
research
∙
08/06/2020
Concentration Bounds for Co-occurrence Matrices of Markov Chains
Co-occurrence statistics for sequential data are common and important da...
research
∙
07/20/2020
Solving Sparse Linear Systems Faster than Matrix Multiplication
Can linear systems be solved faster than matrix multiplication? While th...
research
∙
07/15/2020
Vertex Sparsification for Edge Connectivity
Graph compression or sparsification is a basic information-theoretic and...
research
∙
07/06/2020
Faster Graph Embeddings via Coarsening
Graph embeddings are a ubiquitous tool for machine learning tasks, such ...
research
∙
05/05/2020
Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers
We present a general framework of designing efficient dynamic approximat...
research
∙
05/03/2020
A Study of Performance of Optimal Transport
We investigate the problem of efficiently computing optimal transport (O...
research
∙
10/23/2019
Vertex Sparsifiers for c-Edge Connectivity
We show the existence of O(f(c)k) sized vertex sparsifiers that preserve...
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,...
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...
research
∙
10/15/2019
Flowless: Extracting Densest Subgraphs Without Flow Computations
We propose a simple and computationally efficient method for dense subgr...
research
∙
08/06/2019
Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds
In this paper we study the problem of dynamically maintaining graph prop...
research
∙
08/01/2019
Dynamic Optimality Refuted -- For Tournament Heaps
We prove a separation between offline and online algorithms for finger-b...
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...
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...
research
∙
06/24/2019
Fully Dynamic Spectral Vertex Sparsifiers and Applications
We study dynamic algorithms for maintaining spectral vertex sparsifiers ...
research
∙
06/04/2019
Higher-Order Accelerated Methods for Faster Non-Smooth Optimization
We provide improved convergence rates for various non-smooth optimizatio...
research
∙
01/21/2019
Iterative Refinement for ℓ_p-norm Regression
We give improved algorithms for the ℓ_p-regression problem, _xx_p such t...
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...
research
∙
08/16/2018
Constant Arboricity Spectral Sparsifiers
We show that every graph is spectrally similar to the union of a constan...
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 ...
research
∙
05/23/2018
Incomplete Nested Dissection
We present an asymptotically faster algorithm for solving linear systems...
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 ...
research
∙
04/11/2018
Fully Dynamic Effective Resistances
In this paper we consider the fully-dynamic All-Pairs Effective Resistan...
research
∙
02/07/2018
Current Flow Group Closeness Centrality for Complex Networks
Current flow closeness centrality (CFCC) has a better discriminating abi...
research
∙
11/22/2017
On Computing Min-Degree Elimination Orderings
We study faster algorithms for producing the minimum degree ordering use...
research
∙
02/12/2015
Spectral Sparsification of Random-Walk Matrix Polynomials
We consider a fundamental algorithmic question in spectral graph theory:...
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...
research
∙
10/06/2011