Theory of Computing Report

A unique opportunity to work on fundamental questions at the intersection of disciplines -freedom to pursue your own research agenda without boundaries -up to 3 years at the Santa Fe Institute
-dedicated research & collaboration funds
-a structured leadership training program
-competitive salary & paid family leave
-opportunities for transdisciplinary collaboration w/ leading researchers worldwide

Website: https://www.santafe.edu/SFIfellowship
Email: Hilary Skolnik hilary@santafe.edu

By shacharlovett

Authors: Alexis Langlois-Rémillard, Mia Müßig

Finding a set of vertices in a graph with no edges between them, INDSET, is a well-known NP-complete problem. The queen graph of a chessboard is constructed by taking vertices as the tiles of the chessboard and drawing edges between two tiles if a queen can move from one to the other. We call INDQUEENS the independent set problem on a queen graph where the chessboard is a polyomino. We prove that INDQUEENS on polyominoes is NP-complete, proving a conjecture of Langlois-Rémillard--Müßig--Roldán. As our reduction is parsimonious, we can further prove that it is #P-complete. We furthermore prove that INDROOKS on polyominoes is #P-complete, despite being solvable in polynomial time.

Authors: Krit Grover, Marcelo Ponce

The Traveling Salesman Problem is a classical NP-hard problem with significant implications in logistics, circuit design, and operations research. This paper presents a comparative study of four approaches to solving the Traveling Salesman Problem: brute-force enumeration, a 2-approximation algorithm using minimum spanning trees, simulated annealing, and the Quantum Approximate Optimization Algorithm. We implement each technique and evaluate them on graphs of varying sizes to analyze performance, solution quality, and scalability. In doing so, we have also developed an open-source framework that allows researchers and practitioners to explore, test and extend these methods.

Authors: Leonid A. Levin

The article develops further Kolmogorov's Algorithmic Complexity Theory. The definition of Randomness is modified to satisfy strong invariance properties (conservation inequalities). This allows definitions of concepts such as Mutual Information in individual infinite sequences. Applications to several areas, like Probability Theory, Theory of Algorithms, Intuitionistic Logic are considered. These theories are simplified substantially with the postulate that the objects they consider are independent of (have small mutual information with) any sequence specified by a mathematical property.

Authors: Tameem Choudhury, Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan

The Orthogonal Vectors Problem (OV$_{n,d}$) takes as input two sets $A,B$ each containing $n$ $d$-dimensional Boolean vectors, and outputs $1$ if and only if there exists $a \in A$ and $b \in B$ such that $a$ and $b$ are orthogonal. The OV conjecture states that for every $\varepsilon > 0$, there exists a constant $c \geq 1$ such that there is no algorithm deciding OV$_{n,d}$ for $d = c \log n$ with running time $O(n^{2-\varepsilon})$. The analogous $k$-OV conjecture hypothesizes a lower bound of $n^{k-ε}$ for the same problem with $k$ sets. We prove these results and variants unconditionally in concrete computational models. We study a natural monotone version of the $k$-OV conjecture and shows that it holds for monotone circuits and constant-depth (not necessarily monotone) circuits when $d = n^{Ω(1)}.$ We show that the monotone version of the OV conjecture holds for monotone circuits. More formally, we show that for every $ε> 0$, there exists $c$ such that any monotone circuit family computing the negation of OV$_{n,d}$ with $d=c\log n$ must have size $Ω(n^{2-ε})$. We also prove stronger Boolean formula and branching program lower bounds for OV$_{n,d}$, strengthening a previous result of Kane and Williams (ITCS 2019). In particular, our Boolean formula lower bound of $Ω(n^2 d)$ is tight up to constant factors.

Authors: Johannes K. Fichte, Johanna Groven, Peter Jonsson, Victor Lagerkvist, Jorke M. de Vlas

The Simple Temporal Problem (STP) is a core framework for quantitative temporal constraints. As STP data can be inconsistent, we study MAXSTP: compute a maximum-cardinality consistent subset of constraints. This extension is NP-hard, and we analyze its parameterized complexity under measures that capture practically relevant instance features: the number of variables $n$ (instance scale), the maximum coefficient magnitude $k$ (numeric range), and structural parameters of the constraint graph such as treewidth $tw$ (decomposability) and vertex cover size $vc$ (density). We show that MAXSTP is W[1]-hard parameterized by $n$, implying that $n$ and parameters that depend on $n$ (including $tw$ and $vc$) are insufficient for fixed-parameter tractability. For combined parameters, we give an $O^*(k^n)$-time algorithm, yielding single-exponential solvability for fixed $k$. While $k+tw$ remains W[1]-hard, MAXSTP is in XP via an $O^*((n\cdot k)^{tw})$ algorithm. Our results suggest that MAXSTP is often computationally harder than optimizing qualitative CSPs. We verify that many such problems (including RCC-8 and Allen's algebra) are FPT when parameterized by $n$ or $tw$. However, we also demonstrate that FPT algorithms for MAXSTP are indeed possible but with other parameters such as $k + vc$.

Authors: Karthik Sheshadri

Let $C\subseteq\F_2^m$ be a binary linear code and let $[m]=L\sqcup R$ be a bipartition of its coordinates. The \emph{conditional decoding matrix} of $C$ at this cut is the matrix $W$ indexed by $\F_2^{L}\times\F_2^{R}$ whose entry $W(x_L,x_R)$ is the coset-leader weight $d\bigl((x_L,x_R),C\bigr)$, the minimum Hamming distance from the word $(x_L,x_R)$ to the code. We prove that the min-plus factorization rank (Barvinok rank) of $W$, and likewise its tropical rank, equal $2^{s}$ exactly, where $s=\dim C-\dim C_L-\dim C_R$ is the classical state complexity of the minimal trellis of $C$ at the cut. The upper bound is a two-party reading of Viterbi decoding on the minimal trellis; the contribution is the matching lower bound, which holds against arbitrary min-plus factorizations rather than only sequential trellis realizations, and is obtained from an explicit $2^{s}\times 2^{s}$ tropically nonsingular submatrix built from a transversal of codewords. Specializing $C$ to the cut space of a graph identifies $W$ with the conditional ground-state energy of Ising signings (the frustration index), and yields natural graph families whose conditional matrices have min-plus rank exponential in the number of vertices; for these families we also record the contrasting local statement that all bounded-radius views of a signing are switching-trivial, so the exponential rank is carried entirely by non-local structure. We note explicitly that this rank measures representational incompressibility, not computational hardness: planar families attain the same exponential rank while their ground states are computable in polynomial time.

Authors: Nick Nordwald, Inés García-Redondo, Anthea Monod

Persistent cohomology provides a principled framework for constructing nonlinear coordinates that reflect the topology of data. However, these topological coordinates can be severely distorted by non-uniform sampling density, limiting their applicability to real-world data. While density-robust circular coordinates have recently been developed, the extension to spherical coordinates remains an open challenge: unlike the circular case, spherical coordinates are obtained through a nonlinear variational problem for sphere-valued maps, to which existing density-correction mechanisms are not directly applicable. In this paper, we introduce the first density-robust construction of spherical coordinates from persistent cohomology. Rather than modifying the coordinate optimization itself, we extend a subsampling-and-alignment framework for circular coordinates to $S^2$, which first computes spherical coordinates on approximately uniform subsamples obtained by rejection sampling and then combines them into a global consensus map. The principal mathematical difficulty is the alignment of independently computed sphere-valued coordinates. We formulate this challenge as a spherical Procrustes problem and establish approximation guarantees for a computationally tractable Euclidean relaxation. Our resulting construction is robust to non-uniform sampling and retains the accuracy of classical spherical coordinates under uniform sampling. Moreover, by computing persistent cohomology only on fixed-size subsamples, our approach avoids the quartic memory bottleneck of the classical spherical coordinate pipeline and scales to substantially larger datasets. We conduct experiments on synthetic data and demonstrate accurate coordinate recovery under severe sampling bias and scalability to datasets of 10,000 points.

Authors: Ebru Dagdelen, Aakash Karlekar, Manav Arora, Matthew Illingsworth, Jonathan Jaquette, Linda J. Cummings, Lou Kondic

When computing sub/super-level-set persistent homology (PH), the effect of noise may introduce millions of (short-lived) topological generators, presenting an obstacle to both the computation of PH of large 3D images, and any analysis of PH that incorporates the number of generators. As such, it is often necessary to denoise the data before computing its PH. We analyze the PH of synthetic 3D images of porous media in the presence of spatially uncorrelated noise, and perform a comparative analysis of various topological measures (e.g. bottleneck distance, Wasserstein distance, persistence statistics and persistence images) to assess their robustness to both noise and the denoising process (i.e. adding spatially uncorrelated Gaussian noise, and denoising by either a Gaussian convolution or a machine learning approach).

Authors: Henry Förster, Michael Hoffmann, Stephen Kobourov, Maria Eleni Pavlidi, Alexandra Weinberger, Johannes Zink

We introduce and study the weighted book thickness of graphs. A $k$-page book embedding of a graph $G=(V,E)$ is defined by a spanning cycle $C$ for $V$ (which does not need to be part of $G$) and a partition $E=\bigcup_{i=1}^{k}E_i$ such that $E\cap C\subseteq E_1$ and each graph $G_i=(V,E_i\cup C)$, for $1 \le i \le k$, is outerplane with outer cycle $C$. If $e\in E_i$, we say that $e$ appears on Page $i$. The classical book thickness of a graph $G$ is the minimum $k$ such that there exists a $k$-page book embedding of $G$, that is, the minimum (over all book embeddings of $G$) achievable maximum page an edge appears on. In contrast, the weighted book thickness is the minimum achievable average page an edge appears on. The embeddings that realize weighted book thickness can differ from those that realize (classical) book thickness. We show that, although every planar graph on at most nine vertices admits a 2-page book embedding realizing its weighted book thickness, already for ten vertices, there is a planar graph for which every realization of its weighted book thickness needs more pages than its book thickness. We prove that there even exists a 2-tree whose weighted book thickness cannot be realized on two pages. On the positive side, we show that for every graph of pathwidth at most two, the weighted book thickness can always be realized by a 2-page book embedding and such an embedding can be found in linear time. Moreover, we prove that it is NP-complete to decide if the weighted book thickness is at most $k$, for some given integer $k$.

Authors: Michael A. Bekos, Thomas Depian, Stefan Felsner, Michael Kaufmann, Philipp Kindermann, Fabrizio Montecchiani, Maria Eleni Pavlidi, Alexandra Weinberger, Alexander Wolff, Johannes Zink

A linear layout of a graph is defined as a total order of the vertices and a partition of the edges to pages. In a stack (queue) layout, no two edges on the same page may cross (nest). The stack (queue) number of a graph is the minimum number of pages required in a stack (queue) layout. This paper focuses on characterizing and recognizing graphs that have both stack number 1 and queue number 1. It is known that the graphs with stack number 1 are exactly the outerplanar graphs. We show that (i) deciding whether a given outerplanar graph has queue number 1 is NP-hard; (ii) deciding whether a given maximal outerplanar graph has queue number 1 can be done in linear time. Moreover, we investigate the interplay between outerpaths with queue number 1 and their maximum vertex degree.

Authors: Frank Nielsen

In this work, we revisit the problem of computing minimum enclosing Bregman balls (Bregman MEBs) of finite sets of parameters. First, we show that Bregman MEBs are equivalent to MEBs of corresponding weighted point sets with respect to the power distance. We then report an efficient Frank--Wolfe $(1+ε)$-approximation algorithm for computing power MEBs, for any $ε>0$. This power MEB approximation algorithm coincides with the Bregman MEB approximation algorithm of Nock and Nielsen (2005) when expressed in the dual gradient space. Finally, we show that the Bregman potential lifting transforms used to construct Bregman Voronoi diagrams can be reinterpreted as the classical paraboloid lifting transform applied to corresponding weighted point sets. In particular, Bregman MEB circumcenters lie on the farthest Bregman Voronoi diagrams or equivalently on the corresponding farthest power diagrams.

Authors: Mark de Berg, Debajyoti Kar, Arindam Khan, Rudrayan Kundu

Let $\mathcal{K}$ be a family of pairwise disjoint objects in the plane. We say that a subset $\mathcal{K}^*\subseteq \mathcal{K}$ is \emph{separable} if it admits a sequence of guillotine cuts that separate all objects in $\mathcal{K}^*$ from each other while not cutting any of them. Urrutia (1996) asked whether any family of $n$ convex objects has a separable subset of size $Ω(n)$. Pach and Tardos (2000) answered this question negatively for line segments, but established positive results for fat objects of similar size. More recently, it was shown that sets of arbitrarily-sized axis-aligned squares also admit a separable subset of linear size. However, the question whether any set of arbitrarily-sized fat convex objects has a separable subset of linear size has remained open, even for disks. A major obstacle is that the existing technique for arbitrarily-sized squares uses only axis-aligned cuts, while even for disks, axis-aligned cuts alone are insufficient to obtain a separable subset of linear size. We resolve this longstanding open problem by proving that every family of pairwise disjoint fat convex objects has a separable subset of linear size. Our result extends to higher dimensions: any family of pairwise disjoint arbitrarily-sized fat convex objects in $\mathbb{R}^d$, where $d$ is a fixed constant, has a subset of linear size that is recursively separable by a sequence of hyperplane cuts. Our framework also yields improved guarantees for important special cases. For axis-aligned squares with axis-aligned guillotine cuts, we leverage additional structural properties of squares to show that at least $13.46\%$ of the squares are separable, improving the previous best bound of $9/256 \approx 3.51\%$ due to Chalermsook, Kugelmann, Orgo, Uniyal, and Zarsav (2025). For disks, by exploiting Oler's packing inequality, we prove that at least $n/93$ disks can always be separated.

Authors: Ji Zeng

A set of four points $\{p_1,p_2,p_3,p_4\}$ on the sphere is a balanced quadruple if there are four real numbers $s_1,s_2,s_3,s_4$, two positive and two negative, such that $s_1p_1+s_2p_2+s_3p_3+s_4p_4 = 0$. Streltsova and Wagner proved that $n$ points on the sphere determine at least $\frac{1}{4} \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor\frac{n-1}{2}\right\rfloor \left\lfloor\frac{n-2}{2}\right\rfloor \left\lfloor\frac{n-3}{2}\right\rfloor$ many balanced quadruples provided any three points are linearly independent. We extend this result from spherical point configurations to rank-three oriented matroids.

Authors: Sergey Pupyrev

Planar graphs are central to graph drawing, with extensive results on planar layouts and related structures. Every planar graph admits a planar straight-line drawing, and algorithms can guarantee additional geometric or combinatorial properties. However, it is unclear which algorithms work best in practice. Even for small graphs with near-perfect manual drawings, standard algorithms might produce poor spacing, distorted faces, or small angles. We present an experimental evaluation of planar graph drawing algorithms on a large benchmark collection of small and medium-sized planar graphs (\(10\)--\(400\) vertices). The study compares established algorithms from the graph drawing literature, practical force-directed and pressure-based heuristics, and new optimization-based methods that directly improve visual properties such as edge-length uniformity, face-area balance, and angular resolution. The results show that no evaluated algorithm is best across all aesthetic criteria, and optimizing one visual property often worsens another. Directly optimizing visual criteria improves targeted scores, and score-guided combination of several methods gives the best aggregate results, but no simple algorithm emerges as a clear universal default. Designing a simple, robust algorithm that performs well across graph families and aesthetic criteria therefore remains an open practical problem.

Authors: Marcel Nöhre, Gerd Stumme

We propose a flexible, two-phase algorithm for labeling line diagrams of ordered sets, in which the nodes of direct neighbors in the order relation are connected by a straight, upward-pointing line. In contrast to the labeling of diagrams of arbitrary graphs, we benefit from the fact that all edges in line diagrams of ordered sets are more or less vertical. In this paper, we study the placement of all labels such that they do not intersect with any nodes, lines, or other labels while minimizing the distances between the nodes and their labels. Our approach starts by filtering the fixed-position model using line diagram-specific readability criteria. For labels that cannot be placed adjacent to their node (overflow labels), we exploit the free space in the graph's interior or the infinite space surrounding the drawing and link the labels with their respective node by straight binding lines that should not cross other nodes or labels if possible. To balance quality and runtime, we derive an initial placement of the overflow labels using a cost function over a sparse grid of candidates, followed by a force-based refinement step to fine-tune the layout. Furthermore, we demonstrate the flexibility of this approach by applying it to the visual constraints of line diagrams in the field of Formal Concept Analysis (FCA), where certain labels have to be placed above their node and others below. This special version of the algorithm shows that a pre-filtering in the first phase and minimal adjustments for the cost function and force-based model are sufficient to handle the dual labeling requirements of concept lattices.

Authors: Yongjie Guan

We resolve Problem 60 of The Open Problems Project under the natural convention that a selected vertex at the total centroid is immobile. A cyclically labeled planar $n$-vertex configuration, $n\ge3$, can be transformed exactly into a regular $n$-gon by finitely many vertex--centroid moves if and only if it is noncollinear. The affirmative direction is independent of this convention, and all moves may be chosen positive, so the selected vertex never crosses the centroid of the other vertices. More generally, any two configurations in a connected open subset of the affinely spanning configuration space can be joined by positive moves whose entire continuous execution remains in that subset. For simple labeled $n$-gons, allowing straight-angle vertices, this yields exact reachability while preserving simplicity precisely within each orientation class. In $\mathbb{R}^d$, it yields mutual reachability of all full-dimensional labeled $n$-point configurations when $n\ge d+2$, while orientation is the only obstruction when $n=d+1$. Writing configurations as coordinate matrices, each move becomes a rank-one perturbation of the identity. Explicit one-move curves and three-move conjugation words yield a finite-word endpoint map with invertible differential at every affinely spanning configuration. The inverse function theorem gives exact local reachability with all intermediate states confined to a prescribed neighborhood, and connectedness makes it global. An elementary ear-reduction argument establishes the required connectivity of simple-polygon orientation classes. The same algebra determines exactly the group generated by positive moves. The proof is existential and nonquantitative.

Authors: Thomas Depian, Joseph Dorfer, Boris Klemz, Matthias Pfretzschner, Lena Schlipf

Deciding whether a given graph admits a planar straight-line drawing where each vertex is placed on some point from a given finite point set is known as Point Set Embeddability and is a classical problem in graph drawing. In this paper, we study the more general embeddability question where the placement of each vertex $v$ is restricted to a list $L(v)$ of admissible points. We first study the case where the given point set is in convex position. We show that this case is NP-hard even if the given graph is a matching and bi-labeled, i.e., each vertex has at most 2 admissible points. On the positive side, we present two efficient algorithms for the case where the given graph $G$ is connected (and not necessarily bi-labeled): if $G$ is equipped with a combinatorial embedding that needs to be respected, we can solve the problem in polynomial time; otherwise we can solve it in FPT-time with regard to the maximum vertex degree. In particular, this answers an open question by Frati, Glisse, Lenhart, Liotta, Mchedlidze, and Nishat [GD'13]. We then turn our attention to the more general case where the given point set is not necessarily in convex position. Here, we show NP-hardness for bi-labeled paths; notably these graphs have a unique combinatorial embedding and maximum degree two. We also present an FPT-algorithm with respect to the vertex cover number for the special case of bi-labeled graphs. We complement this latter result by establishing paraNP-hardness in the tri-labeled setting for vertex cover number 2 and polynomial-time solvability for vertex cover number 1 and arbitrary $L$. Finally, we study optimization and extension variants, where we want to maximize the number of edges or extend a partial drawing, respectively. For the former, we show APX-hardness and for the latter, we provide a parameterized complexity dichotomy under natural extension parameters.

Authors: Cassandra Marcussen, Elchanan Mossel, Colin Sandon

We study the query complexity of recovering a planted assignment from a random constraint-satisfaction instance with one-sided noise. We consider the following 1-CNF recovery problem: an unknown binary string with $n/2$ ones and $n/2$ zeros is queried at individual variables. A query to a $1$-variable returns "$1$" with probability $p$ and "$0$" otherwise, while a $0$-variable always returns "$0$" (each query is a fresh noisy draw). The goal is to recover the binary string with probability at least $1 - δ$. While the naive counting argument may suggest a query complexity of $\log_2 \binom{n}{n/2}=Θ(n)$, we show that the query complexity is $(1+o(1))c(p) \frac{n}{2} \left( \log_2 n + \log_2(1/δ)\right)$, where $c(p) = \tfrac{1}{-\log_2(1-p)}$. We then study planted $k$-CNF satisfaction with one-sided noise. Each $k$-set containing a $1$-variable is included as a clause independently with probability $p$, and an algorithm may ask whether any given $k$-set is a clause. Unlike the $1$-CNF case, a clause-existence query is one-shot: each $k$-set either is or is not a clause, so repeating yields no new information. The model is one-sided because an observed clause certifies that at least one queried variable is assigned 1, whereas its absence does not certify all are assigned 0. The goal is to recover the planted assignment with probability at least $1 - δ$. The counting baseline is $Θ(n)$, yet we prove a query complexity of $(1+o(1))\,c(p,k)\, \frac{n}{2}\left( \log_2 n + \log_2(1/δ)\right)$, where $c(p,k) = \tfrac{1}{k(-\log_2(1-p))}$. These bounds are for adaptive algorithms. We also prove bounds for nonadaptive algorithms, showing that for fixed $p$, adaptivity gives a factor $\exp(Θ(k))$ improvement. Our results also imply lower bounds for noisy sorting of $\{0,1\}$-valued strings, and we study a variant of the model with negations.

Authors: Daniel Bauer, Jan-Henrik Haunert

Given a $k$-coloured point set $P\subseteq \mathbb{R}^2$, the $k$-coloured Non-crossing Euclidean Travelling Salesperson Problem (short $k$-ETSP) asks for $k$ non-crossing closed curves, where one curve spans one corresponding colour class, such that the curves are pairwise non-crossing and the sum of their Euclidean lengths is minimised. This problem is NP-hard as $1$-ETSP is the standard Euclidean Travelling Salesperson Problem. We present a polynomial-time $(k+ε)$-approximation for $k$-ETSP.

Authors: Alexander Firbas, Robert Ganian, Sylvain Meunier, Martin Nöllenburg

Two-layer drawings of bipartite graphs place the vertices of each part on one of two parallel lines and draw the edges as straight-line links. Traditionally, the optimization goal is to find vertex permutations on one or both layers that minimize the induced number of edge crossings. This problem is NP-hard, and crossing-minimal solutions may still contain many crossings. Recently, there has been growing interest in an orthogonal optimization goal, namely removing all crossings by vertex splitting, i.e., replacing original vertices by two or more copies and distributing the adjacencies among them. In this paper, we study a natural extension of the two-layer vertex splitting problem in which the vertex order on one layer is constrained by a given auxiliary tree $T$, motivated by applications such as the visualization of anatomical hierarchies in the Human Reference Atlas. We investigate the parameterized complexity of this problem and obtain two main contributions: (1) a fixed-parameter algorithm with respect to the number $k$ of splits, and (2) an ETH-tight single-exponential fixed-parameter algorithm with respect to the maximum degree of $T$. Moreover, we build on the latter result to obtain an ETH-tight single-exponential algorithm for the classical unconstrained version of the problem, improving upon the previous $O^*(2^{k\cdot \log k})$ algorithms. Finally, we also implement our algorithm and show that it performs well in practice.

Authors: Thomas Depian, Thomas C. van Dijk, Martin Nöllenburg

Geophylogenies are a common type of diagram for visualizing the evolutionary history of species in a geographic context. As a drawing problem, these diagrams are commonly modeled as a rooted binary ''phylogenetic'' tree $T$ where every leaf is associated with a point feature (''site'') in a rectangular map range. The tree is drawn downward planar, its leaves are placed at equidistant positions on the upper boundary of the map, and each leaf is connected to its corresponding site by a straight-line leader. Prior work focuses on minimizing the number of leader crossings, or avoiding leaders altogether. In this paper, we explore paged geophylogenies, where the leaders can be partitioned into multiple pages where only crossings within a page are counted. For the general case, where each page can contain an arbitrary subset of the leaders, we provide an integer linear programming (ILP) formulation for minimizing the number of pages, and a polynomial-time algorithm for a special case that is equivalent to a one-sided tanglegram. We argue that, from a visualization perspective, instead each page must contain only leaders for a single subtree, and provide an $\mathcal{O}(n^7)$ time algorithm for minimizing pages in this setting - which also involves improving the fastest known algorithm for testing the existence of a crossing-free labeling. Counter to what our worst case bound suggests, our implementation can handle instances with hundreds of sites within a second, as we show in our experimental evaluation, which further investigates the trade-offs between leader crossings and the number of pages.

Authors: Vera Chekan, Robert Ganian, Viktoriia Korchemna

An upward planar drawing of a directed acyclic graph is a planar drawing where every edge is pointed upward from its tail to head. Upward planar drawings are among the most natural drawing styles of directed graphs and have been researched in a variety of different settings, recently including that of drawing extension. In the drawing extension setting, one asks: given a graph $G$ and a (typically connected) subgraph $H$ of $G$ with a drawing $Γ(H)$, can we complete $Γ(H)$ to a drawing of $G$? Drawing extension problems have been studied for numerous drawing styles; the vast majority of these are NP-hard and a typical approach aimed at circumventing their intractability is to design parameterized algorithms where the parameter measures "how much" of $G$ is still missing from the pre-drawn graph $H$. Most algorithms obtained within this framework require only a small number of edges to be missing from $H$ in order to remain efficient. In this article, we present a fixed-parameter algorithm for extending upward planar drawings which overcomes this drawback by using the $\textit{vertex+edge deletion distance}$ as the parameter, thus achieving tractability even for instances with many missing edges. A key ingredient towards our result is a novel characterization of "canonical" sets of missing edges which cross a horizontal line segment in the drawing.

Authors: Jon Kleinberg, Amin Saberi, Xizhi Tan, Grigoris Velegkas

Motivated by learning from heterogeneous and overlapping data providers, we study a stylized model of distribution learning from restricted conditional samples. The goal is to learn an unknown distribution $p$ on a finite domain $[n]$. The learner is given a fixed family of queryable sets $\mathscr{S} \subseteq 2^{[n]}$, and each query to $S \in \mathscr{S}$ returns an independent sample from the conditional distribution $p(\cdot \mid S)$. Learnability is governed by the co-occurrence graph associated with $\mathscr{S}$: two domain elements are adjacent if they appear together in some queryable set. Pointwise consistency is achievable when this graph is connected on the target support. PAC learning requires more: it is possible when the co-occurrence graph is complete. The optimal sample complexity of PAC learning ranges from nearly linear to quadratic. Every query family with complete co-occurrence graph admits sample complexity $\widetilde O(n^2/ε^2)$, and this bound is tight in the worst case. On the other hand, if $[n]$ is queryable then ordinary sampling improves the bound to $Θ(n/ε^2)$, and this cannot be improved further even if every set is queryable. More generally, we identify hierarchical comparabilityas a sufficient structural condition on $\mathscr S$ under which the optimal complexity is nearly linear, $\widetilde Θ(n/ε^2)$, with pairwise query families as a canonical example. Finally, the full range of polynomial rates between linear and quadratic is attainable: for every $α\in (1,2)$, there exists a query family with optimal PAC rate $\widetilde Θ(n^α/ε^2)$.

Authors: Bernhard Haeupler, Richard Hladík, Václav Rozhoň, Robert E. Tarjan

We construct a heap with strong beyond-worst-case performance guarantees and explore the analysis of such heaps. First, we unify existing notions of the working-set bound for heaps by proving that essentially all of them are equivalent - with the notable exception of the so-called stack-like bound, which is strictly stronger. This equivalence simplifies the theoretical landscape and extends the range of applications of heaps with working-set bounds. Second, we present the first heap implementation that has the amortized stack-like bound and supports $\mathcal O(1)$-time decrease-key and $o(\log^*n)$-time insert.

Authors: Tolson Bell, William Kuszmaul

Bucketized cuckoo hashing is a practically efficient hash table scheme in which each object $u$ is stored in one of two buckets $h_1(u), h_2(u)$ of capacity $\ell$. For any bucket size $\ell\in\mb{N}$, there is a threshold $ε^*(\ell)=(2/e)^\ell\mathrm{poly}(\ell)$ for which there exists a way to fill the hash table to any load factor less than $1-ε^*$ with low probability of an error. Queries and deletions only need to check two buckets to find whether an object exists. Our contribution is to give a new insertion procedure for bucketized cuckoo hashing. For any $δ\in[.99^\ell,1]$, our algorithm can fill the hash table to load factor $1-ε=1-(1+δ)(ε^*)$ with an expected run time of $O(δ^{-1}(ε^*)^{-1})$ per insertion. This gives the first $\mathrm{poly}(ε^{-1})$ insertion time bound, and the first $f(ε^{-1})$ time bound for load factors that are very close to the optimal threshold. Additionally, our algorithm (which can be viewed as a variation of the classic random-walk algorithm) comes with a very strong amortized guarantee: it performs $O(1)$ amortized expected evictions per insertion. Furthermore, we show that the traditional random-walk algorithm cannot match this guarantee. Finally, our insertion protocol also comes with the feature that, for any key $u$ in the hash table, the query algorithm can \emph{guess} which of the two bins $h_1(u), h_2(u)$ the key $u$ is in with probability $1 - o(1)$ of being correct. Thus positive queries can complete in $1 + o(1)$ expected bin accesses.

Authors: Anton Bukov, Shay Solomon

In the dynamic {\em minimum dominating set (MDS)} problem, the goal is to efficiently maintain an approximate MDS in an $n$-vertex graph with vertex costs in $[1/C,1]$ undergoing edge insertions and deletions. In STACS'19 [HIPS19] it was shown that an $O(\log n)$-approximate MDS can be maintained in {\em unweighted graphs} with $O(Δ\cdot \log n)$ update time, where $Δ$ is an upper bound on the maximum degree throughout the update sequence, and in STOC'23 [SU23] this was extended to weighted graphs and improves the approximation guarantee to $(1+ε)\ln Δ$. Is it possible to achieve $\mathrm{poly}(\log n)$ update time without any dependence on $Δ$, for any nontrivial graph family? This basic question has remained open even in {\bf forests} and even for {\bf unweighted instances}. The {\em arboricity} $α=α(G)$ of a graph $G$ is the minimum number of edge-disjoint forests whose union is $G$, and is a standard measure of sparsity. While $α$ is bounded by $Δ$ in any graph, various real-world graph families exhibit a significant gap between $α$ and $Δ$. In this work, we show that one can maintain an $O(α)$-approximate MDS with update time $O(α\cdot \log (Cn))$, for dynamic graphs whose {\em arboricity} is bounded by $α$ throughout the update sequence. This replaces the dependence on $Δ$ in prior update bounds with $α$, while also improving the approximation guarantee for bounded-arboricity graphs. In particular, for any graph family of constant arboricity, our algorithm gives an $O(1)$-approximation with $O(\log (Cn))$ update time. To achieve this result, our algorithm departs from prior {\em greedy-based} approaches, relying instead on the {\em primal-dual framework} and new structural insights specific to bounded arboricity graphs.

Authors: Marius Garbea, Rishi Patel, Emmanouil Pountourakis

We prove that no algorithm for the knapsack secretary problem can be $1/e$-competitive. The knapsack secretary problem was first introduced by Babaioff, Immorlica, Kempe, and Kleinberg (2007). There have been many improvements to the achievable competitive ratio since then, but the $1/e$ impossibility barrier has remained unchanged. Many combinatorial variants of the secretary problem, including knapsack secretary, inherit the $1/e$ impossibility by embedding the single-choice problem as a special case. We construct a family of hard instances for the $1$-$B$ knapsack secretary problem, which is a special case of the general knapsack secretary problem, to improve the existing impossibility result. We show in this special case that the competitive ratio is at most $0.36437 < \frac{1}{e} - 0.0035$. Our construction is similar to the one used by Abels, Ladewig, Schewior, and Stinzendörfer (2022), for which they show an impossibility of $1/(1+e)$ for ordinal algorithms, where only the relative ranks of the items are known. Our work resolves an open question of theirs by showing that $1/e$ cannot be achieved even in the cardinal case of the $1$-$B$ knapsack secretary problem. We complement our impossibility result with a simple algorithm for $1$-$B$ knapsack secretary that is $(1/5.10-o(1))$-competitive for every fixed $B \geq 2$. This improves the guarantee obtained by applying general-purpose random-order knapsack algorithms to this special case.

Authors: Ben Bals, Panagiotis Charalampopoulos, Oded Lachish, Solon P. Pissis, Hilde Verbeek

We prove an elementary yet powerful combinatorial lemma: in any rooted tree with $L$ leaves, the number of nodes whose depth is smaller than the number of their leaf descendants is at most $L$. For any string $T$ of length $n$, a direct application of this lemma to the suffix trie of $T$ yields that the number of substrings of $T$ whose length is smaller than their number of occurrences in $T$ is at most $n$. This combinatorial insight leads to space-efficient data structures with optimal query times for string counting problems via the following algorithmic framework: store the counts for the at most $n$ ``frequent'' substrings of $T$ in a preprocessing step, and use a reporting query to count for the ``infrequent'' substrings. Our framework acts as a convenient black box, lifting indexes with reporting time $\mathcal{O}(|P|+|\textsf{Occ}_T(P)|)$ to support counting queries in time $\mathcal{O}(|P|)$, where $P$ is the queried pattern and $\textsf{Occ}_T(P)$ is the set of occurrences of $P$ in $T$. As applications, we show efficient indexes for consecutive occurrences, weighted sequences, strings with utilities, and non-overlapping occurrences.

Authors: Constantinos Daskalakis, Gabriele Farina, Brian Hu Zhang

We give a $\text{poly}(d, p, \log(1/ε))$-time algorithm that computes an $ε$-approximate fixed point of any $\ell_p$-nonexpansive map $f : \mathcal{X} \to \mathcal{X}$, where $\mathcal{X} \subset \mathbb R^d$ is a convex compact set and $p$ is an even integer. This is the first algorithm with $\text{poly}(d, \log(1/ε))$ runtime for any fixed $p \ne 2$. Our techniques are based on a computationally efficient version of Sion's theorem for non-compact minmax problems, and extend to more general total search problems that admit low-degree polynomial potentials.

Authors: Arman Mollakhani, Pieter Wuille, Dongning Guo

In the Bitcoin system, transactions arrive continuously at miners' mempools and await inclusion in future blocks. Every non-coinbase transaction must spend one or more unspent outputs created by previous transactions, inducing dependency constraints among transactions in the mempool. At the same time, miners are economically incentivized to prioritize transactions with higher fee rates, measured as transaction fee per unit size. This paper formulates the mempool linearization problem: given a set of transactions with associated fees, sizes, and dependency relationships, compute a dependency-respecting transaction ordering that maximizes fee-rate efficiency while supporting efficient updates as the mempool evolves dynamically. The problem is characterized through a partition of transactions into disjoint dependency-respecting subsets ordered by decreasing aggregate fee rate, together with an equivalent LP formulation. Motivated by structural properties of basic feasible solutions in the simplex method, a new algorithm called spanning forest linearization (SFL) is developed. Operating directly on the transaction dependency graph, SFL iteratively merges and splits chunks of transactions to refine a global ordering, and is guaranteed to terminate at an optimal solution. Evaluation on both synthetic and real-world Bitcoin mempool data shows that SFL consistently computes optimal linearizations with substantially lower runtime than competing approaches, including a method based on the parametric preflow algorithm of Gallo, Grigoriadis, and Tarjan. These results indicate that SFL provides a practical and scalable framework for transaction prioritization by decentralized miners in large and rapidly evolving mempools. SFL has also been incorporated into the Bitcoin Core codebase for transaction cluster linearization.

Authors: Fuwei Xie

We study a one-dimensional exact-cover problem parameterized by three integers $(L,V,W)$: given an integer profile $a_0,\dots,a_{n-1}$, write it as a nonnegative integer combination of a length-$L$ ``horizontal'' block $[1,\dots,1]$, a value-$V$ ``vertical'' block, and a value-$W$ block, while minimizing the number of value-$W$ blocks. We give an $O(n)$ algorithm that eliminates the horizontal-block coupling by a class-wise difference recurrence and then matches residues modulo $V$ on the last $L$ columns. We prove that its output is always a valid \emph{lower bound} on the optimum, via a mod-$L$ class invariant. We then prove the main result: once the profile is dense enough --- a \emph{heavy base} $\min_c a_c \ge B(L,V,W)$ with \[ B(L,V,W)=\Big\lceil \tfrac{(L-1)\lcm(V,W)}{LW}-1\Big\rceil\,W+(L-1)(V-1), \] the bound is \emph{exact}. The exactness proof is a branch-cut argument on the exact dynamic program: two structural equivalences (a horizontal-to-vertical exchange modulo $V$, and a vertical reduction modulo $\lcm(V,W)/W$) collapse the DP to the residue computation, and the two summands of $B$ are exactly the reserves that keep both equivalences from producing a negative residual. We further show the threshold is sharp: for $(L,V,W)=(3,6,4)$, $B=14$, and the profile $(17,16,13,16,17)$ with $\min_c a_c=13$ makes the algorithm strictly undercount, so $B-1$ does not suffice. An independent exact dynamic program agrees with the algorithm on every tested profile with $\min_c a_c\ge B$ across many parameter triples, and the test harness \texttt{test\_general.c} is released for reproduction. The contribution is the algorithm, the branch-cut exactness proof, and the sharp threshold $B(L,V,W)$.

Authors: Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang

This paper studies fractional matching on general graphs in the fully online model of Huang et al. (JACM 2020), in which all vertices arrive online and remain available for only a limited time. The algorithm must make irrevocable fractional matching decisions while the relevant vertices are simultaneously available. We extend the classic Water-Filling algorithm, also known as Balance and originally introduced by Kalyanasundaram and Pruhs (TCS 2000), to the fully online setting. Using an online primal-dual framework, we prove that the generalized Water-Filling algorithm achieves a competitive ratio of $2-\sqrt{2}\approx 0.586$ in the fully online model, and that this analysis is tight. To surpass the $2-\sqrt{2}$ barrier, we incorporate the ideas of eager matching and history-based pricing into Water-Filling. We show that the resulting algorithm achieves an improved competitive ratio of $0.599$, thereby establishing that Water-Filling is not optimal in the fully online setting. On the hardness side, we further improve the known upper bound for fractional fully online matching, reducing the previous best bound of $0.6297$ due to Eckl et al. (ORL 2021) to $0.6132$.

Authors: Debmalya Panigrahi, Fan Wei, Ian Zhang

Language generation in the limit is an elegant model introduced by Kleinberg and Mullainathan [KM24] to formally study language generation by an algorithm that learns solely based on example strings. In this model, an algorithm is said to correctly generate from a language if it never makes an error after some finite time. In contrast, even sophisticated language models are known to regularly hallucinate in practice. In this paper, we initiate the study of language generation in the limit with (infinite) hallucination, i.e., the algorithm may generate incorrect strings infinitely often, but the errors occur at a limited rate (possibly even with 0-measure). We first show that hallucination, even at rate 0, makes generation in the limit strictly more powerful: there are language collections that cannot be generated with finite error but can be generated with infinite error, even when errors occur on a 0-measure set of time-steps. Furthermore, while all countable collections are generatable with finite error, we show a strict hierarchy of (uncountable) language collections characterized by the hallucination rate. This hierarchy extends to breadth, the fraction of the target language generated. While all countable collections can attain the optimal breadth of 1/2 [KW26b], we show strict separation at every breadth and hallucination rate. Finally, we study generation in the limit without repetition, where the algorithm may not repeat strings. This lets us compare the sets of correct and incorrect strings generated, rather than the fractions of correct and incorrect time-steps. Once again, we demonstrate a strict hierarchy at every hallucination rate and breadth. Taken together, these results reveal rich structure in language collections generatable in the limit with hallucination and establish hallucination rate as an important parameter in the theoretical study of language generation.

Authors: Shuchi Chawla, Dimitris Christou, Trung Dang, Zhiyi Huang

We study a mechanism design problem in which a seller controls access to information about a set of stochastic alternatives, and a buyer sequentially acquires information in order to choose a single alternative with high value. The value distributions of the alternatives are known to both parties. The seller posts non adaptive prices for revealing each alternative's realized value, and the buyer responds optimally by following a Pandora's Box strategy: deciding which alternatives to inspect and when to stop by accepting the best inspected alternative. The seller's goal is to maximize his expected revenue, i.e. the total payment collected from all inspections. We study the revenue objective through the lens of simplicity versus optimality. Our main result is that a simple and efficiently computable pricing scheme obtains a 4 approximation in the worst case to the optimal revenue. This pricing rule equalizes the Weitzman indices across all alternatives. In contrast, we show that equalizing the prices themselves can be an unbounded factor worse than the optimum. Furthermore, for several natural special cases, including identically distributed alternatives and monotone hazard rate distributions, we fully characterize the optimal pricing. Finally, we also study a variant of our model under optional inspection, where the buyer may select an alternative without observing its realization. In this setting, we obtain an n/(n-1) approximation for the special case of n identically distributed alternatives, as well as a 2 approximation for the special case where each alternative's value distribution has support size two. Overall, our results highlight both the computational challenges and the power of simple pricing schemes in selling information to a sequential searcher.

Authors: Julien Baste, Cléophée Robin, Marie-Emilie Voge

Diversity optimization seeks multiple high-quality solutions that are sufficiently different from one another, providing a richer representation of the solution space than a single optimum while avoiding the prohibitive cost of complete enumeration. In this work, we introduce the notion of natural diversity, a general condition that connects a combinatorial problem $Π$ and a diversity measure $\texttt{dist}$. We show that if a pair $(Π,\texttt{dist})$ is naturally diverse and we have in hand a completion algorithm that, from a partial solution of $Π$, can complete it into a solution of $Π$, then we can produce a parameterized algorithm solving the diversity variant of $Π$ with regard to the distance $\texttt{dist}$ when parameterized by the size of the solutions and the number of expected solutions. Furthermore, we show that several widely used diversity measures, including pairwise disjointness, Hamming distance, Jaccard distance, and the Otsuka-Ochiai coefficient (under both minimum and sum aggregation), satisfy the natural diversity property for problems in which all the solutions have the same size. Finally, we demonstrate the applicability of our framework by deriving fixed-parameter algorithms for diverse variants of Minimum Vertex Cover and Minimum Steiner Tree. Our results broaden the scope of parameterized diversity algorithms by accommodating natural solution-size parameterizations and a wider class of diversity measures.

Authors: Robert E. Tarjan, Xiaoyang Xu

The pairing heap is a "self-adjusting" implementation of a heap (priority queue) that is widely used in practice because it is simple and efficient. We introduce and analyze a simplified version of the pairing heap that we call the pure pairing heap. Our innovation is to eliminate the assembly pass during delete-min operations. We obtain the following amortized time bounds for operations on pure pairing heaps: $O(\log n)$ time per delete-min, $O(\log\log n \cdot \log\log\log n)$ time per decrease-key operation, and $O(1)$ time for each insert or meld. These bounds match those recently obtained for a more complicated version of pairing heaps, the multipass pairing heap}. These bounds also match the known lower bounds for self-adjusting heaps, except for the decrease-key bound, which is within a factor of $\log\log\log n$ of the lower bound. The main novelty in our analysis is to partition heap items into groups and to analyze each group separately. Our analysis extends to give the same bounds for lazy pairing heaps, a multitree version of pairing heaps.

Authors: Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg, Yibin Zhao, Gernot Zöcklein

In their seminal paper [Cohen et al., 2016], Cohen, Musco, and Pachocki proposed a natural and simple online spectral sparsification algorithm: rows $a_1, a_2, \ldots \in \mathbb{R}^d$ of a matrix $A$ arrive one-by-one, and when row $a_i$ arrives, it is appended to sparsifier $\tilde{A}$ (after appropriately reweighting it) with probability proportional to its current leverage score $$ τ^{\mathrm{OL}}(a_i)=a_i^\top(A_i^\top A_i)^\dagger a_i, \text{ where }A_i = [a_1, a_2, \ldots, a_i]^\top $$ or otherwise discarded forever. For oblivious streams, they showed that this maintains a $(1\pmε)$-spectral approximation $\tilde{A}$ of every $A$ with $O(dε^{-2}\log^2 d)$ many rows. A natural question is whether the same algorithm works for adaptive streams, where each row may depend on the algorithm's previous random choices. The original proof does not extend directly: it analyzes the process in isotropic position with respect to the final matrix $A$, which is not fixed in advance under adaptivity. As an extension of this proof framework remained elusive, various algorithmic variants have since been suggested. In this paper, we show that the original online leverage-score sampling algorithm is indeed robust to adaptive adversaries. Our main technical contribution is a Freedman-type matrix martingale inequality with an evolving isotropic map, allowing the isotropic map used in the concentration argument to change with the stream. As a consequence, this gives the first online sparsification algorithm for adaptive streams that yields a sparsifier of near-optimal size $O(d \varepsilon^{-2}\log^2 d)$ whose working memory is proportional to the size of the sparsifier. For the special case of spectral graph sparsification, we provide an implementation that additionally runs in time near-linear in the stream size.

Authors: Konstantin Tikhomirov

Let $Π$ be a $k\times n$ sparse random matrix. For a fixed $r$-dimensional subspace $V\subset{\mathbb R}^n$, let $U_V:{\mathbb R}^r\to{\mathbb R}^n$ denote an isometry from ${\mathbb R}^r$ onto $V$. The product $ΠU_V$ is a central model in randomized dimension reduction and has been studied primarily through trace and Gaussian comparison inequalities. In this work, we develop an approach to the spectral norm of the matrix product $ΠU_V$, based on entropy estimates for level sets of vectors $x\in V$. Combining the method with existing estimates, we show the following. Assume that \[ k\ge C\,r(\log\log r)^2,\qquad p\ge (\log k)/k. \] Let $Π$ be a $k\times n$ matrix with i.i.d. entries equidistributed with the product $b\,ξ$, where $b$ is a Bernoulli($p$) random variable and $ξ$ is mean-zero, independent of $b$, and satisfies $|ξ|\le1$ almost surely. Then with high probability \[ \|ΠU_V\|\le C\sqrt{kp}. \] Matching results hold for other random models with negatively associated entries.

Authors: Rohan Chauhan, Ioannis Panageas

Learning the natural parameters $z \in \mathbb{R}^n$ of discrete distributions $μ_z$ from independent samples constrained to a subset $S \subseteq \{0,1\}^n$ is a foundational challenge in high-dimensional statistics. Existing methods for efficiently estimating truncated Boolean product distributions, notably the work of [Fotakis et al' COLT'20, Algorithmica '22], require either strong local connectivity assumptions on $S$ -- a property denoted fatness -- or stringent anti-concentration assumptions and necessitate the total mass of the truncation set to be a constant with respect to $n$. Moreover, the results in [Fotakis et al' COLT'20, Algorithmica '22] suffer from sample complexities that scale as $Ω(2^n)$ if the mass of $S$ is exponentially small in $n$. In this work, we circumvent these limitations by analyzing the geometry of $S$ under the measure $μ_z$. We refine the existing parameter estimation guarantees under the fatness assumption, improving the prior sample complexity to $O( \log n / ε^2)$ for $\ell_\infty$-recovery, matching the untruncated minimax rate. We further generalize fatness using the notion of influence utilized in the analysis of Boolean functions and provide sufficient conditions for efficient inference. Notably, unlike previous work, our method does not require sampling at arbitrary parameterizations of the model. Lastly, we establish a theoretical lower bound demonstrating the sample complexity exhibits an intrinsic exponential dependence on the width of the model and the minimum distance between elements in the set.

Authors: Eric Balkanski, Jason Chatzitheodorou, Dimitris Fotakis, Thanos Tolias

The knapsack secretary problem is a generalization of the classical secretary problem where the accepted items must satisfy a knapsack constraint. A line of work has developed constant-competitive algorithms for this problem, with successive improvements culminating in the current best-known competitive ratio of $0.153$. A natural open question was whether the optimal $1/e$ competitive ratio for the classical secretary problem is also achievable for the knapsack secretary problem. We answer this question negatively by showing that no $(1/e - 0.0001)$-competitive algorithm exists for the knapsack secretary problem. The analysis of the family of hard instances we construct proceeds in three steps. First, we reduce the cardinal problem on these instances to an almost-ordinal problem. Second, we formulate a linear program that captures the performance of almost-ordinal algorithms on this instance family. Finally, we exhibit a feasible dual solution whose objective value is strictly below $1/e$. We also give an algorithm that improves the best-known competitive ratio from $0.153$ to $0.178$.

The Theory Group in the Department of Computing Science at University of Alberta invites applications for a one-year (with the possibility of extension) postdoctoral fellowship position. The successful applicant is expected to work closely with Mohammad Salavatipour and Zachary Friggstad and their students in the areas of approximation algorithms for combinatorial optimization problems.

Website: https://friggstad.github.io/pdf_advertisement_2026.pdf
Email: zacharyf@ualberta.ca

By shacharlovett

I applaud Jensen Huang and industry leaders for coming out in support of open large language models. The entire tech sector minus Anthropic has now signed on. Now that the movement has momentum, I urge the signatories to endorse something even more radical that would truly separate us in our economic competition with China: The USA should heavily invest in models not just with open weights, but with open source and open corpus.

Let me back up in case you missed it. Last Friday, Huang pasted a short letter on Twitter calling for American investment in “a strong, open ecosystem” around open source artificial intelligence. “Open source…created a shared foundation of knowledge on which generations of American engineers and entrepreneurs built their institutional sovereignty,” Huang predicts that a similar thing will happen with the embrace of open source AI.

Part of this letter was a plea to the Trump administration, which had been sending signals about banning open source software in a protectionist move to squash insurgent Chinese language machines. Seeing that this would benefit Anthropic and OpenAI and no one else, the CEOs of all of the big and small tech firms quickly signed on to Huang’s letter on Friday.

This is an amazing, positive development, and I want to air some points that Huang left out. I’ve been passionately calling for a deeper investment in open source language models on this blog for years. In fact, this post from last July makes a bunch of points about what I think is necessary for this to happen, and I don’t think any of it has changed.

You should go read that post, but let me summarize what I said for the present moment. What is needed to build a good language model is people, compute, and data. It’s not clear how much of each of these you need, but the answer seems to be a lot. We’ve always had the people, though the promise of impossible riches has lured many smart young minds away from more ethical paths. But now that we have the backing of the entire tech industry, I think this base is covered.

What about compute? Hyperscalers and their economic bedfellows always want you to believe that their massive datacenter buildout is a moat from us open source plebes. But the Chinese models have complicated this story and shown you can get by on the cheap. No one has precise estimates, but models from Chinese companies DeepSeek and Moonshot were arguably trained using under ten million dollars. Dozens of AI startup “NeoLabs” with few concrete ideas are currently being given 10x that by venture firms. Good VCs could make a small bet on the open ecosystem to juice their other investments. Compute for open models will require a massive industrial consortium, but it would cost each member of the consortium a minuscule fraction of their war chests. Let’s work together to build computing agreements for open source development.

Once these models are built out in the open, there is no doubt that they will only get dramatically more efficient. We’ve seen time and time again that machine learning is a field that innovates through “frictionless reproducibility.” Research, code, and data out in the open, evaluated by competitive benchmarking, rapidly improve machine learning systems. It also makes them more efficient. In last year’s post, I wrote about how high-quality ImageNet models went from something only trainable at Google to something you could build on a desktop in less than a year. These sorts of efficiency gains happened throughout the 2010s. The secrecy of labs in the 2020s has harmed the broader engineering field, even though the artifacts produced have been beyond impressive. Put everything out in the open, and we’ll figure out how to make it faster and more efficient. It’s guaranteed.

That brings us to the actual hard part. The data. As my friend and colleague Alyosha Efros loves to remind us, “It’s all about the data,” and language models are trained on unfathomable amounts of it. Discovery in lawsuits has revealed that companies trained these models on pirated libraries of books, academic papers, and copyrighted imagery. The models are trained on collaborative knowledge bases like Wikipedia, countless volunteer forums like Reddit, and all of the public code on GitHub. They are trained on the transcript of every video you post to YouTube. All of this collective work by human society gets slurried into proprietary software so a few zealots can get rich. This is a bad outcome!

The companies are all up front about this use. They have been found liable in court. They have admitted it in papers they have written. They claim this is all fair use because the training was transformative of the texts. Fine, if that’s the case, then it’s fair use to take the outputs of their models and build new ones. This is called “distillation.” Chatbot terms of service agreements do not negate my argument. That the Trump administration is flirting with banning distillation is a travesty.

But I want something bigger. The biggest step to making competitive open source models is allowing the broader community fair use access to the same material the companies used. This is the open corpus. If closed models can exist, then open models should be allowed a level playing field. This will require a long overdue rethinking of intellectual property and what we owe the people who create it.

I think all of these challenges are surmountable. We’re going to have to (a) get young people to care about open source instead of becoming impossibly rich. (b) get billionaires to collaborate in a non-winner-take-all fashion, and (c) have a long hard conversation about copyright law, intellectual property, and fair use standards. But we’ve thrived in an open ecosystem before ChatGPT. It hasn’t even been half a decade of closedness. With the blessing of the entire tech industry, it’s time to open things up again.

Subscribe now

The title of this post is a coinage of Kevin Kelly. His dedication also inspired me to write this post.

By Ben Recht

Authors: Papangkorn Apinyanon

We prove that the solution-search problem for the pencil puzzle Ice Walk is ASP-complete. Our reduction maps Hamiltonian cycles in an undirected maximum-degree-3 spanning subgraph of a rectangular grid graph bijectively to Ice Walk solutions.

Authors: Aparna Gupte, Seyoon Ragavan

We show that under a plausible number-theoretic conjecture, for any constant $s$ there exists an $s$-server private information retrieval (PIR) protocol that on an $n$-bit database requires communication $\exp(O((\log n)^{1/s} (\log \log n)^{1-1/s}))$. Previous constructions attaining the same communication required $2^{O(s)}$ servers. Our number-theoretic conjecture is implied by existing conjectures, namely the generalized repunit conjecture and Schinzel's hypothesis H (either one of these conjectures would suffice alone). Our result builds on the ``matching vector family + $S$-decoding polynomials'' framework pioneered by Efremenko (STOC 2009) and recently refined by Ghasemi, Kopparty, and Sudan (STOC 2025). The main ingredient is a framework for constructing $S$-decoding polynomials with only $k+1$ nonzero coefficients modulo special products of $k$ primes, resolving an open problem posed by Ghasemi and Kopparty (ITCS 2026). By the lower bound shown by Ghasemi and Kopparty, this is the minimum achievable sparsity. We also empirically validate our construction and make our result unconditional for all $s \leq 15$. We also apply our techniques to regimes where $s$ grows with $n$, showing under a stronger variant of our number-theoretic conjecture that the communication complexity of $s$-server matching-vector PIR can be superpolynomially reduced from the previous state of the art for any $s \leq \exp(o(\sqrt{\log \log n/\log \log \log n}))$. The main result for $s = O(1)$ and its proof were discovered in a GPT-5.5 Pro conversation prompted by the authors.

Authors: MingZe Sun, Haiyong Jiang, Bingchen Yang, Haoxuan Song, Yidi Li, Jun Xiao, Peter Wonka

Boundary representation (B-rep) is the standard format for computer-aided design (CAD). This article proposes a lightweight two-stage diffusion-based B-rep generation framework, TG-Diff, that achieves efficient, high-quality B-rep generation by decoupling topology and geometric modeling. In contrast to previous work that generates topology as a collection of vertices, edges, and surfaces together with their relationships, TG-Diff represents topology only as a collection of surfaces and their adjacency relationships. This surface-centric representation inherently alleviates the geometric and topological inconsistencies between separately generated surfaces, edges, and vertices, simplifying the generation process. Based on the surface-centric representation, we develop two independent diffusion models that generate surface adjacency relationships and surface latents, respectively. By using topology as guidance, the surface generation process becomes more stable, leading to stronger structural completeness in the generated B-rep models. The topology diffusion model adopts a Discrete Diffusion Model (D3PM) for efficient binary sampling, avoiding the slow inference of autoregressive methods. Surface latent generation employs a conditional latent diffusion model with a lightweight DiT architecture, where surface adjacency guides geometry generation while reducing computational cost. Finally, edges and vertices are derived from the decoded adjacent surfaces via post-processing to form a final watertight B-rep. Despite its compact computational footprint (82.18M parameters and 2.2 GFLOPs), TG-Diff excels in the validity metric while achieving superior performance on all COV, MMD, and JSD metrics across the DeepCAD and ABC datasets.

Authors: Anders Aamand, Mikkel Abrahamsen, Simon Bartlmae, Arindam Khan, Linda Kleist, Csaba D. Tóth

We consider the problem of online packing of convex polygons into a strip by translations. While online algorithms with a constant competitive ratio have been known for rectangles for decades [Baker and Schwarz, SICOMP 1983], the current best algorithm for convex polygons has competitive ratio $O(n^{\log_2 3-1}\log n) = O(n^{0.59})$, where $n$ is the number of polygons. This algorithm was described by Aamand, Abrahamsen, Beretta, and Kleist [SODA 2023], who also proved a lower bound of $Ω(\sqrt{\log n/\log\log n})$ on the competitive ratio of any algorithm. Their lower bound is obtained via a reduction from \emph{online sorting}, a problem introduced in the same paper, for which they established a lower bound on the competitive ratio. We introduce a new, natural online problem that we call online TSP scheduling. Here, points $x_1,\ldots,x_n$ arrive online from a metric space $(M,d)$, and upon arrival each $x_i$ must be assigned a visit time $p_i\in[0,\infty)$ satisfying $|p_i-p_j|\ge d(x_i,x_j)$ for all $j

Authors: Junye Ji

We formalize in Lean 4 the Kannan-Bachem Smith normal form algorithm for nonsingular square integer matrices. The program returns $S,U,U^{-1},V,V^{-1}$ and proves $UAV=S$, $U^{-1}SV^{-1}=A$, four inverse identities, the Smith divisibility conditions, and equality of $S$ with a canonical reference matrix. Stabilization terminates because each recursive pass strictly decreases the binary size of the active pivot; the outer algorithm recurses on the lower-right block. The computation also emits a flat trace of designated sign-magnitude arithmetic leaves. Branch conditions, quotients, Bezout data, and matrix entries are taken from the recorded primitive runs. Composite phases form their traces by concatenating the charge lists returned by the executed children. Verified self-delimiting codecs define the input and output sizes. Coefficient and work recurrences, closed by a kernel-checked polynomial-envelope calculus, give fixed polynomial bounds for both trace cost and the encoded length of the five output matrices. The theorem concerns these arithmetic primitives; structural operations and compiled Lean runtime are outside the model.

Authors: Bo Peng, Zhihao Gavin Tang

We study online metric facility location in the random-order model with arbitrary positive opening costs. A finite set of candidate facilities and their costs is known in advance, while an adversary fixes a multiset of demand points that arrives in a uniformly random order. This setting includes both prescribed candidate sites and the classical finite full-space node-cost model. For a known horizon, we give a deterministic $4.2674$-competitive algorithm, improving the previous factor $33$ for nonuniform opening costs. At rank $t$, the algorithm uses the positive normalized rank $q_t=t/n$, chooses a candidate minimizing $d(x,y)+λ_t f_y$, where $λ_t=\min\{1,q_t/μ\}$, and opens it when the current connection distance covers this penalized objective. The analysis uses a monotone one-round charge and an upper-envelope decomposition to control later points and the first point of each optimal cluster. With unit opening costs, the rule reduces exactly to a cutoff on the distance improvement attainable from a nearest candidate. A supplementary appendix gives the sharper analysis of the closely related zero-start rank cutoff and obtains a ratio below $3.2805$. We also prove a $3-o(1)$ lower bound for arbitrary randomized online algorithms. The lower bound already holds with uniform costs on a prescribed candidate set and transfers, without loss, to the finite full-space model with nonuniform opening costs. Together with the recent competitive ratio below $2.42$ for full-space uniform costs, this yields a strict separation between the full-space uniform- and nonuniform-cost models.

Authors: Bartłomiej Bosek, Wojciech Nadara, Michał Pilipczuk, Anna Zych-Pawlewicz

Let $\mathscr{C}$ be a class of graphs of bounded expansion and $r,k\in \mathbb{N}$ be fixed. We give a dynamic data structure that for a given dynamic graph $G$, updated by edge insertions and deletions subject to the promise that $G\in \mathscr{C}$ at all times, maintains the answer to the following two queries: (a) Does $G$ contain a distance-$r$ dominating set of size $k$? (b) Does $G$ contain a distance-$r$ independent set of size $k$? The data structure is randomized with error probability bounded by $\varepsilon$, for a parameter $\varepsilon>0$ fixed upon the initialization. The amortized update time is $\log^c n\cdot \log \frac{1}{\varepsilon}$, where $n$ is the vertex count of $G$ and $c$ is a constant that depends only on $r$, $k$, and $\mathscr{C}$. In the case of the first query, the data structure can also output a distance-$r$ dominating set of size $k$, if existent. We also prove that when $r=1$, our data structure for the dominating set query can be implemented even if we only assume that the maintained graph $G$ has degeneracy bounded by a constant $d$, yielding a simpler data structure with an improved amortized update time of $2^{k^{{\cal O}(d)}}\cdot \log^3 n\cdot \log \frac{1}{\varepsilon}$. Finally, we prove that in graphs of degeneracy at most $d$, one can maintain an ${\cal O}(d^2)$-approximation of the minimum size of a (distance-$1$) dominating set with amortized expected update time $d^{{\cal O}(1)}\cdot \log n$.