Theory of Computing Report

The Department of Computing Science at the University of Alberta invites applications for one tenure-track Assistant Professor position, starting as early as July 1st, 2025 in either the area of Theoretical Computing Science (e.g., Data Structures & Algorithm; Streaming, Sketching, and Big Data Algorithms; Computational Complexity; Discrete Optimization; etc.) or Computer Systems.

Website: https://apps.ualberta.ca/careers/posting/1658
Email: csea@ualberta.ca

By shacharlovett

This is the live blog of Lecture 16 of my graduate class “Convex Optimization.” A Table of Contents is here.

Even though this class focuses on modeling, it’s helpful to understand a little bit about how to solve convex optimization problems. Many people can avoid ever looking across the abstraction boundaries. It’s likely possible to get a feel for the optimal use of tools like cvxpy without digging too much into how they work. Whether using Stata to solve regressions or pytorch to fit neural networks, you can learn heuristics for speedups without knowing what’s under the hood. 

Unfortunately, the sad part of computational mathematics is computers are never fast enough. We need to pose problems that are solvable on the compute to which we have access. If you don’t have billions of dollars of Azure credits, then you have to understand a bit about what your solver does to get a solution in a reasonable amount of time. Solver knowledge can save you a lot of trial and error and reliance on folklore. A little bit can take you a long way. 

In this class, I’ll focus on the solvers that try to solve optimality conditions. Gradient-based solvers are the best-known example. For unconstrained convex problems, the gradient vanishes at the optimal solution. So to minimize a function f, our goal is to find a point where

This is solving a nonlinear equation.

For constrained optimization, the KKT conditions generalize the gradient condition. They are a set of equations that are necessary and sufficient for optimality, a combination of nonlinear equations (the gradient of the Lagrangian must equal zero, the equality constraints must be satisfied, and complementary slackness must hold) and constraints on the nonnegativity of variables. Convex solvers try to solve these nonlinear equations subject to holding variables being nonnegative. 

Nonlinear equations don’t typically have nice closed form solutions. To be fair, we learn in high school that linear equations don’t have simple solutions either. We have to slog through Gaussian elimination to solve systems of three equations in three variables. Nonlinear equations are worse, however, as there are no natural analogs of Gaussian elimination.

Instead, we solve nonlinear equations by sequentially solving linear equations. The most famous example of solving nonlinear equations by linear equations is called Newton’s method. Let’s say you want to solve a nonlinear system of equations F(x) = 0, which has n variables and n equations. That is, F has an n-dimensional vector as input and an n-dimensional vector as output. Newton’s method iteratively solves a linear approximation to this equation. Suppose your current approximation is x0. You can make a Taylor approximation to F as

Since F maps n-vectors to n-vectors, the “gradient” here is an n by n matrix called the Jacobian of F. If we set the Taylor approximation equal to zero, we get the update

where v is the solution to the linear equation

Under reasonable conditions, iterating this procedure will find the optimal x.

I’ll talk more about Newton’s method in the coming lectures, but I wanted to at least introduce it today to show why we care so much about solving systems of linear equations. The backbone of optimization methods is the solution of linear equations.

Since the dawn of the computer, we’ve optimized our architectures to solve linear equations. Linear systems solvers are built upon optimized computational primitives that let the end user type “A\b” or “np.linalg.solve(A,b),” and then you don’t have to worry about what’s under the hood. If you can reduce your optimization problem to a few of these API calls, you should consider this a win. You can lean on some of the most optimized numerical software in existence.

Except, as I’ve been saying, it’s not quite that easy. Algorithms for linear equation solving run in “polynomial time,” but the associated scaling may still be prohibitive. Adding two n-vectors together requires approximately n arithmetic operations (or FLOPs, if you prefer). An algorithm that requires a constant multiple of n operations runs in linear time. Multiplying an n x n matrix times a vector requires approximately 2n² arithmetic operations. Algorithms that require a constant multiple of n² operations run in quadratic time. Solving Ax=b for general matrices requires on the order of n³ operations, called cubic time. For large systems, cubic time algorithms are prohibitively expensive. 

It’s thus important for a modeler to understand how computers solve these systems. You want to build models that lean on the strengths of your solvers. If I tell you that arranging your model in a particular order can buy you a factor of 10 speedup, I’m sure you’ll take it. You might never implement a linear system solver, but you should know which models the solvers are best suited for.

Hence, our tour of convex optimization solvers starts with a tour of linear system solvers. Some problems can be solved in linear time. The simplest are diagonal systems. If A is a diagonal matrix, then you can solve for each coordinate independently. This requires only n arithmetic operations. Other more complicated matrix forms also admit linear time solutions. A notable example is the tridiagonal system, where the matrix A is only nonzero on entries just above and below the matrix diagonal.

A step up in complexity is quadratic time. If a matrix is orthogonal, so that A^-1 = A^T, then you can invert it by a matrix multiply in quadratic time. If a matrix is lower triangular or upper triangular, substitution algorithms solve the associated systems in quadratic time. 

Linear systems solvers try to factor the matrix A into a product of matrices where equation solving is at worst quadratic time. With such a factorization, you can solve your system in quadratic time. Most of the cost in modern linear systems solving is thus in matrix factorization. Today’s lecture will take a tour of the most common factorization techniques.

Subscribe now

By Ben Recht

Commuting local Hamiltonians provide a testing ground for studying many of the most interesting open questions in quantum information theory, including the quantum PCP conjecture and the existence of area laws. Although they are a simplified model of quantum computation, the status of the commuting local Hamiltonian problem remains largely unknown. A number of works have shown that increasingly expressive families of commuting local Hamiltonians admit completely classical verifiers. Despite intense work, the largest class of commuting local Hamiltonians we can place in NP are those on a square lattice, where each lattice site is a qutrit. Even worse, many of the techniques used to analyze these problems rely heavily on the geometry of the square lattice and the properties of the numbers 2 and 3 as local dimensions. In this work, we present a new technique to analyze the complexity of various families of commuting local Hamiltonians: guided reductions. Intuitively, these are a generalization of typical reduction where the prover provides a guide so that the verifier can construct a simpler Hamiltonian. The core of our reduction is a new rounding technique based on a combination of Jordan's Lemma and the Structure Lemma. Our rounding technique is much more flexible than previous work, and allows us to show that a larger family of commuting local Hamiltonians is in NP, albiet with the restriction that all terms are rank-1. Specifically, we prove the following two results: 1. Commuting local Hamiltonians in 2D that are rank-1 are contained in NP, independent of the qudit dimension. Note that this family of commuting local Hamiltonians has no restriction on the local dimension or the locality. 2. We prove that rank-1, 3D commuting Hamiltonians with qudits on edges are in NP. To our knowledge this is the first time a family of 3D commuting local Hamiltonians has been contained in NP.

Authors: Casper Gyurik, Alexander Schmidhuber, Robbie King, Vedran Dunjko, Ryu Hayakawa

Topological data analysis (TDA) aims to extract noise-robust features from a data set by examining the number and persistence of holes in its topology. We show that a computational problem closely related to a core task in TDA -- determining whether a given hole persists across different length scales -- is $\mathsf{BQP}_1$-hard and contained in $\mathsf{BQP}$. This result implies an exponential quantum speedup for this problem under standard complexity-theoretic assumptions. Our approach relies on encoding the persistence of a hole in a variant of the guided sparse Hamiltonian problem, where the guiding state is constructed from a harmonic representative of the hole.

Authors: Simon C. Marshall, Scott Aaronson, Vedran Dunjko

This paper furthers existing evidence that quantum computers are capable of computations beyond classical computers. Specifically, we strengthen the collapse of the polynomial hierarchy to the second level if: (i) Quantum computers with postselection are as powerful as classical computers with postselection ($\mathsf{PostBQP=PostBPP}$), (ii) any one of several quantum sampling experiments ($\mathsf{BosonSampling}$, $\mathsf{IQP}$, $\mathsf{DQC1}$) can be approximately performed by a classical computer (contingent on existing assumptions). This last result implies that if any of these experiment's hardness conjectures hold, then quantum computers can implement functions classical computers cannot ($\mathsf{FBQP\neq FBPP}$) unless the polynomial hierarchy collapses to its 2nd level. These results are an improvement over previous work which either achieved a collapse to the third level or were concerned with exact sampling, a physically impractical case. The workhorse of these results is a new technical complexity-theoretic result which we believe could have value beyond quantum computation. In particular, we prove that if there exists an equivalence between problems solvable with an exact counting oracle and problems solvable with an approximate counting oracle, then the polynomial hierarchy collapses to its second level, indeed to $\mathsf{ZPP^{NP}}$.

Authors: Gianfranco Bilardi, Lorenzo De Stefani

It is shown that $S(G) = O\left(m/\log_2 m + d\right)$ pebbles are sufficient to pebble any DAG $G=(V,E)$, with $m$ edges and maximum in-degree $d$. It was previously known that $S(G) = O\left(d n/\log n\right)$. The result builds on two novel ideas. The first is the notion of $B-budget\ decomposition$ of a DAG $G$, an efficiently computable partition of $G$ into at most $2^{\lfloor \frac{m}{B} \rfloor}$ sub-DAGs, whose cumulative space requirement is at most $B$. The second is the challenging vertices technique, which constructs a pebbling schedule for $G$ from a pebbling schedule for a simplified DAG $G'$, obtained by removing from $G$ a selected set of vertices $W$ and their incident edges. This technique also yields improved pebbling upper bounds for DAGs with bounded genus and for DAGs with bounded topological depth.

Authors: Josh Alman, Hantao Yu

Algebraic matrix multiplication algorithms are designed by bounding the rank of matrix multiplication tensors, and then using a recursive method. However, designing algorithms in this way quickly leads to large constant factors: if one proves that the tensor for multiplying $n \times n$ matrices has rank $\leq t$, then the resulting recurrence shows that $M \times M$ matrices can be multiplied using $O(n^2 \cdot M^{\log_n t})$ operations, where the leading constant scales proportionally to $n^2$. Even modest increases in $n$ can blow up the leading constant too much to be worth the slight decrease in the exponent of $M$. Meanwhile, the asymptotically best algorithms use very large $n$, such that $n^2$ is larger than the number of atoms in the visible universe! In this paper, we give new ways to use tensor rank bounds to design matrix multiplication algorithms, which lead to smaller leading constants than the standard recursive method. Our main result shows that, if the tensor for multiplying $n \times n$ matrices has rank $\leq t$, then $M \times M$ matrices can be multiplied using only $n^{O(1/(\log n)^{0.33})} \cdot M^{\log_n t}$ operations. In other words, we improve the leading constant in general from $O(n^2)$ to $n^{O(1/(\log n)^{0.33})} < n^{o(1)}$. We then apply this and further improve the leading constant in a number of situations of interest. We show that, in the popularly-conjectured case where $\omega=2$, a new, different recursive approach can lead to an improvement. We also show that the leading constant of the current asymptotically fastest matrix multiplication algorithm, and any algorithm designed using the group-theoretic method, can be further improved by taking advantage of additional structure of the underlying tensor identities.

Authors: Alexander A. Sherstov, Andrey A. Storozhenko

We fully determine the communication complexity of approximating matrix rank, over any finite field $\mathbb{F}$. We study the most general version of this problem, where $0\leq r0$. Our result is an exponential improvement in $k$ over previous work. We also settle the randomized and quantum communication complexity of several other linear-algebraic problems, for all settings of parameters. This includes the determinant problem (given matrices $A$ and $B$, distinguish between the cases $\mathrm{det}(A+B)=a$ and $\mathrm{det}(A+B)=b$, for fixed field elements $a\ne b)$ and the subspace sum and subspace intersection problem (given subspaces $S$ and $T$ of known dimensions $m$ and $\ell$, respectively, approximate the dimensions of $S+T$ and $S\cap T$).

Authors: Herbert Edelsbrunner, Alexey Garber, Morteza Saghafian

We generalize a classical result by Boris Delaunay that introduced Delaunay triangulations. In particular, we prove that for a locally finite and coarsely dense generic point set $A$ in $\mathbb{R}^d$, every generic point of $\mathbb{R}^d$ belongs to exactly $\binom{d+k}{d}$ simplices whose vertices belong to $A$ and whose circumspheres enclose exactly $k$ points of $A$. We extend this result to the cases in which the points are weighted, and when $A$ contains only finitely many points in $\mathbb{R}^d$ or in $\mathbb{S}^d$. Furthermore, we use the result to give a new geometric proof for the fact that volumes of hypersimplices are Eulerian numbers.

Authors: Roua Rouatbi, Juan Esteban Suarez, Ivo F. Sbalzarini

We introduce the Push-Forward Signed Distance Morphometric (PF-SDM), a novel method for shape quantification in biomedical imaging that is continuous, interpretable, and invariant to shape-preserving transformations. PF-SDM effectively captures the geometric properties of shapes, including their topological skeletons and radial symmetries. This results in a robust and interpretable shape descriptor that generalizes to capture temporal shape dynamics. Importantly, PF-SDM avoids certain issues of previous geometric morphometrics, like Elliptical Fourier Analysis and Generalized Procrustes Analysis, such as coefficient correlations and landmark choices. We present the PF-SDM theory, provide a practically computable algorithm, and benchmark it on synthetic data.

Authors: Tamal K. Dey, Tao Hou, Dmitriy Morozov

Zigzag filtrations of simplicial complexes generalize the usual filtrations by allowing simplex deletions in addition to simplex insertions. The barcodes computed from zigzag filtrations encode the evolution of homological features. Although one can locate a particular feature at any index in the filtration using existing algorithms, the resulting representatives may not be compatible with the zigzag: a representative cycle at one index may not map into a representative cycle at its neighbor. For this, one needs to compute compatible representative cycles along each bar in the barcode. Even though it is known that the barcode for a zigzag filtration with $m$ insertions and deletions can be computed in $O(m^\omega)$ time, it is not known how to compute the compatible representatives so efficiently. For a non-zigzag filtration, the classical matrix-based algorithm provides representatives in $O(m^3)$ time, which can be improved to $O(m^\omega)$. However, no known algorithm for zigzag filtrations computes the representatives with the $O(m^3)$ time bound. We present an $O(m^2n)$ time algorithm for this problem, where $n\leq m$ is the size of the largest complex in the filtration.

Authors: Qisheng Wang, Zhicheng Zhang

Trace distance and infidelity (induced by square root fidelity), as basic measures of the closeness of quantum states, are commonly used in quantum state discrimination, certification, and tomography. However, the sample complexity for their estimation still remains open. In this paper, we solve this problem for pure states. We present a quantum algorithm that estimates the trace distance and square root fidelity between pure states to within additive error $\varepsilon$, given sample access to their identical copies. Our algorithm achieves the optimal sample complexity $\Theta(1/\varepsilon^2)$, improving the long-standing folklore $O(1/\varepsilon^4)$. Our algorithm is composed of a samplized phase estimation of the product of two Householder reflections. Notably, an improved (multi-)samplizer for pure states is used as an algorithmic tool in our construction, through which any quantum query algorithm using $Q$ queries to the reflection operator about a pure state $|\psi\rangle$ can be converted to a $\delta$-close (in the diamond norm) quantum sample algorithm using $\Theta(Q^2/\delta)$ samples of $|\psi\rangle$. This samplizer for pure states is shown to be optimal.

Authors: Maciej Paszyński

We show that assuming the availability of the processor with variable precision arithmetic, we can compute matrix-by-matrix multiplications in $O(N^2log_2N)$ computational complexity. We replace the standard matrix-by-matrix multiplications algorithm $\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix}\begin{bmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{bmatrix}=\begin{bmatrix}A_{11}B_{11}+A_{12}B_{21}&A_{11}B_{12}+A_{12}B_{22}\\A_{21}B_{11}+A_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22}\end{bmatrix}$ by $\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix}\begin{bmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{bmatrix}=\Bigl\lfloor\begin{bmatrix} (A_{11}+\epsilon A_{12})(B_{11}+1/{\epsilon}B_{21})&(A_{11}+\epsilon A_{12})(B_{12}+1/{\epsilon}B_{22})\\(A_{21}+\epsilon A_{22})(B_{11}+1/{\epsilon}B_{21})&(A_{21}+\epsilon A_{22})(B_{12}+1/{\epsilon}B_{22})\end{bmatrix}\Bigr\rfloor \mod \frac{1}{\epsilon}$. The resulting computational complexity for $N\times N$ matrices can be estimated from recursive equation $T(N)=4(N/2)^2$ (multiplication of a matrix by number)+$4(N/2)^2$ (additions of matrices)+$2N^2$ (floor and modulo)+$4T(N/2)$ (recursive calls) as $O(N^2log_2N)$. The novelty of the method lies in the observation, somehow ignored by other matrix-by-matrix multiplication algorithms, that we can multiply matrix entries by non-integer numbers to improve computational complexity. In other words, while having a processor that can compute multiplications, additions, modulo and floor operations with variable precision arithmetic in $O(1)$, we can obtain a matrix-by-matrix multiplication algorithm with $O(N^2log_2N)$ computational complexity. We also present a MATLAB code using VPA variable precision arithmetic emulator that can multiply matrices of size $N\times N$ using $(4log_2N+1)N^2$ variable precision arithmetic operations. This emulator uses $O(N)$ digits to run our algorithm.

Authors: Holger Dell, Anselm Haak, Melvin Kallmayer, Leo Wennmann

We present a randomized algorithm for solving low-degree polynomial equation systems over finite fields faster than exhaustive search. In order to do so, we follow a line of work by Lokshtanov, Paturi, Tamaki, Williams, and Yu (SODA 2017), Bj\"orklund, Kaski, and Williams (ICALP 2019), and Dinur (SODA 2021). In particular, we generalize Dinur's algorithm for $\mathbb{F}_2$ to all finite fields, in particular the "symbolic interpolation" of Bj\"orklund, Kaski, and Williams, and we use an efficient trimmed multipoint evaluation and interpolation procedure for multivariate polynomials over finite fields by Van der Hoeven and Schost (AAECC 2013). The running time of our algorithm matches that of Dinur's algorithm for $\mathbb{F}_2$ and is significantly faster than the one of Lokshtanov et al. for $q>2$. We complement our results with tight conditional lower bounds that, surprisingly, we were not able to find in the literature. In particular, under the strong exponential time hypothesis, we prove that it is impossible to solve $n$-variate low-degree polynomial equation systems over $\mathbb{F}_q$ in time $O((q-\varepsilon)^{n})$. As a bonus, we show that under the counting version of the strong exponential time hypothesis, it is impossible to compute the number of roots of a single $n$-variate low-degree polynomial over $\mathbb{F}_q$ in time ${O((q-\varepsilon)^{n})}$; this generalizes a result of Williams (SOSA 2018) from $\mathbb{F}_2$ to all finite fields.

Authors: Orin Levy, Noam Touitou, Aviv Rosenberg

Online paging is a fundamental problem in the field of online algorithms, in which one maintains a cache of $k$ slots as requests for fetching pages arrive online. In the weighted variant of this problem, each page has its own fetching cost; a substantial line of work on this problem culminated in an (optimal) $O(\log k)$-competitive randomized algorithm, due to Bansal, Buchbinder and Naor (FOCS'07). Existing work for weighted paging assumes that page weights are known in advance, which is not always the case in practice. For example, in multi-level caching architectures, the expected cost of fetching a memory block is a function of its probability of being in a mid-level cache rather than the main memory. This complex property cannot be predicted in advance; over time, however, one may glean information about page weights through sampling their fetching cost multiple times. We present the first algorithm for online weighted paging that does not know page weights in advance, but rather learns from weight samples. In terms of techniques, this requires providing (integral) samples to a fractional solver, requiring a delicate interface between this solver and the randomized rounding scheme; we believe that our work can inspire online algorithms to other problems that involve cost sampling.

Authors: Owais Aijaz, Syed Muhammad Ali, Yousuf Uyghur

Seam carving, a content-aware image resizing technique, has garnered significant attention for its ability to resize images while preserving important content. In this paper, we conduct a comprehensive analysis of four algorithmic design techniques for seam carving: brute-force, greedy, dynamic programming, and GPU-based parallel algorithms. We begin by presenting a theoretical overview of each technique, discussing their underlying principles and computational complexities. Subsequently, we delve into empirical evaluations, comparing the performance of these algorithms in terms of runtime efficiency. Our experimental results provide insights into the theoretical complexities of the design techniques.

Authors: Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia, Stefan Tiegel

We prove that there is a universal constant $C>0$ so that for every $d \in \mathbb N$, every centered subgaussian distribution $\mathcal D$ on $\mathbb R^d$, and every even $p \in \mathbb N$, the $d$-variate polynomial $(Cp)^{p/2} \cdot \|v\|_{2}^p - \mathbb E_{X \sim \mathcal D} \langle v,X\rangle^p$ is a sum of square polynomials. This establishes that every subgaussian distribution is \emph{SoS-certifiably subgaussian} -- a condition that yields efficient learning algorithms for a wide variety of high-dimensional statistical tasks. As a direct corollary, we obtain computationally efficient algorithms with near-optimal guarantees for the following tasks, when given samples from an arbitrary subgaussian distribution: robust mean estimation, list-decodable mean estimation, clustering mean-separated mixture models, robust covariance-aware mean estimation, robust covariance estimation, and robust linear regression. Our proof makes essential use of Talagrand's generic chaining/majorizing measures theorem.

Authors: Nick Fischer, Bernhard Haeupler, Rustam Latypov, Antti Roeyskoe, Aurelio L. Sulser

We give the first parallel algorithm with optimal $\tilde{O}(m)$ work for the classical problem of computing Single-Source Shortest Paths in general graphs with negative-weight edges. In graphs without negative edges, Dijkstra's algorithm solves the Single-Source Shortest Paths (SSSP) problem with optimal $\tilde O(m)$ work, but is inherently sequential. A recent breakthrough by Bernstein, Nanongkai, Wulff-Nilsen; FOCS '22 achieves the same for general graphs. Parallel shortest path algorithms are more difficult and have been intensely studied for decades. Only very recently, multiple lines of research culminated in parallel algorithms with optimal work $\tilde O(m)$ for various restricted settings, such as approximate or exact algorithms for directed or undirected graphs without negative edges. For general graphs, the best known algorithm by [shvinkumar, Bernstein, Cao, Grunau, Haeupler, Jiang, Nanongkai, Su; ESA '24 still requires $m^{1+o(1)}$ work. This paper presents a randomized parallel algorithm for SSSP in general graphs with near-linear work $\tilde O(m)$ and state-of-the-art span $n^{1/2 + o(1)}$. We follow a novel bottom-up approach leading to a particularly clean and simple algorithm. Our algorithm can be seen as a \emph{near-optimal parallel black-box reduction} from SSSP in general graphs to graphs without negative edges. In contrast to prior works, the reduction in this paper is both parallel and essentially without overhead, only affecting work and span by polylogarithmic factors.

Authors: Njagi Mwaniki, Erik Garrison, Nadia Pisanti

In this paper, we introduce flubbles, a new definition of "bubbles" corresponding to variants in a (pan)genome graph $G$. We then show a characterization for flubbles in terms of equivalence classes regarding cycles in an intermediate data structure we built from the spanning tree of the $G$, which leads us to a linear time and space solution for finding all flubbles. Furthermore, we show how a related characterization also allows us to efficiently detect what we define as hairpin inversions: a cycle preceded and followed by the same path in the graph; being the latter necessarily traversed both ways, this structure corresponds to inversions. Finally, Inspired by the concept of Program Structure Tree introduced fifty years ago to represent the hierarchy of the control structure of a program, we define a tree representing the structure of G in terms of flubbles, the flubble tree, which we also find in linear time. The hierarchy of variants introduced by the flubble tree paves the way for new investigations of (pan)genomic structures and their decomposition for practical analyses. We have implemented our methods into a prototype tool named povu which we tested on human and yeast data. We show that povu can find flubbles and also output the flubble tree while being as fast (or faster than) well established tools that find bubbles, such as vg and BubbleGun. Moreover, we show how, within the same time, povu can find hairpin inversions that, to the best of our knowledge, no other tool is able to find. Our tool is freely available at https://github.com/urbanslug/povu/ under the MIT License.

Authors: Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, Vaishali Surianarayanan, Jie Xue

The \textsc{Capacitated $d$-Hitting Set} problem involves a universe $U$ with a capacity function $\mathsf{cap}: U \rightarrow \mathbb{N}$ and a collection $\mathcal{A}$ of subsets of $U$, each of size at most $d$. The goal is to find a minimum subset $S \subseteq U$ and an assignment $\phi : \mathcal{A} \rightarrow S$ such that for every $A \in \mathcal{A}$, $\phi(A) \in A$, and for each $x \in U$, $|\phi^{-1}(x)| \leq \mathsf{cap}(x)$. For $d=2$, this is known as \textsc{Capacitated Vertex Cover}. In the weighted variant, each element of $U$ has a positive integer weight, with the objective of finding a minimum-weight capacitated hitting set. Chuzhoy and Naor [SICOMP 2006] provided a factor-3 approximation for \textsc{Capacitated Vertex Cover} and showed that the weighted case lacks an $o(\log n)$-approximation unless $P=NP$. Kao and Wong [SODA 2017] later independently achieved a $d$-approximation for \textsc{Capacitated $d$-Hitting Set}, with no $d - \epsilon$ improvements possible under the Unique Games Conjecture. Our main result is a parameterized approximation algorithm with runtime $\left(\frac{k}{\epsilon}\right)^k 2^{k^{O(kd)}}(|U|+|\mathcal{A}|)^{O(1)}$ that either concludes no solution of size $\leq k$ exists or finds $S$ of size $\leq 4/3 \cdot k$ and weight at most $2+\epsilon$ times the minimum weight for solutions of size $\leq k$. We further show that no FPT-approximation with factor $c > 1$ exists for unweighted \textsc{Capacitated $d$-Hitting Set} with $d \geq 3$, nor with factor $2 - \epsilon$ for the weighted version, assuming the Exponential Time Hypothesis. These results extend to \textsc{Capacitated Vertex Cover} in multigraphs. Additionally, a variant of multi-dimensional \textsc{Knapsack} is shown hard to FPT-approximate within $2 - \epsilon$.

Authors: John Augustine, Fabien Dufoulon, Gopal Pandurangan

Byzantine agreement is a fundamental problem in fault-tolerant distributed networks that has been studied intensively for the last four decades. Most of these works designed protocols for complete networks. A key goal in Byzantine protocols is to tolerate as many Byzantine nodes as possible. The work of Dwork, Peleg, Pippenger, and Upfal [STOC 1986, SICOMP 1988] was the first to address the Byzantine agreement problem in sparse, bounded degree networks and presented a protocol that achieved almost-everywhere agreement among honest nodes. In such networks, all known Byzantine agreement protocols (e.g., Dwork, Peleg, Pippenger, and Upfal, STOC 1986; Upfal, PODC 1992; King, Saia, Sanwalani, and Vee, FOCS 2006) that tolerated a large number of Byzantine nodes had a major drawback that they were not fully-distributed -- in those protocols, nodes are required to have initial knowledge of the entire network topology. This drawback makes such protocols inapplicable to real-world communication networks such as peer-to-peer (P2P) networks, which are typically sparse and bounded degree and where nodes initially have only local knowledge of themselves and their neighbors. Indeed, a fundamental open question raised by the above works is whether one can design Byzantine protocols that tolerate a large number of Byzantine nodes in sparse networks that work with only local knowledge, i.e., fully-distributed protocols. The work of Augustine, Pandurangan, and Robinson [PODC 2013] presented the first fully-distributed Byzantine agreement protocol that works in sparse networks, but it tolerated only up to $O(\sqrt{n}/ polylog(n))$ Byzantine nodes (where $n$ is the total network size). We answer the earlier open question by presenting fully-distributed Byzantine agreement protocols for sparse, bounded degree networks that tolerate significantly more Byzantine nodes -- up to $O(n/ polylog(n))$ of them.

Authors: Nick Fischer, Ce Jin, Yinzhan Xu

The 3SUM problem is one of the cornerstones of fine-grained complexity. Its study has led to countless lower bounds, but as has been sporadically observed before -- and as we will demonstrate again -- insights on 3SUM can also lead to algorithmic applications. The starting point of our work is that we spend a lot of technical effort to develop new algorithms for 3SUM-type problems such as approximate 3SUM-counting, small-doubling 3SUM-counting, and a deterministic subquadratic-time algorithm for the celebrated Balog-Szemer\'edi-Gowers theorem from additive combinatorics. As consequences of these tools, we derive diverse new results in fine-grained complexity and pattern matching algorithms, answering open questions from many unrelated research areas. Specifically: - A recent line of research on the "short cycle removal" technique culminated in tight 3SUM-based lower bounds for various graph problems via randomized fine-grained reductions [Abboud, Bringmann, Fischer; STOC '23] [Jin, Xu; STOC '23]. In this paper we derandomize the reduction to the important 4-Cycle Listing problem. - We establish that \#3SUM and 3SUM are fine-grained equivalent under deterministic reductions. - We give a deterministic algorithm for the $(1+\epsilon)$-approximate Text-to-Pattern Hamming Distances problem in time $n^{1+o(1)} \cdot \epsilon^{-1}$. - In the $k$-Mismatch Constellation problem the input consists of two integer sets $A, B \subseteq [N]$, and the goal is to test whether there is a shift $c$ such that $|(c + B) \setminus A| \leq k$ (i.e., whether $B$ shifted by $c$ matches $A$ up to $k$ mismatches). For moderately small $k$ the previously best running time was $\tilde O(|A| \cdot k)$ [Cardoze, Schulman; FOCS '98] [Fischer; SODA '24]. We give a faster $|A| \cdot k^{2/3} \cdot N^{o(1)}$-time algorithm in the regime where $|B| = \Theta(|A|)$.

Authors: Akanksha Agrawal, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Shaily Verma

The classic greedy coloring (first-fit) algorithm considers the vertices of an input graph $G$ in a given order and assigns the first available color to each vertex $v$ in $G$. In the {\sc Grundy Coloring} problem, the task is to find an ordering of the vertices that will force the greedy algorithm to use as many colors as possible. In the {\sc Partial Grundy Coloring}, the task is also to color the graph using as many colors as possible. This time, however, we may select both the ordering in which the vertices are considered and which color to assign the vertex. The only constraint is that the color assigned to a vertex $v$ is a color previously used for another vertex if such a color is available. Whether {\sc Grundy Coloring} and {\sc Partial Grundy Coloring} admit fixed-parameter tractable (FPT) algorithms, algorithms with running time $f(k)n^{\OO(1)}$, where $k$ is the number of colors, was posed as an open problem by Zaker and by Effantin et al., respectively. Recently, Aboulker et al. (STACS 2020 and Algorithmica 2022) resolved the question for \Grundycol\ in the negative by showing that the problem is W[1]-hard. For {\sc Partial Grundy Coloring}, they obtain an FPT algorithm on graphs that do not contain $K_{i,j}$ as a subgraph (a.k.a. $K_{i,j}$-free graphs). Aboulker et al.~re-iterate the question of whether there exists an FPT algorithm for {\sc Partial Grundy Coloring} on general graphs and also asks whether {\sc Grundy Coloring} admits an FPT algorithm on $K_{i,j}$-free graphs. We give FPT algorithms for {\sc Partial Grundy Coloring} on general graphs and for {\sc Grundy Coloring} on $K_{i,j}$-free graphs, resolving both the questions in the affirmative. We believe that our new structural theorems for partial Grundy coloring and ``representative-family'' like sets for $K_{i,j}$-free graphs that we use in obtaining our results may have wider algorithmic applications.

Authors: David Dekker, Carl Henrik Häll, Anders Peterson, Christiane Schmidt

A seemingly simple, yet widely applicable subroutine in automated train scheduling is the insertion of a new train path to a timetable in a railway network. We believe it to be the first step towards a new train-rerouting framework in case of large disturbances or maintenance works. Other applications include handling ad-hoc requests and modifying train paths upon request from railway undertakings. We propose a fast and scalable path-insertion algorithm based on dynamic programming that is able to output multiple suitable paths. Our algorithm uses macroscopic data and can run on railway networks with any number of tracks. We apply the algorithm on the line from G\"oteborg S\"aven\"as to the Norwegian border at Kornsj\"o. For a time window of seven hours, we obtain eight suitable paths for a freight train within 0.3 seconds after preprocessing.

Authors: Chandra Chekuri, Anand Louis

We consider algorithms and spectral bounds for sparsest cut and conductance in directed polymatrodal networks. This is motivated by recent work on submodular hypergraphs \cite{Yoshida19,LiM18,ChenOT23,Veldt23} and previous work on multicommodity flows and cuts in polymatrodial networks \cite{ChekuriKRV15}. We obtain three results. First, we obtain an $O(\sqrt{\log n})$-approximation for sparsest cut and point out how this generalizes the result in \cite{ChenOT23}. Second, we consider the symmetric version of conductance and obtain an $O(\sqrt{OPT \log r})$ approximation where $r$ is the maximum degree and we point out how this generalizes previous work on vertex expansion in graphs. Third, we prove a non-constructive Cheeger like inequality that generalizes previous work on hypergraphs. We provide a unified treatment via line-embeddings which were shown to be effective for submodular cuts in \cite{ChekuriKRV15}.

Authors: Greg Bodwin, Tuong Le

A reachability preserver is a basic kind of graph sparsifier, which preserves the reachability relation of an $n$-node directed input graph $G$ among a set of given demand pairs $P$ of size $|P|=p$. We give constructions of sparse reachability preservers in the online setting, where $G$ is given on input, the demand pairs $(s, t) \in P$ arrive one at a time, and we must irrevocably add edges to a preserver $H$ to ensure reachability for the pair $(s, t)$ before we can see the next demand pair. Our main results are: -- There is a construction that guarantees a maximum preserver size of $$|E(H)| \le O\left( n^{0.72}p^{0.56} + n^{0.6}p^{0.7} + n\right).$$ This improves polynomially on the previous online upper bound of $O( \min\{np^{0.5}, n^{0.5}p\}) + n$, implicit in the work of Coppersmith and Elkin [SODA '05]. -- Given a promise that the demand pairs will satisfy $P \subseteq S \times V$ for some vertex set $S$ of size $|S|=:\sigma$, there is a construction that guarantees a maximum preserver size of $$|E(H)| \le O\left( (np\sigma)^{1/2} + n\right).$$ A slightly different construction gives the same result for the setting $P \subseteq V \times S$. This improves polynomially on the previous online upper bound of $O( \sigma n)$ (folklore). All of these constructions are polynomial time, deterministic, and they do not require knowledge of the values of $p, \sigma$, or $S$. Our techniques also give a small polynomial improvement in the current upper bounds for offline reachability preservers, and they extend to a stronger model in which we must commit to a path for all possible reachable pairs in $G$ before any demand pairs have been received. As an application, we improve the competitive ratio for Online Unweighted Directed Steiner Forest to $O(n^{3/5 + \varepsilon})$.

Authors: Lorenzo De Stefani, Vedant Gupta

Asymptotically tight lower bounds are derived for the Input/Output (I/O) complexity of a class of dynamic programming algorithms including matrix chain multiplication, optimal polygon triangulation, and the construction of optimal binary search trees. Assuming no recomputation of intermediate values, we establish an $\Omega\left(\frac{n^3}{\sqrt{M}B}\right)$ I/O lower bound, where $n$ denotes the size of the input and $M$ denotes the size of the available fast memory (cache). When recomputation is allowed, we show the same bound holds for $M < cn$, where $c$ is a positive constant. In the case where $M \ge 2n$, we show an $\Omega\left(n/B\right)$ I/O lower bound. We also discuss algorithms for which the number of executed I/O operations matches asymptotically each of the presented lower bounds, which are thus asymptotically tight. Additionally, we refine our general method to obtain a lower bound for the I/O complexity of the Cocke-Younger-Kasami algorithm, where the size of the grammar impacts the I/O complexity. An upper bound with asymptotically matching performance in many cases is also provided.

Authors: Dariusz Dereniowski, Janusz Dybizbański, Przemysław Karpiński, Michał Zakrzewski, Paweł Żyliński

We present a simple linear-time algorithm that finds a spanning tree $T$ of a given $2$-edge-connected graph $G$ such that each vertex $v$ of $T$ has degree at most $\lceil \frac{\deg_G(v)}{2}\rceil + 1$.

I’ve posted quite a bit about the binary tiling of the hyperbolic plane recently, including what you get when you shrink its vertical edges, a related “nowhere-neat” tessellation, the connection to Smith charts and Escher, a method to 3-color its tiles, a half-flipped variation of the tiling, and its applications in proving that folding origami is hard. But I thought there might be room for one more post, in honor of the Wikipedia binary tiling article’s new Good Article Status. This one is about something I wanted to include in the Wikipedia article, but couldn’t, because I couldn’t find published sources describing it: a way of numbering tiles that encodes their position in a tiling and instantly proves the assertion in the article that there are uncountably many binary tilings.

The basic idea is very simple: in the binary tiling (in its conventional view as a pattern of similar squares or rectangles in the Poincaré half-plane), if you look directly upward from any tile, some of the tiles above it will extend farther to the left, and some of them will extend farther to the right. We will encode this by a binary sequence, where a 1 encodes a tile that extends to the left, and a 0 encodes a tile that extends to the right. (This seems backwards, but there’s a reason for this choice that will become clear soon.) To make it backwards in a different way, I want to write this sequence in right-to-left order, so that for instance the encoding …1100 means that the closest two tiles above it extend to the right, and the next two extend to the left. Here’s a picture with some examples. The label in each square only encodes the tiles that you can see in the picture, but the tiling itself can continue above these squares in multiple different ways, resulting in different continuations of these labels.

If you read the binary sequences in a single row, left-to-right, they should look familiar: they’re just the binary encodings of the non-negative integers 0, 1, 2, 3, … in order. That’s why I chose the backwards order of binary digits and backwards choice of what 0 and 1 mean: with the digits in the other order we would get the bit-reversal permutation of these numbers and with the other choice of what 0 and 1 mean they would count down rather than counting up.

The binary representation of an ordinary integer eventually terminates, with all higher-order binary digits equal to zero for a non-negative integer (or equal to one for a two’s-complement negative integer). But the binary sequences coming from a binary tiling might not terminate in this way. Any binary sequence is possible, and uniquely determines the entire tiling surrounding a tile with that sequence as its label. To find the tiling from a binary sequence, just place tiles directly above the labeled tile, as the sequence dictates, and then fill in everything else below them in the only way possible. There are uncountably many binary sequences (for instance, each two real numbers in the unit interval have different binary expansions), but only countably many of them can show up as the labels in a single binary tiling. For this reason we know that there are uncountably many different binary tilings.

But because we’re ordering the binary sequences right-to-left, they’re not the binary expansions of real numbers. And because they aren’t eventually zero, they’re not the binary expansions of ordinary integers. Instead, they’re the binary expansions of a more exotic number system, the 2-adic integers. You can think of the arithmetic of these numbers as just like ordinary binary arithmetic except that it continues infinitely to the left, in the same way that ordinary binary arithmetic on real numbers continues infinitely to the right.

The 2-adic integers contain the ordinary integers (sometimes called in this context rational integers) but they also contain any rational number whose denominator is odd. These can be recognized as the 2-adic numbers whose binary expansion is eventually repeating. More precisely, when a 2-adic number has a repeating pattern of length \(i\) that repeats the binary expansion of the integer \(n\), it can be thought of as equal to the rational number \(-n/(2^i-1)\). As an example that is eventually repeating but not purely repeating, the rational number \(\tfrac13\) is a 2-adic integer with a binary expansion …0101011 that, after the rightmost 1, repeats with a period-2 pattern. (Try multiplying it by 3 in binary and watch all the nonzero bits get carried away!)

We can encode many convenient properties of the tiling in properties of these numbers:

• Two tiles of the same tiling have a non-reflective symmetry of the tiling that takes one to the other, if and only if they are labeled by the same 2-adic integer.

• The image of a tile labeled \(x\), in the reflection of the tiling, has the label \(-x-1\), the 2-adic integer with all bits flipped.

• The left neighbor of a tile labeled \(x\) is labeled \(x-1\), and the right neighbor is labeled \(x+1\). The two neighbors below a tile labeled \(x\) are labeled \(2x\) and \(2x+1\).

• Each 2-adic integer is either odd or even (according to its last binary digit, just like ordinary integers). If a tile is labeled by an even number \(x\), it is on the left side of the tile above it, which is labeled \(x/2\). If a tile is labeled by an odd number \(y\), it is on the right side of the tile above it, which is labeled \((x-1)/2\).

• Two labels \(x\) and \(y\) appear together in the same tiling if and only if one of the two labels can be obtained from the other by multiplying by a power of two and then adding a rational integer. This is true if and only if their binary sequences are eventually equal (after removing finite prefixes of possibly different lengths), with one exception: negative and positive rational integer labels do belong to the same tiling, but have binary sequences that are eventually all zero or eventually all one.

• A tiling has a one-dimensional group of symmetries, obtained by scaling the Poincaré half-plane drawing by a factor of \(2^i\), if and only if its labels are rational numbers whose binary expansions have period \(i\). For instance the unique tiling for which scaling by 2 is a symmetry is the one where all the labels are rational integers.

Based on this labeling, we can count the number of distinct tilings (counting reflections as distinct) for which scaling by \(2^i\) is a symmetry: they are the number of distinct binary sequences of length \(i\), up to rotations, minus one. The minus one is because of the rational integer labels. For instance, there are two tilings for which multiplication by four (\(i=2\)) is a symmetry, with repeating patterns 00 = 11 (the rational integers) and 01 = 10 (integers \(\pm\tfrac13\)), which is its own mirror reflection. There are three tilings for which multiplication by eight is a symmetry: the rational integers again, and two mirror-image tilings with repeating patterns 001 and 011.

(Discuss on Mastodon)

By David Eppstein

Authors: Prabhanjan Ananth, John Bostanci, Aditya Gulati, Yao-Ting Lin

We study the (in)feasibility of quantum pseudorandom notions in a quantum analog of the random oracle model, where all the parties, including the adversary, have oracle access to the same Haar random unitary. In this model, we show the following: - (Unbounded-query secure) pseudorandom unitaries (PRU) exist. Moreover, the PRU construction makes two calls to the Haar oracle. - We consider constructions of PRUs making a single call to the Haar oracle. In this setting, we show that unbounded-query security is impossible to achieve. We complement this result by showing that bounded-query secure PRUs do exist with a single query to the Haar oracle. - We show that multi-copy pseudorandom state generators and function-like state generators (with classical query access), making a single call to the Haar oracle, exist. Our results have two consequences: (a) when the Haar random unitary is instantiated suitably, our results present viable approaches for building quantum pseudorandom objects without relying upon one-way functions and, (b) for the first time, we show that the key length in pseudorandom unitaries can be generically shrunk (relative to the output length). Our results are also some of the first usecases of the new "path recording" formalism for Haar random unitaries, introduced in the recent breakthrough work of Ma and Huang.

Authors: Roozbeh Bassirian, Bill Fefferman, Itai Leigh, Kunal Marwaha, Pei Wu

We find a modification to QMA where having one quantum proof is strictly less powerful than having two unentangled proofs, assuming EXP $\ne$ NEXP. This gives a new route to prove QMA(2) = NEXP that overcomes the primary drawback of a recent approach [arXiv:2402.18790 , arXiv:2306.13247] (QIP 2024). Our modification endows each proof with a form of *multipartite* unentanglement: after tracing out one register, a small number of qubits are separable from the rest of the state.

Authors: Avantika Agarwal, Shalev Ben-David

We study the quantum-classical polynomial hierarchy, QCPH, which is the class of languages solvable by a constant number of alternating classical quantifiers followed by a quantum verifier. Our main result is that QCPH is infinite relative to a random oracle (previously, this was not even known relative to any oracle). We further prove that higher levels of PH are not contained in lower levels of QCPH relative to a random oracle; this is a strengthening of the somewhat recent result that PH is infinite relative to a random oracle (Rossman, Servedio, and Tan 2016). The oracle separation requires lower bounding a certain type of low-depth alternating circuit with some quantum gates. To establish this, we give a new switching lemma for quantum algorithms which may be of independent interest. Our lemma says that for any $d$, if we apply a random restriction to a function $f$ with quantum query complexity $\mathrm{Q}(f)\le n^{1/3}$, the restricted function becomes exponentially close (in terms of $d$) to a depth-$d$ decision tree. Our switching lemma works even in a "worst-case" sense, in that only the indices to be restricted are random; the values they are restricted to are chosen adversarially. Moreover, the switching lemma also works for polynomial degree in place of quantum query complexity.

Authors: Halley Fritze, Sushovan Majhi, Marissa Masden, Atish Mitra, Michael Stickney

Filamentary structures (topologically embedded graphs with a metric structure) are ubiquitous in science and engineering. A challenging problem in topological data analysis (TDA) is to reconstruct the topology and geometry of such an underlying (usually unknown) metric graph from possibly noisy data sampled around it. Reeb graphs have recently been successfully employed in abstract metric graph reconstruction under Gromov$\unicode{x2013}$Hausdorff noise: the sample is assumed to be metrically close to the ground truth. However, such a strong global density assumption is hardly achieved in applications, making the existing Reeb graph-based methods untractible. We relax the density assumption to give provable geometric reconstruction schemes, even when the sample is metrically close only locally. A very different yet more relevant paradigm focuses on the reconstruction of metric graphs$\unicode{x2014}$embedded in the Euclidean space$\unicode{x2014}$from Euclidean samples that are only Hausdorff-close. We further extend our methodologies to provide novel, provable guarantees for the successful geometric reconstruction of Euclidean graphs under the Hausdorff noise model. Our technique produces promising results in reconstructing earthquake plate tectonic boundaries from the global earthquake catalog.

Authors: Sam Hiken, Nicole Wein

We study the token swapping problem, in which we are given a graph with an initial assignment of one distinct token to each vertex, and a final desired assignment (again with one token per vertex). The goal is to find the minimum length sequence of swaps of adjacent tokens required to get from the initial to final assignment. The token swapping problem is known to be NP-complete. It is also known to have a polynomial-time 4-approximation algorithm. From the hardness-of-approximation side, it is known to be NP-hard to approximate with ratio better than 1001/1000. Our main result is an improvement of the approximation ratio of the lower bound: We show that it is NP-hard to approximate with ratio better than 14/13. We then turn our attention to the 0/1-weighted version, in which every token has a weight of either 0 or 1, and the cost of a swap is the sum of the weights of the two participating tokens. Unlike standard token swapping, no constant-factor approximation is known for this version, and we provide an explanation. We prove that 0/1-weighted token swapping is NP-hard to approximate with ratio better than $(1-\varepsilon) \ln(n)$ for any constant $\epsilon>0$. Lastly, we prove two barrier results for the standard (unweighted) token swapping problem. We show that one cannot beat the current best known approximation ratio of 4 using a large class of algorithms which includes all known algorithms, nor can one beat it using a common analysis framework.

Authors: Mohsen Ghaffari, Christoph Grunau

A recent work by Christiansen, Nowicki, and Rotenberg provides dynamic algorithms for coloring sparse graphs, concretely as a function of the arboricity alpha of the input graph. They give two randomized algorithms: O({alpha} log {alpha}) implicit coloring in poly(log n) worst-case update and query times, and O(min{{alpha} log {alpha}, {alpha} log log log n}) implicit coloring in poly(log n) amortized update and query times (against an oblivious adversary). We improve these results in terms of the number of colors and the time guarantee: First, we present an extremely simple algorithm that computes an O({alpha})-implicit coloring with poly(log n) amortized update and query times. Second, and as the main technical contribution of our work, we show that the time complexity guarantee can be strengthened from amortized to worst-case. That is, we give a dynamic algorithm for implicit O({alpha})-coloring with poly(log n) worst-case update and query times (against an oblivious adversary).

Authors: Mohsen Ghaffari, Christoph Grunau

This paper improves and in two cases nearly settles, up to logarithmically lower-order factors, the deterministic complexity of some of the most central problems in distributed graph algorithms, which have been studied for over three decades: Near-Optimal Network Decomposition: We present a deterministic distributed algorithm that computes a network decomposition in approximately O(log^2 n) rounds, with O(log n) diameter and O(log n) colors. This round complexity is near-optimal in the following sense: even given an ideal network decomposition, using it (in the standard way) requires round complexity equal to the product of diameter and number of colors, which is known to be approximately Omega(log^2 n). This near-optimality is remarkable, considering the rarity of optimal deterministic distributed algorithms and that for network decomposition, the first polylogarithmic-round algorithm was achieved only recently, by Rozhon and Ghaffari [STOC 2020], after three decades. Near-Optimal Ruling Set: We present a deterministic distributed algorithm that computes an O(log log n) ruling set in approximately O(log n) rounds. This is an exponential improvement over the O(log n) ruling set of Awerbuch, Goldberg, Luby, and Plotkin [FOCS 1989], while almost matching their O(log n) round complexity. Our result's round complexity nearly matches the approximately Omega(log n) lower bound established by Balliu, Brandt, Kuhn, and Olivetti [STOC 2022], which applies to any poly(log log n) ruling set. Improved Maximal Independent Set (MIS): We present a deterministic distributed algorithm for computing an MIS in approximately O(log^(5/3) n) rounds. This improves upon the approximately O(log^2 n) complexity achieved by Ghaffari and Grunau [STOC 2023] and breaks the log-squared barrier necessary for any method based on network decomposition.

Authors: Yu Chen, Zihan Tan

We study the following distance realization problem. Given a quasi-metric $D$ on a set $T$ of terminals, does there exist a directed Okamura-Seymour graph that realizes $D$ as the (directed) shortest-path distance metric on $T$? We show that, if we are further given the circular ordering of terminals lying on the boundary, then Monge property is a sufficient and necessary condition. This generalizes previous results for undirected Okamura-Seymour instances. With the circular ordering, we give a greedy algorithm for constructing a directed Okamura-Seymour instance that realizes the input quasi-metric. The algorithm takes the dual perspective concerning flows and routings, and is based on a new way of analyzing graph structures, by viewing graphs as \emph{paths and their intersections}. We believe this new understanding is of independent interest and will prove useful in other problems in graph theory and graph algorithms. We also design an efficient algorithm for finding such a circular ordering that makes $D$ satisfy Monge property, if one exists. Combined with our result above, this gives an efficient algorithm for the distance realization problem.

Authors: Ajitesh Srivastava, Shang-Hua Teng

Given a network with an ongoing epidemic, the network immunization problem seeks to identify a fixed number of nodes to immunize in order to maximize the number of infections prevented. One of the fundamental computational challenges in network immunization is that the objective function is generally neither submodular nor supermodular. As a result, no efficient algorithm is known to consistently find a solution with a constant approximation guarantee. Traditionally, this problem is addressed using proxy objectives, which offer better approximation properties. However, converting to these indirect optimizations often introduces losses in effectiveness. In this paper, we overcome these fundamental barriers by utilizing the underlying stochastic structures of the diffusion process. Similar to the traditional influence objective, the immunization objective is an expectation that can be expressed as the sum of objectives over deterministic instances. However, unlike the former, some of these terms are not submodular. The key step is proving that this sum has a bounded deviation from submodularity, thereby enabling the greedy algorithm to achieve constant factor approximation. We show that this approximation still stands considering a variety of immunization settings and spread models.

Authors: MohammadTaghi Hajiaghayi, Shayan Chashm Jahan, Mohammad Sharifi, Suho Shin, Max Springer

The online bipartite matching problem, extensively studied in the literature, deals with the allocation of online arriving vertices (items) to a predetermined set of offline vertices (agents). However, little attention has been given to the concept of class fairness, where agents are categorized into different classes, and the matching algorithm must ensure equitable distribution across these classes. We here focus on randomized algorithms for the fair matching of indivisible items, subject to various definitions of fairness. Our main contribution is the first (randomized) non-wasteful algorithm that simultaneously achieves a $1/2$ approximation to class envy-freeness (CEF) while simultaneously ensuring an equivalent approximation to the class proportionality (CPROP) and utilitarian social welfare (USW) objectives. We supplement this result by demonstrating that no non-wasteful algorithm can achieve an $\alpha$-CEF guarantee for $\alpha > 0.761$. In a similar vein, we provide a novel input instance for deterministic divisible matching that demonstrates a nearly tight CEF approximation. Lastly, we define the ``price of fairness,'' which represents the trade-off between optimal and fair matching. We demonstrate that increasing the level of fairness in the approximation of the solution leads to a decrease in the objective of maximizing USW, following an inverse proportionality relationship.

Authors: Daniel Salwasser, Daniel Seemaier, Lars Gottesbüren, Peter Sanders

We present TeraPart, a memory-efficient multilevel graph partitioning method that is designed to scale to extremely large graphs. In balanced graph partitioning, the goal is to divide the vertices into $k$ blocks with balanced size while cutting as few edges as possible. Due to its NP-hard nature, heuristics are prevalent in this field, with the multilevel framework as the state-of-the-art method. Recent work has seen tremendous progress in speeding up partitioning algorithms through parallelism. The current obstacle in scaling to larger graphs is the high memory usage due to auxiliary data structures and storing the graph itself in memory. In this paper, we present and study several optimizations to significantly reduce their memory footprint. We devise parallel label propagation clustering and graph contraction algorithms that use $O(n)$ auxiliary space instead of $O(np)$, where $p$ is the number of processors. Moreover, we employ an existing compressed graph representation that enables iterating over a neighborhood by on-the-fly decoding at speeds close to the uncompressed graph. Combining these optimizations yields up to a 16-fold reduction in peak memory, while retaining the same solution quality and similar speed. This configuration can partition a graph with one trillion edges in under 8 minutes \emph{on a single machine} using around 900\,GiB of RAM. This is the first work to employ the multilevel framework at this scale, which is vital to achieving low edge cuts. Moreover, our distributed memory implementation handles graphs of up to 16 trillion edges on 128 machines with 256\,GiB each in just under 10 minutes. Finally, we present a version of shared-memory parallel FM local search that uses $O(m)$ space instead of $O(nk)$, reducing peak memory by factor 5.8 on medium-sized graphs without affecting running time.

Authors: Aditya Anand, Euiwoong Lee, Amatya Sharma

Given a fixed arity $k \geq 2$, Min-$k$-CSP on complete instances involves a set of $n$ variables $V$ and one nontrivial constraint for every $k$-subset of variables (so there are $\binom{n}{k}$ constraints). The goal is to find an assignment that minimizes unsatisfied constraints. Unlike Max-$k$-CSP that admits a PTAS on dense or expanding instances, the approximability of Min-$k$-CSP is less understood. For some CSPs like Min-$k$-SAT, there's an approximation-preserving reduction from general to dense instances, making complete instances unique for potential new techniques. This paper initiates a study of Min-$k$-CSPs on complete instances. We present an $O(1)$-approximation algorithm for Min-2-SAT on complete instances, the minimization version of Max-2-SAT. Since $O(1)$-approximation on dense or expanding instances refutes the Unique Games Conjecture, it shows a strict separation between complete and dense/expanding instances. Then we study the decision versions of CSPs, aiming to satisfy all constraints; which is necessary for any nontrivial approximation. Our second main result is a quasi-polynomial time algorithm for every Boolean $k$-CSP on complete instances, including $k$-SAT. We provide additional algorithmic and hardness results for CSPs with larger alphabets, characterizing (arity, alphabet size) pairs that admit a quasi-polynomial time algorithm on complete instances.

The CS department at the University of Wisconsin-Madison is hiring in algorithmic fairness, accountability, and transparency, safety, and privacy (all broadly construed), please see the first URL.

The department is broadly hiring in all other areas as well, please see the second URL, including understanding the strengths and limitations of AI, both theoretically and experimentally.

Website: https://academicjobsonline.org/ajo/jobs/28862, https://academicjobsonline.org/ajo?joblist—1930
Email: silwal@cs.wisc.edu

By shacharlovett

 Here are my random thoughts on the election:

1) Here is a list of things I DONT care about

 a) Candidates Gender or Race. The people who say its about time we had a female president might not want to vote for a President Marjorie Taylor Green. (A while back I thought that the first african-american president and/or first female president would be a republican since such a candidates might take some usually-democratic voters into the republican camp. One of many predictions I was wrong about.)

b) Candidates personal lives. Attempts to tie a candidates affairs to their policies never made sense to me.

c) How well the candidate did in school. I care what they know and don't know now, and also if they know what they don't know. (Who was the last president to not have a college degree? I will tell you at the end of this post.)

d) Their religion. There were people who agreed with JFK on policy issues but did not want to vote for him because he was Catholic. I didn't understand it then nor do I understand it now. Biden is Catholic but this rarely comes up. Romney was Mormon and this only came up in the Republican primary, not in the general.  So I am glad it is no longer an issue. Having said that, we still haven't had a Jewish president, a Muslim President, or an Atheist president. 

e) Do I care if the candidate X will benefit me personally? It is very hard to tell that. Someone like Elon Musk is clearly going to support Kamala since she believes global warming is true and the e-cars will be a part of dealing with it. This is an example of someone supporting someone since it benefits them personally. Oh, bad example.

 Vance thinks people vote this way as he recently said that women past child-bearing age should not care about abortion rights.

f) There are ads that say things like I served in the military defending our country, and now I want to defined your rights to XXX. I don't see how serving in the military makes them a better senator or whatever. 

g) I don't care how they are doing at polls. Some of the articles saying that candidate X is ahead  also tend to say that that shows X  is better. I campaigned for George McGovern in 1972 and he went on to lose by a lot.  Some of my friends told me that I backed a loser and tried to make that an insult (I have better friends now). This puzzled me then since the fact that my candidate lost says NOTHING about how he would do as president.

2) DO I care about if they lie? Depends on how much and about what. That Vance changes his mind about Trump (he was anti-Trump in 2016) or that Kamala changed her mind on fracking are the standard lies that politicians always tell so I don't care about that. This may be a reflection on the low standards we have. More serious are lies that they KNOW are false and might ENDANGER people.

3) DO I care if they changed their mind on an issue. All I care about is how they feel NOW, though if they changed their mind I might not believe them.

4) I  DO care about policy and ability to get things done and to consider all sides of an issue. (I won't say what policies I like since I am trying to keep this post non-partisan).

5) Some of the attacks on Kamala have been a women should not be president. This puzzles me since there will come a time when the Republicans have a female candidate.

6) I am surprised there is anyone who is still undecided. We know both candidates  VERY WELL. What more information do you need?

7) Articles like Five Reasons Kamala Will Win or Five Reasons Trump Will Win are usually crap. For example, one of the reasons Kamala will win is People are tired of  Trump's corruption. But that just means that the author of the article is tired of it, and the author does not speak for the American people. An argument like Kamala is ahead in 5 of the 7 swing states (if it were true) is the kind of argument I want to see. More to the point- an argument that someone will win should not be partisan.

8) Since JD Vance might lose Trump some votes (actually I doubt that) I have heard the old argument that Sarah Palin cost McCain the Presidency, or at least cost him some votes. I began to think do we really know that? so I looked at some articles both new and old about this. I found things like:

The American public did not want Sarah Palin a heartbeat away from the presidency because of her views, or because of her perceived lack of intelligence or blah blah. Hence she cost McCain votes.

NONE of the articles I read pointed to polls or other EVIDENCE for this point of view.

There probably is some evidence on the issue (I do not know which way it would go)  somewhere but the LACK of any INTEREST in it bothers me.

9) I am surprised there are any undecided voters at this point. Both candidates are known to the public, so I don't see what more there is to think about. I accidentally already said this, however (a) I don't want to mess up my numbering and (ii) I do feel strongly about this point, so its worth having twice.

10) Because of Americas only-2-party-system you end up voting for people you agree with on some things but not others. I can imagine Mike Pence saying:

I prefer Trump to Kamala on the abortion issue.

I prefer Kamala to Trump on the  Hang Mike Pence issue.

Gee, who do I vote for?

 Actually he has said he is voting for neither one. 

11) IF Kamala wins then the decision to make Tim Walz her VP will be seen as genius.

      IF Kamala does not win Pennsylvania and loses the election then NOT picking Josh Shapiro (popular governor of PA) will be seen as stupid.

I call bullshit on both of those. There are SO MANY factors  at play here. This reminds me of when a basketball team wins 100-99 and the sportscasters are saying things like

The decision to concentrate on 3-point shots was genius!

12) More generally, after-the-fact pundits all have their own theories about why candidate X won, even those who were confident that candidate Y was going to win, and those theories are either partisan or just uninformed. It is hard to know what works, even after the fact.

13) I had a post, here, about breaking the record for number-of-living-ex-presidents.  I speculated that  if

a) Biden won in 2020 and lost in 2024 (I overlooked the option of his not running.)

b) Carter lives to see the winner of the 2024 election inaugurated

THEN we would have SIX living ex-presidents, which would break the record. They would be 

Carter, Clinton, Bush Jr, Obama, Trump, Biden.

If Trump wins then should Trump count? I think so- he would be a president AND an ex-president. If Kamala wins I won't have that issue. When I wrote that I didn't think Carter would last this long (he is 100), but he may very well. In fact, he has already voted!

14) Allan Lichtman is an American Historian (does that mean he studies American History or that he is American AND a historian?) who has a system to predict who will win the presidential election that has been correct 9 out of the last 10 elections. See here for his system. He predicts Kamala. I personally do not put to much stock in that since its going to be VERY CLOSE (hmmm- that's my prediction, and I could be wrong). While he is a democrat his system is OBJECTIVE-- he would have to be to be right so often. Even so, he is getting hate mail. This makes no sense. Predicting that X will happen does not mean you have an opinion about if X is good or bad. 

15) When people argue passionately about a rules change (e.g., get rid of the electoral college) I do not believe them- they would argue the other way if the current rules favored their candidate. 

16) JD Vance recently came out against the laws that say you can't wear political stuff at the polling place. He said that BOTH Kamala supporters and Trump supporters should be allowed to wear political T-shirts and hats and  what not at the polling place. NO HE DIDN"T. He applauded a Trump Supporter for calling a Poll Worker a XXX and told him to YYY in for asking her to follow the polling place's rules prohibiting political merchandise. See here. (I use XXX and YYY so that this post won't get censored as happened in the past, see here. Oddly enough, this morning the ban was lifted, so for the original post that was banned see here.)  No word yet on if he is going to praise a Texas man for punching a poll worker who told him to remove his Trump hat, see here.

The last president who did not have a college degree was Harry Truman.

By gasarch

A natural model of a source of randomness consists of a long stream of symbols $X = X_1\circ\ldots\circ X_t$, with some guarantee on the entropy of $X_i$ conditioned on the outcome of the prefix $x_1,\dots,x_{i-1}$. We study unpredictable sources, a generalization of the almost Chor--Goldreich (CG) sources considered in [DMOZ23]. In an unpredictable source $X$, for a typical draw of $x\sim X$, for most $i$, $x_i$ has a low probability of occurring given $x_1,\dots,x_{i-1}$. Such a model relaxes the unrealistic assumption of a CG source that for every $i$, and every $x_1,\dots,x_{i-1}$, the next symbol $X_i$ has sufficiently large entropy. Unpredictable sources subsume all previously considered notions of almost CG sources, including those for which it was unknown whether random walks using $X$ mix, and including those that are equivalent to general sources with high min entropy. We prove that random walks using unpredictable sources do mix, and as a result obtain seeded online condensers with constant entropy gap, and (seedless) deterministic condensers outputting a constant fraction of the entropy. In particular, our condensers run in space comparable to the total entropy of the stream $X$, even when its length is not known ahead of time. As another corollary, we obtain a new extractor based on expander random walks handling lower entropy than the classic expander based construction relying on spectral techniques [Gil98]. As our main technical tool, we provide a novel analysis covering a key case of adversarial random walks on lossless expanders that [DMOZ23] fails to address. As part of the analysis, we provide a ``chain rule for vertex probabilities''. The standard chain rule states that for every $x \sim X$ and $i$, $\Pr(x_1,\dots,x_i)= \Pr[X_i = x_i|X_{[1,i-1]}=x_1,\dots,x_{i-1}] \cdot \Pr(x_1,\dots,x_{i-1})$. If $W(x_1,\dots,x_i)$ is the vertex reached using $x_1,\dots,x_i$, then the chain rule for vertex probabilities essentially states that the same phenomena occurs for a typical $x$: \[\Pr [V_i = W(x_1,\dots,x_i)] \leq \Pr[X_i = x_i|X_{[1,i-1]}=x_1,\dots,x_{i-1}] \cdot \Pr[V_{i-1} = W(x_1,\dots,x_{i-1})],\] where $V_i$ is the vertex distribution of the random walk at step $i$ using $X$.

Kyle Cranmer wrote a thorough, detailed response to my Higgs polemic, and I strongly encourage you to read the whole thing. I agree with almost every point he raises.1

Kyle is far more gracious in his post than he needed to be. My post was over the top. If you are a regular reader, you know I try to be playful and polemical in my writing. Part of what makes my writing fun for me and the people who engage with me is my habitual line stepping. Sometimes, playful writing leads to imprecision, and I’m fine with that. There is a delicate trade-off between reach and precision in scientific writing that all science writers balance.

My main point was that the Higgs discovery doesn’t provide a good defense of statistical testing. Kyle and I disagree here, and that’s fine. But note that I was not pulling my critique out of thin air. There was disagreement among the physics community at the time and the previous post links to some of the relevant debate on the subject. However, I definitely have a tendency to go overboard. There are two parts I’d change if I were allowed a revision. 

First, the term “Majority vote.” When I wrote that the participatory decision making in the CERN collaboration was done by majority voting, I didn’t mean this literally. However, there is nothing in the text around the phrase to see that I was exaggerating for emphasis. I apologize for taking poetic license here, as this is a place where I should have been precise. As Kyle points out, the governance structures at CERN are consensus-based and very intricate. The point I was hoping to raise with this passage is that science through complex governance systems is itself kind of weird! These large collaborations are a late 20th century phenomenon and are aberrational in the extended history of modern science. I am deeply interested in the structures you put in place to build deliberative governance structures to make proclamations about scientific results. 

The statistical rules were set, as Kyle says, by consensus. They were part of the governance structure. The fact that these rules, which people not named me can debate the validity of, helped 3000+ people reach a consensus is striking. The compelling evidence of the Higgs is the consensus, not the statistics.

The second part that I would delete not because I disagree with it but because it completely detracts from the argument. In describing how the Higgs Boson fails Ian Hacking’s sprayability criterion, I wrote

“The Higgs field has no bearing on any physics at any scale anyone would ever care about. So I don’t care either way if physicists think they found a Higgs. It has zero bearing on my existence.“

I mean, I agree with this, but why should anyone care whether I care? This isn’t a good argument. What I should have said is that it’s not enough to keep banging the same protons together to get further confirmation beyond 20 or 30 𝜎 or whatever. At some point, the confirmation need come from other experimental evidence. For instance, a lot of people raised objections to the statistics used in LIGO’s gravitational wave interferometry. However, their GW170817 event provided auxiliary confirmation. The LIGO interferometer detected a gravitational wave event, triangulated a region in the sky where they thought it came from, and international telescopes confirmed colliding neutron stars in that location. At some point I’m sure we’ll get a similar new means of seeing the Higgs, but we don’t have it yet.

I’d recommend a couple of other rejoinders to the debate. I agree with all of what David Chapman says in this note about the complexity of discovery. Rex Douglass, who tends to be even spicier than me, raises more points about why frequentist tests are not good summaries of experiments with any degree of complexity.

OK, but what about the title? I always overestimate the accessibility of the cutesy references I make in titling posts.2 This one referred to an over-the-top but deeply prescient polemic by Jean Baudrillard “The Gulf War Did Not Take Place.” Baudrillard’s point was never to deny that the violence and death didn’t happen but to describe the multiple levels of mediation on the battlefield and in news propaganda that created a baffling hyperreality where it was impossible to distinguish a presented war from a human rights atrocity. It’s heavy French postmodern stuff, but Baudriallardian hyperreality is evermore present in our social media-driven world. It’s interesting that, despite spending the majority of their lives in a hellish online hyperreality, the number of twitter users who are aware of Baudriallard’s work is near zero.

I don’t think the title is a perfect fit for the Higgs discovery, but what makes contemporary fundamental physics so baffling to everyone (as Kyle admits, physicists included!) is how mediated the highly subatomic is from actionable reality. We’re probing things that we can only know exist through the most complicated, expensive, and specific experiments we’ve ever devised. Kyle’s point, which again I fumbled in an attempt to be provocative and literary, is that establishing that something is happening at such scales requires excessive amounts of deeply human regulatory structures. When you call it bureaucracy, it touches a nerve. No one wants to admit they like bureaucracy. But we could chalk up the Higgs as evidence that bureaucracy is necessary for certain endeavors.

In any event, I use irreverence (i.e., shitposting) to engage with tricky philosophical questions. I know that people unfamiliar with my schtick might read me as just being an asshole.3 That’s fair. One good thing that came out of this post is many readers’ thoughtful and generous engagement with an argument I’m still workshopping. I don’t consider this blog to be the last word on anything, and the conversation is part of what I value about it. Another good thing that came out of the twitter hate was science writer Dan Garisto calling me “a smugly incurious Latour for tech bros.” I need to add that line to my bio. 

Subscribe now

By Ben Recht

Authors: Yuxuan Yu, Yuzhuo Fang, Hua Tong, Yongjie Jessica Zhang

In this paper, we present a novel algorithm that integrates deep learning with the polycube method (DL-Polycube) to generate high-quality hexahedral (hex) meshes, which are then used to construct volumetric splines for isogeometric analysis. Our DL-Polycube algorithm begins by establishing a connection between surface triangular meshes and polycube structures. We employ deep neural network to classify surface triangular meshes into their corresponding polycube structures. Following this, we combine the acquired polycube structural information with unsupervised learning to perform surface segmentation of triangular meshes. This step addresses the issue of segmentation not corresponding to a polycube while reducing manual intervention. Quality hex meshes are then generated from the polycube structures, with employing octree subdivision, parametric mapping and quality improvement techniques. The incorporation of deep learning for creating polycube structures, combined with unsupervised learning for segmentation of surface triangular meshes, substantially accelerates hex mesh generation. Finally, truncated hierarchical B-splines are constructed on the generated hex meshes. We extract trivariate B\'ezier elements from these splines and apply them directly in isogeometric analysis. We offer several examples to demonstrate the robustness of our DL-Polycube algorithm.

Authors: Juan Juan Gerardo Alcázar, Carlos Hermoso, Hüsnü Anıl Çoban, Uğur Gözütok

In this paper we provide, first, a general symbolic algorithm for computing the symmetries of a given rational surface, based on the classical differential invariants of surfaces, i.e. Gauss curvature and mean curvature. In practice, the algorithm works well for sparse parametrizations (e.g. toric surfaces) and PN surfaces. Additionally, we provide a specific, also symbolic algorithm for computing the symmetries of ruled surfaces; this algorithm works extremely well in practice, since the problem is reduced to that of rational space curves, which can be efficiently solved by using existing methods. The algorithm for ruled surfaces is based on the fact, proven in the paper, that every symmetry of a rational surface must also be a symmetry of its line of striction, which is a rational space curve. The algorithms have been implemented in the computer algebra system Maple, and the implementations have been made public; evidence of their performance is given in the paper.

Authors: Marius Costandin

For $S \in \mathbb{N}^n$ and $T \in \mathbb{N}$, the Subset Sum Problem (SSP) $\exists^? x \in \{0,1\}^n $ such that $S^T\cdot x = T$ can be interpreted as the problem of deciding whether the intersection of the positive unit hypercube $Q_n = [0,1]^n$ with the hyperplane $S^T\cdot \left(x - \frac{S}{\|S\|^2 }\cdot T \right) = 0$ contains at least a vertex. In this paper, we give an algorithm of complexity $\mathcal{O}\left( \frac{1}{\epsilon}\cdot n^b \right)$, for some absolute constant $b$, which either proves that there are no vertices in a slab of thickness $\epsilon$ either finds a vertex in the slab of thickness $4\cdot \epsilon$. It is shown that any vertex $P$ in a slab of thickness $\epsilon$ meets $\left| \frac{S^T\cdot P}{T} - 1 \right| \leq \epsilon$, therefore making the proposed algorithm a FPTAS for the SSP.

Authors: Bodo Manthey, Jesse van Rhijn

We show that the problem of counting the number of 2-optimal tours in instances of the Travelling Salesperson Problem (TSP) on complete graphs is #P-complete. In addition, we show that the expected number of 2-optimal tours in random instances of the TSP on complete graphs is $O(1.2098^n \sqrt{n!})$. Based on numerical experiments, we conjecture that the true bound is at most $O(\sqrt{n!})$, which is approximately the square root of the total number of tours.

Authors: Aaron Bernstein, Jiale Chen, Aditi Dudeja, Zachary Langley, Aaron Sidford, Ta-Wei Tu

We consider the foundational problem of maintaining a $(1-\varepsilon)$-approximate maximum weight matching (MWM) in an $n$-node dynamic graph undergoing edge insertions and deletions. We provide a general reduction that reduces the problem on graphs with a weight range of $\mathrm{poly}(n)$ to $\mathrm{poly}(1/\varepsilon)$ at the cost of just an additive $\mathrm{poly}(1/\varepsilon)$ in update time. This improves upon the prior reduction of Gupta-Peng (FOCS 2013) which reduces the problem to a weight range of $\varepsilon^{-O(1/\varepsilon)}$ with a multiplicative cost of $O(\log n)$. When combined with a reduction of Bernstein-Dudeja-Langley (STOC 2021) this yields a reduction from dynamic $(1-\varepsilon)$-approximate MWM in bipartite graphs with a weight range of $\mathrm{poly}(n)$ to dynamic $(1-\varepsilon)$-approximate maximum cardinality matching in bipartite graphs at the cost of a multiplicative $\mathrm{poly}(1/\varepsilon)$ in update time, thereby resolving an open problem in [GP'13; BDL'21]. Additionally, we show that our approach is amenable to MWM problems in streaming, shared-memory work-depth, and massively parallel computation models. We also apply our techniques to obtain an efficient dynamic algorithm for rounding weighted fractional matchings in general graphs. Underlying our framework is a new structural result about MWM that we call the "matching composition lemma" and new dynamic matching subroutines that may be of independent interest.