Theory of Computing Report

Today’s post is by my co-instructor Deb Raji, in which she shares her reflections on our graduate class on machine learning. Deb and I both violently agreed and disagreed throughout the semester, and that’s part of what made the class so fun to teach. I’m excited to share her perspectives here on argmin. You can follow Deb on Twitter and Bluesky.

“Machine learning evaluation” is usually relegated to the last lecture of any Intro to Machine Learning course—a longstanding afterthought of the field, unfairly pushed to the back corners of the minds of students, researchers and practitioners alike. On its surface, machine learning evaluation should be simple. We have expectations of what a model can do, and we should be able to straightforwardly measure what it is that the model actually does -- the discrepancy should be as simple as running the model on a hold out set and comparing its predictions to ground truth.

Despite the imperfection of our first attempt, I like that our class immediately tried to open up the Pandora’s box of this topic and properly engage with its complexity. We didn’t run away or pretend to understand something that the field has been avoiding almost since its inception. And I believe we were rewarded for that. Within just a couple weeks of inquiry, it became immediately clear that machine learning evaluation was not as simple as we’d like to think.

The first breakdown happened with our foray into the formal assumptions of the hold out method, the central dogma of evaluating supervised learning models. Take an adequate sample of in-distribution data and keep it secret. Compare your model’s predictions on this data to some ground truth expectation of what the outcome or label should be -- the degree of overlap between the predictions and ground truth in your test set is your evaluation. This is the statistical rationale behind every benchmark, and we walked through the nice generalization claims that follow from that rationale. But then we started walking through actual examples -- wait, how many test sets are actually kept secret? What does it mean for a benchmark to be representative? How big are these samples - are they big enough for any of the generalization claims to even hold?

Soon enough, we were learning new terminology to describe these assumption violations: benchmark bias, data contamination, statistical power. Some of the discrepancies were just strange signs of the times -- for instance, for large language model evaluation, we don’t even sample our test and train data from the same distribution anymore, violating a foundational assumption of the hold out method. Even when a training set is provided (as it is for benchmarks like GLUE, SuperGLUE and ARC-AGl), people train on whatever they want and then at most fine tune on that training set to orient the task before evaluation on the test set. This wasn’t the case with past benchmarks like ImageNet, and this doesn’t align with the historical statistical assumption of benchmark evaluations for predictions. We keep holding on to the hold out method as if it means something, but there’s no reason we should expect the same kind of statistical guarantees with this new approach to evaluation -- it’s clear that for modern benchmarks, the old rules don’t apply.

This led us very quickly down the garden path of alternative views on “benchmarking” and the new crop of efforts tentatively exploring what lay beyond the default benchmarking paradigm. Despite clear deviations from the statistical assumptions of the hold out method, we concluded that benchmarks are still good for something, and are, in many cases, still consistently reliable proxies for algorithm selection and ranking. They also don’t fall short of exposing functional blind spots, and regularly reveal model capabilities that surprise us. At the same time, though, they are clearly not enough - it was fun to explore how Human-AI interaction lab studies, randomized experiments, compilable unit tests, online evaluations and other attempts in the field to explore outside the paradigm were providing another layer of insight into how these models behave, especially in deployment. If anything, I wish we had spent more time looking beyond the benchmarking paradigm and exploring what those alternative evaluation approaches had to offer.

Another major theme of the course that I wish we had more time to dig into was validity. It took us perhaps too long to properly convey to the class what validity and reliability were about and to break down the pretty unfamiliar concepts on internal, external and construct validity. These are concepts traditionally brought up in the context of experimental evaluations -- internal validity is about how much you can trust your experimental results; external validity about the generalizability of these experimental results; and construct validity oriented about how well you operationalized and designed the experiment relative to the real world problem you meant to evaluate for. The crude mapping of these concepts to the machine learning context - is internal validity “all the stuff you need to do to impress reviewer 2”? Is external validity about generalization to another benchmark or generalization to a real world setting? How do we even begin to think about construct validity for a “general purpose” model? This discussion lasted for about three classes, and I don’t even think we came close to a satisfying resolution.

There were certainly parts of the course I’d revisit completely -- it took a couple of classes to make progress on a coherent discussion on uncertainty; the detour into scoring rules, calibration and forecasting felt a bit disconnected. But even with some of these kinks, we pretty much always had a productive discussion, in no large part due to the remarkable engagement of our students. When designing it, we had no idea who would want to take this class (I feared no one would!), but we were pleasantly surprised by the strong enthusiasm and a fairly long waiting list. In the end, we were able to compose a class that was purposefully disciplinarily diverse. It included people working on robotics, NLP, vision; in ML application areas that included energy, healthcare, chemistry, computational biology, economics and more. We even had a few folks coming in from statistics and CS theory. It was just a radically fun space to be in, and I appreciate their contributions to the class the most. On one hand it made teaching challenging -- in one class on uncertainty, I could tell all the engineering and robotics people were bored of the discussion on uncertainty propagation, while some of the class had never heard of it; meanwhile, that same group struggled to grok confidence intervals, a topic the statistics students had long mastered. It was clear within a few months that the prerequisite knowledge was unevenly distributed, and this undoubtedly made things more difficult. But on the other hand, we learned so much from the discipline-specific experiences and perspectives shared on the topic -- from the over-reliance on demos in robotics to how computer vision’s ImageNet shaped the field and the NLP view on vibe-based evaluation. I often felt that the students could teach themselves, and that things were most informative for all of us when Ben and I got out of the way and let the conversation linger.

I like how we ended the class, which was an acknowledgement of something that I don’t even know if we fully grasped when getting into this: how we evaluate machine learning has far-reaching consequences. It’s not just leverage in competitive testing and algorithm ranking in papers or marketing materials—it’s also a barometer for market entry and procurement, with measurements used in litigation, policyaking, post-deployment monitoring, and audits of product safety. Throughout the class, it became clear that the severity of the problems we considered was a function of the stakes of measurement. When intense precision and validity were required, the measurement challenge grew exponentially.

By the time the course was winding down, I felt, like Ben, that we had more questions than answers. And why not? We had opened up Pandora’s box, we had shaken up the hornet’s nest, and these were the consequences. But ultimately, I’m grateful - I have long felt unsatisfied with the state of machine learning evaluation, and I now feel vindicated in my concern. Through the (often historical) readings and deep interdisciplinary discussions with the class, it became clear that I was far from alone. Almost since the beginning of the machine learning field, we have struggled with establishing a more principled approach to evaluation. Long before the chaos of large language models, we had felt this sore spot and ignored it. Now feels like a perfect time to dig in and finally figure things out.

Subscribe now

By Deb Raji (@rajiinio)

Authors: Alex Bortolotti, Monaldo Mastrolilli, Luis Felipe Vargas

The Sum-of-Squares (SoS) hierarchy, also known as Lasserre hierarchy, has emerged as a promising tool in optimization. However, it remains unclear whether fixed-degree SoS proofs can be automated [O'Donnell (2017)]. Indeed, there are examples of polynomial systems with bounded coefficients that admit low-degree SoS proofs, but these proofs necessarily involve numbers with an exponential number of bits, implying that low-degree SoS proofs cannot always be found efficiently. A sufficient condition derived from the Nullstellensatz proof system [Raghavendra and Weitz (2017)] identifies cases where bit complexity issues can be circumvented. One of the main problems left open by Raghavendra and Weitz is proving any result for refutations, as their condition applies only to polynomial systems with a large set of solutions. In this work, we broaden the class of polynomial systems for which degree-$d$ SoS proofs can be automated. To achieve this, we develop a new criterion and we demonstrate how our criterion applies to polynomial systems beyond the scope of Raghavendra and Weitz's result. In particular, we establish a separation for instances arising from Constraint Satisfaction Problems (CSPs). Moreover, our result extends to refutations, establishing that polynomial-time refutation is possible for broad classes of polynomial time solvable constraint problems, highlighting a first advancement in this area.

Authors: Yuni Iwamasa, Tomoki Matsuda, Shunya Morihira, Hanna Sumita

In this paper, we present a general framework for efficiently computing diverse solutions to combinatorial optimization problems. Given a problem instance, the goal is to find $k$ solutions that maximize a specified diversity measure; the sum of pairwise Hamming distances or the size of the union of the $k$ solutions. Our framework applies to problems satisfying two structural properties: (i) All solutions are of equal size and (ii) the family of all solutions can be represented by a surjection from the family of ideals of some finite poset. Under these conditions, we show that the problem of computing $k$ diverse solutions can be reduced to the minimum cost flow problem and the maximum $s$-$t$ flow problem. As applications, we demonstrate that both the unweighted minimum $s$-$t$ cut problem and the stable matching problem satisfy the requirements of our framework. By utilizing the recent advances in network flows algorithms, we improve the previously known time complexities of the diverse problems, which were based on submodular function minimization.

Authors: Yaroslav Alekseev, Yuval Filmus, Ian Mertz, Alexander Smal, Antoine Vinciguerra

In a seminal work, Buhrman et al. (STOC 2014) defined the class $CSPACE(s,c)$ of problems solvable in space $s$ with an additional catalytic tape of size $c$, which is a tape whose initial content must be restored at the end of the computation. They showed that uniform $TC^1$ circuits are computable in catalytic logspace, i.e., $CL=CSPACE(O(\log{n}), 2^{O(\log{n})})$, thus giving strong evidence that catalytic space gives $L$ strict additional power. Their study focuses on an arithmetic model called register programs, which has been a focal point in development since then. Understanding $CL$ remains a major open problem, as $TC^1$ remains the most powerful containment to date. In this work, we study the power of catalytic space and register programs to compute circuits of larger depth. Using register programs, we show that for every $\epsilon > 0$, $SAC^2 \subseteq CSPACE\left(O\left(\frac{\log^2{n}}{\log\log{n}}\right), 2^{O(\log^{1+\epsilon} n)}\right)$ This is an $O(\log \log n)$ factor improvement on the free space needed to compute $SAC^2$, which can be accomplished with near-polynomial catalytic space. We also exhibit non-trivial register programs for matrix powering, which is a further step towards showing $NC^2 \subseteq CL$.

Authors: Palash Dey, Ashlesha Hota, Sudeshna Kolay

In the knapsack problems with neighborhood constraints that were studied before, the input is a graph $\mathcal{G}$ on a set $\mathcal{V}$ of items, each item $v \in \mathcal{V}$ has a weight $w_v$ and profit $p_v$, the size $s$ of the knapsack, and the demand $d$. The goal is to compute if there exists a feasible solution whose total weight is at most $s$ and total profit is at most $d$. Here, feasible solutions are all subsets $\mathcal{S}$ of the items such that, for every item in $\mathcal{S}$, at least one of its neighbors in $\mathcal{G}$ is also in $\mathcal{S}$ for \hor, and all its neighbors in $\mathcal{G}$ are also in $\mathcal{S}$ for \hand~\cite{borradaile2012knapsack}. We study a relaxation of the above problems. Specifically, we allow all possible subsets of items to be feasible solutions. However, only those items for which we pick at least one or all of its neighbor (out-neighbor for directed graph) contribute to profit whereas every item picked contribute to the weight; we call the corresponding problems \sor and \sand. We show that both \sor and \sand are strongly \NPC even on undirected graphs. Regarding parameterized complexity, we show both \sor and \hor are \WTH parameterized by the size $s$ of the knapsack size. Interestingly, both \sand and \hand are \WOH parameterized by knapsack size, $s$ plus profit demand, $d$ and also parameterized by solution size, $b$. For \sor and \hor, we present a randomized color-coding-based pseudo-\FPT algorithm, parameterized by the solution size $b$, and consequently by the demand $d$. We then consider the treewidth of the input graph as our parameter and design pseudo fixed-parameter tractable (\FPT) algorithm parameterized by treewidth, $\text{tw}$ for all variants. Finally, we present an additive $1$ approximation for \sor when both the weight and profit of every vertex is $1$.

Authors: Wenqiang Zhou, Zhendong Yu, Xinyu Liu, Jiaming Yang, Rong Xiao, Tao Wang, Chenwei Tang, Jiancheng Lv

Quantization Aware Training (QAT) is a neural network quantization technique that compresses model size and improves operational efficiency while effectively maintaining model performance. The paradigm of QAT is to introduce fake quantization operators during the training process, allowing the model to autonomously compensate for information loss caused by quantization. Making quantization parameters trainable can significantly improve the performance of QAT, but at the cost of compromising the flexibility during inference, especially when dealing with activation values with substantially different distributions. In this paper, we propose an effective learnable adaptive neural network quantization method, called Adaptive Step Size Quantization (ASQ), to resolve this conflict. Specifically, the proposed ASQ method first dynamically adjusts quantization scaling factors through a trained module capable of accommodating different activations. Then, to address the rigid resolution issue inherent in Power of Two (POT) quantization, we propose an efficient non-uniform quantization scheme. We utilize the Power Of Square root of Two (POST) as the basis for exponential quantization, effectively handling the bell-shaped distribution of neural network weights across various bit-widths while maintaining computational efficiency through a Look-Up Table method (LUT). Extensive experimental results demonstrate that the proposed ASQ method is superior to the state-of-the-art QAT approaches. Notably that the ASQ is even competitive compared to full precision baselines, with its 4-bit quantized ResNet34 model improving accuracy by 1.2\% on ImageNet.

Authors: Raheleh Jalali, Ondřej Ježil

We prove the correctness of the AKS algorithm \cite{AKS} within the bounded arithmetic theory $T^{count}_2$ or, equivalently, the first-order consequence of the theory $VTC^0$ expanded by the smash function, which we denote by $VTC^0_2$. Our approach initially demonstrates the correctness within the theory $S^1_2 + iWPHP$ augmented by two algebraic axioms and then show that they are provable in $VTC^0_2$. The two axioms are: a generalized version of Fermat's Little Theorem and an axiom adding a new function symbol which injectively maps roots of polynomials over a definable finite field to numbers bounded by the degree of the given polynomial. To obtain our main result, we also give new formalizations of parts of number theory and algebra: $\bullet$ In $PV_1$: We formalize Legendre's Formula on the prime factorization of $n!$, key properties of the Combinatorial Number System and the existence of cyclotomic polynomials over the finite fields $Z/p$. $\bullet$ In $S^1_2$: We prove the inequality $lcm(1,\dots, 2n) \geq 2^n$. $\bullet$ In $VTC^0$: We verify the correctness of the Kung--Sieveking algorithm for polynomial division.

Authors: Jacobus Conradi, Anne Driemel

Many application areas collect unstructured trajectory data. In subtrajectory clustering, one is interested to find patterns in this data using a hybrid combination of segmentation and clustering. We analyze two variants of this problem based on the well-known \textsc{SetCover} and \textsc{CoverageMaximization} problems. In both variants the set system is induced by metric balls under the Fr\'echet distance centered at polygonal curves. Our algorithms focus on improving the running time of the update step of the generic greedy algorithm by means of a careful combination of sweeps through a candidate space. In the first variant, we are given a polygonal curve $P$ of complexity $n$, distance threshold $\Delta$ and complexity bound $\ell$ and the goal is to identify a minimum-size set of center curves $\mathcal{C}$, where each center curve is of complexity at most $\ell$ and every point $p$ on $P$ is covered. A point $p$ on $P$ is covered if it is part of a subtrajectory $\pi_p$ of $P$ such that there is a center $c\in\mathcal{C}$ whose Fr\'echet distance to $\pi_p$ is at most $\Delta$. We present an approximation algorithm for this problem with a running time of $O((n^2\ell + \sqrt{k_\Delta}n^{5/2})\log^2n)$, where $k_\Delta$ is the size of an optimal solution. The algorithm gives a bicriterial approximation guarantee that relaxes the Fr\'echet distance threshold by a constant factor and the size of the solution by a factor of $O(\log n)$. The second problem variant asks for the maximum fraction of the input curve $P$ that can be covered using $k$ center curves, where $k\leq n$ is a parameter to the algorithm. Here, we show that our techniques lead to an algorithm with a running time of $O((k+\ell)n^2\log^2 n)$ and similar approximation guarantees. Note that in both algorithms $k,k_\Delta\in O(n)$ and hence the running time is cubic, or better if $k\ll n$.

Authors: Ivor van der Hoog, Thijs van der Horst Eva Rotenberg, Lasse Wulf

The Fr\'echet distance is a distance measure between trajectories in the plane or walks in a graph G. Given constant-time shortest path queries in a graph G, the Discrete Fr\'echet distance $F_G(P, Q)$ between two walks P and Q can be computed in $O(|P| \cdot |Q|)$ time using a dynamic program. Driemel, van der Hoog, and Rotenberg [SoCG'22] show that for weighted planar graphs this approach is likely tight, as there can be no strongly subquadratic algorithm to compute a $1.01$-approximation of $F_G(P, Q)$ unless the Orthogonal Vector Hypothesis (OVH) fails. Such quadratic-time conditional lower bounds are common to many Fr\'echet distance variants. However, they can be circumvented by assuming that the input comes from some well-behaved class: There exist $(1+\varepsilon)$-approximations, both in weighted graphs and in Rd, that take near-linear time for $c$-packed or $\kappa$-straight walks in the graph. In Rd, there also exists a near-linear time algorithm to compute the Fr\'echet distance whenever all input edges are long compared to the distance. We consider computing the Fr\'echet distance in unweighted planar graphs. We show that there exist no 1.25-approximations of the discrete Fr\'echet distance between two disjoint simple paths in an unweighted planar graph in strongly subquadratic time, unless OVH fails. This improves the previous lower bound, both in terms of generality and approximation factor. We subsequently show that adding graph structure circumvents this lower bound: If the graph is a regular tiling with unit-weighted edges, then there exists an $\tilde{O}( (|P| + |Q|)^{1.5})$-time algorithm to compute $D_F(P, Q)$. Our result has natural implications in the plane, as it allows us to define a new class of well-behaved curves that facilitate $(1+\varepsilon)$-approximations of their discrete Fr\'echet distance in subquadratic time.

Authors: Jack Spalding-Jamieson, Anurag Murty Naredla

Given two points in the plane, and a set of "obstacles" given as curves through the plane with assigned weights, we consider the point-separation problem, which asks for the minimum-weight subset of the obstacles separating the two points. A few computational models for this problem have been previously studied. We give a unified approach to this problem in all models via a reduction to a particular shortest-path problem, and obtain improved running times in essentially all cases. In addition, we also give fine-grained lower bounds for many cases.

Authors: Amir Carmel, Debarati Das, Evangelos Kipouridis, Evangelos Pipis

Fitting distances to tree metrics and ultrametrics are two widely used methods in hierarchical clustering, primarily explored within the context of numerical taxonomy. Given a positive distance function $D:\binom{V}{2}\rightarrow\mathbb{R}_{>0}$, the goal is to find a tree (or ultrametric) $T$ including all elements of set $V$ such that the difference between the distances among vertices in $T$ and those specified by $D$ is minimized. In this paper, we initiate the study of ultrametric and tree metric fitting problems in the semi-streaming model, where the distances between pairs of elements from $V$ (with $|V|=n$), defined by the function $D$, can arrive in an arbitrary order. We study these problems under various distance norms: For the $\ell_0$ objective, we provide a single-pass polynomial-time $\tilde{O}(n)$-space $O(1)$ approximation algorithm for ultrametrics and prove that no single-pass exact algorithm exists, even with exponential time. Next, we show that the algorithm for $\ell_0$ implies an $O(\Delta/\delta)$ approximation for the $\ell_1$ objective, where $\Delta$ is the maximum and $\delta$ is the minimum absolute difference between distances in the input. This bound matches the best-known approximation for the RAM model using a combinatorial algorithm when $\Delta/\delta=O(n)$. For the $\ell_\infty$ objective, we provide a complete characterization of the ultrametric fitting problem. We present a single-pass polynomial-time $\tilde{O}(n)$-space 2-approximation algorithm and show that no better than 2-approximation is possible, even with exponential time. We also show that, with an additional pass, it is possible to achieve a polynomial-time exact algorithm for ultrametrics. Finally, we extend the results for all these objectives to tree metrics by using only one additional pass through the stream and without asymptotically increasing the approximation factor.

Authors: Arnaud Casteigts, Michelle Döring, Nils Morawietz

Given an undirected graph $G$, the problem of deciding whether $G$ admits a simple and proper time-labeling that makes it temporally connected is known to be NP-hard (G\"obel et al., 1991). In this article, we relax this problem and ask whether a given degree sequence can be realized as a temporally connected graph. Our main results are a complete characterization of the feasible cases, and a recognition algorithm that runs in $O(n)$ time for graphical degree sequences (realized as simple temporal graphs) and in $O(n+m)$ time for multigraphical degree sequences (realized as non-simple temporal graphs, where the number of time labels on an edge corresponds to the multiplicity of the edge in the multigraph). In fact, these algorithms can be made constructive at essentially no cost. Namely, we give a constructive $O(n+m)$ time algorithm that outputs, for a given (multi)graphical degree sequence $\mathbf{d}$, a temporally connected graph whose underlying (multi)graph is a realization of $\mathbf{d}$, if one exists.

Authors: Christian Bertram

In the online metric traveling salesperson problem, $n$ points of a metric space arrive one by one and have to be placed (immediately and irrevocably) into empty cells of a size-$n$ array. The goal is to minimize the sum of distances between consecutive points in the array. This problem was introduced by Abrahamsen, Bercea, Beretta, Klausen, and Kozma [ESA'24] as a generalization of the online sorting problem, which was introduced by Aamand, Abrahamsen, Beretta, and Kleist [SODA'23] as a tool in their study of online geometric packing problems. Online metric TSP has been studied for a range of fixed metric spaces. For 1-dimensional Euclidean space, the problem is equivalent to online sorting, where an optimal competitive ratio of $\Theta(\sqrt n)$ is known. For $d$-dimensional Euclidean space, the best-known upper bound is $O(2^{d} \sqrt{dn\log n})$, leaving a gap to the $\Omega(\sqrt n)$ lower bound. Finally, for the uniform metric, where all distances are 0 or 1, the optimal competitive ratio is known to be $\Theta(\log n)$. We study the problem for a general metric space, presenting an algorithm with competitive ratio $O(\sqrt n)$. In particular, we close the gap for $d$-dimensional Euclidean space, completely removing the dependence on dimension. One might hope to simultaneously guarantee competitive ratio $O(\sqrt n)$ in general and $O(\log n)$ for the uniform metric, but we show that this is impossible.

Authors: Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, Jean-Florent Raymond

The paper deals with the Feedback Vertex Set problem parameterized by the solution size. Given a graph $G$ and a parameter $k$, one has to decide if there is a set $S$ of at most $k$ vertices such that $G-S$ is acyclic. Assuming the Exponential Time Hypothesis, it is known that FVS cannot be solved in time $2^{o(k)}n^{\mathcal{O}(1)}$ in general graphs. To overcome this, many recent results considered FVS restricted to particular intersection graph classes and provided such $2^{o(k)}n^{\mathcal{O}(1)}$ algorithms. In this paper we provide generic conditions on a graph class for the existence of an algorithm solving FVS in subexponential FPT time, i.e. time $2^{k^\varepsilon} \mathop{\rm poly}(n)$, for some $\varepsilon<1$, where $n$ denotes the number of vertices of the instance and $k$ the parameter. On the one hand this result unifies algorithms that have been proposed over the years for several graph classes such as planar graphs, map graphs, unit-disk graphs, pseudo-disk graphs, and string graphs of bounded edge-degree. On the other hand it extends the tractability horizon of FVS to new classes that are not amenable to previously used techniques, in particular intersection graphs of ``thin'' objects like segment graphs or more generally $s$-string graphs.

Authors: Lars Gottesbüren, Nikolai Maas, Dominik Rosch, Peter Sanders, Daniel Seemaier

The current landscape of balanced graph partitioning is divided into high-quality but expensive multilevel algorithms and cheaper approaches with linear running time, such as single-level algorithms and streaming algorithms. We demonstrate how to achieve the best of both worlds with a \emph{linear time multilevel algorithm}. Multilevel algorithms construct a hierarchy of increasingly smaller graphs by repeatedly contracting clusters of nodes. Our approach preserves their distinct advantage, allowing refinement of the partition over multiple levels with increasing detail. At the same time, we use \emph{edge sparsification} to guarantee geometric size reduction between the levels and thus linear running time. We provide a proof of the linear running time as well as additional insights into the behavior of multilevel algorithms, showing that graphs with low modularity are most likely to trigger worst-case running time. We evaluate multiple approaches for edge sparsification and integrate our algorithm into the state-of-the-art multilevel partitioner KaMinPar, maintaining its excellent parallel scalability. As demonstrated in detailed experiments, this results in a $1.49\times$ average speedup (up to $4\times$ for some instances) with only 1\% loss in solution quality. Moreover, our algorithm clearly outperforms state-of-the-art single-level and streaming approaches.

Authors: Michael A. Bender, Martín Farach-Colton, Riko Jacob, Hanna Komlós, David Tench, Evan West

Algorithms in the data stream model use $O(polylog(N))$ space to compute some property of an input of size $N$, and many of these algorithms are implemented and used in practice. However, sketching algorithms in the graph semi-streaming model use $O(V polylog(V))$ space for a $V$-vertex graph, and the fact that implementations of these algorithms are not used in the academic literature or in industrial applications may be because this space requirement is too large for RAM on today's hardware. In this paper we introduce the external semi-streaming model, which addresses the aspects of the semi-streaming model that limit its practical impact. In this model, the input is in the form of a stream and $O(V polylog(V))$ space is available, but most of that space is accessible only via block I/O operations as in the external memory model. The goal in the external semi-streaming model is to simultaneously achieve small space and low I/O cost. We present a general transformation from any vertex-based sketch algorithm to one which has a low sketching cost in the new model. We prove that this automatic transformation is tight or nearly (up to a $O(\log(V))$ factor) tight via an I/O lower bound for the task of sketching the input stream. Using this transformation and other techniques, we present external semi-streaming algorithms for connectivity, bipartiteness testing, $(1+\epsilon)$-approximating MST weight, testing k-edge connectivity, $(1+\epsilon)$-approximating the minimum cut of a graph, computing $\epsilon$-cut sparsifiers, and approximating the density of the densest subgraph. These algorithms all use $O(V poly(\log(V), \epsilon^{-1},k)$ space. For many of these problems, our external semi-streaming algorithms outperform the state of the art algorithms in both the sketching and external-memory models.

Authors: Antoine Amarilli, Corentin Barloy, Louis Jachiet, Charles Paperman

We study the dynamic membership problem for regular tree languages under relabeling updates: we fix an alphabet ${\Sigma}$ and a regular tree language $L$ over ${\Sigma}$ (expressed, e.g., as a tree automaton), we are given a tree $T$ with labels in ${\Sigma}$, and we must maintain the information of whether the tree $T$ belongs to $L$ while handling relabeling updates that change the labels of individual nodes in $T$. (The shape and size of the tree remain the same throughout.) Our first contribution is to show that this problem admits an $O(\log n / \log \log n)$ algorithm for any fixed regular tree language, improving over known algorithms that achieve $O(\log n)$. This generalizes the known $O(\log n / \log \log n)$ upper bound over words, and it matches the lower bound of ${\Omega}(\log n / \log \log n)$ from dynamic membership to some word languages and from the existential marked ancestor problem. Our second contribution is to introduce a class of regular languages, dubbed almost-commutative tree languages, and show that dynamic membership to such languages under relabeling updates can be done in constant time per update. Almost-commutative languages generalize both commutative languages and finite languages, and they are the analogue for trees of the ZG languages enjoying constant-time dynamic membership over words. Our main technical contribution is to show that this class is conditionally optimal when we assume that the alphabet features a neutral letter, i.e., a letter that has no effect on membership to the language. More precisely, we show that any regular tree language with a neutral letter which is not almost-commutative cannot be maintained in constant time under the assumption that prefix-U1 problem from (Amarilli, Jachiet, Paperman, ICALP'21) also does not admit a constant-time algorithm.

Authors: Gabriele Fici, Giuseppe Romana, Marinella Sciortino, Cristian Urbina

We study how the application of injective morphisms affects the number $r$ of equal-letter runs in the Burrows-Wheeler Transform (BWT). This parameter has emerged as a key repetitiveness measure in compressed indexing. We focus on the notion of BWT-run sensitivity after application of an injective morphism. For binary alphabets, we characterize the class of morphisms that preserve the number of BWT-runs up to a bounded additive increase, by showing that it coincides with the known class of primitivity-preserving morphisms, which are those that map primitive words to primitive words. We further prove that deciding whether a given binary morphism has bounded BWT-run sensitivity is possible in polynomial time with respect to the total length of the images of the two letters. Additionally, we explore new structural and combinatorial properties of synchronizing and recognizable morphisms. These results establish new connections between BWT-based compressibility, code theory, and symbolic dynamics.

Authors: Shuyi Yan

The online stochastic matching problem was introduced by [FMMM09], together with the $(1-\frac1e)$-competitive Suggested Matching algorithm. In the most general edge-weighted setting, this ratio has not been improved for more than one decade, until recently [Yan24] beat the $1-\frac1e$ bound and [QFZW23] further improved the ratio to $0.650$. Both of these works measure the online competitiveness against the offline LP relaxation introduced by [JL14]. This LP has also played an important role in other settings since it is a natural choice for two-choices online algorithms. In this paper, we propose an upper bound of $0.663$ and a lower bound of $0.662$ for edge-weighted online stochastic matching under Jaillet-Lu LP. First, we propose a hard instance and prove that the optimal online algorithm for this instance only has a competitive ratio $<0.663$. Then, we show that a near-optimal algorithm for this instance can be generalized to work on all instances and achieve a competitive ratio $>0.662$. It indicates that more powerful LPs are necessary if we want to further improve the ratio by $0.001$.

Authors: Peter Robinson, Xianbin Zhu

We initiate the study of approximate maximum matching in the vertex partition model, for graphs subject to dynamic changes. We assume that the $n$ vertices of the graph are partitioned among $k$ players, who execute a distributed algorithm and communicate via message passing. An adaptive adversary may perform dynamic updates to the graph topology by inserting or removing edges between the nodes, and the algorithm needs to respond to these changes by adapting the output of the players, with the goal of maintaining an approximate maximum matching. The main performance metric in this setting is the algorithm's update time, which corresponds to the number of rounds required for updating the solution upon an adversarial change. For the standard setting of single-edge insertions and deletions, we obtain the following results: We give a randomized Las Vegas algorithm with an expected update time of $O( \frac{\sqrt{m}}{\beta k} )$ rounds that maintains a $\frac{2}{3}$-approximate maximum matching that is also maximal, where $m$ is the number of edges of the graph. We also show that any algorithm has a worst case update time of $\Omega( \frac{n}{\beta k^2\log n} )$, assuming a link bandwidth of $O(\beta\log n)$ bits per round, if it maintains a matching that is maximal and does not have any 3-augmenting paths. For batch-dynamic updates, where the adversary may modify up to $\ell\ge 1$ edges at once, we prove the following: There is a randomized algorithm that succeeds with high probability in maintaining a $\frac{2}{3}$-approximate maximum matching and has a worst case update time of $\Omega( \frac{\ell\log n}{\sqrt{\beta k}} )$ rounds. We show that $\Omega( \frac{\ell}{\beta k \log n} )$ poses a lower bound for maintaining a maximal matching without 3-augmenting paths.

Authors: Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann

Let G be a weighted (directed) graph with n vertices and m edges. Given a source vertex s, Dijkstra's algorithm computes the shortest path lengths from s to all other vertices in O(m + n log n) time. This bound is known to be worst-case optimal via a reduction to sorting. Theoretical computer science has developed numerous fine-grained frameworks for analyzing algorithmic performance beyond standard worst-case analysis, such as instance optimality and output sensitivity. Haeupler et al. [FOCS '24] consider the notion of universal optimality, a refined complexity measure that accounts for both the graph topology and the edge weights. For a fixed graph topology, the universal running time of a weighted graph algorithm is defined as its worst-case running time over all possible edge weightings of G. An algorithm is universally optimal if no other algorithm achieves a better asymptotic universal running time on any particular graph topology. They show that Dijkstra's algorithm can be made universally optimal by replacing the heap with a custom data structure. We revisit their result. We introduce a simple heap property called timestamp optimality, where the cost of popping an element x is logarithmic in the number of elements inserted between pushing and popping x. We show that timestamp optimal heaps are not only easier to define but also easier to implement. Using these timestamps, we provide a significantly simpler proof that Dijkstra's algorithm, with the right kind of heap, is universally optimal.

Authors: Yen-Hsiang Chang, Aydın Buluç, James Demmel

The approximate minimum degree algorithm is widely used before numerical factorization to reduce fill-in for sparse matrices. While considerable attention has been given to the numerical factorization process, less focus has been placed on parallelizing the approximate minimum degree algorithm itself. In this paper, we explore different parallelization strategies, and introduce a novel parallel framework that leverages multiple elimination on distance-2 independent sets. Our evaluation shows that parallelism within individual elimination steps is limited due to low computational workload and significant memory contention. In contrast, our proposed framework overcomes these challenges by parallelizing the work across elimination steps. To the best of our knowledge, our implementation is the first scalable shared memory implementation of the approximate minimum degree algorithm. Experimental results show that we achieve up to an 8.30x speedup using 64 threads over the state-of-the-art sequential implementation in SuiteSparse.

Authors: Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin

We give a deterministic $O(m\log^{2/3}n)$-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the $O(m+n\log n)$ time bound of Dijkstra's algorithm on sparse graphs, showing that Dijkstra's algorithm is not optimal for SSSP.

Authors: Hessa Al-Thani, Viswanath Nagarajan

We study a fundamental stochastic selection problem involving $n$ independent random variables, each of which can be queried at some cost. Given a tolerance level $\delta$, the goal is to find a value that is $\delta$-approximately minimum (or maximum) over all the random variables, at minimum expected cost. A solution to this problem is an adaptive sequence of queries, where the choice of the next query may depend on previously-observed values. Two variants arise, depending on whether the goal is to find a $\delta$-minimum value or a $\delta$-minimizer. When all query costs are uniform, we provide a $4$-approximation algorithm for both variants. When query costs are non-uniform, we provide a $5.83$-approximation algorithm for the $\delta$-minimum value and a $7.47$-approximation for the $\delta$-minimizer. All our algorithms rely on non-adaptive policies (that perform a fixed sequence of queries), so we also upper bound the corresponding ''adaptivity'' gaps. Our analysis relates the stopping probabilities in the algorithm and optimal policies, where a key step is in proving and using certain stochastic dominance properties.

I’ve received several requests over the semester for the syllabus from our class on Machine Learning Evaluation. There were two reasons I didn’t readily share it. First, I made the mistake of relying too heavily on Canvas. Using Canvas means that course content lives behind an obnoxious campus IT firewall. I’m not going to do this again. From now on, my course materials will be on public webpages, and I’ll use Canvas only for announcements and assignments. You’d think I’d have figured this out by this point in my academic career, but I suppose we are constantly honing our craft. This is just a note-to-self that I’m putting on the blog. Hold me to the commitment next semester, dear readers.

The second reason is perhaps a bit more justifiable: Deb and I were making up the course as we went along. This is the way a good grad seminar should go, right? We all figure out the boundaries of an intellectual field together. It felt a bit premature to be sharing the syllabus before we knew what the course was. We’re at the end of the semester, and I’m still not 100% sure I know what the course is. It usually takes me three iterations to solidify a class, and after that, I never want to teach it again. But after the first iteration of machine learning evaluation, I still feel very much at the beginning of figuring out how to teach this topic properly.

With these disclaimers, let me share what we ended up reading. Click the link below:

At some point, I will tidy up these citations to be neatly in APA format. I suppose I could ask ChatGPT to do that for me, no? But hopefully the links here all work, and there aren’t too many egregious citation typos. I’ve also added links to the relevant blog posts where I thought out loud about the class. These add some context about what we actually ended up discussing in seminar.

Even with this context, the syllabus doesn’t tell the entire story of how we worked through the class, but it’s a decent skeleton. Reviewing it this morning, I think much of this structure would remain the same if I were to teach the course again. I might move around a couple of the topics next time. Certainly, some of these topics were presented in a suboptimal order due to constraints in the instructors’ schedules. But I wouldn’t add anything. If anything, I’d want to expand upon some of the parts that felt a bit rushed and perhaps drop a few topics that seemed to add more heat than light.

Up through week 5 is a tight story, more of how machine learning and prediction systems have traditionally been evaluated. Week 6 on construct validity was also illuminating, and I’d make this section two weeks, adding in a bit more philosophy of science. Specifically, I would spend more time on the problem of induction and Lakatosian Defense in science and engineering.

This brings us to the three weeks on uncertainty. In hindsight, Deb and I would reshuffle the material in Weeks 7-9, and we would certainly change the reading assignments. For example, I’d drop the survey of scoring rules by Gneiting and Raftery, which, while establishing interesting mathematical foundations, doesn’t give much insight into why we should use scoring rules in the first place.

That said, the uncertainty block was the part of the course where I learned the most. Namely, what is so interesting about uncertainty quantification is how evaluation metrics dictate the algorithms we use, both for making predictions and reporting uncertainty. The metric itself dictates how to make predictions from the data you have thus far recorded. My conclusion is that uncertainty-quantified prediction is nothing but defensive bookkeeping. I need to write this down in detail before teaching the course again. I’m currently writing up a paper on this viewpoint with Juanky Perdomo.

The most controversial week of the class was the one where we tried to discuss “contemporary” machine learning benchmarks. Sigh. I’d probably throw out all of this reading. The shelf life of “contemporary” evaluation in machine learning seems to be a week. One way of viewing this is that AI is too good now, and no benchmark is safe. Another view is that creating and evaluating benchmarks is challenging, and you can’t just throw together a random dataset and declare it a benchmark. The right perspective is probably in the middle.

However, it’s impossible to tell because the new papers on evaluation all have less content than a tweet. It’s a rough state of affairs! Even the two papers we assigned as mandatory reading don’t say much beyond “depending on how you format your axes, you can convince yourself of anything you want about LLMs.” This can win you a best paper award.

From a practical perspective, for “frontier models,” it’s unfortunately impossible to decouple their evaluation from the billions of dollars being thrown at them. We might have to be patient and wait for the craze to pass before we make sense of them. Perhaps we’ll be ready when I teach this class again in 2027.

The LLM unit at least motivated why we need to care about social program evaluation in machine learning, and I thought the two weeks spent on RCTs and program evaluation were solid, though a bit rushed. It’s a lot to pack into a semester!

Finally, missing from this syllabus are readings from my forthcoming book. I’m not at liberty to share them widely just yet. It will be published later this year, and I’ll add it to the syllabus when it becomes available. I will make an official announcement soon, I promise!

The most positive signal from the class is that writing this post has convinced me that I want to teach it again. It’s always a good sign when I come away from the class with new research projects, and I have more than a few germinating. Evaluation is so critical to machine learning engineering, and yet our courses tend to just teach methods. What’s funny about the current state of affairs is the atheoretical nature of machine learning means evaluation is all we have. Machine learning is most helpful when we don’t understand some phenomenon, but how can we evaluate outcomes without a firm causal theory of how entities are linked to each other? That’s the central question we grappled with this semester, and it’s one we’ll continue to grapple with moving forward.

Subscribe now

By Ben Recht

Trevisan and Vadhan (FOCS 2000) introduced the notion of (seedless) extractors for samplable distributions. They showed that under a very strong complexity theoretic hardness assumption (specifically, that there exists a problem in $\E=\DTIME(2^{O(n)})$ that cannot be computed by size $2^{\Omega(n)}$ circuits that have an oracle to $\Sigma_6^{\P}$) there are extractors for samplable distributions with large min-entropy of $k=(1-\gamma) \cdot n$, for some small constant $\gamma>0$. Recently, Ball, Shaltiel and Silbak (STOC 2025) were able to reduce the min-entropy threshold to $k=n^{1-\gamma}$. Ball et al., point out that their approach does not work for $k\frac{1}{i}$, we construct an extractor for samplable distributions with min-entropy $k=n^{\alpha}$, under a hardness assumption in which $6$ is replaced with $i+3$ (the aforementioned result is a obtained for $i=3$). We also provide a multiplicative version of our extractors (under a stronger hardness assumption) addressing an open problem of Ball et al. Our work builds on the approach of Ball et al., who reduced the task of constructing extractors for samplable distributions with min-entropy $k$, to the task of constructing errorless condensers for samplable distributions with min-entropy $k$. Our main technical contribution is a new construction of errorless condensers for samplable distributions with $k=n^{\alpha}$ under the hardness assumption stated above, improving upon the min-entropy threshold achieved in Ball et al. (which cannot achieve $k<\sqrt{n}$). Our insight is that the technique used by Ball et al. to reduce the task of constructing extractors to that of constructing errorless condensers, can \emph{itself} be used to construct errorless condensers for polynomially small min-entropy when combined with ``win-win analysis'' approaches that are inspired by some early work on seeded extractors and dispersers. In order to do this, we adapt these approaches from the information theoretic scenario of seeded extractors and dispersers to the computational scenario of errorless condensers for samplable distributions.

Last week I visited Harvard and MIT, and as advertised in my last post, gave the Yip Lecture at Harvard on the subject “How Much Math Is Knowable?” The visit was hosted by Harvard’s wonderful Center of Mathematical Sciences and Applications (CMSA), directed by my former UT Austin colleague Dan Freed. Thanks so much to everyone at CMSA for the visit.

And good news! You can now watch my lecture on YouTube here:

I’m told it was one of my better performances. As always, I strongly recommend watching at 2x speed.

I opened the lecture by saying that, while obviously it would always be an honor to give the Yip Lecture at Harvard, it’s especially an honor right now, as the rest of American academia looks to Harvard to defend the value of our entire enterprise. I urged Harvard to “fight fiercely,” in the words of the Tom Lehrer song.

I wasn’t just fishing for applause; I meant it. It’s crucial for people to understand that, in its total war against universities, MAGA has now lost, not merely the anti-Israel leftists, but also most conservatives, classical liberals, Zionists, etc. with any intellectual scruples whatsoever. To my mind, this opens up the possibility for a broad, nonpartisan response, highlighting everything universities (yes, even Harvard ) do for our civilization that’s worth defending.

For three days in my old hometown of Cambridge, MA, I met back-to-back with friends and colleagues old and new. Almost to a person, they were terrified about whether they’ll be able to keep doing science as their funding gets decimated, but especially terrified for anyone who they cared about on visas and green cards. International scholars can now be handcuffed, deported, and even placed in indefinite confinement for pretty much any reason—including long-ago speeding tickets—or no reason at all. The resulting fear has paralyzed, in a matter of months, an American scientific juggernaut that took a century to build.

A few of my colleagues personally knew Rümeysa Öztürk, the Turkish student at Tufts who currently sits in prison for coauthoring an editorial for her student newspaper advocating the boycott of Israel. I of course disagree with what Öztürk wrote … and that is completely irrelevant to my moral demand that she go free. Even supposing the government had much more on her than this one editorial, still the proper response would seem to be a deportation notice—“either contest our evidence in court, or else get on the next flight back to Turkey”—rather than grabbing Öztürk off the street and sending her to indefinite detention in Louisiana. It’s impossible to imagine any university worth attending where the students live in constant fear of imprisonment for the civil expression of opinions.

To help calibrate where things stand right now, here’s the individual you might expect to be most on board with a crackdown on antisemitism at Harvard:

Jason Rubenstein, the executive director of Harvard Hillel, said that the school is in the midst of a long — and long-overdue — reckoning with antisemitism, and that [President] Garber has taken important steps to address the problem. Methodical federal civil rights oversight could play a constructive role in that reform, he said. “But the government’s current, fast-paced assault against Harvard – shuttering apolitical, life-saving research; targeting the university’s tax-exempt status; and threatening all student visas … is neither deliberate nor methodical, and its disregard for the necessities of negotiation and due process threatens the bulwarks of institutional independence and the rule of law that undergird our shared freedoms.”

Meanwhile, as the storm clouds over American academia continue to darken, I’ll just continue to write what I think about everything, because what else can I do?

Last night, alas, I lost yet another left-wing academic friend, the fourth or fifth I’ve lost since October 7. For while I was ready to take a ferocious public stand against the current US government, for the survival and independence of our universities, and for free speech and due process for foreign students, this friend regarded all that as insufficient. He demanded that I also clear the tentifada movement of any charge of antisemitism. For, as he patiently explained to me (while worrying that I wouldn’t grasp the point), while the protesters may have technically violated university rules, disrupted education, created a hostile environment in the sense of Title VI antidiscrimination law in ways that would be obvious were we discussing any other targeted minority, etc. etc., still, the only thing that matters morally is that the protesters represent “the powerless,” whereas Zionist Jews like me represent “the powerful.” So, I told this former friend to go fuck himself. Too harsh? Maybe if he hadn’t been Jewish himself, I could’ve forgiven him for letting the world’s oldest conspiracy theory colonize his brain.

For me, the deep significance of in-person visits, including my recent trip to Harvard, is that they reassure me of the preponderance of sanity within my little world—and thereby of my own sanity. Online, every single day I feel isolated and embattled: pressed in on one side by MAGA forces who claim to care about antisemitism, but then turn out to want the destruction of science, universities, free speech, international exchange, due process of law, and everything else that’s made the modern world less than fully horrible; and on the other side, by leftists who say they stand with me for science and academic freedom and civil rights and everything else that’s good, but then add that the struggle needs to continue until the downfall of the scheming, moneyed Zionists and the liberation of Palestine from river to sea.

When I travel to universities to give talks, though, I meet one sane, reasonable human being after another. Almost to a person, they acknowledge the reality of antisemitism, ideological monoculture, bureaucracy, spiraling costs, and many other problems at universities—and they care about universities enough to want to fix those problems, rather than gleefully nuking the universities from orbit as MAGA is doing. Mostly, though, people just want me to sign Quantum Computing Since Democritus, or tell me how much they like this blog, or ask questions about quantum algorithms or the Busy Beaver function. Which is fine too, and which you can do in the comments.

By Scott

Authors: Anuj Dawar, Erich Grädel, Leon Kullmann, Benedikt Pago

We consider the Ideal Proof System (IPS) introduced by Grochow and Pitassi and pose the question of which tautologies admit symmetric proofs, and of what complexity. The symmetry requirement in proofs is inspired by recent work establishing lower bounds in other symmetric models of computation. We link the existence of symmetric IPS proofs to the expressive power of logics such as fixed-point logic with counting and Choiceless Polynomial Time, specifically regarding the graph isomorphism problem. We identify relationships and tradeoffs between the symmetry of proofs and other parameters of IPS proofs such as size, degree and linearity. We study these on a number of standard families of tautologies from proof complexity and finite model theory such as the pigeonhole principle, the subset sum problem and the Cai-F\"urer-Immerman graphs, exhibiting non-trivial upper bounds on the size of symmetric IPS proofs.

Authors: Nikolay Bazhenov, Dariusz Kalociński, Michał Wrocławski

We investigate whether every computable member of a given class of structures admits a fully primitive recursive (also known as punctual) or fully P-TIME copy. A class with this property is referred to as punctually robust or P-TIME robust, respectively. We present both positive and negative results for structures corresponding to well-known representations of trees, such as binary trees, ordered trees, sequential (or prefix) trees, and partially ordered (poset) trees. A corollary of one of our results on trees is that semilattices and lattices are not punctually robust. In the main result of the paper, we demonstrate that, unlike Boolean algebras, modal algebras - that is, Boolean algebras with modality - are not punctually robust. The question of whether distributive lattices are punctually robust remains open. The paper contributes to a decades-old program on effective and feasible algebra, which has recently gained momentum due to rapid developments in punctual structure theory and its connections to online presentations of structures.

Authors: Nick Fischer, Elazar Goldenberg, Mursalin Habib, C. S. Karthik

The classical rank aggregation problem seeks to combine a set X of n permutations into a single representative "consensus" permutation. In this paper, we investigate two fundamental rank aggregation tasks under the well-studied Ulam metric: computing a median permutation (which minimizes the sum of Ulam distances to X) and computing a center permutation (which minimizes the maximum Ulam distance to X) in two settings. $\bullet$ Continuous Setting: In the continuous setting, the median/center is allowed to be any permutation. It is known that computing a center in the Ulam metric is NP-hard and we add to this by showing that computing a median is NP-hard as well via a simple reduction from the Max-Cut problem. While this result may not be unexpected, it had remained elusive until now and confirms a speculation by Chakraborty, Das, and Krauthgamer [SODA '21]. $\bullet$ Discrete Setting: In the discrete setting, the median/center must be a permutation from the input set. We fully resolve the fine-grained complexity of the discrete median and discrete center problems under the Ulam metric, proving that the naive $\widetilde{O}(n^2 L)$-time algorithm (where L is the length of the permutation) is conditionally optimal. This resolves an open problem raised by Abboud, Bateni, Cohen-Addad, Karthik C. S., and Seddighin [APPROX '23]. Our reductions are inspired by the known fine-grained lower bounds for similarity measures, but we face and overcome several new highly technical challenges.

Authors: Bruno Bauwens, Bruno Loff

Ball, Liu, Mazor and Pass proved that the existence of key-agreement protocols is equivalent to the hardness of a certain problem about interactive Kolmogorov complexity. We generalize the statement and give a short proof of the difficult implication.

Authors: Sándor P. Fekete, Peter Kramer, Jan-Marc Reinhardt, Christian Rieck, Christian Scheffer

Tilt models offer intuitive and clean definitions of complex systems in which particles are influenced by global control commands. Despite a wide range of applications, there has been almost no theoretical investigation into the associated issues of filling and draining geometric environments. This is partly because a globally controlled system (i.e., passive matter) exhibits highly complex behavior that cannot be locally restricted. Thus, there is a strong need for theoretical studies that investigate these models both (1) in terms of relative power to each other, and (2) from a complexity theory perspective. In this work, we provide (1) general tools for comparing and contrasting different models of global control, and (2) both complexity and algorithmic results on filling and draining.

Authors: Jean Cardinal, Xavier Goaoc, Sarah Wajsbrot

Geometric hitting set problems, in which we seek a smallest set of points that collectively hit a given set of ranges, are ubiquitous in computational geometry. Most often, the set is discrete and is given explicitly. We propose new variants of these problems, dealing with continuous families of convex polyhedra, and show that they capture decision versions of the two-level finite adaptability problem in robust optimization. We show that these problems can be solved in strongly polynomial time when the size of the hitting/covering set and the dimension of the polyhedra and the parameter space are constant. We also show that the hitting set problem can be solved in strongly quadratic time for one-parameter families of convex polyhedra in constant dimension. This leads to new tractability results for finite adaptability that are the first ones with so-called left-hand-side uncertainty, where the underlying problem is non-linear.

Authors: Daniele Carnevale, Gianlorenzo D'Angelo, Martin Olsen

In a temporal graph the edge set dynamically changes over time according to a set of time-labels associated with each edge that indicates at which time-steps the edge is available. Two vertices are connected if there is a path connecting them in which the edges are traversed in increasing order of their labels. We study the problem of scheduling the availability time of the edges of a temporal graph in such a way that all pairs of vertices are connected within a given maximum allowed time $a$ and the overall number of labels is minimized. The problem, known as \emph{Minimum Aged Labeling} (MAL), has several applications in logistics, distribution scheduling, and information spreading in social networks, where carefully choosing the time-labels can significantly reduce infrastructure costs, fuel consumption, or greenhouse gases. The problem MAL has previously been proved to be NP-complete on undirected graphs and \APX-hard on directed graphs. In this paper, we extend our knowledge on the complexity and approximability of MAL in several directions. We first show that the problem cannot be approximated within a factor better than $O(\log n)$ when $a\geq 2$, unless $\text{P} = \text{NP}$, and a factor better than $2^{\log ^{1-\epsilon} n}$ when $a\geq 3$, unless $\text{NP}\subseteq \text{DTIME}(2^{\text{polylog}(n)})$, where $n$ is the number of vertices in the graph. Then we give a set of approximation algorithms that, under some conditions, almost match these lower bounds. In particular, we show that the approximation depends on a relation between $a$ and the diameter of the input graph. We further establish a connection with a foundational optimization problem on static graphs called \emph{Diameter Constrained Spanning Subgraph} (DCSS) and show that our hardness results also apply to DCSS.

Authors: Laure Morelle, Ignasi Sau, Dimitrios M. Thilikos

A replacement action is a function $\mathcal{L}$ that maps each graph $H$ to a collection of graphs of size at most $|V(H)|$. Given a graph class $\mathcal{H}$, we consider a general family of graph modification problems, called $\mathcal{L}$-Replacement to $\mathcal{H}$, where the input is a graph $G$ and the question is whether it is possible to replace some induced subgraph $H_1$ of $G$ on at most $k$ vertices by a graph $H_2$ in $\mathcal{L}(H_1)$ so that the resulting graph belongs to $\mathcal{H}$. $\mathcal{L}$-Replacement to $\mathcal{H}$ can simulate many graph modification problems including vertex deletion, edge deletion/addition/edition/contraction, vertex identification, subgraph complementation, independent set deletion, (induced) matching deletion/contraction, etc. We present two algorithms. The first one solves $\mathcal{L}$-Replacement to $\mathcal{H}$ in time $2^{{\rm poly}(k)}\cdot |V(G)|^2$ for every minor-closed graph class $\mathcal{H}$, where {\rm poly} is a polynomial whose degree depends on $\mathcal{H}$, under a mild technical condition on $\mathcal{L}$. This generalizes the results of Morelle, Sau, Stamoulis, and Thilikos [ICALP 2020, ICALP 2023] for the particular case of Vertex Deletion to $\mathcal{H}$ within the same running time. Our second algorithm is an improvement of the first one when $\mathcal{H}$ is the class of graphs embeddable in a surface of Euler genus at most $g$ and runs in time $2^{\mathcal{O}(k^{9})}\cdot |V(G)|^2$, where the $\mathcal{O}(\cdot)$ notation depends on $g$. To the best of our knowledge, these are the first parameterized algorithms with a reasonable parametric dependence for such a general family of graph modification problems to minor-closed classes.

Authors: Markus Chimani, Max Ilsen

We consider the Minimum Multi-Commodity Flow Subgraph (MMCFS) problem: given a directed graph $G$ with edge capacities $\mathit{cap}$ and a retention ratio $\alpha\in(0,1)$, find an edge-wise minimum subgraph $G' \subseteq G$ such that for all traffic matrices $T$ routable in $G$ using a multi-commodity flow, $\alpha\cdot T$ is routable in $G'$. This natural yet novel problem is motivated by recent research that investigates how the power consumption in backbone computer networks can be reduced by turning off connections during times of low demand without compromising the quality of service. Since the actual traffic demands are generally not known beforehand, our approach must be traffic-oblivious, i.e., work for all possible sets of simultaneously routable traffic demands in the original network. In this paper we present the problem, relate it to other known problems in literature, and show several structural results, including a reformulation, maximum possible deviations from the optimum, and NP-hardness (as well as a certain inapproximability) already on very restricted instances. The most significant contribution is a tight $\max(\frac{1}{\alpha}, 2)$-approximation based on an algorithmically surprisingly simple LP-rounding scheme.

Authors: Ernestine Großmann, Ivor van der Hoog, Henrik Reinstädtler, Eva Rotenberg, Christian Schulz, Juliette Vlieghe

Dynamic graph algorithms have seen significant theoretical advancements, but practical evaluations often lag behind. This work bridges the gap between theory and practice by engineering and empirically evaluating recently developed approximation algorithms for dynamically maintaining graph orientations. We comprehensively describe the underlying data structures, including efficient bucketing techniques and round-robin updates. Our implementation has a natural parameter $\lambda$, which allows for a trade-off between algorithmic efficiency and the quality of the solution. In the extensive experimental evaluation, we demonstrate that our implementation offers a considerable speedup. Using different quality metrics, we show that our implementations are very competitive and can outperform previous methods. Overall, our approach solves more instances than other methods while being up to 112 times faster on instances that are solvable by all methods compared.

Authors: Jonathan Landers

We investigate how sorting algorithms efficiently overcome the exponential size of the permutation space. Our main contribution is a new continuous-time formulation of sorting as a gradient flow on the permutohedron, yielding an independent proof of the classical $\Omega(n \log n)$ lower bound for comparison-based sorting. This formulation reveals how exponential contraction of disorder occurs under simple geometric dynamics. In support of this analysis, we present algebraic, combinatorial, and geometric perspectives, including decision-tree arguments and linear constraints on the permutohedron. The idea that efficient sorting arises from structure-guided logarithmic reduction offers a unifying lens for how comparisons tame exponential spaces. These observations connect to broader questions in theoretical computer science, such as whether the existence of structure can explain why certain computational problems permit efficient solutions.

Authors: Markus Lohrey, Leon Rische, Louisa Seelbach Benkner, Julio Xochitemol

We consider streaming algorithms for approximating a product of input probabilities up to multiplicative error of $1-\epsilon$. It is shown that every randomized streaming algorithm for this problem needs space $\Omega(\log n + \log b - \log \epsilon) - \mathcal{O}(1)$, where $n$ is length of the input stream and $b$ is the bit length of the input numbers. This matches an upper bound from Alur et al.~up to a constant multiplicative factor. Moreover, we consider the threshold problem, where it is asked whether the product of the input probabilities is below a given threshold. It is shown that every randomized streaming algorithm for this problem needs space $\Omega(n \cdot b)$.

Authors: Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup, Hanzhi Wang, Shuyi Yan

We study discounted random walks in a directed graph. In each vertex, the walk will either terminate with some probability $\alpha$, or continue to a random out-neighbor. We are interested in the probability $\pi(s,t)$ that such a random walk starting in $s$ ends in $t$. We wish to, with constant probability, estimate $\pi(s, t)$ within a constant relative error, unless $\pi(s, t) < \delta$ for some given threshold $\delta$. The current status is as follows. Algorithms with worst-case running time $\tilde O(m)$ and $O(1/\delta)$ are known. A more complicated algorithm is known, which does not perform better in the worst case, but for the average running time over all $n$ possible targets $t$, it achieves an alternative bound of $O(\sqrt{d/\delta})$. All the above algorithms assume query access to the adjacency list of a node. On the lower bound side, the best-known lower bound for the worst case is $\Omega(n^{1/2}m^{1/4})$ with $\delta \leq 1/(n^{1/2}m^{1/4})$, and for the average case it is $\Omega(\sqrt{n})$ with $\delta \leq 1/n$. This leaves substantial polynomial gaps in both cases. In this paper, we show that the above upper bounds are tight across all parameters $n$, $m$ and $\delta$. We show that the right bound is $\tilde\Theta(\min\{m, 1/\delta\})$ for the worst case, and $\tilde\Theta(\min\{m, \sqrt{d/\delta}, 1/\delta\})$ for the average case. We also consider some additional graph queries from the literature. One allows checking whether there is an edge from $u$ to $v$ in constant time. Another allows access to the adjacency list of $u$ sorted by out-degree. We prove that none of these access queries help in the worst case, but if we have both of them, we get an average-case bound of $\tilde \Theta(\min\{m,\sqrt{d/\delta}, (1/\delta)^{2/3}\})$.

Authors: Shiri Chechik, Hongyi Chen, Tianyi Zhang

Given a graph, an edge coloring assigns colors to edges so that no pairs of adjacent edges share the same color. We are interested in edge coloring algorithms under the W-streaming model. In this model, the algorithm does not have enough memory to hold the entire graph, so the edges of the input graph are read from a data stream one by one in an unknown order, and the algorithm needs to print a valid edge coloring in an output stream. The performance of the algorithm is measured by the amount of space and the number of different colors it uses. This streaming edge coloring problem has been studied by several works in recent years. When the input graph contains $n$ vertices and has maximum vertex degree $\Delta$, it is known that in the W-streaming model, an $O(\Delta^2)$-edge coloring can be computed deterministically with $\tilde{O}(n)$ space [Ansari, Saneian, and Zarrabi-Zadeh, 2022], or an $O(\Delta^{1.5})$-edge coloring can be computed by a $\tilde{O}(n)$-space randomized algorithm [Behnezhad, Saneian, 2024] [Chechik, Mukhtar, Zhang, 2024]. In this paper, we achieve polynomial improvement over previous results. Specifically, we show how to improve the number of colors to $\tilde{O}(\Delta^{4/3+\epsilon})$ using space $\tilde{O}(n)$ deterministically, for any constant $\epsilon > 0$. This is the first deterministic result that bypasses the quadratic bound on the number of colors while using near-linear space.

Authors: Greg Bodwin, Gary Hoppenworth, Zihan Tan

In FOCS 2017, Borradaille, Le, and Wulff-Nilsen addressed a long-standing open problem by proving that minor-free graphs have light spanners. Specifically, they proved that every $K_h$-minor-free graph has a $(1+\epsilon)$-spanner of lightness $O_{\epsilon}(h \sqrt{\log h})$, hence constant when $h$ and $\epsilon$ are regarded as constants. We extend this result by showing that a more expressive size/stretch tradeoff is available. Specifically: for any positive integer $k$, every $n$-node, $K_h$-minor-free graph has a $(2k-1)$-spanner with sparsity \[O\left(h^{\frac{2}{k+1}} \cdot \text{polylog } h\right),\] and a $(1+\epsilon)(2k-1)$-spanner with lightness \[O_{\epsilon}\left(h^{\frac{2}{k+1}} \cdot \text{polylog } h \right).\] We further prove that this exponent $\frac{2}{k+1}$ is best possible, assuming the girth conjecture. At a technical level, our proofs leverage the recent improvements by Postle (2020) to the remarkable density increment theorem for minor-free graphs.

Authors: S. Mundhra

We present the first explicit comparison-based algorithm that sorts the sumset $X + Y = \{x_i + y_j,\ \forall 0 \le i, j < n\}$, where $X$ and $Y$ are sorted arrays of real numbers, in optimal $O(n^2)$ time and comparisons. While Fredman (1976) proved the theoretical existence of such an algorithm, a concrete construction has remained open for nearly five decades. Our algorithm exploits the structured monotonicity of the sumset matrix to perform amortized constant-comparisons and insertions, eliminating the $\log(n)$ overhead typical of comparison-based sorting. We prove correctness and optimality in the standard comparison model, extend the method to $k$-fold sumsets with $O(n^k)$ performance, and outline potential support for dynamic updates. Experimental benchmarks show significant speedups over classical algorithms such as MergeSort and QuickSort when applied to sumsets. These results resolve a longstanding open problem in sorting theory and contribute novel techniques for exploiting input structure in algorithm design.

Authors: Artur Czumaj, Guichen Gao, Mohsen Ghaffari, Shaofeng H. -C. Jiang

The $k$-center problem is a fundamental optimization problem with numerous applications in machine learning, data analysis, data mining, and communication networks. The $k$-center problem has been extensively studied in the classical sequential setting for several decades, and more recently there have been some efforts in understanding the problem in parallel computing, on the Massively Parallel Computation (MPC) model. For now, we have a good understanding of $k$-center in the case where each local MPC machine has sufficient local memory to store some representatives from each cluster, that is, when one has $\Omega(k)$ local memory per machine. While this setting covers the case of small values of $k$, for a large number of clusters these algorithms require undesirably large local memory, making them poorly scalable. The case of large $k$ has been considered only recently for the fully scalable low-local-memory MPC model for the Euclidean instances of the $k$-center problem. However, the earlier works have been considering only the constant dimensional Euclidean space, required a super-constant number of rounds, and produced only $k(1+o(1))$ centers whose cost is a super-constant approximation of $k$-center. In this work, we significantly improve upon the earlier results for the $k$-center problem for the fully scalable low-local-memory MPC model. In the low dimensional Euclidean case in $\mathbb{R}^d$, we present the first constant-round fully scalable MPC algorithm for $(2+\varepsilon)$-approximation. We push the ratio further to $(1 + \varepsilon)$-approximation albeit using slightly more $(1 + \varepsilon)k$ centers. All these results naturally extends to slightly super-constant values of $d$. In the high-dimensional regime, we provide the first fully scalable MPC algorithm that in a constant number of rounds achieves an $O(\log n/ \log \log n)$-approximation for $k$-center.

Authors: Junyao Zhao

Online contention resolution scheme (OCRS) is a powerful technique for online decision making, which--in the case of matroids--given a matroid and a prior distribution of active elements, selects a subset of active elements that satisfies the matroid constraint in an online fashion. OCRS has been studied mostly for product distributions in the literature. Recently, universal OCRS, that works even for correlated distributions, has gained interest, because it naturally generalizes the classic notion, and its existence in the random-order arrival model turns out to be equivalent to the matroid secretary conjecture. However, currently very little is known about how to design universal OCRSs for any arrival model. In this work, we consider a natural and relatively flexible arrival model, where the OCRS is allowed to preselect (i.e., non-adaptively select) the arrival order of the elements, and within this model, we design simple and optimal universal OCRSs that are computationally efficient. In the course of deriving our OCRSs, we also discover an efficient reduction from universal online contention resolution to the matroid secretary problem for any arrival model, answering a question from Dughmi (2020).

Authors: Sanjeev Khanna, Aaron Putterman, Madhu Sudan

We study the problem of constructing hypergraph cut sparsifiers in the streaming model where a hypergraph on $n$ vertices is revealed either via an arbitrary sequence of hyperedge insertions alone ({\em insertion-only} streaming model) or via an arbitrary sequence of hyperedge insertions and deletions ({\em dynamic} streaming model). For any $\epsilon \in (0,1)$, a $(1 \pm \epsilon)$ hypergraph cut-sparsifier of a hypergraph $H$ is a reweighted subgraph $H'$ whose cut values approximate those of $H$ to within a $(1 \pm \epsilon)$ factor. Prior work shows that in the static setting, one can construct a $(1 \pm \epsilon)$ hypergraph cut-sparsifier using $\tilde{O}(nr/\epsilon^2)$ bits of space [Chen-Khanna-Nagda FOCS 2020], and in the setting of dynamic streams using $\tilde{O}(nr\log m/\epsilon^2)$ bits of space [Khanna-Putterman-Sudan FOCS 2024]; here the $\tilde{O}$ notation hides terms that are polylogarithmic in $n$, and we use $m$ to denote the total number of hyperedges in the hypergraph. Up until now, the best known space complexity for insertion-only streams has been the same as that for the dynamic streams. This naturally poses the question of understanding the complexity of hypergraph sparsification in insertion-only streams. Perhaps surprisingly, in this work we show that in \emph{insertion-only} streams, a $(1 \pm \epsilon)$ cut-sparsifier can be computed in $\tilde{O}(nr/\epsilon^2)$ bits of space, \emph{matching the complexity} of the static setting. As a consequence, this also establishes an $\Omega(\log m)$ factor separation between the space complexity of hypergraph cut sparsification in insertion-only streams and dynamic streams, as the latter is provably known to require $\Omega(nr \log m)$ bits of space.

Authors: Antoine Amarilli, Florin Manea, Tina Ringleb, Markus L. Schmid

It is well-known that checking whether a given string $w$ matches a given regular expression $r$ can be done in quadratic time $O(|w|\cdot |r|)$ and that this cannot be improved to a truly subquadratic running time of $O((|w|\cdot |r|)^{1-\epsilon})$ assuming the strong exponential time hypothesis (SETH). We study a different matching paradigm where we ask instead whether $w$ has a subsequence that matches $r$, and show that regex matching in this sense can be solved in linear time $O(|w| + |r|)$. Further, the same holds if we ask for a supersequence. We show that the quantitative variants where we want to compute a longest or shortest subsequence or supersequence of $w$ that matches $r$ can be solved in $O(|w| \cdot |r|)$, i. e., asymptotically no worse than classical regex matching; and we show that $O(|w| + |r|)$ is conditionally not possible for these problems. We also investigate these questions with respect to other natural string relations like the infix, prefix, left-extension or extension relation instead of the subsequence and supersequence relation. We further study the complexity of the universal problem where we ask if all subsequences (or supersequences, infixes, prefixes, left-extensions or extensions) of an input string satisfy a given regular expression.

Authors: Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff, Samson Zhou

We show that both clustering and subspace embeddings can be performed in the streaming model with the same asymptotic efficiency as in the central/offline setting. For $(k, z)$-clustering in the streaming model, we achieve a number of words of memory which is independent of the number $n$ of input points and the aspect ratio $\Delta$, yielding an optimal bound of $\tilde{\mathcal{O}}\left(\frac{dk}{\min(\varepsilon^4,\varepsilon^{z+2})}\right)$ words for accuracy parameter $\varepsilon$ on $d$-dimensional points. Additionally, we obtain amortized update time of $d\,\log(k)\cdot\text{polylog}(\log(n\Delta))$, which is an exponential improvement over the previous $d\,\text{poly}(k,\log(n\Delta))$. Our method also gives the fastest runtime for $(k,z)$-clustering even in the offline setting. For subspace embeddings in the streaming model, we achieve $\mathcal{O}(d)$ update time and space-optimal constructions, using $\tilde{\mathcal{O}}\left(\frac{d^2}{\varepsilon^2}\right)$ words for $p\le 2$ and $\tilde{\mathcal{O}}\left(\frac{d^{p/2+1}}{\varepsilon^2}\right)$ words for $p>2$, showing that streaming algorithms can match offline algorithms in both space and time complexity.

Authors: Sanjeev Khanna, Aaron Putterman, Madhu Sudan

We initiate the study of spectral sparsification for instances of Constraint Satisfaction Problems (CSPs). In particular, we introduce a notion of the \emph{spectral energy} of a fractional assignment for a Boolean CSP instance, and define a \emph{spectral sparsifier} as a weighted subset of constraints that approximately preserves this energy for all fractional assignments. Our definition not only strengthens the combinatorial notion of a CSP sparsifier but also extends well-studied concepts such as spectral sparsifiers for graphs and hypergraphs. Recent work by Khanna, Putterman, and Sudan [SODA 2024] demonstrated near-linear sized \emph{combinatorial sparsifiers} for a broad class of CSPs, which they term \emph{field-affine CSPs}. Our main result is a polynomial-time algorithm that constructs a spectral CSP sparsifier of near-quadratic size for all field-affine CSPs. This class of CSPs includes graph (and hypergraph) cuts, XORs, and more generally, any predicate which can be written as $P(x_1, \dots x_r) = \mathbf{1}[\sum a_i x_i \neq b \mod p]$. Based on our notion of the spectral energy of a fractional assignment, we also define an analog of the second eigenvalue of a CSP instance. We then show an extension of Cheeger's inequality for all even-arity XOR CSPs, showing that this second eigenvalue loosely captures the ``expansion'' of the underlying CSP. This extension specializes to the case of Cheeger's inequality when all constraints are even XORs and thus gives a new generalization of this powerful inequality which converts the combinatorial notion of expansion to an analytic property.

Right after the election I wrote a post predicting what would happen to higher education under Trump, most of which is coming true, but I had a massive failure of imagination missing the direct attacks on major universities. I won't detail all the challenges to higher ed, which change daily with every new executive order and court ruling. The Chronicle has a good tracker of these changes.

But often lost in all the news are the actual people who aren't making the news hurt by these actions, through no fault of their own: A student who had his visa cancelled while out of the country so he can't get back in. PhD students who just lost their funding when their advisor's grant was cancelled. A postdoc in a similar situation just months before he starts an academic job. A young faculty member who had to hold off submitting a Career award proposal until a TRO restored the indirect cost. A recently tenured professor at a good US university interviewing outside of the country. Potential students in other countries trying to decide if they should still go to school and build a life in the US. 

The number of people, grants and universities affected is still on the low end, nearly all students continue to study, graduate and work without any problems, and many universities have offered legal and financial support to affected students and faculty. In my humble opinion, the strong educational opportunities inside the US still greatly exceed those outside. Universities have weathered many challenges before: McCarthyism in the 50s, campus occupations and protests in the 60s, and budget challenges from the great depression, to the fiscal crisis and covid. Trump's time as president has an end date and we'll get through all of this, but it requires all of us to push back and remind the administration and the public about the important role our universities play in the health of the country.

And as much as it pains me to say this as a Cornell alum, I'm rooting for Harvard.

By Lance Fortnow