Richard Peng

Santosh S. Vempala

Commun. ACM, July, 2024

Entrywise Approximate Laplacian Solving.

[BibT_eX]

[DOI]

CoRR, 2024

Efficient Historical Butterfly Counting in Large Temporal Bipartite Networks via Graph Structure-aware Index.

[BibT_eX]

[DOI]

CoRR, 2024

Distance queries over dynamic interval graphs.

[BibT_eX]

[DOI]

Comput. Geom., 2024

Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time.

[BibT_eX]

[DOI]

Aaron Sidford

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Scalable Algorithm for Finding Balanced Subgraphs with Tolerance in Signed Networks.

[BibT_eX]

[DOI]

Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2024

2023

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

[BibT_eX]

[DOI]

SIAM J. Comput., December, 2023

Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow.

[BibT_eX]

[DOI]

Commun. ACM, December, 2023

A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems.

[BibT_eX]

[DOI]

Algorithmica, December, 2023

Towards Lightweight and Automated Representation Learning System for Networks.

[BibT_eX]

[DOI]

IEEE Trans. Knowl. Data Eng., September, 2023

Simpler Analyses of Union-Find.

[BibT_eX]

[DOI]

CoRR, 2023

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

[BibT_eX]

[DOI]

CoRR, 2023

Hardness of Graph-Structured Algebraic and Symbolic Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 18th International Symposium, 2023

The Bit Complexity of Efficient Continuous Optimization.

[BibT_eX]

[DOI]

Mehrdad Ghadiri

Santosh S. Vempala

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow.

[BibT_eX]

[DOI]

Aaron Sidford

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Exponential Convergence of Sinkhorn Under Regularization Scheduling.

[BibT_eX]

[DOI]

Proceedings of the SIAM Conference on Applied and Computational Discrete Algorithms, 2023

2022

Fast Algorithms for 𝓁p-Regression.

[BibT_eX]

[DOI]

CoRR, 2022

Exponential Convergence of Sinkhorn Under Regularization Scheduling.

[BibT_eX]

[DOI]

CoRR, 2022

Sparsified block elimination for directed laplacians.

[BibT_eX]

[DOI]

Zhuoqing Song

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Faster maxflow via improved dynamic spectral vertex sparsifiers.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

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

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

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

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Unit-Weight Laplacians are Complete for Linear Systems Modulo $p$.

[BibT_eX]

[DOI]

CoRR, 2021

Sparse Regression Faster than dω.

[BibT_eX]

[DOI]

Mehrdad Ghadiri

Santosh S. Vempala

CoRR, 2021

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

[BibT_eX]

[DOI]

CoRR, 2021

𝓁2-norm Flow Diffusion in Near-Linear Time.

[BibT_eX]

[DOI]

Li Chen

CoRR, 2021

Vertex Sparsification for Edge Connectivity.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

LightNE: A Lightweight Graph Processing System for Network Embedding.

[BibT_eX]

[DOI]

Proceedings of the SIGMOD '21: International Conference on Management of Data, 2021

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

[BibT_eX]

[DOI]

Yu Gao

Yang P. Liu

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Minor Sparsifiers and the Distributed Laplacian Paradigm.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2-norm Flow Diffusion in Near-Linear Time.

[BibT_eX]

[DOI]

Li Chen

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Determinant-Preserving Sparsification of SDDM Matrices.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

Concentration Bounds for Co-occurrence Matrices of Markov Chains.

[BibT_eX]

[DOI]

CoRR, 2020

A Study of Performance of Optimal Transport.

[BibT_eX]

[DOI]

CoRR, 2020

Flowless: Extracting Densest Subgraphs Without Flow Computations.

[BibT_eX]

[DOI]

Junxing Wang

Proceedings of the WWW '20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, 2020

Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

A Matrix Chernoff Bound for Markov Chains and Its Application to Co-occurrence Matrices.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Faster Graph Embeddings via Coarsening.

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

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

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs.

[BibT_eX]

[DOI]

Aaron Sidford

Zhao Song

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Vertex Sparsifiers for c-Edge Connectivity.

[BibT_eX]

[DOI]

Yang P. Liu

Mark Sellke

CoRR, 2019

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

[BibT_eX]

[DOI]

Sorrachai Yingchareonthawornchai

CoRR, 2019

Dynamic Optimality Refuted - For Tournament Heaps.

[BibT_eX]

[DOI]

CoRR, 2019

Higher-Order Accelerated Methods for Faster Non-Smooth Optimization.

[BibT_eX]

[DOI]

Brian Bullins

CoRR, 2019

Iterative Refinement for 𝓁p-norm Regression.

[BibT_eX]

[DOI]

CoRR, 2019

Current Flow Group Closeness Centrality for Complex Networks?

[BibT_eX]

[DOI]

Proceedings of the World Wide Web Conference, 2019

Optimal Offline Dynamic 2, 3-Edge/Vertex Connectivity.

[BibT_eX]

[DOI]

Bryce Sandlund

Daniel Dominic Sleator

Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

Flows in almost linear time via adaptive preconditioning.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Fully dynamic spectral vertex sparsifiers and applications.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Iterative Refinement for ℓp-norm Regression.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

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

[BibT_eX]

[DOI]

Deeksha Adil

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

2018

High-Performance Graph Algorithms (Dagstuhl Seminar 18241).

[BibT_eX]

[DOI]

Henning Meyerhenke

Ilya Safro

Dagstuhl Reports, 2018

Constant Arboricity Spectral Sparsifiers.

[BibT_eX]

[DOI]

CoRR, 2018

Fully Dynamic Effective Resistances.

[BibT_eX]

[DOI]

CoRR, 2018

Incomplete nested dissection.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Graph Sketching against Adaptive Adversaries Applied to the Minimum Degree Algorithm.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

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

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Parameterizing the Hardness of Binary Search Tree Access Sequences by Inversion Counts.

[BibT_eX]

[DOI]

Meng He

Yinzhan Xu

Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics, 2018

2017

Partitioning Well-Clustered Graphs: Spectral Clustering Works!

[BibT_eX]

[DOI]

He Sun

Luca Zanetti

SIAM J. Comput., 2017

On Computing Min-Degree Elimination Orderings.

[BibT_eX]

[DOI]

CoRR, 2017

Offline Dynamic Higher Connectivity.

[BibT_eX]

[DOI]

Bryce Sandlund

Daniel Dominic Sleator

CoRR, 2017

Concave Flow on Small Depth Directed Networks.

[BibT_eX]

[DOI]

CoRR, 2017

Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

A Framework for Analyzing Resparsification Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Density Independent Algorithms for Sparsifying k-Step Random Walks.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2017

2016

Faster Spectral Sparsification and Numerical Algorithms for SDD Matrices.

[BibT_eX]

[DOI]

Alex Levin

ACM Trans. Algorithms, 2016

Scalable Constrained Clustering: A Generalized Spectral Method.

[BibT_eX]

[DOI]

CoRR, 2016

Sparsified Cholesky and multigrid solvers for connection laplacians.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Approximate Undirected Maximum Flows in O(mpolylog(n)) Time.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

An Empirical Study of Cycle Toggling Based Laplacian Solvers.

[BibT_eX]

[DOI]

Proceedings of the 2016 Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing, 2016

SPALS: Fast Alternating Least Squares via Implicit Leverage Scores Sampling.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

On Fully Dynamic Graph Sparsifiers.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Simple and Scalable Constrained Clustering: a Generalized Spectral Method.

[BibT_eX]

[DOI]

Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, 2016

2015

Sparsified Cholesky Solvers for SDD linear systems.

[BibT_eX]

[DOI]

Yin Tat Lee

Daniel A. Spielman

CoRR, 2015

Spectral Sparsification of Random-Walk Matrix Polynomials.

[BibT_eX]

[DOI]

CoRR, 2015

Lp Row Sampling by Lewis Weights.

[BibT_eX]

[DOI]

Michael B. Cohen

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Improved Parallel Algorithms for Spanners and Hopsets.

[BibT_eX]

[DOI]

Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, 2015

Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling.

[BibT_eX]

[DOI]

Michael Mitzenmacher

Jakub Pachocki

Shen Chen Xu

Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015

Uniform Sampling for Matrix Approximation.

[BibT_eX]

[DOI]

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification.

[BibT_eX]

[DOI]

Proceedings of The 28th Conference on Learning Theory, 2015

2014

Approaching Optimality for Solving SDD Linear Systems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

Nearly-Linear Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2014

Partitioning Well-Clustered Graphs with k-Means and Heat Kernel.

[BibT_eX]

[DOI]

He Sun

Luca Zanetti

CoRR, 2014

A Note on Cut-Approximators and Approximating Undirected Max Flows.

[BibT_eX]

[DOI]

CoRR, 2014

A Generalized Cheeger Inequality.

[BibT_eX]

[DOI]

CoRR, 2014

Stretching Stretch.

[BibT_eX]

[DOI]

CoRR, 2014

Preconditioning in Expectation.

[BibT_eX]

[DOI]

CoRR, 2014

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

[BibT_eX]

[DOI]

CoRR, 2014

An efficient parallel solver for SDD linear systems.

[BibT_eX]

[DOI]

Daniel A. Spielman

Proceedings of the Symposium on Theory of Computing, 2014

Solving SDD linear systems in nearly mlog1/2n time.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

Solving 1-Laplacians in Nearly Linear Time: Collapsing and Expanding a Topological Ball.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013

Algorithm Design Using Spectral Graph Theory.

[BibT_eX]

[DOI]

PhD thesis, 2013

Fully Dynamic $(1+ε)$-Approximate Matchings

[BibT_eX]

[DOI]

Manoj Gupta

CoRR, 2013

Parallel Algorithms for Approximate Undirected Shortest Paths in $m\log^{3+α}n$ Work.

[BibT_eX]

[DOI]

Shen Chen Xu

CoRR, 2013

Parallel graph decompositions using random shifts.

[BibT_eX]

[DOI]

Shen Chen Xu

Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, 2013

Approximate Maximum Flow on Separable Undirected Graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Runtime guarantees for regression problems.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2013

Iterative Row Sampling.

[BibT_eX]

[DOI]

Mu Li

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Fully Dynamic (1+ e)-Approximate Matchings.

[BibT_eX]

[DOI]

Manoj Gupta

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning.

[BibT_eX]

[DOI]

Mihail N. Kolountzakis

Internet Math., 2012

Iterative Approaches to Row Sampling

[BibT_eX]

[DOI]

CoRR, 2012

A fast solver for a class of linear systems.

[BibT_eX]

[DOI]

Commun. ACM, 2012

Faster approximate multicommodity flow using quadratically coupled flows.

[BibT_eX]

[DOI]

Jonathan A. Kelner

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices.

[BibT_eX]

[DOI]

Alex Levin

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Faster and simpler width-independent parallel algorithms for positive semidefinite programming.

[BibT_eX]

[DOI]

Kanat Tangwongsan

Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures, 2012

2011

Approximation algorithms for speeding up dynamic programming and denoising aCGH data.

[BibT_eX]

[DOI]

ACM J. Exp. Algorithmics, 2011

Electrical Flow Algorithms for Total Variation Minimization

[BibT_eX]

[DOI]

Aleksander Madry

CoRR, 2011

Solving SDD linear systems in time Õ(mlog nlog(1/ε))

[BibT_eX]

[DOI]

CoRR, 2011

Linear-work greedy parallel approximate set cover and variants.

[BibT_eX]

[DOI]

Guy E. Blelloch

Kanat Tangwongsan

Proceedings of the SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2011

Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs.

[BibT_eX]

[DOI]

Proceedings of the SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2011

Approximate Dynamic Programming using Halfspace Queries and Multiscale Monge Decomposition.

[BibT_eX]

[DOI]

Russell Schwartz

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

A Nearly-m log n Time Solver for SDD Linear Systems.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Approximate Dynamic Programming for Fast Denoising of aCGH Data

[BibT_eX]

[DOI]

Russell Schwartz

CoRR, 2010

Approaching optimality for solving SDD systems

[BibT_eX]

[DOI]