Theory of Computing Report

This is the second live blog of Lecture 7 of my graduate seminar “Feedback, Learning, and Adaptation.” A table of contents is here.

When talking about sequential decision making and optimal control, I can’t avoid discussing the mathematical concept of regret. Regret is the preferred theoretical metric for evaluating bandit algorithms, and bandit algorithms are a core method for online decision-making.

Invariably, every time I try to explain “regret,” I get the question, “Wait, why do we care about that?” So to have an answer that I can point to in the future, I’m going to write a few blog posts.

We can use the setup from the last blog. We have a two-player game with repeated interactions. In every round t,

1. Information x_t is revealed to both players.

2. Player One takes action u_t

3. Player Two takes action d_t

4. A score r_t is assigned based on the triple (x_t,u_t,d_t).

Player One is the “decision maker,” and their action has to be computable from a few lines of code. Their goal is to accumulate as high a score as possible, summed across all rounds. Player two wants the sum of all of the r_t to be as low as possible.

You could think of designing the optimal policy as an optimization problem. Given a description of what Player Two can do, you can design a strategy for Player One. If Player Two is totally random, you could perhaps maximize the expected score. If Player Two is deterministic, you could maximize the score assuming Player Two plays the best possible strategy against you. Regret provides a flexible framework for going beyond both of these formulations.

To define regret, we imagine a counterfactual world in which Player One knows something about Player Two’s strategy in advance. The regret of some strategy is the difference between the score of a policy built on knowing this secret of Player Two and the score of the strategy that has to learn as it goes. It is called regret because it estimates how much the score could be improved with the benefit of hindsight.

Sometimes this regret is really large. Consider the following example. In each round, Player Two thinks of a color, Red or Blue, and Player One has to guess which color Player Two is thinking of. Player One gets a 1 if they guess correctly and a 0 otherwise. Player Two agrees to choose their sequence in advance, but only reveal one number to Player One in each round. In the counterfactual world, Player One would know the entire sequence and would receive a perfect score. In reality, Player One can’t do better than guessing, so they would be hard-pressed to get more than half of the colors correct.

This is where regret gets confusing. We ask, what if Player One in the counterfactual world has the benefit of hindsight but is constrained in their strategies? In this color guessing game, what if Player One is forced to choose one color in their counterfactual world? They see the entire sequence but can only pick red or blue. In this case, if Player Two chooses an even number of Red and Blues, the omniscient yet restricted Player One can only get half of the answers correct. A real-world strategy of random guessing will fare just as well as this counterfactual strategy with the benefit of hindsight.

No matter how many times I explain it, I find this setup confusing. Let me write it again: The regret model requires two things: a secret of Player Two and a restricted strategy set of Player One. In the real world, Player One has a flexible strategy set, but is missing information. In the counterfactual world, Player One has a restricted strategy set, but extra knowledge. Regret bounds the difference in scores achieved in these two worlds.

You might ask why this particular example of color guessing is interesting. I’m not sure it is, but it’s the one we’ll use next week when discussing forecasting. When someone tells you that they have calibrated predictions, they are doing this sort of sleight of hand and comparing against something that you probably don’t actually care about.

But let’s spend some time discussing examples where regret is reasonable. I’ll start with the canonical example: the stochastic multiarmed bandit. If Player Two is random and stationary, then the best strategy in hindsight makes a lot more sense. In our game of colors, this is the multiarmed bandit problem, the most annoyingly named subject in decision making. In the classic version of this problem, you have two slot machines and want to find the one with the highest payout. Each round, you are allowed to choose one of the machines to play. We model the payout from each machine as an independent draw from a fixed probability distribution. These distributions have different means, and your goal is to devise a strategy that results in the highest expected payout.

What would the best policy do? No matter how clever you are, you can’t beat the strategy of only using the machine with the higher mean payout. If you knew the expected payouts in advance and your goal is to maximize the expected payout, you would use only the machine with the highest expected payout. Thus, we can think of the secret held by Player Two to be the mean payouts of each machine.

If you didn’t know this secret, what would you do? You’d probably spend some time with each machine, look at which one is giving you higher returns, and then pick that one forever. This seems like a reasonable strategy.1 But note that this strategy necessarily has nonzero regret, because you necessarily have to try both machines to figure out which one is best.

Any strategy you devise for the real world has a particular expected regret, which is the difference between the expected payout of playing the best machine and the expected value of your strategy. In the case of our multiarmed bandit, the worst regret is accrued by always playing the suboptimal machine. So the regret would grow linearly with the number of pulls. Bandit algorithms seek strategies for which regret grows sublinearly.

Outside the casino, variants of the stochastic multiarmed bandit are reasonable models for adaptive experimentation. Suppose you want to select between treatments A and B that maximizes the average benefit to some cohort of subjects. If you can randomly sample individuals from the cohort, there will be regret associated with the number of subjects assigned to the suboptimal treatment in a randomized experiment, and there will be regret associated with the chance your experiment selects the suboptimal treatment. You would like to minimize application of the wrong treatment, but also be pretty sure you are finding the right one. You can compare this to the policy that assigned everyone to the optimal policy in advance.

Tomorrow I’ll talk through three other examples where regret feels like the right concept to me. In hindsight, it’s not always worth the headaches and confusion associated with regret minimization, but there are enough positive examples to make it a concept worth understanding.

Subscribe now

By Ben Recht

The next TCS+ talk will take place this coming Wednesday, April 8th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Rahul Ilango from MIT will speak about “Gödel in Cryptography: Zero-Knowledge Proofs With No Interaction, No Setup, and Perfect Soundness” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: Gödel showed that there are true but unprovable statements. This was bad news for Hilbert, who hoped that every true statement was provable. In this talk, I’ll describe why Gödel’s result is, in fact, good news for cryptography.

Specifically, Gödel’s result allows for the following strange scenario: a cryptographic system S is insecure, but it is impossible to prove that S is insecure. As I will explain, in this scenario (defined carefully), S is secure for nearly all practical purposes.

Leveraging this idea, we effectively construct — under longstanding assumptions — a classically-impossible cryptographic dream object: “zero-knowledge proofs for NP with no interaction, no setup, and perfect soundness” (I won’t assume you know what this means!). As an application, our result lets one give an ordinary mathematical proof that a Sudoku puzzle is solvable without revealing how to solve it. Previously, it was not known how to do this.

Paper link: https://eccc.weizmann.ac.il/report/2025/095/

By plustcs

Authors: Fangjun Hu, Christian Kokail, Milan Kornjača, Pedro L. S. Lopes, Weiyuan Gong, Sheng-Tao Wang, Xun Gao, Stefan Ostermann

Learning quantum states from measurement data is a central problem in quantum information and computational complexity. In this work, we study the problem of learning to generate mixed states on a finite-dimensional lattice. Motivated by recent developments in mixed state phases of matter, we focus on arbitrary states in the trivial phase. A state belongs to the trivial phase if there exists a shallow preparation channel circuit under which local reversibility is preserved throughout the preparation. We prove that any mixed state in this class can be efficiently learned from measurement access alone. Specifically, given copies of an unknown trivial phase mixed state, our algorithm outputs a shallow local channel circuit that approximately generates this state in trace distance. The sample complexity and runtime are polynomial (or quasi-polynomial) in the number of qubits, assuming constant (or polylogarithmic) circuit depth and gate locality. Importantly, the learner is not given the original preparation circuit and relies only on its existence. Our results provide a structural foundation for quantum generative models based on shallow channel circuits. In the classical limit, our framework also inspires an efficient algorithm for classical diffusion models using only a polynomial overhead of training and generation.

Authors: Runshi Tang, Yuefeng Han, Anru R. Zhang

In this note, we propose a general framework for proving computational lower bounds in norm approximation by leveraging a reverse detection--estimation gap. The starting point is a testing problem together with an estimator whose error is significantly smaller than the corresponding computational detection threshold. We show that such a gap yields a lower bound on the approximation distortion achievable by any algorithm in the underlying computational class. In this way, reverse detection--estimation gaps can be turned into a general mechanism for certifying the hardness of approximating nontrivial norms. We apply this framework to the spectral norm of order-$d$ symmetric tensors in $\mathbb{R}^{p^d}$. Using a recently established low-degree hardness result for detecting nonzero high-order cumulant tensors, together with an efficiently computable estimator whose error is below the low-degree detection threshold, we prove that any degree-$D$ low-degree algorithm with $D \le c_d(\log p)^2$ must incur distortion at least $p^{d/4-1/2}/\operatorname{polylog}(p)$ for the tensor spectral norm. Under the low-degree conjecture, the same conclusion extends to all polynomial-time algorithms. In several important settings, this lower bound matches the best known upper bounds up to polylogarithmic factors, suggesting that the exponent $d/4-1/2$ captures a genuine computational barrier. Our results provide evidence that the difficulty of approximating tensor spectral norm is not merely an artifact of existing techniques, but reflects a broader computational barrier.

Authors: Deepanshu Kush

Since the breakthrough superpolynomial multilinear formula lower bounds of Raz (Theory of Computing 2006), proving such lower bounds against multilinear algebraic branching programs (mABPs) has been a longstanding open problem in algebraic complexity theory. All known multilinear lower bounds rely on the min-partition rank method, and the best bounds against mABPs have remained quadratic (Alon, Kumar, and Volk, Combinatorica 2020). We show that the min-partition rank method cannot prove superpolynomial mABP lower bounds: there exists a full-rank multilinear polynomial computable by a polynomial-size mABP. This is an unconditional barrier: new techniques are needed to separate $\mathsf{mVBP}$ from higher classes in the multilinear hierarchy. Our proof resolves an open problem of Fabris, Limaye, Srinivasan, and Yehudayoff (ECCC 2026), who showed that the power of this method is governed by the minimum size $N(n)$ of a combinatorial object called a $1$-balanced-chain set system, and proved $N(n) \le n^{O(\log n/\log\log n)}$. We prove $N(n) = n^{O(1)}$ by giving the chain-builder a binary choice at each step, biasing what was a symmetric random walk into one where the imbalance increases with probability at most $1/4$; a supermartingale argument combined with a multi-scale recursion yields the polynomial bound.

Authors: Jesse Beisegel, Ekkehard Köhler, Robert Scheffler, Martin Strehler

The Maximum (Minimum) Leaf Spanning Tree problem asks for a spanning tree with the largest (smallest) number of leaves. As spanning trees are often computed using graph search algorithms, it is natural to restrict this problem to the set of search trees of some particular graph search, e.g., find the Breadth-First Search (BFS) tree with the largest number of leaves. We study this problem for Generic Search (GS), BFS and Lexicographic Breadth-First Search (LBFS) using search trees that connect each vertex to its first neighbor in the search order (first-in trees) just like the classic BFS tree. In particular, we analyze the complexity of these problems, both in the classical and in the parameterized sense. Among other results, we show that the minimum and maximum leaf problems are in FPT for the first-in trees of GS, BFS and LBFS when parameterized by the number of leaves in the tree. However, when these problems are parameterized by the number of internal vertices of the tree, they are W[1]-hard for the first-in trees of GS, BFS and LBFS.

Authors: Tiange Li, Yinan Li, Youming Qiao, Dacheng Tao, Yingjie Wang

In Grochow and Qiao (SIAM J. Comput., 2021), the complexity class Tensor Isomorphism (TI) was introduced and isomorphism problems for groups, algebras, and polynomials were shown to be TI-complete. In this paper, we study average-case algorithms for several TI-complete problems over finite fields, including algebra isomorphism, matrix code conjugacy, and $4$-tensor isomorphism. Our main results are as follows. Over the finite field of order $q$, we devise (1) average-case polynomial-time algorithms for algebra isomorphism and matrix code conjugacy that succeed in a $1/Θ(q)$ fraction of inputs and (2) an average-case polynomial-time algorithm for the $4$-tensor isomorphism that succeeds in a $1/q^{Θ(1)}$ fraction of inputs. Prior to our work, algorithms for algebra isomorphism with rigorous average-case analyses ran in exponential time, albeit succeeding on a larger fraction of inputs (Li--Qiao, FOCS'17; Brooksbank--Li--Qiao--Wilson, ESA'20; Grochow--Qiao--Tang, STACS'21). These results reveal a finer landscape of the average-case complexities of TI-complete problems, providing guidance for cryptographic systems based on isomorphism problems. Our main technical contribution is to introduce the spectral properties of random matrices into algorithms for TI-complete problems. This leads to not only new algorithms but also new questions in random matrix theory over finite fields. To settle these questions, we need to extend both the generating function approach as in Neumann and Praeger (J. London Math. Soc., 1998) and the characteristic sum method of Gorodetsky and Rodgers (Trans. Amer. Math. Soc., 2021).

Authors: Shuyang Gong, Brice Huang, Shuangping Li, Mark Sellke

We study the binary perceptron, a random constraint satisfaction problem that asks to find a Boolean vector in the intersection of independently chosen random halfspaces. A striking feature of this model is that at every positive constraint density, it is expected that a $1-o_N(1)$ fraction of solutions are \emph{strongly isolated}, i.e. separated from all others by Hamming distance $Ω(N)$. At the same time, efficient algorithms are known to find solutions at certain positive constraint densities. This raises a natural question: can any isolated solution be algorithmically visible? We answer this in the negative: no algorithm whose output is stable under a tiny Gaussian resampling of the disorder can \emph{reliably} locate isolated solutions. We show that any stable algorithm has success probability at most $\frac{3\sqrt{17}-9}{4}+o_N(1)\leq 0.84233$. Furthermore, every stable algorithm that finds a solution with probability $1-o_N(1)$ finds an isolated solution with probability $o_N(1)$. The class of stable algorithms we consider includes degree-$D$ polynomials up to $D\leq o(N/\log N)$; under the low-degree heuristic \cite{hopkins2018statistical}, this suggests that locating strongly isolated solutions requires running time $\exp(\widetildeΘ(N))$. Our proof does not use the overlap gap property. Instead, we show via Pitt's correlation inequality that after a random perturbation of the disorder, the number of solutions located close to a pre-existing isolated solution cannot concentrate at $1$.

Authors: Xi Chen, Yuhao Li, Mihalis Yannakakis

We give an $O(\log^2 n)$-query algorithm for finding a Tarski fixed point over the $4$-dimensional lattice $[n]^4$, matching the $Ω(\log^2 n)$ lower bound of [EPRY20]. Additionally, our algorithm yields an ${O(\log^{\lceil (k-1)/3\rceil+1} n)}$-query algorithm for any constant $k$, improving the previous best upper bound ${O(\log^{\lceil (k-1)/2\rceil+1} n)}$ of [CL22]. Our algorithm uses a new framework based on \emph{safe partial-information} functions. The latter were introduced in [CLY23] to give a reduction from the Tarski problem to its promised version with a unique fixed point. This is the first time they are directly used to design new algorithms for Tarski fixed points.

Authors: Ivor van der Hoog, Henrik Reinstädtler, Eva Rotenberg

We present a new fully dynamic algorithm for maintaining convex hulls under insertions and deletions while supporting geometric queries. Our approach combines the logarithmic method with a deletion-only convex hull data structure, achieving amortised update times of $O(\log n \log \log n)$ and query times of $O(\log^2 n)$. We provide a robust and non-trivial implementation that supports point-location queries, a challenging and non-decomposable class of convex hull queries. We evaluate our implementation against the state of the art, including a new naive baseline that rebuilds the convex hull whenever an update affects it. On hulls that include polynomially many data points (e.g. $Θ(n^\varepsilon)$ for some $\varepsilon$), such as the ones that often occur in practice, our method outperforms all other techniques. Update-heavy workloads strongly favour our approach, which is in line with our theoretical guarantees. Yet, our method remains competitive all the way down to when the update to query ratio is $1$ to $10$. Experiments on real-world data sets furthermore reveal that existing fully dynamic techniques suffer from significant robustness issues. In contrast, our implementation remains stable across all tested inputs.

Authors: Reilly Browne, Hsien-Chih Chang

Given an unweighted graph $G$, the *minimum $r$-dominating set problem* asks for the smallest-cardinality subset $S$ such that every vertex in $G$ is within radius $r$ of some vertex in $S$. While the $r$-dominating set problem on planar graphs admits a PTAS from Baker's shifting/layering technique when $r$ is constant, it becomes significantly harder when $r$ can depend on $n$. Under the Exponential-Time Hypothesis, Fox-Epstein et al. [SODA 2019] showed that no efficient PTAS exists for the unbounded $r$-dominating set problem on planar graphs. One may also consider the harder *vertex-weighted metric $r$-dominating set*, where edges have lengths, vertices have positive weights, and the goal is to find an $r$-dominating set of minimum total weight. This led to the development of *bicriteria* algorithms that allow radius-$(1+\varepsilon)r$ balls while achieving a $1+\varepsilon$ approximation to the optimal weight. We establish the first *single-criteria* polynomial-time $O(1)$-approximation algorithm for the vertex-weighted metric $r$-dominating set on planar graphs, where $r$ is part of the input and can be arbitrarily large. Our algorithm applies the quasi-uniformity sampling of Chan et al. [SODA 2012] by bounding the *shallow cell complexity* of the radius-$r$ ball system to be linear in $n$. Two technical innovations enable this: 1. Since discrete ball systems on planar graphs are neither pseudodisks nor amenable to standard union-complexity arguments, we construct a *support graph* for arbitrary distance ball systems as contractions of Voronoi cells, with sparseness as a byproduct. 2. We assign each depth-($\geq 3$) cell to a unique 3-tuple of ball centers, enabling Clarkson-Shor techniques to reduce counting to depth-*exactly*-3 cells, which we prove are $O(n)$ by a geometric argument on our Voronoi contraction support.

Authors: Guokai Li, Jiaxin, Liang, Mo Liu, Yanzhe, Lei, Stefanus Jasin, Fenghua Yang, Preet Baxi

We study a Bayesian binary sequential hypothesis testing problem with multiple large language models (LLMs). Each LLM $j$ has per-query cost $c_j>0$, random waiting time with mean $μ_j>0$ and sub-Gaussian tails, and \emph{asymmetric} accuracies: the probability of returning the correct label depends on the true hypothesis $θ\in\{A,B\}$ and needs not be the same under $A$ and $B$. This asymmetry induces two distinct information rates $(I_{j,A}, I_{j,B})$ per LLM, one under each hypothesis. The decision-maker chooses LLMs sequentially, observes their noisy binary answers, and stops when the posterior probability of one hypothesis exceeds $1-α$. The objective is to minimize the sum of expected query cost and expected waiting cost, $\mathbb{E}[C_π] + \mathbb{E}[g(W_π)]$, where $C_π$ is the total query cost, $W_π$ is the total waiting time and $g$ is a polynomial function (e.g., $g(x)=x^ρ$ with $ρ\ge 1$). We prove that as the error tolerance $α\to0$, the optimal policy is asymptotically equivalent to one that uses at most two LLMs. In this case, a single-LLM policy is \emph{not} generically optimal: optimality now requires exploiting a two-dimensional tradeoff between information under $A$ and information under $B$. Any admissible policy induces an expected information-allocation vector in $\mathbb{R}_+^2$, and we show that the optimal allocation lies at an extreme point of the associated convex set when $α$ is relatively small, and hence uses at most two LLMs. We construct belief-dependent policies that first mix between two LLMs when the posterior is ambiguous, and then switch to a single ``specialist'' LLM when the posterior is sufficiently close to one of the hypotheses. These policies match the universal lower bound up to a $(1+o(1))$ factor as $α\rightarrow 0$.

Authors: Andrew Au

We prove that any algorithm computing the sum-exclude-self of an unsigned $d$-bit integer array of length $n$ under sublinear space must perform two linear passes over the input. More precisely, the algorithm must read at least $n-1$ input elements before any output cell receives its final value, and at least $n - \lfloor t/d \rfloor$ additional elements thereafter, where $t = o(nd)$ bits is the working memory size. This gives a total of $2n - 1 - \lfloor t/d \rfloor$ element reads. A trivial modification of the standard two-pass algorithm achieves this bound exactly for all practical input sizes. The proof uses this toy problem as a worked example to demonstrate the choke-point technique for proving sublinear-space lower bounds.

Authors: Andrei Feodorov, Sebastian Haslebacher

We present a new algorithm for finding an $ε$-approximate fixed point of an $\ell_\infty$-contracting function $f : [0, 1]^d \rightarrow [0, 1]^d$. Our algorithm is based on the query-efficient algorithm by Chen, Li, and Yannakakis (STOC 2024), but comes with an improved upper bound of $(\log \frac{1}ε)^{\mathcal{O}(d \log d)}$ on the overall runtime (while still being query-efficient). By combining this with a recent decomposition theorem for $\ell_\infty$-contracting functions, we then describe a second algorithm that finds an $ε$-approximate fixed point in $(\log \frac{1}ε)^{\mathcal{O}(\sqrt{d} \log d)}$ queries and time. The key observation here is that decomposition theorems such as the one for $\ell_\infty$-contracting maps often allow a trade-off: If an algorithm's runtime is worse than its query complexity in terms of the dependency on the dimension $d$, then we can improve the runtime at the expense of weakening the query upper bound. By well-known reductions, our results imply a faster algorithm for $ε$-approximately solving Shapley stochastic games.

Authors: Weiming Feng, Heng Guo, Minji Yang

We show polylogarithmic mixing time bounds for the alternating-scan sampler for positively weighted restricted Boltzmann machines. This is done via analysing the same chain and the Glauber dynamics for ferromagnetic two-spin systems, where we obtain new mixing time bounds up to the critical thresholds.

Authors: Shaofeng H. -C. Jiang, Yaonan Jin, Jianing Lou, Weicheng Wang

We study Euclidean $k$-Means under the Massively Parallel Computation (MPC) model, focusing on the \emph{fully-scalable} setting. Our main result is a fully-scalable $O((\log n/\log\log n)^2)$-approximation in $O(1)$ rounds. Previously, fully-scalable algorithms for $k$-Means either run in super-constant $O(\log\log n \cdot \log\log\log n)$ rounds, albeit with a better $O(1)$-approximation [Cohen-Addad et al., SODA'26], or suffer from bicriteria guarantees [Bhaskara and Wijewardena, ICML'18; Czumaj et al., ICALP'24]. Our algorithm also gives an $O(\log n/\log\log n)$-approximation for $k$-Median, which improves a recent $O(\log n)$-approximation [Goranci et al., SODA'26], and this $o(\log n)$ ratio breaks the fundamental barrier of tree embedding methods used therein. Our main technical contribution is a new variant of the MP algorithm [Mettu and Plaxton, SICOMP'03] that works for general metrics, whose new guarantee is the Lagrangian Multiplier Preserving (LMP) property, which, importantly, holds even under arbitrary distance distortions. Allowing distance distortion is crucial for efficient MPC implementations and useful for efficient algorithm design in general, whereas preserving the LMP property under distance distortion is known to be a significant technical challenge. As a byproduct of our techniques, we also obtain an $O(1)$-approximation to the optimal \emph{value} in $O(1)$ rounds, which conceptually suggests that achieving a true $O(1)$-approximation (for the solution) in $O(1)$ rounds may be a sensible goal for future study.

Authors: Matthias Bentert, Fedor V. Fomin, Petr A. Golovach

Many problems are known to be solvable in subexponential parameterized time when the input graph is planar. The bidimensionality framework of Demaine, Fomin, Hajiaghay, and Thilikos [JACM'05] and the treewidth-pattern-covering approach by Fomin, Lokshtanov, Marx, Pilipczuk, Pilipczuk, and Saurabh [SICOMP'22] give robust tools for designing such algorithms. However, there are still many problems for which we do not know whether subexponential parameterized algorithms exist. The bidimensionality framework is not able to handle weights or directed graphs and the treewidth-pattern-covering approach only works for finding connected solutions. Building on a result by Nederlof [STOC'20], we provide a framework that is able to solve a variety of problems in planar graphs in subexponential parameterized time for which this was previously not known (where the polynomial part of the running time is usually $O(n^{2.49})$). Our framework can handle weights, does not require solutions to contain only few connected components, and applies to cases where the number of potential patterns of a solution is exponential in the parameter. We then use the framework to show that various weighted problems like Weighted Partial Vertex Cover, Maximum-Weight Induced Forest, Minimum-Weight Rooted Simple Minor, and Maximum-Weight Rooted Parallel Induced Minor allow for subexponential parameterized algorithms. This was previously not known for any of them. Moreover, we present a very easy-to-use fragment of our framework. This fragment allows for significantly simpler proofs in the case of Maximum-Weight Independent Set and Maximum $(k, n-k)$-Cut and is able to show a subexponential parameterized algorithm for weighted versions of Densest $k$-Subgraph. Even the unweighted version was not known before and is stated as an open problem in the existing literature.

Authors: Sebastian Lüderssen, Stefan Neumann, Pan Peng

We study four-cycle counting in arbitrary order graph streams. We present a 3-pass algorithm for $(1+\varepsilon)$-approximating the number of four-cycles using $\widetilde{O}(m/\sqrt{T})$ space, where $m$ is the number of edges and $T$ the number of four-cycles in the graph. This improves upon a 3-pass algorithm by Vorotnikova using space $\widetilde{O}(m/T^{1/3})$ and matches a multi-pass lower bound of $Ω(m/\sqrt{T})$ by McGregor and Vorotnikova.

Authors: Dildar Ali, Ansh Jasrotia, Abishek Salaria, Suman Banerjee

How to utilize an allocated budget effectively for branding and promotion of a commercial house is an important problem, particularly when multiple advertising media are available. There exist multiple such media, and among them, two popular ones are billboards and social media advertisements. In this context, the question naturally arises: how should a budget be allocated to maximize total influence? Although there is significant literature on the effective use of budgets in individual advertising media, there are hardly any studies examining budget allocation across multiple advertising media. To bridge this gap, this paper introduces the \textsc{Budget Splitting Problem in Billboard and Social Network Advertisement}. We introduce the notion of \emph{interaction effect} to capture the additional influence due to triggers from multiple media of advertising. Using this notion, we propose a noble influence function $Φ(,)$ that captures the total influence and shows that this function is non-negative, monotone, and non-bisubmodular. We introduce \emph{bi-submodularity ratio $(γ)$} and \emph{generalized curvature $(α)$} to measure how close a function is to being bi-submodular and how far a function is from being modular, respectively. We propose the Randomized Greedy and Two-Phase Adaptive Greedy approach, where the influence function is non-bisubmodular and achieves an approximation guarantee of $\frac{1}α\left(1-e^ {-γα} \right)$. We conducted several experiments using real-world datasets and observed that the proposed solution approach's budget splitting leads to a greater influence than existing approaches.

Authors: Yannic Maus, Alexandre Nolin, Florian Schager

We obtain better algorithms for computing more balanced orientations and degree splits in LOCAL. Important to our result is a connection to the hypergraph sinkless orientation problem [BMNSU, SODA'25] We design an algorithm of complexity $\mathcal{O}(\varepsilon^{-1} \cdot \log n)$ for computing a balanced orientation with discrepancy at most $\varepsilon \cdot \mathrm{deg}(v)$ for every vertex $v \in V$. This improves upon a previous result by [GHKMSU, Distrib. Comput. 2020] of complexity $\mathcal{O}(\varepsilon^{-1} \cdot \log \varepsilon^{-1} \cdot (\log \log \varepsilon^{-1})^{1.71} \cdot \log n)$. Further, we show that this result can also be extended to compute undirected degree splits with the same discrepancy and in the same runtime. As as application we show that $(3 / 2 + \varepsilon)Δ$-edge coloring can now be solved in $\mathcal{O}(\varepsilon^{-1} \cdot \log^2 Δ\cdot \log n + \varepsilon^{-2} \cdot \log n)$ rounds in LOCAL. Note that for constant $\varepsilon$ and $Δ= \mathcal{O}(2^{\log^{1/3} n})$ this runtime matches the current state-of-the-art for $(2Δ- 1)$-edge coloring in [Ghaffari & Kuhn, FOCS'21].

Authors: Alexandre Dupont-Bouillard

In this study, we tackle the problem of finding a maximum \emph{co-3-plex}, which is a subset of vertices of an input graph, inducing a subgraph of maximum degree 2. We focus on the class of chordal graphs. By observing that the graph induced by a co-3-plex in a chordal graph is a set of isolated triangles and induced paths, we reduce the problem of finding a maximum weight co-3-plex in a graph $G$ to that of finding a maximum stable set in an auxiliary graph $\mathcal{A}(G)$ of exponential size. This reduction allows us to derive an exponential variable-sized linear programming formulation for the maximum weighted co-3-plex problem. We show that the pricing subproblem of this formulation reduces to solving a maximum vertex and edge weight induced path. Such a problem is solvable in polynomial time; therefore, this exhibits a polynomial time column generation algorithm solving the maximum co-3-plex problem on chordal graphs. Moreover, this machinery exhibits a new application for the maximum vertex and edge weighted induced path problems.

Authors: Mark Goh, Lara Caroline Pereira dos Santos, Matthias Sperl

The binary paint shop problem (BPSP) is an APX-hard optimization problem in which, given n car models that occur twice in a sequence of length 2n, the goal is to find a colouring sequence such that the two occurrences of each model are painted differently, while minimizing the number of times the paint is swapped along the sequence. A recent classical heuristic, known as the recursive star greedy (RSG) algorithm, is conjectured to achieve an expected paint swap ratio of 0.361, thereby outperforming the QAOA with circuit depth p = 7. Since the performance of the QAOA with logarithmic circuit depth is instance independent, the average paint swap ratio is upper-bounded by the QAOA, which numerical evidence suggests is approximately between 0.265 and 0.282. To provide hardware-relevant comparisons, we additionally implement the BPSP on a D-Wave Quantum Annealer Advantage 2, obtaining a minimum paint swap ratio of 0.320. Given that the QAOA with logarithmic circuit depth does not exhibit quantum advantage for sparse optimization problems such as the BPSP, this implies the existence of a classical algorithm that surpasses both the RSG algorithm and logarithmic depth QAOA. We provide numerical evidence that the Mean-Field Approximate Optimization Algorithm (MF-AOA) is one such algorithm that beats all known classical heuristics and quantum algorithms to date with a paint swap ratio of approximately 0.2799.

Authors: Aviad Rubinstein, Sahil Singla

We revisit three fundamental problems in algorithms under uncertainty: the Secretary Problem, Prophet Inequality, and Stochastic Probing, each subject to general downward-closed constraints. When elements have binary values, all three problems admit a tight $\tildeΘ(\log n)$-factor approximation guarantee. For general (non-binary) values, however, the best known algorithms lose an additional $\log n$ factor when discretizing to binary values, leaving a quadratic gap of $\tildeΘ(\log n)$ vs. $\tildeΘ(\log^2 n)$. We resolve this quadratic gap for all three problems, showing $\tildeΩ(\log^2 n)$-hardness for two of them and an $O(\log n)$-approximation algorithm for the third. While the technical details differ across settings, and between algorithmic and hardness proofs, all our results stem from a single core observation, which we call the Big-Decisions-First Principle: Under uncertainty, it is better to resolve high-stakes (large-value) decisions early.

Authors: Mahsa Derakhshan, Tao Yu

Randomized greedy algorithms form one of the simplest yet most effective approaches for computing approximate matchings in graphs. In this paper, we focus on the class of vertex-iterative (VI) randomized greedy matching algorithms, which process the vertices of a graph $G=(V,E)$ in some order $π$ and, for each vertex $v$, greedily match it to the first available neighbor according to a preference order $σ(v)$. Various VI algorithms have been studied, each corresponding to a different distribution over $π$ and $σ(v)$. We develop a unified framework for analyzing this family of algorithms and use it to obtain improved approximation ratios for Ranking and FRanking, the state-of-the-art randomized greedy algorithms for the random-order and adversarial-order settings, respectively. In Ranking, the decision order is drawn uniformly at random and used as the common preference order, whereas FRanking uses an adversarial decision order and a uniformly random preference order shared by all vertices. We obtain an approximation ratio of $0.560$ for Ranking, improving on the $0.5469$ bound of Derakhshan et al. [SODA 2026]. For FRanking, we obtain a ratio of $0.539$, improving on the $0.521$ bound of Huang et al. [JACM 2020]. These results also imply state-of-the-art approximation ratios for oblivious matching and fully online matching problems on general graphs. Our analysis framework also enables us to prove improved approximation ratios for graphs with no short odd cycles. Such graphs form an intermediate class between general graphs and bipartite graphs. In particular, we show that Ranking is at least $0.570$-competitive for graphs that are both triangle-free and pentagon-free. For graphs whose shortest odd cycle has length at least $129$, we prove that Ranking is at least $0.615$-competitive.

For those of you who haven’t seen, there were actually two “bombshell” QC announcements this week. One, from Caltech, including friend-of-the-blog John Preskill, showed how to do quantum fault-tolerance with lower overhead than was previously known, by using high-rate codes, which could work for example in neutral-atom architectures (or possibly other architectures that allow nonlocal operations, like trapped ions). The second bombshell, from Google, gave a lower-overhead implementation of Shor’s algorithm to break 256-bit elliptic curve cryptography.

Notably, out of an abudance of caution, the Google team chose to “publish” its result via a cryptographic zero-knowledge proof that their circuit exists (so, without revealing the details to attackers). This is the first time I’ve ever seen a new mathematical result actually announced that way, although I understand that there’s precedent in the 1500’s, when mathematicians would (for example) prove their ability to solve quartic equations by challenging their rivals to duels. I’m not sure how much it will actually help, as once other groups know that a smaller circuit exists, it might be only a short time until they’re able to find it as well.

Neither of these results change the basic principles of QC that we’ve known for decades, but they do change the numbers.

When you put both of them together, Bitcoin signatures for example certainly look vulnerable to quantum attack earlier than was previously known!  In particular, the Caltech group estimates that a mere 25,000 physical qubits might suffice for this, where a year ago the best estimates were in the millions. How much time will this save — maybe a year?  Subtracting, of course, off a number of years that no one knows.

In any case, these results provide an even stronger impetus for people to upgrade now to quantum-resistant cryptography.  They—meaning you, if relevant—should really get on that!

When I got an early heads-up about these results—especially the Google team’s choice to “publish” via a zero-knowledge proof—I thought of Frisch and Peierls, calculating how much U-235 was needed for a chain reaction in 1940, but not publishing it, even though the latest results on nuclear fission had been openly published just the year prior. Will we, in quantum computing, also soon cross that threshold? But I got strong pushback on that analogy from the cryptography and cybersecurity people who I most respect. They said: we have decades of experience with this, and the answer is that you publish. And, they said, if publishing causes people still using quantum-vulnerable systems to crap their pants … well, maybe that’s what needs to happen right now.

Naturally, journalists have been hounding me for comments, though it was the worst possible week, when I needed to host like four separate visitors in Austin. I hope this post helps! Please feel free to ask questions or post further details in the comments.

And now, with no time for this blog post to leaven and rise, I need to go home for my family’s Seder. Happy Passover!

By Scott

A sheet of a4 paper has aspect ratio \(1:\sqrt2\). This means you can crease it along the shorter of its two midlines to get two rectangles with the same aspect ratio (of a5 size) and continue in the same way recursively.

Now, whenever you subdivide one rectangle into two smaller rectangles in this recursion, connect the centerpoints of the two new rectangles by a line segment. The union of all of these line segments is a fractal, the H-tree.

It comes arbitrarily close to any point of the initial rectangle, so its closure is the whole rectangle and its fractal dimension is two. But the points that belong to the H-tree (normalized with one corner of the rectangle at the origin) all have at least one coordinate that is a dyadic rational multiple of one of the rectangle sides. So as a subset of a countable union of axis-parallel lines, the H-tree has measure zero.

At each finite level of recursive construction (using closed line segments) the union of the segments is a kind of topological tree called a dendroid. Roughly this means that its a connected compact set with a unique arc connecting each two points. The full H-tree is not compact (it is not closed: its closure is a different set, the whole rectangle). But this is not the only way that it is not tree-like: it no longer has the property of having a unique arc connecting each two points! This is because it has certain simple closed curves as subsets, within which you can connect pairs of points in two different ways around the curve.

In this it differs from some other fractal space-filling trees like the one below, which might be called an X-tree. An X-tree can be formed by recursively subdividing a square into four smaller squares, adding an open line segment for the diagonal of each square. Or, instead, you could form an X-tree the way my code drew it: start with a grid of a power of two size, draw the diagonals of the whole grid, and then remove (or redraw as white) the grid points whose coordinates have binary representations ending in differing numbers of \(0\) bits. You can find arcs of the X-tree whose two ends get arbitrarily close to each other, but they do not form simple closed curves because their limit point is missing. Instead, in the H-tree, a branch of the tree can have an interior point of another segment as its limit point, so the limit point is not missing.

Looking again at the H-tree, one can see additional tree-like structures in the negative space where the H-tree isn’t.

It’s common to see planar surfaces divided up by pairs of interdigitating trees: the two trees of a river network and of the ridgelines separating the river’s branches are a familiar example.

I’ve used this idea of interdigitating trees in several of my research papers and in several old posts here. The complement of a tree would have a tree-like skeleton (for instance the X-tree has a \(45^\circ\)-rotated X-tree-like dual skeleton). But because the H-tree is not a tree, its interdigitated forest has many separate fractal trees. These trees are not exactly the same as the connected components of the complement of the H-tree: like the H-tree itself their points have one coordinate that is a dyadic rational multiple of the initial rectangle side, so they miss many points of the outer rectangle. But I think they have the same closures as the connected components.

(Discuss on Mastodon)

By David Eppstein

I blogged about Pope Leo XIV here. Pope Leo XIV has an undergraduate degree in mathematics. He saw my post and asked for my help with his latest encyclical. 

LEO: Let's have lunch together at Popeyes.

BILL: Why Popeyes?

LEO: The name is Pope-yes so I get a discount.

BILL: Your treat. [We met at Pope-yes and had the following discussion.]

LEO: I am working on an encyclical to resolve the tension between miracles in the Bible and modern science. 

BILL: What's the issue?

LEO: The Bible has miracles in it that seem to violate the laws of science. There are a few ways to resolve this cosmic conflict.

a) The miracles are allegorical. This is insulting to both God and Man. 

b) The miracles can be explained by natural phenomena. For example:

The Red Sea was split by  a big wind. This is acceptable. The timing of the big wind is the miracle.

BILL: Let me guess the problem: There are some miracles that cannot fit into modern science.

LEO: Exactly!  And I hope that Christians who are scientists (not to be confused with Christian Science, see here) will take up the study of miracles and see how they can fit into modern science.

BILL: Give me an example of a miracle that cannot be resolved with modern science and we'll see what we can do about that.

LEO:  Recall the miracle of loaves and fishes:

---------------------------------------------

A crowd of 4000 came to hear Jesus preach. When he was done they were hungry. 

Jesus told his disciples: 

I have compassion for these people; they have already been with me three days and have nothing to eat.  I do not want to send them away hungry, or they may collapse on the way. What food do we have?

The disciples responded:

Seven loaves and a few small fish.

Jesus told the crowd to sit down on the ground. Then he took the seven loaves and the fish and when he had given thanks, he broke them and gave them to the disciples, and they in turn gave to the people. They all ate and were satisfied. There were even leftovers. 

--------------------------------------------

So how could Jesus take seven loaves of bread and a few fish and feed thousands of people? How can this be explained with modern science?

BILL: I have a way to resolve it but you may not like it.

LEO: Let's hear it.

BILL: Jesus used the Banach-Tarski paradox  (see here) --- when he broke the bread,  he divided one loaf into 5 pieces, some of which were not measurable, and put them back together to get two loaves. Repeat until you can feed 5000 people. Same with the fishes.

LEO: Great! Why wouldn't I like that?

BILL: It only works if you're pro-(axiom of) choice. 

LEO: I'll have to run this by a subset of my advisors.

BILL: Which subset?

LEO: The Large Cardinals

By gasarch

Since the breakthrough superpolynomial multilinear formula lower bounds of Raz (Theory of Computing 2006), proving such lower bounds against multilinear algebraic branching programs (mABPs) has been a longstanding open problem in algebraic complexity theory. All known multilinear lower bounds rely on the min-partition rank method, and the best bounds against mABPs have remained quadratic (Alon, Kumar, and Volk, Combinatorica 2020). We show that the min-partition rank method cannot prove superpolynomial mABP lower bounds: there exists a full-rank multilinear polynomial computable by a polynomial-size mABP. This is an unconditional barrier: new techniques are needed to separate mVBP from higher classes in the multilinear hierarchy. Our proof resolves an open problem of Fabris, Limaye, Srinivasan, and Yehudayoff (ECCC 2026), who showed that the power of this method is governed by the minimum size $N(n)$ of a combinatorial object called a $1$-balanced-chain set system, and proved $N(n) \le n^{O(\log n/\log\log n)}$. We prove $N(n) = n^{O(1)}$ by giving the chain-builder a binary choice at each step, biasing what was a symmetric random walk into one where the imbalance increases with probability at most $1/4$; a supermartingale argument combined with a multi-scale recursion yields the polynomial bound.

Authors: Andrew Krapivin, Benjamin Przybocki, Bernardo Subercaseaux

We present several novel encodings for cardinality constraints, which use fewer clauses than previous encodings and, more importantly, introduce new generally applicable techniques for constructing compact encodings. First, we present a CNF encoding for the $\text{AtMostOne}(x_1,\dots,x_n)$ constraint using $2n + 2 \sqrt{2n} + O(\sqrt[3]{n})$ clauses, thus refuting the conjectured optimality of Chen's product encoding. Our construction also yields a smaller monotone circuit for the threshold-2 function, improving on a 50-year-old construction of Adleman and incidentally solving a long-standing open problem in circuit complexity. On the other hand, we show that any encoding for this constraint requires at least $2n + \sqrt{n+1} - 2$ clauses, which is the first nontrivial unconditional lower bound for this constraint and answers a question of Kučera, Savický, and Vorel. We then turn our attention to encodings of $\text{AtMost}_k(x_1,\dots,x_n)$, where we introduce "grid compression", a technique inspired by hash tables, to give encodings using $2n + o(n)$ clauses as long as $k = o(\sqrt[3]{n})$ and $4n + o(n)$ clauses as long as $k = o(n)$. Previously, the smallest known encodings were of size $(k+1)n + o(n)$ for $k \le 5$ and $7n - o(n)$ for $k \ge 6$.

Authors: Christoph Brauer, Arne Hindersmann, Timo de Wolff

In this article, we investigate vacuum leakage detection problems in composite manufacturing. Our approach uses Voronoi diagrams, a well-known structure in discrete geometry. The Voronoi diagram of the vacuum connection positions partitions the component surface. We use this partition to narrow down potential leak locations to a small area, making an efficient manual search feasible. To further reduce the search area, we propose refined Voronoi diagrams. We evaluate both variants using a novel dataset consisting of several hundred one- and two-leak positions along with their corresponding flow values. Our experimental results demonstrate that Voronoi-based predictive models are highly accurate and have the potential to resolve the leakage detection bottleneck in composite manufacturing.

Authors: Eunku Park

Computing the Voronoi diagram of mixed geometric objects in $R^3$ is challenging due to the high cost of exact geometric predicates via Cylindrical Algebraic Decomposition (CAD). We propose an efficient exact verification framework that characterizes the parameter space connectivity by computing certified topological transition sets. We analyze the fundamental non-quadric case: the trisector of two skew lines and one circle in $R^3$. Since the bisectors of circles and lines are not quadric surfaces, the pencil-of-quadrics analysis previously used for the trisectors of three lines is no longer applicable. Our pipeline uses exact symbolic evaluations to identify transition walls. Jacobian computations certify the absence of affine singularities, while projective closure shows singular behavior is isolated at a single point at infinity, $p_{\infty}$. Tangent-cone analysis at $p_{\infty}$ yields a discriminant $Δ_Q = 4ks^2(k-1)$, identifying $k=0,1$ as bifurcation values. Using directional blow-up coordinates, we rigorously verify that the trisector's real topology remains locally constant between these walls. Finally, we certify that $k=0,1$ are actual topological walls exhibiting reducible splitting. This work provides the exact predicates required for constructing mixed-object Voronoi diagrams beyond the quadric-only regime.

Authors: Seonmi Choi, Semin Oh, Jeong Rye Park, Seung Yeop Yang

Persistent homology is a central tool in topological data analysis, but its application to large and noisy datasets is often limited by computational cost and the presence of spurious topological features. Noise not only increases data size but also obscures the underlying structure of the data. In this paper, we propose the Refined Characteristic Lattice Algorithm (RCLA), a grid-based method that integrates data reduction with threshold-based denoising in a single procedure. By incorporating a threshold parameter $k$, RCLA removes noise while preserving the essential structure of the data in a single pass. We further provide a theoretical guarantee by proving a stability theorem under a homogeneous Poisson noise model, which bounds the bottleneck distance between the persistence diagrams of the output and the underlying shape with high probability. In addition, we introduce an automatic parameter selection method based on nearest-neighbor statistics. Experimental results demonstrate that RCLA consistently outperforms existing methods, and its effectiveness is further validated on a 3D shape classification task.

Authors: Andreas Bluhm, Matthias C. Caro, Francisco Escudero Gutiérrez, Junseo Lee, Aadil Oufkir, Cambyse Rouzé, Myeongjin Shin

In this work, we study the problems of certifying and learning quantum $k$-local Hamiltonians, for a constant $k$. Our main contributions are as follows: - Certification of Hamiltonians. We show that certifying a local Hamiltonian in normalized Frobenius norm via access to its time-evolution operator can be achieved with only $O(1/\varepsilon)$ evolution time. This is optimal, as it matches the Heisenberg-scaling lower bound of $Ω(1/\varepsilon)$. To our knowledge, this is the first optimal algorithm for testing a Hamiltonian property. A key ingredient in our analysis is the Bonami Hypercontractivity Lemma from Fourier analysis. - Learning Gibbs states. We design an algorithm for learning Gibbs states of local Hamiltonians in trace norm that is sample-efficient in all relevant parameters. In contrast, previous approaches learned the underlying Hamiltonian (which implies learning the Gibbs state), and thus inevitably suffered from exponential sample complexity scaling in the inverse temperature. - Certification of Gibbs states. We give an algorithm for certifying Gibbs states of local Hamiltonians in trace norm that is both sample and time-efficient in all relevant parameters, thereby solving a question posed by Anshu (Harvard Data Science Review, 2022).

Authors: Tillmann Miltzow

We introduce a lightweight and accessible approach to computation over the real numbers, with the aim of clarifying both the underlying concepts and their relevance in modern research. The material is intended for a broad audience, including instructors who wish to incorporate real computation into algorithms courses, their students, and PhD students encountering the subject for the first time. Rather than striving for completeness, we focus on a carefully selected set of results that can be presented and proved in a classroom setting. This allows us to highlight core techniques and recurring ideas while maintaining an approachable exposition. In some places, the presentation is intentionally informal, prioritizing intuition and practical understanding over full technical precision. We position our exposition relative to existing literature, including Matousek's lecture notes on ER-completeness and the recent compendium of ER-complete problems by Schaefer, Cardinal, and Miltzow. While these works provide deep and comprehensive perspectives, our goal is to offer an accessible entry point with proofs and examples suitable for teaching. Our approach follows modern formulations of real computation that emphasize binary input, real-valued witnesses, and restricted use of constants, aligning more closely with contemporary complexity theory, while acknowledging the foundational contributions of the Blum--Shub--Smale model.

Authors: Yury Makarychev

We study approximation algorithms for satisfiable and nearly satisfiable instances of ordering constraint satisfaction problems (ordering CSPs). Ordering CSPs arise naturally in ranking and scheduling, yet their approximability remains poorly understood beyond a few isolated cases. We introduce a general framework for designing approximation algorithms for ordering CSPs. The framework relaxes an input instance to an auxiliary ordering CSP, solves the relaxation, and then applies a randomized transformation to obtain an ordering for the original instance. This reduces the search for approximation algorithms to an optimization problem over randomized transformations. Our main technical contribution is to show that the power of this framework is captured by a structured class of transformations, which we call strong IDU transformations: every transformation used in the framework can be replaced by a strong IDU transformation without weakening the resulting approximation guarantee. We then classify strong IDU transformations and show that optimizing over them reduces to an explicit optimization problem whose dimension depends only on the maximum predicate arity $k$ and the desired precision $δ> 0$. As a consequence, for any finite ordering constraint language, we can compute a strong IDU transformation whose guarantee is within $δ$ of the best guarantee achievable by the framework, in time depending only on $k$ and $δ$. The framework applies broadly and yields nontrivial approximation guarantees for a wide class of ordering predicates.

Authors: Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk

Given an $H$-minor-free graph $G$ and an integer $k$, our main technical contribution is sampling in randomized polynomial time an induced subgraph $G'$ of $G$ and a tree decomposition of $G'$ of width $\widetilde{O}(k)$ such that for every $Z\subseteq V(G)$ of size $k$, with probability at least $\left(2^{\widetilde{O}(\sqrt{k})}|V(G)|^{O(1)}\right)^{-1}$, we have $Z \subseteq V(G')$ and every bag of the tree decomposition contains at most $\widetilde{O}(\sqrt{k})$ vertices of $Z$. Having such a tree decomposition allows us to solve a wide range of problems in (randomized) time $2^{\widetilde{O}(\sqrt{k})}n^{O(1)}$ where the solution is a pattern $Z$ of size $k$, e.g., Directed $k$-Path, $H$-Packing, etc. In particular, our result recovers all the algorithmic applications of the pattern-covering result of Fomin et al. [SIAM J. Computing 2022] (which requires the pattern to be connected) and the planar subgraph-finding algorithms of Nederlof [STOC 2020]. Furthermore, for $K_{h,3}$-free graphs (which include bounded-genus graphs) and for a fixed constant $d$, we signficantly strengthen the result by ensuring that not only $Z$ has intersection $\widetilde{O}(\sqrt{k})$ with each bag, but even the distance-$d$ neighborhood $N^d_{G}[Z]$ as well. This extension makes it possible to handle a wider range of problems where the neighborhood of the pattern also plays a role in the solution, such as partial domination problems and problems involving distance constraints.

Authors: Xiao Mao, Aviad Rubinstein

We present novel randomized approximation schemes for the Edit Distance (ED) problem and the Longest Common Subsequence (LCS) problem that, for any constant $ε>0$, compute a $(1+ε)$-approximation for ED and a $(1-ε)$-approximation for LCS in time $n^2 / 2^{\log^{Ω(1)}(n)}$ for two strings of total length at most $n$. This running time improves upon the classical quadratic-time dynamic programming algorithms by a quasi-polynomial factor. Our results yield significant insights into fine-grained complexity: Firstly, for ED, prior work indicates that any exact algorithm cannot be improved beyond a few logarithmic factors without refuting established complexity assumptions [Abboud, Hansen, Vassilevska Williams, Williams, 2016]; our quasi-polynomial speed-up shows a separation the complexity of approximate ED from that of exact ED, even for approximation factor arbitrarily close to $1$. Secondly, for LCS, obtaining similar approximation-time tradeoffs via deterministic algorithms would imply breakthrough circuit lower bounds [Chen, Goldwasser, Lyu, Rothblum, Rubinstein, 2019]; our randomized algorithm demonstrates derandomization hardness for LCS approximation.

Authors: Vincent Cohen-Addad, Marina Drygala, Nathan Klein, Ola Svensson

The Weighted Tree Augmentation Problem (WTAP) is a fundamental network design problem where the goal is to find a minimum-cost set of additional edges (links) to make an input tree 2-edge-connected. While a 2-approximation is standard and the integrality gap of the classic Cut LP relaxation is known to be at least 1.5, achieving approximation factors significantly below 2 has proven challenging. Recent advances of Traub and Zenklusen using local search culminated in a ratio of $1.5+ε$, establishing the state-of-the-art. In this work, we present a randomized approximation algorithm for WTAP with an approximation ratio below 1.49. Our approach is based on designing and rounding a strong linear programming relaxation for WTAP which incorporates variables that represent subsets of edges and the links used to cover them, inspired by lift-and-project methods like Sherali-Adams.

Authors: Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely, Andreas Wiese

The (Non-Preemptive) Throughput Maximization problem is a natural and fundamental scheduling problem. We are given $n$ jobs, where each job $j$ is characterized by a processing time and a time window, contained in a global interval $[0,T)$, during which~$j$ can be scheduled. Our goal is to schedule the maximum possible number of jobs non-preemptively on a single machine, so that no two scheduled jobs are processed at the same time. This problem is known to be strongly NP-hard. The best-known approximation algorithm for it has an approximation ratio of $1/0.6448 + \varepsilon \approx 1.551 + \varepsilon$ [Im, Li, Moseley IPCO'17], improving on an earlier result in [Chuzhoy, Ostrovsky, Rabani FOCS'01]. In this paper we substantially improve the approximation factor for the problem to $4/3+\varepsilon$ for any constant~$\varepsilon>0$. Using pseudo-polynomial time $(nT)^{O(1)}$, we improve the factor even further to $5/4+\varepsilon$. Our results extend to the setting in which we are given an arbitrary number of (identical) machines.

Authors: Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann, André Nichterlein, Camille Richer

We consider the well-studied problem of finding a spanning tree with minimum average distance between vertex pairs (called a MAD tree). This is a classic network design problem which is known to be NP-hard. While approximation algorithms and polynomial-time algorithms for some graph classes are known, the parameterized complexity of the problem has not been investigated so far. We start a parameterized complexity analysis with the goal of determining the border of algorithmic tractability for the MAD tree problem. To this end, we provide a linear-time algorithm for graphs of constant modular width and a polynomial-time algorithm for graphs of bounded treewidth; the degree of the polynomial depends on the treewidth. That is, the problem is in FPT with respect to modular width and in XP with respect to treewidth. Moreover, we show it is in FPT when parameterized by vertex integrity or by an above-guarantee parameter. We complement these algorithms with NP-hardness on split graphs.

Authors: Guillaume Chapuy, Guillem Perarnau

Given two functions $\mathbf{a}\!:\! [n] \rightarrow [n]$ and $\mathbf{b}\!:\! [n] \rightarrow [n]$ chosen uniformly at random, any word $w=w_1w_2\dots w_k\in \{a,b\}^k$ induces a random function $\mathbf{w}\!:\! [n] \rightarrow [n]$ by composition, i.e. $\mathbf{w}=φ_{w_k}\circ \dots \circ φ_{w_1}$ with $φ_a=\mathbf{a}$ and $φ_b=\mathbf{b}$. We study the following question: assuming $w$ is fixed but unknown, and $n$ goes to infinity, does one sample of $\mathbf{w}$ carry enough information to (partially) recover the word $w$ with good enough probability? We show that the length of $w$, and its exponent (largest $d$ such that $w={u}^d$ for some word ${u}$) can be recovered with high probability. We also prove that the random functions stemming from two different words are separated in total variation distance, provided that certain ``auto-correlation'' word-depending constant $c(w)$ is different for each of them. We give an explicit expression for $c(w)$ and conjecture that non-isomorphic words have different constants. We prove that this is the case assuming a major conjecture in transcendental number theory, Schanuel's conjecture.

• Firefox testing reveals as many as 5% of crashes are caused by hardware memory faults.

• Useless advice about making technical online content accessible, from my university’s head bureaucrat for online content accessibility bureaucracy (\(\mathbb{M}\)): “I would recommend avoiding PDFs altogether. They are extremely difficult to make accessible. If PDF format is absolutely necessary, create a document in Microsoft Office and then save it as a PDF.”

  Meanwhile, TeX Live 2026 + ltx-talk has been working for me in making pdf-format slide decks that pass all Acrobat accessibility checks, and I have moved on from experiments in using it to using it in production for all my course lecture slides. There is no real alternative to some form of TeX for content involving mathematics. This works. And if you’re already using LaTeX + beamer, it’s not difficult.

• Knuth’s packing puzzle (\(\mathbb{M}\)), a variant of Hoffman’s packing puzzle with 28 rectangular cuboids of carefully chosen shapes that should fit into a cube. Like Hoffman’s, this is difficult.

• White faceted aluminum flows through branching curved surfaces to form the pillars and dome of an architectural folly by Marc Fornes (\(\mathbb{M}\)).

• Wikipedia prohibits the use of LLMs to generate or rewrite article content (\(\mathbb{M}\)).

• Folded cyanotype art by Fritz Horstman (\(\mathbb{M}\)). More description.

• Sumerian clock (\(\mathbb{M}\)).

• Goran Konjevod’s curved and pleated origami vases (\(\mathbb{M}\)).

• Two years ago in connection with SAT-solver optimization of cascading stylesheet files I briefly mentioned the possibility that CSS might be Turing-complete, with a link to some attempts at demonstrating this via simulation of the Rule 110 cellular automaton (\(\mathbb{M}\)). These attempts were unsatisfactory for a couple of reasons: Rule 110’s completeness requires an infinite array of cells and a mostly-repeating pattern of initial cell values, the demonstrations had only finite arrays of cells of fixed size implemented as html objects, and each step of the simulation required some user interaction. Since then Clement Cherlin has found a better solution: a CSS Turing machine simulator whose only interaction requirement is that you move the mouse to a starting position within 5 seconds of opening the page. It still appears to use html elements as tape cells, so the tape has a predetermined size, but having a fixed and finite tape is less of a problem for Turing machines than for Rule 110. You can still do arbitrary computations for which you already know how much tape you’re going to need (which I guess can be described as Turing completeness). But determining whether the computation terminates is not an undecidable problem, because with a fixed tape size the total number of machine–tape states is finite.

• Women talking about their experience in mathematics (\(\mathbb{M}\)).

• Unexpected cutbacks in international student visa approvals by the Canadian government (far beyond their projected cutbacks) lead to program cuts and faculty layoffs at Canadian universities (\(\mathbb{M}\), via). According to an auditor report, the Canadian immigration department “did not know why approval rates were lower than projected”. The story focuses on BC but it appears that the effects are nationwide.

• A report on the huge amount of bot traffic putting strain on Wikipedia’s infrastructure, and the steps taken to counter it (\(\mathbb{M}\)).

• ICML’26 had two groups of reviewers one for which LLM use was forbidden and another for which it was not. Reviewers could state their preference and only those who claimed to be ok with forbidding LLM use were assigned to that group. But then, ~500 of the reviewers in the LLM-forbidden group were caught using LLMs through hidden watermarks in the papers they reviewed (\(\mathbb{M}\), via). As a consequence, ~400 of those reviewers had their submissions desk-rejected (~500 rejections).

• On the perspective of Manet’s Bar at the Folies-Bergère (\(\mathbb{M}\)). The face-on view of a waitress blankly staring across an empty bar while her reflection interacts with a customer seems like an impossible piece of artistic license, but Malcolm Park made a photographic reconstruction without even an in-shot camera reflection.

• Maybe everyone else already knew this geometric food trick (\(\mathbb{M}\)), but it took me years to discover it: subdivide your artichoke hearts into quarters or sixths before removing the choke, not after. That way, the nearly convex shape of the pieces, compared to the bowl shape of a whole heart, makes it much easier to remove the choke with a straight cut of a sharp knife.

• An improved algorithmic 4-color theorem (\(\mathbb{M}\)). Previous proofs could only produce a single reducible subconfiguration at a time; with linear time to find and handle each subconfiguration, they led to algorithms for 4-coloring planar graphs with \(O(n^2)\) total time. This new preprint claims to find a linear number of disjoint reducible subconfigurations, leading to an \(O(n\log n)\) algorithm.

By David Eppstein

This is a live blog of Lecture 7 of my graduate seminar “Feedback, Learning, and Adaptation.” A table of contents is here.

The Monday after Spring Break is always a weird class with people trickling in from their various excursions. So it’s an ideal time for a weird lecture. I decided it was time for some game theory.

The goal of this seminar was to focus on the power of feedback, to understand how to think about complex interconnected systems, and to understand how feedback design allows systems to “generalize” and “behave effectively in unknown future settings”.

In classical control, you can argue that feedback is for stabilization, for maintaining fixed points, for rejecting disturbances, or for recovering from failure. We covered some of these ideas in the first part of the course.

However, there’s another view of feedback, one that’s ubiquitous in machine learning and artificial intelligence. It’s the one that’s most prevalent in the quantitative social sciences. And, increasingly, based on my interactions with Berkeley graduate students, in robotics. That is the idea of feedback as a way to augment optimization.

In optimal control, feedback is used for the most narrow-minded reason: it lowers cost. Feedback policies, because they search over a larger space of policies, have lower cost than open-loop policies. That’s it. Feedback provides more information to the decision-maker, and a decision-maker who uses information will achieve a lower cost than one who doesn’t.

The optimal control model of feedback is game theoretic with rules of engagement staged as follows:

In every round t,

1. Information x_t is revealed to both players.

2. Player one takes action u_t

3. Player two takes action d_t

4. A score r_t is assigned based on the triple (x_t,u_t,d_t).

Player One is the “decision maker,” and their action has to be computable from a few lines of code. Their goal is to accumulate as high a score as possible, summed across all rounds. Player two wants the sum of all of the r_t to be as low as possible.

Player One’s action can be computed based on the rules of the game and all of the moves they’ve seen thus far. This is why if they optimally use the revealed information, they will have no worse cost than if they throw the information out.

Player Two is “the adversary.” Their power dictates how hard the game is for the decision maker. In some formulations, Player Two chooses oblivious random actions. You can make Player One’s life harder by making Player Two an omniscient god that knows Player One’s strategy in advance and can compute undecidable functions to topple them.

If there is a single round and Player Two is random, this game is called decision theory. We’ve collectively decided that the best strategies against random adversaries are those that maximize the expected value of the score. Don’t ask me why. If there are two rounds, it’s stochastic programming. If there are an infinite number of rounds, but there is no relationship between the rounds, it’s a bandit problem. If there are infinitely many rounds and the information follows a Markov chain, this is stochastic optimal control or reinforcement learning. In this case, when the costs are quadratic, the Markovian dynamics linear, and the adversary normally distributed, this is the linear quadratic regulator problem.

When Player Two is adversarial, Player One seeks a strategy to maximize their score against the best imaginable opponent. If there is a single round and Player Two is adversarial, this is called game theory or robust optimization. If there are an infinite number of rounds, but there is no relationship between the rounds, it’s a non-stochastic bandit problem. If there are infinitely many rounds and the information follows a Markov chain, this is robust optimal control. The linear version of this robust control problem is called the H_♾️ optimal control problem. Phew!

Now, every single one of these problems requires a slightly different algorithmic solution. That’s what keeps us in business. For every gradation, the solution details can fill a textbook. But they are all variations of the same game-theoretic framework. Having been formalized in the late 1940s and honed in the military-industrial boom of the 1950s and 1960s, this game-theoretic model of control and decision-making has been standard since the 1970s.

I’m not saying any of this is wrong, per se. I am saying that it is a bit limited as a framework. Part of the motivation for this course was to make better sense of this “graph” I made in a blog series a couple of years ago.

I observed that decision-making frameworks were distinguished by two variables: the impact each action had on a system external to the decision-maker (the x-axis) and the frequency with which decisions could be made (the y-axis). Game-theoretic decision making requires first figuring out where on this graph you want to operate. If you have a problem that calls for a specific level of impact and have the authority to act at a specific speed, you can find a particular solution using a proper game-theoretic formulation. How powerful you make Player Two will affect the complexity of your decision system and its conservatism. Since you have no idea what the future holds, your conception of Player Two is a subjective decision, but at least it’s one you can precisely describe. In this sense, the optimal framework is nice because you can declaratively compute decision policies based on systems modeling.

But if you have problems that span multiple regions of this space, or ones that lie below that red curve, the optimization framework gets stuck. If you have problems where the costs are ambiguous or variable, it’s hard to argue in favor of a policy based on models of cumulative reward. If you care about multiple levels of interaction impacts and speed, optimization stops being helpful.

The problem is that if you want to move into high-impact regimes where your authority is less than you’d desire, no single system gets you there. At some point, you have to think a bit more broadly about what systems push hard against this red curve. We’re forced above the red curve because of different limits, some fundamental, some conceptual. Physical law, computational efficiency, and even the ability to model keep us on one side of the curve.

I’m not sure this class helped me understand how to move beyond this curve, but it helped me understand a bit better why we’re stuck with it. The action-impact curve shows that single optimization problems can’t govern complex systems on their own. How do existing complex systems, be they natural or artificial, get around it? I’ll reserve the last two lectures of the class for this sort of abstract navel gazing.

Subscribe now

By Ben Recht

Authors: Pallavi Jain, Anshul Thakur

Kemeny Consensus is a well-known rank aggregation method in social choice theory. In this method, given a set of rankings, the goal is to find a ranking $Π$ that minimizes the total Kendall tau distance to the input rankings. Computing a Kemeny consensus is NP-hard, and even verifying whether a given ranking is a Kemeny consensus is coNP-complete. Fitzsimmons and Hemaspaandra [IJCAI 2021] established the computational intractability of achieving a desired consensus through manipulative actions. Kemeny Consensus is an optimisation problem related to Kemeny's rule. In this paper, we consider a decision problem related to Kemeny's rule, known as Kemeny Score, in which the goal is to decide whether there exists a ranking $Π$ whose total Kendall tau distance from the given rankings is at most $k$. Computation of Kemeny score is known to be NP-complete. In this paper, we investigate the impact of several manipulation actions on the Kemeny Score problem, in which given a set of rankings, an integer $k$, and a ranking $X$, the question is to decide whether it is possible to manipulate the given rankings so that the total Kendall tau distance of $X$ from the manipulated rankings is at most $k$. We show that this problem can be solved in polynomial time for various manipulation actions. Interestingly, these same manipulation actions are known to be computationally hard for Kemeny consensus.

Authors: Benjamin Przybocki, Bernardo Subercaseaux, Marijn J. H. Heule

Bounded Variable Addition (BVA) is a central preprocessing method in modern state-of-the-art SAT solvers. We provide a graph-theoretic characterization of which 2-CNF encodings can be constructed by an idealized BVA algorithm. Based on this insight, we prove new results about the behavior and limitations of BVA and its interaction with other preprocessing techniques. We show that idealized BVA, plus some minor additional preprocessing (e.g., equivalent literal substitution), can reencode any 2-CNF formula with $n$ variables into an equivalent 2-CNF formula with $(\tfrac{\lg(3)}{4}+o(1))\,\tfrac{n^2}{\lg n}$ clauses. Furthermore, we show that without the additional preprocessing the constant factor worsens from $\tfrac{\lg(3)}{4} \approx 0.396$ to $1$, and that no reencoding method can achieve a constant below $0.25$. On the other hand, for the at-most-one constraint on $n$ variables, we prove that idealized BVA cannot reencode this constraint using fewer than $3n-6$ clauses, a bound that we prove is achieved by actual implementations. In particular, this shows that the product encoding for at-most-one, which uses $2n+o(n)$ clauses, cannot be constructed by BVA regardless of the heuristics used. Finally, our graph-theoretic characterization of BVA allows us to leverage recent work in algorithmic graph theory to develop a drastically more efficient implementation of BVA that achieves a comparable clause reduction on random monotone 2-CNF formulas.

Authors: Daqing Wan

van Emde Boas (1981) conjectured that computing a shortest non-zero vector of a lattice in an Euclidean space is NP-hard. In this paper, we prove that this conjecture is true and hence de-randomize the classical randomness result of Ajtai (1998). Our proof builds on the construction of Bennet-Peifert (2023) on locally dense lattices via Reed-Solomon codes, and depends crucially on the work of Deligne on the Weil conjectures for higher dimensional varieties over finite fields.

Authors: Brian Kyanjo, Talea L. Mayo, Alexander A. Robel

ICESEE (ICE Sheet statE and parameter Estimator) is a Python-based, open-source data assimilation framework designed for seamless integration with ice sheet and Earth system models. It implements a parallel Ensemble Kalman Filter (EnKF) with full MPI support for scalable assimilation in state and parameter spaces. ICESEE uses a matrix-free update scheme from Evensen (2003), which avoids explicit forecast error covariance construction and eliminates the need for localization in high-dimensional, nonlinear systems. ICESEE also supports four EnKF variants, including a localized version for methodological testing. It enables indirect inference of unobserved model parameters through a hybrid assimilation-inversion strategy. The framework features modular coupling interfaces, adaptive state indexing, and efficient parallel I/O, making it extensible to a variety of modeling environments. ICESEE has been successfully coupled with ISSM, Icepack, and other models. In this study, we focus on applications with ISSM and Icepack, demonstrating ICESEE's interoperability, performance, scalability, and ability to improve state estimates and infer uncertain parameters. Performance benchmarks show strong and weak scaling, highlighting ICESEE's potential for large-scale, observation-constrained ice sheet reanalyses.

Authors: Gitan Balogh, June Cagan, Bea Fatima, Auguste H. Gezalyan, Danesh Sivakumar, Arushi Srinivasan, Yixuan Sun, Vahe Zaprosyan, David M. Mount

Neighborhood graphs and clustering algorithms are fundamental structures in both computational geometry and data analysis. Visualizing them can help build insight into their behavior and properties. The Ipe extensible drawing editor, developed by Otfried Cheong, is a widely used software system for generating figures. One particular aspect of Ipe is the ability to add Ipelets, which extend its functionality. Here we showcase a set of Ipelets designed to help visualize neighborhood graphs and clustering algorithms. These include: $\eps$-neighbor graphs, furthest-neighbor graphs, Gabriel graphs, $k$-nearest neighbor graphs, $k^{th}$-nearest neighbor graphs, $k$-mutual neighbor graphs, $k^{th}$-mutual neighbor graphs, asymmetric $k$-nearest neighbor graphs, asymmetric $k^{th}$-nearest neighbor graphs, relative-neighbor graphs, sphere-of-influence graphs, Urquhart graphs, Yao graphs, and clustering algorithms including complete-linkage, DBSCAN, HDBSCAN, $k$-means, $k$-means++, $k$-medoids, mean shift, and single-linkage. Our Ipelets are all programmed in Lua and are freely available.

Authors: Hridhaan Banerjee, Soren Brown, June Cagan, Auguste H. Gezalyan, Megan Hunleth, Veena Kailad, Chaewoon Kyoung, Rowan Shigeno, Yasmine Tajeddin, Andrew Wagger, Kelin Zhu, David M. Moun

Higher-order Voronoi diagrams and Delaunay mosaics in polygonal metrics have only recently been studied, yet no tools exist for visualizing them. We introduce a tool that fills this gap, providing dynamic interactive software for visualizing higher-order Voronoi diagrams and Delaunay mosaics along with clustering and tools for exploring overlap and outer regions in the Hilbert polygonal metric. We prove that $k^{th}$ order Voronoi cells are not always star-shaped and establish complexity bounds for our algorithm, which generates all order Voronoi diagrams at once. Our software unifies and extends previous tools for visualizing the Hilbert, Funk, and Thompson geometries.

Authors: Panagiotis Rigas, George Ioannakis, Ioannis Emiris

We introduce VoroFields, a hierarchical neural-field framework for approximating generalized Voronoi diagrams of finite geometric site sets in low-dimensional domains under arbitrary evaluable point-to-site distances. Instead of constructing the diagram combinatorially, VoroFields learns a continuous, differentiable surrogate whose maximizer structure induces the partition implicitly. The Voronoi cells correspond to maximizer regions of the field, with boundaries defined by equal responses between competing sites. A hierarchical decomposition reduces the combinatorial complexity by refining only near envelope transition strata. Experiments across site families and metrics demonstrate accurate recovery of cells and boundary geometry without shape-specific constructions.