Publications

Optimizing Sparse SYK

Published in (In submission), 2025

Matthew Ding, Robbie King, Bobak T. Kiani, and Eric R. Anschuetz. In submission, poster at Quantum Information Processing (QIP 2025).

Space Complexity of Minimum Cut Problems in Single-Pass Streams

Published in Innovations in Theoretical Computer Science (ITCS), 2025

We consider the problem of finding a minimum cut of a weighted graph presented as a single-pass stream. While graph sparsification in streams has been intensively studied, the specific application of finding minimum cuts in streams is less well-studied. To this end, we show upper and lower bounds on minimum cut problems in insertion-only streams for a variety of settings, including for both randomized and deterministic algorithms, for both arbitrary and random order streams, and for both approximate and exact algorithms. One of our main results is an \(\widetilde{O}(n/\epsilon)\) space algorithm with fast update time for approximating a spectral cut query with high probability on a stream given in an arbitrary order. Our result breaks the \(\Omega(n/\epsilon^2)\) space lower bound required of a sparsifier that approximates all cuts simultaneously. Using this result, we provide streaming algorithms with near optimal space of \(\widetilde{O}(n/\epsilon)\) for minimum cut and approximate all-pairs effective resistances, with matching space lower-bounds. The amortized update time of our algorithms is \(\widetilde{O}(1)\), provided that the number of edges in the input graph is at least \((n/\epsilon^2)^{1+o(1)}\). We also give a generic way of incorporating sketching into a recursive contraction algorithm to improve the post-processing time of our algorithms. In addition to these results, we give a random-order streaming algorithm that computes the {\it exact} minimum cut on a simple, unweighted graph using \(\widetilde{O}(n)\) space. Finally, we give an \(\Omega(n/\epsilon^2)\) space lower bound for deterministic minimum cut algorithms which matches the best-known upper bound up to polylogarithmic factors.

Matthew Ding, Alexandro Garces, Jason Li, Honghao Lin, Jelani Nelson, Vihan Shah, and David P. Woodruff. Innovations in Theoretical Computer Science (ITCS 2025).
Paper Link | Download Slides

Deterministic Minimum Steiner Cut in Maximum Flow Time

Published in European Symposium on Algorithms (ESA), 2024

We devise a deterministic algorithm for minimum Steiner cut, which uses \((\log n)^{O(1)}\) maximum flow calls and additional near-linear time. This algorithm improves on Li and Panigrahi’s (FOCS 2020) algorithm, which uses \((\log n)^{O(1/\epsilon^4)}\) maximum flow calls and additional \(O(m^{1+\epsilon})\) time, for \(\epsilon > 0\). Our algorithm thus shows that deterministic minimum Steiner cut can be solved in maximum flow time up to polylogarithmic factors, given any black-box deterministic maximum flow algorithm. Our main technical contribution is a novel deterministic graph decomposition method for terminal vertices that generalizes all existing s-strong partitioning methods, which we believe may have future applications.

Matthew Ding and Jason Li. European Symposium on Algorithms (ESA 2024).
Paper Link | Download Slides

Fast and Robust State Estimation and Tracking via Hierarchical Learning

Published in IEEE Transactions on Automatic Control (TAC), 2024

Fully distributed estimation and tracking solutions to large-scale multi-agent networks suffer slow convergence and are vulnerable to network failures. In this paper, we aim to speed up the convergence and enhance the resilience of state estimation and tracking using a simple hierarchical system architecture wherein agents are clusters into smaller networks, and a parameter server exists to aid the information exchanges among networks. The information exchange among networks is expensive and occurs only once in a while. We propose two consensus + innovation algorithms for the state estimation and tracking problems, respectively. In both algorithms, we use a novel hierarchical push-sum consensus component. For the state estimation, we use dual averaging as the local innovation component. State tracking is much harder to tackle in the presence of dropping-link failures and the standard integration of the consensus and innovation approaches are no longer applicable. Moreover, dual averaging is no longer feasible. Our algorithm introduces a pair of additional variables per link and ensure the relevant local variables evolve according to the state dynamics, and use projected local gradient descent as the local innovation component. We also characterize the convergence rates of both of the algorithms under linear local observation model and minimal technical assumptions. We numerically validate our algorithm through simulation of both state estimation and tracking problems.

Connor Mclaughlin, Matthew Ding, Denis Erdogmus, and Lili Su. IEEE Transactions on Automatic Control (TAC), accepted with minor revision.
Paper Link

BeeGees: Stayin’ Alive in Chained BFT

Published in ACM Symposium on Principles of Distributed Computing (PODC), 2023

Modern chained Byzantine Fault Tolerant (BFT) systems leverage a combination of pipelining and leader rotation to obtain both efficiency and fairness. These protocols, however, require a sequence of three or four consecutive honest leaders to commit operations. Therefore, even simple leader failures such as crashes can weaken liveness, resulting in high commit latency or lack of commit all together. We show that, unfortunately, this vulnerability is inherent to all existing BFT protocols that rotate leaders with pipelined agreement. To resolve this liveness shortcoming we present BeeGees, a novel chained BFT protocol that successfully commits blocks even with non-consecutive honest leaders. It does this while also maintaining quadratic word complexity with threshold signatures, linear word complexity with SNARKs, and responsiveness between consecutive honest leaders. BeeGees reduces the expected commit latency of HotStuff by a factor of three under failures, and the worst-case latency by a factor of seven.

Neil Giridharan, Florian Suri-Payer, Matthew Ding, Heidi Howard, Ittai Abraham, and Natacha Crooks. ACM Symposium on Principles of Distributed Computing (PODC 2023).
Paper Link