Matthew Ding

Matthew Ding

he/him

Undergraduate CS Researcher at UC Berkeley

Publications

You can also find my articles on my Google Scholar profile.

Optimizing Sparse SYK

Published in (In submission), 2025

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

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/ε⁴)} maximum flow calls and additional O(m^{1+ε}) time, for ε > 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 (In submission), 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). Conditional Acceptance.
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 BeeGees1, 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