Theory of Computing Report

June 2-5, 2026 University of Copenhagen https://sites.google.com/view/wact2026/ Registration deadline: February 28, 2026 Algebraic Complexity Theory investigates the computational complexity of algebraic problems, focusing on arithmetic circuits, polynomial computation, and algebraic models of computation. The goal of this workshop is to present recent advances in the field of algebraic complexity and to highlight the deep underlying … Continue reading 9th Workshop on Algebraic Complexity Theory

By shacharlovett

We give new algorithms for tree evaluation (S. Cook et. al. TOCT 2012) in the catalytic-computing model (Buhrman et. al. STOC 2014). Two existing approaches aim to solve tree evaluation in low space: on the one hand, J. Cook and Mertz (STOC 2024) give an algorithm for TreeEval running in super-logarithmic space $O(\log n\log\log n)$ and super-polynomial time $n^{O(\log\log n)}$. On the other hand, a simple reduction from TreeEval to circuit evaluation, combined with the result of Buhrman et al. (STOC 2014), gives a catalytic algorithm for TreeEval running in logarithmic $O(\log n)$ free space and polynomial time, but with polynomial catalytic space. We show that the latter result can be improved. We give a catalytic algorithm for TreeEval with logarithmic $O(\log n)$ free space, polynomial runtime, and subpolynomial $2^{\log^\epsilon n}$ catalytic space (for any $\epsilon > 0$). Our result opens a new line of attack on putting TreeEval in logspace, and immediately implies an improved simulation of time by catalytic space, by the reduction of Williams (STOC 2025). Our catalytic TreeEval algorithm is inspired by a connection to matching-vector families and private information retrieval, and improved constructions of (uniform) matching-vector families would imply improvements to our algorithm.

Symmetry of Information (SoI) is a fundamental result in Kolmogorov complexity stating that for all $n$-bit strings $x$ and $y$, $K(x,y) = K(y) + K(x \mid y)$ up to an additive error of $O(\log n)$ [ZL70]. In contrast, understanding whether SoI holds for time-bounded Kolmogorov complexity measures is closely related to longstanding open problems in complexity theory and cryptography, such as the P versus NP question [LW95, Hir22] and the existence of one-way functions [HILNO23, HLO24, HLN24]. In this paper, we prove that SoI fails for $rKt$ complexity, the randomized analogue of Levin's $Kt$ complexity [Lev84]. This is the first unconditional result of this type for a randomized notion of time-bounded Kolmogorov complexity. More generally, we establish a close relationship between the validity of SoI for $rKt$ and the existence of randomized algorithms approximating $rKt(x)$. Motivated by applications in cryptography, we also establish the failure of SoI for a related notion called $pKt$ complexity [HLO24], and provide an extension of the results to the average-case setting. Finally, we prove a near-optimal lower bound on the complexity of estimating conditional $rKt$, a result that might be of independent interest. Our findings complement those of [Ron04], who demonstrated the failure of SoI for $Kt$ complexity. In contrast, the randomized setting poses a significant challenge, which we overcome using insights from [KK25], structural results about $rKt$ implied by SoI, and techniques from meta-complexity [Oli19] and the theory of computational pseudorandomness [TV07].

Authors: Yoav Moran, Oded Schwartz, Shuncheng Yuan

Fast matrix multiplication algorithms are asymptotically faster than the classical cubic-time algorithm, but they are often slower in practice. One important obstacle is the use of complex coefficients, which increases arithmetic overhead and limits practical efficiency. This paper focuses on transforming complex-coefficient matrix multiplication schemes into equivalent real- or rational-coefficient ones. We present a systematic method that, given a complex-coefficient scheme, either constructs a family of equivalent rational algorithms or proves that no equivalent rational scheme exists. Our approach relies only on basic linear-algebraic properties of similarity transformations of complex matrices. This method recovers the previously known ad hoc results of Dumas, Pernet, and Sedoglavic (2025) and extends them to more general settings, including algorithms involving rational coefficients and square roots, with $i=\sqrt{-1}$ as a special case. Using this framework, we show that no rational scheme is equivalent to Smirnov's $\langle4,4,9,104\rangle$ $\mathbb{Q}[\sqrt{161}]$ algorithm (2022) and that no real scheme is equivalent to the $\langle4,4,4,48\rangle$ complex algorithm of Kaporin (2024). More generally, our approach can also be used to prove the non-existence of integer-coefficient schemes.

Authors: Thomas Boudier, Fabian Kuhn, Augusto Modanese, Ronja Stimpert, Jukka Suomela

We present a complete classification of the distributed computational complexity of local optimization problems in directed cycles for both the deterministic and the randomized LOCAL model. We show that for any local optimization problem $Π$ (that can be of the form min-sum, max-sum, min-max, or max-min, for any local cost or utility function over some finite alphabet), and for any \emph{constant} approximation ratio $α$, the task of finding an $α$-approximation of $Π$ in directed cycles has one of the following complexities: 1. $O(1)$ rounds in deterministic LOCAL, $O(1)$ rounds in randomized LOCAL, 2. $Θ(\log^* n)$ rounds in deterministic LOCAL, $O(1)$ rounds in randomized LOCAL, 3. $Θ(\log^* n)$ rounds in deterministic LOCAL, $Θ(\log^* n)$ rounds in randomized LOCAL, 4. $Θ(n)$ rounds in deterministic LOCAL, $Θ(n)$ rounds in randomized LOCAL. Moreover, for any given $Π$ and $α$, we can determine the complexity class automatically, with an efficient (centralized, sequential) meta-algorithm, and we can also efficiently synthesize an asymptotically optimal distributed algorithm. Before this work, similar results were only known for local search problems (e.g., locally checkable labeling problems). The family of local optimization problems is a strict generalization of local search problems, and it contains numerous commonly studied distributed tasks, such as the problems of finding approximations of the maximum independent set, minimum vertex cover, minimum dominating set, and minimum vertex coloring.

Authors: Thomas Delépine

$(1^a, 2^b)$-coloring is the problem of partitioning the vertex set of a graph into $a$ independent sets and $b$ 2-independent sets. This problem was recently introduced by Choi and Liu. We study the computational complexity and extremal properties of $(1^a, 2^b)$-coloring. We prove that this problem is NP-Complete even when restricted to certain classes of planar graphs, and we also investigate the extremal values of $b$ when $a$ is fixed and in some $(a + 1)$-colorable classes of graphs. In particular, we prove that $k$-degenerate graphs are $(1^k, 2^{O(\sqrt{n})})$-colorable, that triangle-free planar graphs are $(1^2, 2^{O(\sqrt{n})})$-colorable and that planar graphs are $(1^3, 2^{O(\sqrt{n})})$-colorable. All upper bounds obtained are tight up to a constant factor.

Authors: Matěj Doležálek, Mateusz Michałek

We present a family of flattening methods of tensors which we call Kronecker-Koszul flattenings, generalizing the famous Koszul flattenings and further equations of secant varieties studied among others by Landsberg, Manivel, Ottaviani and Strassen. We establish new border rank criteria given by vanishing of minors of Kronecker-Koszul flattenings. We obtain the first explicit polynomial equations -- tangency flattenings -- vanishing on secant varieties of Segre variety, but not vanishing on cactus varieties. Additionally, our polynomials have simple determinantal expressions. As another application, we provide a new, computer-free proof that the border rank of the $2\times2$ matrix multiplication tensor is $7$.

Authors: Christoph Grüne, Berit Johannes, James B. Orlin, Lasse Wulf

Many natural optimization problems derived from $\sf NP$ admit bilevel and multilevel extensions in which decisions are made sequentially by multiple players with conflicting objectives, as in interdiction, adversarial selection, and adjustable robust optimization. Such problems are naturally modeled by alternating quantifiers and, therefore, lie beyond $\sf NP$, typically in the polynomial hierarchy or $\sf PSPACE$. Despite extensive study of these problem classes, relatively few natural completeness results are known at these higher levels. We introduce a general framework for proving completeness in the polynomial hierarchy and $\sf PSPACE$ for problems derived from $\sf NP$. Our approach is based on a refinement of $\sf NP$, which we call $\sf NP$ with solutions ($\sf NP$-$\sf S$), in which solutions are explicit combinatorial objects, together with a restricted class of reductions -- solution-embedding reductions -- that preserve solution structure. We define $\sf NP$-$\sf S$-completeness and show that a large collection of classical $\sf NP$-complete problems, including Clique, Vertex Cover, Knapsack, and Traveling Salesman, are $\sf NP$-$\sf S$-complete. Using this framework, we establish general meta-theorems showing that if a problem is $\sf NP$-$\sf S$-complete, then its natural two-level extensions are $Σ_2^p$-complete, its three-level extensions are $Σ_3^p$-complete, and its $k$-level extensions are $Σ_k^p$-complete. When the number of levels is unbounded, the resulting problems are $\sf PSPACE$-complete. Our results subsume nearly all previously known completeness results for multilevel optimization problems derived from $\sf NP$ and yield many new ones simultaneously, demonstrating that high computational complexity is a generic feature of multilevel extensions of $\sf NP$-complete problems.

Authors: Stefan Goessner

The kinematics of particles and rigid bodies in the plane are investigated up to higher-order accelerations. Discussion of point trajectories leads from higher-order poles to higher-order Bresse circles of the moving plane. Symplectic geometry in vector space R^2 is used here as a new approach and leads to some new recursive vector formulas. This article is dedicated to the memory of Professor Pennestri.

Authors: Niels Holtgrefe, Jannik Schestag, Norbert Zeh

In the Maximize Phylogenetic Diversity problem, we are given a phylogenetic tree that represents the genetic proximity of species, and we are asked to select a subset of species of maximum phylogenetic diversity to be preserved through conservation efforts, subject to budgetary constraints that allow only k species to be saved. This neglects that it is futile to preserve a predatory species if we do not also preserve at least a subset of the prey it feeds on. Thus, in the Optimizing PD with Dependencies ($ε$-PDD) problem, we are additionally given a food web that represents the predator-prey relationships between species. The goal is to save a set of k species of maximum phylogenetic diversity such that for every saved species, at least one of its prey is also saved. This problem is NP-hard even when the phylogenetic tree is a star. The $α$-PDD problem alters PDD by requiring that at least some fraction $α$ of the prey of every saved species are also saved. In this paper, we study the parameterized complexity of $α$-PDD. We prove that the problem is W[1]-hard and in XP when parameterized by the solution size k, the diversity threshold D, or their complements. When parameterized by the vertex cover number of the food web, $α$-PDD is fixed-parameter tractable (FPT). A key measure of the computational difficulty of a problem that is FPT is the size of the smallest kernel that can be obtained. We prove that, when parameterized by the distance to clique, 1-PDD admits a linear kernel. Our main contribution is to prove that $α$-PDD does not admit a polynomial kernel when parameterized by the vertex cover number plus the diversity threshold D, even if the phylogenetic tree is a star. This implies the non-existence of a polynomial kernel for $α$-PDD also when parameterized by a range of structural parameters of the food web, such as its dist[...]

Authors: Swati Gupta, Jai Moondra, Mohit Singh

OMD and its variants give a flexible framework for OCO where the performance depends crucially on the choice of the mirror map. While the geometries underlying OPGD and OEG, both special cases of OMD, are well understood, it remains a challenging open question on how to construct an optimal mirror map for any given constrained set and a general family of loss functions, e.g., sparse losses. Motivated by parameterizing a near-optimal set of mirror maps, we consider a simpler question: is it even possible to obtain polynomial gains in regret by using mirror maps for geometries that interpolate between $L_1$ and $L_2$, which may not be possible by restricting to only OEG ($L_1$) or OPGD ($L_2$). Our main result answers this question positively. We show that mirror maps based on block norms adapt better to the sparsity of loss functions, compared to previous $L_p$ (for $p \in [1, 2]$) interpolations. In particular, we construct a family of online convex optimization instances in $\mathbb{R}^d$, where block norm-based mirror maps achieve a provable polynomial (in $d$) improvement in regret over OEG and OPGD for sparse loss functions. We then turn to the setting in which the sparsity level of the loss functions is unknown. In this case, the choice of geometry itself becomes an online decision problem. We first show that naively switching between OEG and OPGD can incur linear regret, highlighting the intrinsic difficulty of geometry selection. To overcome this issue, we propose a meta-algorithm based on multiplicative weights that dynamically selects among a family of uniform block norms. We show that this approach effectively tunes OMD to the sparsity of the losses, yielding adaptive regret guarantees. Overall, our results demonstrate that online mirror-map selection can significantly enhance the ability of OMD to exploit sparsity in online convex optimization.

Authors: Chendi Qian, Christopher Morris, Stefanie Jegelka, Christian Sohler

There has been a growing interest in using neural networks, especially message-passing neural networks (MPNNs), to solve hard combinatorial optimization problems heuristically. However, existing learning-based approaches for hard combinatorial optimization tasks often rely on supervised training data, reinforcement learning, or gradient estimators, leading to significant computational overhead, unstable training, or a lack of provable performance guarantees. In contrast, classical approximation algorithms offer such performance guarantees under worst-case inputs but are non-differentiable and unable to adaptively exploit structural regularities in natural input distributions. We address this dichotomy with the fundamental example of Uniform Facility Location (UniFL), a variant of the combinatorial facility location problem with applications in clustering, data summarization, logistics, and supply chain design. We develop a fully differentiable MPNN model that embeds approximation-algorithmic principles while avoiding the need for solver supervision or discrete relaxations. Our approach admits provable approximation and size generalization guarantees to much larger instances than seen during training. Empirically, we show that our approach outperforms standard non-learned approximation algorithms in terms of solution quality, closing the gap with computationally intensive integer linear programming approaches. Overall, this work provides a step toward bridging learning-based methods and approximation algorithms for discrete optimization.

Authors: Solveig Wittig, Antonis Vasileiou, Robert R. Nerem, Timo Stoll, Floris Geerts, Yusu Wang, Christopher Morris

In recent years, there has been growing interest in understanding neural architectures' ability to learn to execute discrete algorithms, a line of work often referred to as neural algorithmic reasoning. The goal is to integrate algorithmic reasoning capabilities into larger neural pipelines. Many such architectures are based on (message-passing) graph neural networks (MPNNs), owing to their permutation equivariance and ability to deal with sparsity and variable-sized inputs. However, existing work is either largely empirical and lacks formal guarantees or it focuses solely on expressivity, leaving open the question of when and how such architectures generalize beyond a finite training set. In this work, we propose a general theoretical framework that characterizes the sufficient conditions under which MPNNs can learn an algorithm from a training set of small instances and provably approximate its behavior on inputs of arbitrary size. Our framework applies to a broad class of algorithms, including single-source shortest paths, minimum spanning trees, and general dynamic programming problems, such as the $0$-$1$ knapsack problem. In addition, we establish impossibility results for a wide range of algorithmic tasks, showing that standard MPNNs cannot learn them, and we derive more expressive MPNN-like architectures that overcome these limitations. Finally, we refine our analysis for the Bellman-Ford algorithm, yielding a substantially smaller required training set and significantly extending the recent work of Nerem et al. [2025] by allowing for a differentiable regularization loss. Empirical results largely support our theoretical findings.

Authors: Antoine Amarilli, Sebastien Labbe, Charles Paperman

We introduce the task of out-of-order membership to a formal language L, where the letters of a word w are revealed one by one in an adversarial order. The length |w| is known in advance, but the content of w is streamed as pairs (i, w[i]), received exactly once for each position i, in arbitrary order. We study efficient algorithms for this task when L is regular, seeking tight complexity bounds as a function of |w| for a fixed target language. Most of our results apply to an algebraically defined variant dubbed out-of-order evaluation: this problem is defined for a fixed finite monoid or semigroup S, and our goal is to compute the ordered product of the streamed elements of w. We show that, for any fixed regular language or finite semigroup, both problems can be solved in constant time per streamed symbol and in linear space. However, the precise space complexity strongly depends on the algebraic structure of the target language or evaluation semigroup. Our main contributions are therefore to show (deterministic) space complexity characterizations, which we do for out-of-order evaluation of monoids and semigroups. For monoids, we establish a trichotomy: the space complexity is either Θ(1), Θ(log n), or Θ(n), where n = |w|. More specifically, the problem admits a constant-space solution for commutative monoids, while all non-commutative monoids require Ω(log n) space. We further identify a class of monoids admitting an O(log n)-space algorithm, and show that all remaining monoids require Ω(n) space. For general semigroups, the situation is more intricate. We characterize a class of semigroups admitting constant-space algorithms for out-of-order evaluation, and show that semigroups outside this class require at least Ω(log n) space.

Authors: Tomáš Masařík, Michał Włodarczyk, Mehmet Akif Yıldız

We consider the problem of partitioning the edges of a graph into as few paths as possible. This is a~subject of the classic conjecture of Gallai and a recurring topic in combinatorics. Regarding the complexity of partitioning a graph optimally, Peroché [Discret. Appl. Math., 1984] proved that it is NP-hard already on graphs of maximum degree four, even when we only ask if two paths suffice. We show that the problem is solvable in polynomial time on subcubic graphs and then we present an efficient algorithm for ``almost-subcubic'' graphs. Precisely, we prove that the problem is fixed-parameter tractable when parameterized by the edge-deletion distance to a subcubic graph. To this end, we reduce the task to model checking in first-order logic extended by disjoint-paths predicates ($\mathsf{FO}\text{+}\mathsf{DP}$) and then we employ the recent tractability result by Schirrmacher, Siebertz, Stamoulis, Thilikos, and Vigny [LICS 2024].

Authors: Timo Gervens, Martin Grohe, Louis Härtel, Philipp Silva da Fonseca

We revisit the algorithmic problem of reconstructing a graph from homomorphism counts that has first been studied in (Böker et al., STACS 2024): given graphs $F_1,\ldots,F_k$ and counts $m_1,\ldots,m_k$, decide if there is a graph $G$ such that the number of homomorphisms from $F_i$ to $G$ is $m_i$, for all $i$. We prove that the problem is NEXP-hard if the counts $m_i$ are specified in binary and $Σ_2^p$-complete if they are in unary. Furthermore, as a positive result, we show that the unary version can be solved in polynomial time if the constraint graphs are stars of bounded size.

Authors: Alexander Lindermayr, Guido Schäfer, Jens Schlöter, Leen Stougie

We consider the problem of online preemptive scheduling on a single machine to minimize the total flow time. In clairvoyant scheduling, where job processing times are revealed upon arrival, the Shortest Remaining Processing Time (SRPT) algorithm is optimal. In practice, however, exact processing times are often unknown. At the opposite extreme, non-clairvoyant scheduling, in which processing times are revealed only upon completion, suffers from strong lower bounds on the competitive ratio. This motivates the study of intermediate information models. We introduce a new model in which processing times are revealed gradually during execution. Each job consists of a sequence of operations, and the processing time of an operation becomes known only after the preceding one completes. This models many scheduling scenarios that arise in computing systems. Our main result is a deterministic $O(m^2)$-competitive algorithm, where $m$ is the maximum number of operations per job. More specifically, we prove a refined competitive ratio in $O(m_1 \cdot m_2)$, where $m_1$ and $m_2$ are instance-dependent parameters describing the operation size structure. Our algorithm and analysis build on recent advancements in robust flow time minimization (SODA '26), where jobs arrive with estimated sizes. However, in our setting we have no bounded estimate on a job's processing time. Thus, we design a highly adaptive algorithm that gradually explores a job's operations while working on them, and groups them into virtual chunks whose size can be well-estimated. This is a crucial ingredient of our result and requires a much more careful analysis compared to the robust setting. We also provide lower bounds showing that our bounds are essentially best possible. For the special case of scheduling with uniform obligatory tests, we show that SRPT at the operation level is $2$-competitive, which is best possible.

Authors: Ho-Lin Chen, Tsun Ming Cheung, Peng-Ting Lin, Meng-Tsung Tsai

We study the space complexity of computing a sparse subgraph of a directed graph that certifies connectivity in the streaming and distributed models. Formally, for a directed graph $G=(V,A)$ and $k\in \mathbb{N}$, a $k$-node strong connectivity certificate is a subgraph $H=(V,A')\subseteq G$ such that for every pair of distinct nodes $s,t\in V$, the number of pairwise internally node-disjoint paths from $s$ to $t$ in $H$ is at least $k$ or the corresponding number in $G$. In light of the inherent hardness of directed connectivity problems, several prior work focused on restricted graph classes, showing that several problems that are hard in general become efficiently solvable when the input graph is a tournament (i.e., a directed complete graph) (Chakrabarti et al. [SODA 2020]; Baweja, Jia, and Woddruff [ITCS 2022]), or close to a tournament in edit distance (Ghosh and Kuchlous [ESA 2024]). Extending this line of work, our main result shows, at a qualitative level, that the streaming complexity of strong connectivity certificates and related problems is parameterized by independence number, demonstrating a continuum of hardness for directed graph connectivity problems. Quantitatively, for an $n$-node graph with independence number $α$, we give $p$-pass randomized algorithms that compute a $k$-node strong connectivity certificate of size $O(αn)$ using $\tilde{O}(k^{1-1/p}αn^{1+1/p})$ space in the insertion-only model. For the lower bound, we show that even when $k=1$, any $p$-pass streaming algorithm for a 1-node strong connectivity certificate in the insertion-only model requires $Ω(αn/p)$ space. To derive these lower bounds, we introduce the gadget-embedding tournament framework to construct direct-sum-type hard instances with a prescribed independence number, which is applicable to lower-bounding a wide range of directed graph problems.

Authors: Yen-Cheng Chang, Tsun Ming Cheung, Meng-Tsung Tsai, Ting-An Wu

The geometric congruence problem is a fundamental building block in many computer vision and image recognition tasks. This problem considers the decision task of whether two point sets are congruent under translation and rotation. A related and more general problem, geometric hashing, considers the task of compactly encoding multiple point sets for efficient congruence queries. Despite its wide applications, both problems have received little prior attention in space-aware settings. In this work, we study the two-dimensional congruence testing and geometric hashing problem in the streaming model, where data arrive as a stream and the primary goal is to minimize the space usage. To meaningfully analyze space complexity, we address the underaddressed issue of input precision by working in the finite-precision rational setting: the input point coordinates are rational numbers of the form $p/q$ with $|p|, |q| \le U$. Our result considers a stronger variant of congruence testing called congruence identification, for which we obtain a 3-pass randomized streaming algorithm using $O(\log n(\log U+\log n))$ space. Using the congruence identification algorithm as a building block, we give a 6-pass $O(m\log n (\log n + \log U + \log m))$-space randomized streaming algorithm that outputs a hash function of length $O(\log n+\log U+\log m)$. Our key technical tool for achieving space efficiency is the use of complex moments. While complex moment methods are widely employed as heuristics in object recognition, their effectiveness is often limited by vanishing moment issues (Flusser and Suk [IEEE Trans. Image Process 2006]). We show that, in the rational setting, it suffices to track only $O(\log n)$ complex moments to ensure a non-vanishing moment, thus providing a sound theoretical guarantee for recovering a valid rotation in positive instances.

Authors: Yu Chen, Zihan Tan, Mingyang Yang

Given a large graph $G$ with a set of its $k$ vertices called terminals, a \emph{quality-$q$ flow sparsifier} is a small graph $G'$ that contains the terminals and preserves all multicommodity flows between them up to some multiplicative factor $q\ge 1$, called the \emph{quality}. Constructing flow sparsifiers with good quality and small size ($|V(G')|$) has been a central problem in graph compression. The most common approach of constructing flow sparsifiers is contraction: first compute a partition of the vertices in $V(G)$, and then contract each part into a supernode to obtain $G'$. When $G'$ is only allowed to contain all terminals, the best quality is shown to be $O(\log k/\log\log k)$ and $Ω(\sqrt{\log k/\log\log k})$. In this paper, we show that allowing a few Steiner nodes does not help much in improving the quality. Specifically, there exist $k$-terminal graphs such that, even if we allow $k\cdot 2^{(\log k)^{Ω(1)}}$ Steiner nodes in its contraction-based flow sparsifier, the quality is still $Ω\big((\log k)^{0.3}\big)$.

Authors: Mohammad Mahdian, Jieming Mao, Enze Sun, Kangning Wang, Yifan Wang

In the secretary problem, a set of secretary candidates arrive in a uniformly random order and reveal their values one by one. A company, who can only hire one candidate and hopes to maximize the expected value of its hire, needs to make irrevocable online decisions about whether to hire the current candidate. The classical framework of evaluating a policy is to compute its worst-case competitive ratio against the optimal solution in hindsight, and there the best policy -- the ``$1/e$ law'' -- has a competitive ratio of $1/e$. We propose an alternative evaluation framework through the lens of regret -- the worst-case additive difference between the optimal hindsight solution and the expected performance of the policy, assuming that each value is normalized between $0$ and $1$. The $1/e$ law for the classical framework has a regret of $1 - 1/e \approx 0.632$; by contrast, we show that the class of ``pricing curves'' algorithms can guarantee a regret of at most $1/4 = 0.25$ (which is tight within the class), and the class of ``best-only pricing curves'' algorithms can guarantee a regret of at most $0.190$ (with a lower bound of $0.171$). In addition, we show that in general, no policy can give a regret guarantee better than $0.152$. Finally, we discuss other objectives in our regret-minimization framework, such as selecting the top-$k$ candidates for $k > 1$, or maximizing revenue during the selection process.

Authors: Alexandros Kouridakis, Anay Mehrotra, Alkis Kalavasis, Constantine Caramanis

In truncated linear regression, samples $(x,y)$ are shown only when the outcome $y$ falls inside a certain survival set $S^\star$ and the goal is to estimate the unknown $d$-dimensional regressor $w^\star$. This problem has a long history of study in Statistics and Machine Learning going back to the works of (Galton, 1897; Tobin, 1958) and more recently in, e.g., (Daskalakis et al., 2019; 2021; Lee et al., 2023; 2024). Despite this long history, however, most prior works are limited to the special case where $S^\star$ is precisely known. The more practically relevant case, where $S^\star$ is unknown and must be learned from data, remains open: indeed, here the only available algorithms require strong assumptions on the distribution of the feature vectors (e.g., Gaussianity) and, even then, have a $d^{\mathrm{poly} (1/\varepsilon)}$ run time for achieving $\varepsilon$ accuracy. In this work, we give the first algorithm for truncated linear regression with unknown survival set that runs in $\mathrm{poly} (d/\varepsilon)$ time, by only requiring that the feature vectors are sub-Gaussian. Our algorithm relies on a novel subroutine for efficiently learning unions of a bounded number of intervals using access to positive examples (without any negative examples) under a certain smoothness condition. This learning guarantee adds to the line of works on positive-only PAC learning and may be of independent interest.

Authors: Binh-Minh Bui-Xuan, Florent Krasnopol, Bruno Monasson, Nathalie Sznajder

Temporal graphs are graphs where the presence or properties of their vertices and edges change over time. When time is discrete, a temporal graph can be defined as a sequence of static graphs over a discrete time span, called lifetime, or as a single graph where each edge is associated with a specific set of time instants where the edge is alive. For static graphs, Courcelle's Theorem asserts that any graph problem expressible in monadic second-order logic can be solved in linear time on graphs of bounded tree-width. We propose the first adaptation of Courcelle's Theorem for monadic second-order logic on temporal graphs that does not explicitly rely on the lifetime as a parameter. We then introduce the notion of derivative over a sliding time window of a chosen size, and define the tree-width and twin-width of the temporal graph's derivative. We exemplify its usefulness with meta theorems with respect to a temporal variant of first-order logic. The resulting logic expresses a wide range of temporal graph problems including a version of temporal cliques, an important notion when querying time series databases for community structures.

I sometimes assign open problems as extra credit problems. Some thoughts:

1) Do you tell the students the problems are open?

YES- it would be unfair for a student to work on something they almost surely won't get.

NO- Some Open Problems are open because people are scared to work on them. Having said that, I think P vs NP is beyond the one smart person phase or even the if they don't know it's hard maybe they can solve it phase.

NO- See Page 301 of this interview with George Dantzig where he talks about his mistaking an open problem for a homework and ... solving it.

CAVEAT---There are OPEN PROBLEMS!!! and there are open problems???  If I make up a problem, think about it for 30 minutes, and can't solve it, it's open but might not be hard. See next point. 

 I tell the students:

This is a problem I made up but could not solve. It may be that I am missing just one idea or combination of ideas so it is quite possible you will solve it even though I could not. Of course, it could be that it really is hard. 

A friend of mine who is not in academia thought that telling the students that I came up with a problem I could not solve, but maybe they can,  is a terrible idea. He said that if a student solves it, they will think worse of me. I think he's clearly wrong.  If I am enthused about their solution and give NO indication that I was close to solving it (even if I was) then there is no way they would think less of me.

Is there any reason why telling the students I could not solve it but they might be able to is a bad idea? 

2) Should Extra Credit count towards the grade? (We ignore that there are far more serious problems with grades with whatever  seems to make them obsolete: Calculators, Cliff  notes,  Cheating, Encyclopedias, Wikipedia, the Internet, ChatGPT, other AI, your plastic pal who's fun to be with.) 

No- if they count towards the grade then they are not extra credit. 

I tell the students they DO NOT count for the grade but they DO count for a letter I may write them.

What do you do? 

By gasarch

So, a group based in Sydney, Australia has put out a preprint with a new estimate of the resource requirements for Shor’s algorithm, claiming that if you use LDPC codes rather than the surface code, you should be able to break RSA-2048 with fewer than 100,000 physical qubits, which is an order-of-magnitude improvement over the previous estimate by friend-of-the-blog Craig Gidney. I’ve now gotten sufficiently many inquiries about it that it’s passed the threshold of blog-necessity.

A few quick remarks, and then we can discuss more in the comments section:

• Yes, this is serious work. The claim seems entirely plausible to me, although it would be an understatement to say that I haven’t verified the details. The main worry I’d have is simply that LDPC codes are harder to engineer than the surface code (especially for superconducting qubits, less so for trapped-ion), because you need wildly nonlocal measurements of the error syndromes. Experts (including Gidney himself, if he likes!) should feel free to opine in the comments.
  
• I have no idea by how much this shortens the timeline for breaking RSA-2048 on a quantum computer. A few months? Dunno. I, for one, had already “baked in” the assumption that further improvements were surely possible by using better error-correcting codes. But it’s good to figure it out explicitly.
  
• On my Facebook, I mused that it might be time for the QC community to start having a conversation about whether work like this should still be openly published—a concern that my friends in the engineering side of QC have expressed to me. I got strong pushback from cryptographer and longtime friend Nadia Heninger, who told me that the crypto community has already had this conversation for decades, and has come down strongly on the side of open publication, albeit with “responsible disclosure” waiting periods, which are often 90 days. While the stakes would surely be unusually high with a full break of RSA-2048, Nadia didn’t see that the basic principles there were any different. Nadia’s arguments updated me in the direction of saying that groups with further improvements to the resource requirements for Shor’s algorithm should probably just go ahead and disclose what they’ve learned, and the crypto community will have their backs as having done what they’ve learned over the decades was the right thing. Certainly, any advantage that such disclosure would give to hackers, who could take the new Shor circuits and simply submit them to the increasingly powerful QCs that will gradually come online via cloud services, needs to be balanced against the loud, clear, open warning the world will get to migrate faster to quantum-resistant encryption.
  
• I’m told that these days, the biggest practical game is breaking elliptic curve cryptography, not breaking Diffie-Hellman or RSA. Somewhat ironically, elliptic curve crypto is likely to fall to quantum computers a bit before RSA and Diffie-Hellman will fall, because ECC’s “better security” (against classical attacks, that is) led people to use 256-bit keys rather than 2,048-bit keys, and Shor’s algorithm mostly just cares about the key size.
  
• In the acknowledgments of the paper, I’m thanked for “thoughtful feedback on the title.” Indeed, their original title was about “breaking RSA-2048″ with 100,000 physical qubits. When they sent me a draft, I pointed out to them that they need to change it, since journalists would predictably misinterpret it to mean that they’d already done it, rather than simply saying that it could be done.

By Scott

We show an unconditional classical oracle separation between the class of languages that can be verified using a quantum proof (QMA) and the class of languages that can be verified with a classical proof (QCMA). Compared to the recent work of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC 2026), our proof is conceptually and technically simpler, and readily extends to other oracle separations. In particular, our techniques yield the first unconditional classical oracle separation between the class of languages that can be decided with quantum advice (BQP/qpoly) and the class of languages that can be decided with classical advice (BQP/poly), improving on the quantum oracle separation of Aaronson and Kuperberg (CCC 2007) and the classically-accessible classical oracle separation of Li, Liu, Pelecanos and Yamakawa (ITCS 2024). Our oracles are based on the code intersection problem introduced by Yamakawa and Zhandry (FOCS 2022), combined with codes that have extremely good list-recovery properties.

• Morphing between a polyhedron and its dual using 3d-printed scissor-link edges (\(\mathbb{M}\)) raises the question of which polyhedra can be realized in this way. The linked paper by Liao, Kiper, and Krishnan suggests that they need to be midscribed and have equal-length edges to avoid binding during the morph. A much weaker but obvious necessary condition is that for each pair of dual edges the lengths are equal. But it is unclear which polyhedra have realizations with this property.

• Frank Vigor Morley’s realizations of regular polygons using knotted paper strips (\(\mathbb{M}\)). Morley was the son of Frank Morley, a geometer known for Morley’s theorem on triangle trisectors.

• Type 8 pentagonal cobblestone tiling in Kleve, Germany.

• The Brouwer fixed-point theorem in action, as exhibited by Github labels (\(\mathbb{M}\), via): If you try to define a continuous function from text colors to contrasting background colors, there will be some text colors whose background is the same as the text rather than contrasting with it. Discontinuity is necessary to avoid this. This is from 2023 so I suspect the specific buggy behavior is long fixed but the phenomenon will recur for any attempt like this one to define a formula using only continuous building blocks.

• Complexity in Computer Science (\(\mathbb{M}\)), free online textbook, about to be published through Cambridge University Press.

• Archive.today / archive.is / archive.ph etc initiates a DDOS attack against a blogger they accused of doxing them, sparking calls to blacklist them from reference link archiving on Wikipedia (\(\mathbb{M}\)).

• The Lambek–Moser theorem (\(\mathbb{M}\)) is a bijective equivalence between two different-looking mathematical objects: partitions of the positive integers into two disjoint subsets, and pairs of almost-inverse monotone functions from positive integers to non-negative integers.

  Real monotone functions are inverse when their graphs are mirror reflections across the diagonal line \(y=x\). We can define something like a graph for an integer function, a staircase curve whose lowest point above any integer on the \(x\)-axis gives the function value; then two integer functions are almost-inverse when these curves are mirror reflections. The image below shows these two reflected staircase curves for the prime-counting function and its almost-inverse. This pair of functions corresponds to the partition of positive integers into prime and non-prime (composite or one).

  By using this equivalence to go from functions to partitions and back, you can sometimes get amazing formulas for sequences of integers that you might not expect to have a formula at all. For instance, the \(n\)th number that is not a \(k\)th power (for integer \(k>1\)) has the formula:

  \[n+\left\lfloor\sqrt[k]{n + \lfloor\sqrt[k]{n}\rfloor}\right\rfloor.\]

  Now a Good Article on Wikipedia.

  

• Lisa Dusseault crafts a cellular automaton lace scarf (\(\mathbb{M}\)).

• When science discourages correction: How publishers profit from mistakes (\(\mathbb{M}\)). Douglas Sheil and Erik Meijaard argue that the profit motive disincentivizes publishers from maintaining the integrity of the scientific record.

• As part of the Integrated Explicit Analytic Number Theory network, Terry Tao finds a need to revive tables of logarithms, with machine-verified proofs of their accuracy (\(\mathbb{M}\)).

• The Music of the Primes, Corinthia Beatrix Aberlé (\(\mathbb{M}\)). On connections between musical tuning systems and the Riemann zeta function.

• CCC vs GCC (\(\mathbb{M}\)). An LLM-generated compiler passes all unit tests but somehow manages to generate code that runs complex SQLite queries 158,000 times slower than GCC.

• I have been experimenting with ltx-talk as a replacement for beamer as a way to use LaTeX to make lecture slides (\(\mathbb{M}\)), in preparation for the April 24 doomsday in which all online content of all US universities is required to meet WCAG 2.1 A/AA accessibility standards (including properly tagged pdf). My test slide deck is based on beamer slides on union-find and its analysis from my graduate data structures course. It sort of works but is still obviously a work in progress.

  Minor issues:

  • This requires lualatex 2025-11-01 or more recent. I can run this in Overleaf Labs but cannot find a recent-enough MacTeX.

  • The LaTeX preamble is different and the formatting changes it makes were largely undocumented.

  • I needed a hack to make natbib work. Actually two hacks but one was already there for beamer.

  • I had to change \begin{frame}{Title} to \begin{frame}\frametitle{Title} everywhere.

  • I had to change \column{size} to \begin{column}{size} ... \end{column} everywhere.

  • The tabular environment needs to be tagged for whether it is really a table (and which of its rows are headers) or just for formatting; see the LaTeX tagging project’s accessible formatting tips.

  Major issues:

  • Compiling $\approx 2\times 10^{19728}$ (\(\approx 2\times 10^{19728}\)) caused lualatex to get into an apparent infinite loop and time out. Is it trying to calculate \(10^{19728}\)??

  • Some expressions with $\dots$ produce empty output. This would be a minor issue but having this empty output in the cells of a tabular environment caused lualatex to crash with the code “error: (nodes): fuzzy token cleanup in whatsit node with type whatsit and subtype 29”. Using $\ldots$ or $\cdots$ as appropriate worked.

  • beamer has an option \begin{frame}[allowframebreaks] that paginates overlong frames, necessary for bibtex bibliographies. It does not work in ltx-talk and I cannot find a replacement for this functionality. The test deck uses a tiny font for the bibliography but this is not very satisfactory and will not scale to larger bibliographies.

• It’s good to see there are still people online crazy enough to think that emulating a GameBoy using arbitrary precision arithmetic implemented purely through compass and straightedge constructions is a good idea (\(\mathbb{M}\)).

• The cleveref apocalypse is on us (\(\mathbb{M}\)). The cleveref LaTeX package is long-unmaintained and breaks on recent LaTeX versions, and an arXiv update to TeXlive means that we can no longer keep limping along using old-enough versions of TeX to avoid the problem. I haven’t yet tried it but my bookmarked solution is to switch to zref-clever.

By David Eppstein

We prove that for any 3-player game $\mathcal G$, whose query distribution has the same support as the GHZ game (i.e., all $x,y,z\in \{0,1\}$ satisfying $x+y+z=0\pmod{2}$), the value of the $n$-fold parallel repetition of $\mathcal G$ decays exponentially fast: \[ \text{val}(\mathcal G^{\otimes n}) \leq \exp(-n^c)\] for all sufficiently large $n$, where $c>0$ is an absolute constant. We also prove a concentration bound for the parallel repetition of the GHZ game: For any constant $\epsilon>0$, the probability that the players win at least a $\left(\frac{3}{4}+\epsilon\right)$ fraction of the $n$ coordinates is at most $\exp(-n^c)$, where $c=c(\epsilon)>0$ is a constant. In both settings, our work exponentially improves upon the previous best known bounds which were only polynomially small, i.e., of the order $n^{-\Omega(1)}$. Our key technical tool is the notion of \emph{algebraic spreadness} adapted from the breakthrough work of Kelley and Meka (FOCS '23) on sets free of 3-term progressions.

The Department of CS at University of Alaska Fairbanks invites applications for a fully funded PhD position in TCS and ML.

The PhD position is fully funded for the first three years.

Desired Background

• A Master’s degree in CS, Math.

• Programming knowledge in Python is desired

Website: https://sites.google.com/view/sangramkishorjena
Email: skjena@alaska.edu

By shacharlovett

Traditionally, protocol performance is summarized using two metrics: latency (measured in rounds), and communication complexity (measured asymptotically, e.g., $O(n^2)$). If both are small, we might expect the protocol to perform well in practice. But this intuition is incomplete. When Low Latency and Low Communication Aren’t Enough Consider two protocols: Protocol...

Authors: Cornelius Brand, Radu Curticapean, Petteri Kaski, Baitian Li, Ian Orzel, Tim Seppelt, Jiaheng Wang

The complexity of bilinear maps (equivalently, of $3$-mode tensors) has been studied extensively, most notably in the context of matrix multiplication. While circuit complexity and tensor rank coincide asymptotically for $3$-mode tensors, this correspondence breaks down for $d \geq 4$ modes. As a result, the complexity of $d$-mode tensors for larger fixed $d$ remains poorly understood, despite its relevance, e.g., in fine-grained complexity. Our paper explores this intermediate regime. First, we give a "graph-theoretic" proof of Strassen's $2ω/3$ bound on the asymptotic rank exponent of $3$-mode tensors. Our proof directly generalizes to an upper bound of $(d-1)ω/3$ for $d$-mode tensors. Using refined techniques available only for $d\geq 4$ modes, we improve this bound beyond the current state of the art for $ω$. We also obtain a bound of $d/2+1$ on the asymptotic exponent of circuit complexity of generic $d$-mode tensors and optimized bounds for $d \in \{4,5\}$. To the best of our knowledge, asymptotic circuit complexity (rather than rank) of tensors has not been studied before. To obtain a robust theory, we first ask whether low complexity of $T$ and $U$ imply low complexity of their Kronecker product $T \otimes U$. While this crucially holds for rank (and thus for circuit complexity in $3$ modes), we show that assumptions from fine-grained complexity rule out such a submultiplicativity for the circuit complexity of tensors with many modes. In particular, assuming the Hyperclique Conjecture, this failure occurs already for $d=8$ modes. Nevertheless, we can salvage a restricted notion of submultiplicativity. From a technical perspective, our proofs heavily make use of the graph tensors $T_H$, as employed by Christandl and Zuiddam ({\em Comput.~Complexity}~28~(2019)~27--56) and [...]

Authors: Grzegorz Gutowski, Mikołaj Rams

For a directed graph $G$, and a linear order $\ll$ on the vertices of $G$, we define backedge graph $G^\ll$ to be the undirected graph on the same vertex set with edge $\{u,w\}$ in $G^\ll$ if and only if $(u,w)$ is an arc in $G$ and $w \ll u$. The directed clique number of a directed graph $G$ is defined as the minimum size of the maximum clique in the backedge graph $G^\ll$ taken over all linear orders $\ll$ on the vertices of $G$. A natural computational problem is to decide for a given directed graph $G$ and a positive integer $t$, if the directed clique number of $G$ is at most $t$. This problem has polynomial algorithm for $t=1$ and is known to be \NP-complete for every fixed $t\ge3$, even for tournaments. In this note we prove that this problem is $Σ^\mathsf{P}_{2}$-complete when $t$ is given on the input.

Authors: Simon Gmeiner, Andreas S. Schulz

How can a stack of identical blocks be arranged to extend beyond the edge of a table as far as possible? We consider a generalization of this classic puzzle to blocks that differ in width and mass. Despite the seemingly simple premise, we demonstrate that it is unlikely that one can efficiently determine a stack configuration of maximum overhang. Formally, we prove that the Block-Stacking Problem is NP-hard, partially answering an open question from the literature. Furthermore, we demonstrate that the restriction to stacks without counterweights has a surprising connection to the Airplane Refueling Problem, another famous puzzle, and to Robust Appointment Scheduling, a problem of practical relevance. In addition to revealing a remarkable relation to the real-world challenge of devising schedules under uncertainty, their equivalence unveils a polynomial-time approximation scheme, that is, a $(1+ε)$-approximation algorithm, for Block Stacking without counterbalancing and a $(2+ε)$-approximation algorithm for the general case.

Authors: Austen Fan, Jin-Yi Cai, Shuai Shao, Zhuxiao Tang

We prove a complete complexity classification theorem for the planar eight-vertex model. For every parameter setting in ${\mathbb C}$ for the eight-vertex model, the partition function is either (1) computable in P-time for every graph, or (2) \#P-hard for general graphs but computable in P-time for planar graphs, or (3) \#P-hard even for planar graphs. The classification has an explicit criterion. In (2), we discover new P-time computable eight-vertex models on planar graphs beyond Kasteleyn's algorithm for counting planar perfect matchings. They are obtained by a combinatorial transformation to the planar {\sc Even Coloring} problem followed by a holographic transformation to the tractable cases in the planar six-vertex model. In the process, we also encounter non-local connections between the planar eight vertex model and the bipartite Ising model, conformal lattice interpolation and Möbius transformation from complex analysis. The proof also makes use of cyclotomic fields.

Authors: Giannis Spiliopoulos, Alexandros Troupiotis-Kapeliaris, Kostas Patroumpas, Nikolaos Liapis, Dimitrios Skoutas, Dimitris Zissis, Nikos Bikakis

Modeling vessel activity at sea is critical for a wide range of applications, including route planning, transportation logistics, maritime safety, and environmental monitoring. Over the past two decades, the Automatic Identification System (AIS) has enabled real-time monitoring of hundreds of thousands of vessels, generating huge amounts of data daily. One major challenge in using AIS data is the presence of large gaps in vessel trajectories, often caused by coverage limitations or intentional transmission interruptions. These gaps can significantly degrade data quality, resulting in inaccurate or incomplete analysis. State-of-the-art imputation approaches have mainly been devised to tackle gaps in vehicle trajectories, even when the underlying road network is not considered. But the motion patterns of sailing vessels differ substantially, e.g., smooth turns, maneuvering near ports, or navigating in adverse weather conditions. In this application paper, we propose HABIT, a lightweight, configurable H3 Aggregation-Based Imputation framework for vessel Trajectories. This data-driven framework provides a valuable means to impute missing trajectory segments by extracting, analyzing, and indexing motion patterns from historical AIS data. Our empirical study over AIS data across various timeframes, densities, and vessel types reveals that HABIT produces maritime trajectory imputations performing comparably to baseline methods in terms of accuracy, while performing better in terms of latency while accounting for vessel characteristics and their motion patterns.

Authors: Alessandro Epasto, Xin Lyu, Pasin Manurangsi

We study the computational cost of differential privacy in terms of memory efficiency. While the trade-off between accuracy and differential privacy is well-understood, the inherent cost of privacy regarding memory use remains largely unexplored. This paper establishes for the first time an unconditional space lower bound for user-level differential privacy by introducing a novel proof technique based on a multi-player communication game. Central to our approach, this game formally links the hardness of low-memory private algorithms to the necessity of ``contribution capping'' -- tracking and limiting the users who disproportionately impact the dataset. We demonstrate that winning this communication game requires transmitting information proportional to the number of over-active users, which translates directly to memory lower bounds. We apply this framework, as an example, to the fundamental problem of estimating the number of distinct elements in a stream and we prove that any private algorithm requires almost $\widetildeΩ(T^{1/3})$ space to achieve certain error rates in a promise variant of the problem. This resolves an open problem in the literature (by Jain et al. NeurIPS 2023 and Cummings et al. ICML 2025) and establishes the first exponential separation between the space complexity of private algorithms and their non-private $\widetilde{O}(1)$ counterparts for a natural statistical estimation task. Furthermore, we show that this communication-theoretic technique generalizes to broad classes of problems, yielding lower bounds for private medians, quantiles, and max-select.

Authors: Antoine Amarilli, Claire David, Nadime Francis, Victor Marsault, Mikaël Monet, Yann Strozecki

We give the first two algorithms to enumerate all binary words of $\{0,1\}^\ell$ (like Gray codes) while ensuring that the delay and the auxiliary space is independent from $\ell$, i.e., constant time for each word, and constant memory in addition to the $\ell$ bits storing the current word. Our algorithms are given in two new computational models: tape machines and deque machines. We also study more restricted models, queue machines and stack machines, and show that they cannot enumerate all binary words with constant auxiliary space, even with unrestricted delay. A tape machine is a Turing machine that stores the current binary word on a single working tape of length $\ell$. The machine has a single head and must edit its tape to reach all possible words of $\{0,1\}^{\ell}$ , and output them (in unit time, by entering special output states), with no duplicates. We construct a tape machine that achieves this task with constant delay between consecutive outputs, which implies that the machine implements a so-called skew-tolerant quasi-Gray code. We then construct a more involved tape machine that implements a Gray code. A deque machine stores the current binary word on a double-ended queue of length $\ell$, and stores a constant-size internal state. It works as a tape machine, except that it modifies the content of the deque by performing push and pop operations on the endpoints. We construct deque machines that enumerate all words of $\{0,1\}^\ell$ with constant-delay. The main technical challenge in this model is to correctly detect when enumeration has finished. Our work on deque machine is also motivated by other contexts in which endpoint modifications occur naturally. In particular, our result is a first step towards enumerating walks in directed graphs with constant delay and constant auxiliary space, addressing a core task in modern graph database query processing.

Authors: Althaf P, Amit Chattopadhyay, Osamu Saeki

A merge tree is a fundamental topological structure used to capture the sub-level set (and similarly, super-level set) topology in scalar data analysis. The interleaving distance is a theoretically sound, stable metric for comparing merge trees. However, computing this distance exactly is NP-hard. First fixed-parameter tractable (FPT) algorithm for it's exact computation introduces the concept of an $\varepsilon$-good map between two merge trees, where $\varepsilon$ is a candidate value for the interleaving distance. The complexity of their algorithm is $O(2^{2τ}(2τ)^{2τ+2}\cdot n^2\log^3n)$ where $τ$ is the degree-bound parameter and $n$ is the total number of nodes in both the merge trees. Their algorithm exhibits exponential complexity in $τ$, which increases with the increasing value of $\varepsilon$. In the current paper, we propose an improved FPT algorithm for computing the $\varepsilon$-good map between two merge trees. Our algorithm introduces two new parameters, $η_f$ and $η_g$, corresponding to the numbers of leaf nodes in the merge trees $M_f$ and $M_g$, respectively. This parametrization is motivated by the observation that a merge tree can be decomposed into a collection of unique leaf-to-root paths. The proposed algorithm achieves a complexity of $O\!\left(n^2\log n+η_g^{η_f}(η_f+η_g)\, n \log n \right)$. To obtain this reduced complexity, we assume that number of possible $\varepsilon$-good maps from $M_f$ to $M_g$ does not exceed that from $M_g$ to $M_f$. Notably, the parameters $η_f$ and $η_g$ are independent of the choice of $\varepsilon$. Compared to their algorithm, our approach substantially reduces the search space for computing an optimal $\varepsilon$-good map. We also provide a formal proof of correctness for the proposed algorithm.

Authors: David Shmoys, Varun Suriyanarayana, Seeun William Umboh

The Joint Replenishment Problem (JRP) is a classical inventory management problem, that aims to model the trade-off between coordinating orders for multiple commodities (and their cost) with holding costs incurred by meeting demand in advance. Moseley, Niaparast and Ravi introduced a natural online generalization of the JRP in which inventory corresponding to demands may be replenished late, for a delay cost, or early, for a holding cost. They established that when the holding and delay costs are monotone and uniform across demands, there is a 30-competitive algorithm that employs a greedy strategy and a dual-fitting based analysis. We develop a 5-competitive algorithm that handles arbitrary monotone demand-specific holding and delay cost functions, thus simultaneously improving upon the competitive ratio and relaxing the uniformity assumption. Our primal-dual algorithm is in the spirit of the work Buchbinder, Kimbrel, Levi, Makarychev, and Sviridenko, which maintains a wavefront dual solution to decide when to place an order and which items to order. The main twist is in deciding which requests to serve early. In contrast to the work of Moseley et al., which ranks early requests in ascending order of desired service time and serves them until their total holding cost matches the ordering cost incurred for that item, we extend to the non-uniform case by instead ranking in ascending order of when the delay cost of a demand would reach its current holding cost. An important special case of the JRP is the single-item lot-sizing problem. Here, Moseley et al. gave a 3-competitive algorithm when the holding and delay costs are uniform across demands. We provide a new algorithm for which the competitive ratio is $φ+1 \approx 2.681$, where $φ$ is the golden ratio, which again holds for arbitrary monotone holding-delay costs.

Authors: Daniele Carnevale, Gianlorenzo D'Angelo

Temporal graphs represent networks in which connections change over time, with edges available only at specific moments. Motivated by applications in logistics, multi-agent information spreading, and wireless networks, we introduce the D-Temporal Multi-Broadcast (D-TMB) problem, which asks for scheduling the availability of edges so that a predetermined subset of sources reach all other vertices while optimizing the worst-case temporal distance D from any source. We show that D-TMB generalizes ReachFast (arXiv:2112.08797). We then characterize the computational complexity and approximability of D-TMB under six definitions of temporal distance D, namely Earliest-Arrival (EA), Latest-Departure (LD), Fastest-Time (FT), Shortest-Traveling (ST), Minimum-Hop (MH), and Minimum-Waiting (MW). For a single source, we show that D-TMB can be solved in polynomial time for EA and LD, while for the other temporal distances it is NP-hard and hard to approximate within a factor that depends on the adopted distance function. We give approximation algorithms for FT and MW. For multiple sources, if feasibility is not assumed a priori, the problem is inapproximable within any factor unless P = NP, even with just two sources. We complement this negative result by identifying structural conditions that guarantee tractability for EA and LD for any number of sources.

Authors: Michael A. Bender, William Kuszmaul, Elaine Shi, Rose Silver

We give a (strongly) history-independent two-choice balls-and-bins algorithm on $n$ bins that supports both insertions and deletions on a set of up to $m$ balls, while guaranteeing a maximum load of $m / n + O(1)$ with high probability, and achieving an expected recourse of $O(\log \log (m/n))$ per operation. To the best of our knowledge, this is the first history-independent solution to achieve nontrivial guarantees of any sort for $m/n \ge ω(1)$ and is the first fully dynamic solution (history independent or not) to achieve $O(1)$ overload with $o(m/n)$ expected recourse.

Authors: Mirabel Mendoza-Cadena, Arturo Merino, Mads Anker Nielsen, Kevin Schewior

This paper introduces a framework for combinatorial variants of perpetual-scheduling problems. Given a set system $(E,\mathcal{I})$, a schedule consists of an independent set $I_t \in \mathcal{I}$ for every time step $t \in \mathbb{N}$, with the objective of fulfilling frequency requirements on the occurrence of elements in $E$. We focus specifically on combinatorial bamboo garden trimming, where elements accumulate height at growth rates $g(e)$ for $e \in E$ given as a convex combination of incidence vectors of $\mathcal{I}$ and are reset to zero when scheduled, with the goal of minimizing the maximum height attained by any element. Using the integrality of the matroid-intersection polytope, we prove that, when $(E,\mathcal{I})$ is a matroid, it is possible to guarantee a maximum height of at most 2, which is optimal. We complement this existential result with efficient algorithms for specific matroid classes, achieving a maximum height of 2 for uniform and partition matroids, and 4 for graphic and laminar matroids. In contrast, we show that for general set systems, the optimal guaranteed height is $Θ(\log |E|)$ and can be achieved by an efficient algorithm. For combinatorial pinwheel scheduling, where each element $e\in E$ needs to occur in the schedule at least every $a_e \in \mathbb{N}$ time steps, our results imply bounds on the density sufficient for schedulability.

Authors: R. Jay Martin

We formalize a constructive subclass of locality-preserving deterministic operators acting on graph-indexed state systems. We define the class of Bounded Local Generator Classes (BLGC), consisting of finite-range generators operating on bounded state spaces under deterministic composition. Within this class, incremental update cost is independent of total system dimension. We prove that, under the BLGC assumptions, per-step operator work satisfies W_t = O(1) as the number of nodes M \to \infty, establishing a structural decoupling between global state size and incremental computational effort. The framework admits a Hilbert-space embedding in \ell^2(V; \mathbb{R}^d) and yields bounded operator norms on admissible subspaces. The result applies specifically to the defined subclass and does not claim universality beyond the stated locality and boundedness constraints.

Authors: Ioannis Caragiannis, Vasilis Gkatzelis, Sebastian Homrighausen

In a setting where $m$ items need to be partitioned among $n$ agents, we evaluate the performance of mechanisms that take as input each agent's \emph{ordinal preferences}, i.e., their ranking of the items from most- to least-preferred. The standard measure for evaluating ordinal mechanisms is the \emph{distortion}, and the vast majority of the literature on distortion has focused on worst-case analysis, leading to some overly pessimistic results. We instead evaluate the distortion of mechanisms with respect to their expected performance when the agents' preferences are generated stochastically. We first show that no ordinal mechanism can achieve a distortion better than $e/(e-1)\approx 1.582$, even if each agent needs to receive exactly one item (i.e., $m=n$) and every agent's values for different items are drawn i.i.d.\ from the same known distribution. We then complement this negative result by proposing an ordinal mechanism that achieves the optimal distortion of $e/(e-1)$ even if each agent's values are drawn from an agent-specific distribution that is unknown to the mechanism. To further refine our analysis, we also optimize the \emph{distortion gap}, i.e., the extent to which an ordinal mechanism approximates the optimal distortion possible for the instance at hand, and we propose a mechanism with a near-optimal distortion gap of $1.076$. Finally, we also evaluate the distortion and distortion gap of simple mechanisms that have a one-pass structure.

Authors: M. Szusterman

This paper investigates the extension complexity of polytopes by exploiting the correspondence between non-negative factorizations of slack matrices and randomized communication protocols. We introduce a geometric characterization of extension complexity based on the width of Markovian protocols, as a variant of the framework introduced by Faenza et al. This enables us to derive a new upper bound of $\tilde{O}(n^3\cdot 1.5^n)$ for the extension complexity of the matching polytope $P_{\text{match}}(n)$, improving upon the standard $2^n$-bound given by Edmonds' description. Additionally, we recover Goemans' compact formulation for the permutahedron using a one-round protocol based on sorting networks.

Authors: Yael Kirkpatrick, John Kuszmaul, Surya Mathialagan, Virginia Vassilevska Williams

We consider the classic 3SUM problem: given sets of integers $A, B, C $, determine whether there is a tuple $(a, b, c) \in A \times B \times C$ satisfying $a + b + c = 0$. The 3SUM Hypothesis, central in fine-grained complexity, states that there does not exist a truly subquadratic time 3SUM algorithm. Given this long-standing barrier, recent work over the past decade has explored 3SUM from a data structural perspective. Specifically, in the 3SUM in preprocessed universes regime, we are tasked with preprocessing sets $A, B$ of size $n$, to create a space-efficient data structure that can quickly answer queries, each of which is a 3SUM problem of the form $A', B', C'$, where $A' \subseteq A$ and $B' \subseteq B$. A series of results have achieved $\tilde{O}(n^2)$ preprocessing time, $\tilde{O}(n^2)$ space, and query time improving progressively from $\tilde{O}(n^{1.9})$ [CL15] to $\tilde{O}(n^{11/6})$ [CVX23] to $\tilde{O}(n^{1.5})$ [KPS25]. Given these series of works improving query time, a natural open question has emerged: can one achieve both truly subquadratic space and truly subquadratic query time for 3SUM in preprocessed universes? We resolve this question affirmatively, presenting a tradeoff curve between query and space complexity. Specifically, we present a simple randomized algorithm achieving $\tilde{O}(n^{1.5 + \varepsilon})$ query time and $\tilde{O}(n^{2 - 2\varepsilon/3})$ space complexity. Furthermore, our algorithm has $\tilde{O}(n^2)$ preprocessing time, matching past work. Notably, quadratic preprocessing is likely necessary for our tradeoff as either the preprocessing or the query time must be at least $n^{2-o(1)}$ under the 3SUM Hypothesis.

Authors: Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman, Meirav Zehavi

We consider the fair division of indivisible items among $n$ agents with additive non-negative normalized valuations, with the goal of obtaining high value guarantees, that is, close to the proportional share for each agent. We prove that partitions where \emph{every} part yields high value for each agent are asymptotically limited by a discrepancy barrier of $Θ(\sqrt{n})$. Guided by this, our main objective is to overcome this barrier and achieve stronger individual guarantees for each agent in polynomial time. Towards this, we are able to exhibit an exponential improvement over the discrepancy barrier. In particular, we can create partitions on-the-go such that when agents arrive sequentially (representing a previously-agreed priority order) and pick a part autonomously and rationally (i.e., one of highest value), then each is guaranteed a part of value at least $\mathsf{PROP} - \mathcal{O}{(\log n)}$. Moreover, we show even better guarantees for three restricted valuation classes such as those defined by: a common ordering on items, a bound on the multiplicity of values, and a hypergraph with a bound on the \emph{influence} of any agent. Specifically, we study instances where: (1) the agents are ``close'' to unanimity in their relative valuation of the items -- a generalization of the ordered additive setting; (2) the valuation functions do not assign the same positive value to more than $t$ items; and (3) the valuation functions respect a hypergraph, a setting introduced by Christodoulou et al. [EC'23], where agents are vertices and items are hyperedges. While the sizes of the hyperedges and neighborhoods can be arbitrary, the influence of any agent $a$, defined as the number of its neighbors who value at least one item positively that $a$ also values positively, is bounded.

Authors: Jonas Ellert, Tomasz Kociumaka

A key principle in string processing is local consistency: using short contexts to handle matching fragments of a string consistently. String synchronizing sets [Kempa, Kociumaka; STOC 2019] are an influential instantiation of this principle. A $τ$-synchronizing set of a length-$n$ string is a set of $O(n/τ)$ positions, chosen via their length-$2τ$ contexts, such that (outside highly periodic regions) at least one position in every length-$τ$ window is selected. Among their applications are faster algorithms for data compression, text indexing, and string similarity in the word RAM model. We show how to preprocess any string $T \in [0..σ)^n$ in $O(n\logσ/\log n)$ time so that, for any $τ\in[1..n]$, a $τ$-synchronizing set of $T$ can be constructed in $O((n\logτ)/(τ\log n))$ time. Both bounds are optimal in the word RAM model with word size $w=Θ(\log n)$. Previously, the construction time was $O(n/τ)$, either after an $O(n)$-time preprocessing [Kociumaka, Radoszewski, Rytter, Waleń; SICOMP 2024], or without preprocessing if $τ<0.2\log_σn$ [Kempa, Kociumaka; STOC 2019]. A simple version of our method outputs the set as a sorted list in $O(n/τ)$ time, or as a bitmask in $O(n/\log n)$ time. Our optimal construction produces a compact fully indexable dictionary, supporting select queries in $O(1)$ time and rank queries in $O(\log(\tfrac{\logτ}{\log\log n}))$ time, matching unconditional cell-probe lower bounds for $τ\le n^{1-Ω(1)}$. We achieve this via a new framework for processing sparse integer sequences in a custom variable-length encoding. For rank and select queries, we augment the optimal variant of van Emde Boas trees [Pătraşcu, Thorup; STOC 2006] with a deterministic linear-time construction. The above query-time guarantees hold after preprocessing time proportional to the encoding size (in words).

We show that for any unsatisfiable CNF formula $\varphi$ that requires resolution refutation width at least $w$, and for any $1$-stifling gadget $g$ (for example, $g=MAJ_3$), (1) every resolution-over-parities (Res($\oplus$)) refutation of the lifted formula $\varphi \circ g$ of size at most $S$ has depth at least $\Omega(w^2/\log S)$; (2) every Res($\oplus$) refutation of the lifted formula $\varphi \circ g$ has size $\Omega(w^2)$. The first result substantially extends and simplifies all previously known lifting theorems for bounded-depth Res($\oplus$). The lifting result of Itsykson and Knop [IK, ITCS'26] requires gadgets of logarithmic size and applies only to refutations of depth at most $O(n\log n)$, whereas our result applies to nearly quadratic depth. The liftings of Bhattacharya and Chattopadhyay [BC, ECCC'25] and of Byramji and Imagliazzo [BI, arXiv'25] apply to nearly quadratic depth as well, but rely on a much stronger assumption of $(\Omega(n),\Omega(n))$-DT-hardness, which is far less standard than large resolution width. Our proof combines the random-walk-with-restarts method of Alekseev and Itsykson [AI, STOC'25] with a new idea: the random walk is defined relative to the structure of the refutation graph, rather than by a distribution on inputs induced by the formula. Using this technique, we substantially strengthen the supercritical size-depth tradeoff of Itsykson and Knop [IK, ITCS'26], both by improving the depth lower bound and by reducing the size of the separating formulas to polynomial in the number of variables, with the latter resolving an open question. In particular, we construct a family of polynomial-size formulas that admit polynomial-size resolution refutations, while any Res($\oplus$) refutation of depth $o(n^2/\log^4 n)$ necessarily has superpolynomial size. Our second result yields a pure quadratic lower bound on the size of Res($\oplus$) refutations, improving upon the previously known near-quadratic lower bound of [BI, arXiv'25].

The following are prepared remarks that I delivered by Zoom to a student group at my old stomping-grounds of MIT, and which I thought might interest others (even though much of it will be familiar to Shtetl-Optimized regulars). The students asked me to share my “optimistic vision” for the year 2050, so I did my best to oblige. A freewheeling discussion then followed, as a different freewheeling discussion can now follow in the comments section.

---

I was asked to share my optimistic vision for the future. The trouble is, optimistic visions for the future are not really my shtick!

It’s not that I’m a miserable, depressed person—I only sometimes am! It’s just that, on a local level, I try to solve the problems in front of me, which have often been problems in computational complexity or quantum computing theory.

And then, on a global level, I worry about the terrifying problems of the world, such as climate change, nuclear war, and of course the resurgence of populist, authoritarian strongmen who’ve turned their backs on the Enlightenment and appeal to the basest instincts of humanity. I won’t name any names.

So then my optimistic vision is simply that we survive all this—“we” meaning the human race, but also meaning communities that I personally care about, like Americans, academics, scientists, and my extended family. We survive all of it so that we can reach the next crisis, the one where we don’t even know what it is yet.

---

But I get the sense that you wanted more optimism than that! Since I’ve spent 27 years working in quantum computing, the easiest thing for me to do would be to spin an optimistic story about how QC is going to make our lives so much better in 2050, by, I dunno, solving machine learning and optimization problems much faster, curing cancer, fixing global warming, whatever.

The good news is that there has been spectacular progress over the past couple years toward actually building a scalable QC. We now have two-qubit gates with 99.9% accuracy, close to the threshold where quantum error-correction becomes a net win. We can now do condensed-matter physics simulations that give us numbers that we don’t know how to get classically. I think it’s fair to say that all the key ideas and hardware building blocks for a fault-tolerant quantum computer are now in place, and what remains is “merely” the staggeringly hard engineering problem, which might take a few years, or a decade or more, but should eventually be solved.

The trouble for the optimistic vision is that the applications, where quantum algorithms outperform classical ones, have stubbornly remained pretty specialized. In fact, the two biggest ones remain the two that we knew about in the 1990s:

1. simulation of quantum physics and chemistry themselves, and
2. breaking existing public-key encryption.

Quantum simulation could help with designing better batteries, or solar cells, or high-temperature superconductors, or other materials, but the road from improved understanding to practical value is long and uncertain. Meanwhile, breaking public-key cryptography could help various spy agencies and hackers and criminal syndicates, but it doesn’t obviously help the world.

The quantum speedups that we know outside those two categories—for example, for optimization and machine learning—tend to be either modest or specialized or speculative.

Honestly, the application of QC that excites me the most, by far, is just disproving all the people who said QC was impossible!

So much for QC then.

---

And so we come to the elephant in the room—the elephant in pretty much every room nowadays—which is AI. AI has now reached a place that exceeds the imaginations of many of the science-fiction writers of generations past—excelling not only at writing code and solving math competition problems but at depth of emotional understanding. Many of my friends are terrified of where this is leading us—and not in some remote future but in 5 or 10 or 20 years. I think they’re probably correct to be terrified. There’s an enormous range of possible outcomes on the table, including ones where the new superintelligences that we bring into being treat humans basically as humans treated the dodo bird, or the earlier hominids that used to share the earth with us.

But, within this range of outcomes, I think there are also some extremely good ones. Look, for millennia, people have prayed to God or gods for help, life, health, longevity, freedom, justice—and for millennia, God has famously been pretty slow to answer their prayers. A superintelligence that was aligned with human values would be nothing less than a God who did answer, who did deliver all those things, because we had created it to do so. Or for religious people, perhaps such an AI would be the means by which the old God was finally able to deliver all those things into the temporal world. These are the stakes here.

To switch metaphors, people sometimes describe the positive AI-enabled future as “luxury space communism.” AI would take care of all of our material needs, leaving us to seek value in our lives through family, friendships, competition, hobbies, humor, art, entertainment, or exploration. The super-AI would give us the freedom to pursue all those things, but would not give us the freedom to harm each other, to curtail each others’ freedoms, or to build a bad AI capable of overthrowing it. The super-AI would be a singleton, a monotheistic God or its emissary on earth.

Many people say that something would still be missing from this future. After all, we humans would no longer really be needed for anything—for building or advancing or defending civilization. To put a personal fine point on it, my students and colleagues and I wouldn’t needed any more to discover new scientific truths or to write about them. That would all be the AI’s job.

I agree that something would be lost here. But on the other hand, what fraction of us are needed right now for these things? Most humans already derive the meaning in their lives from family and community and enjoying art and music and food and things like that. So maybe the remaining fraction of us should just get over ourselves! On the whole, while this might not be the best future imaginable, I would accept it in a heartbeat given the realistic alternatives on offer. Thanks for listening.

By Scott