Theory of Computing Report

I hope the intent of my call on Monday was clear: we should strive for something that any team can build from scratch as long as they have access to the training corpus, the software, and computing resources. We want something open to the public, as the models are a reflection of public intelligence and culture. As Colin Fraser remarked on Bluesky, “there’s no going back to the world before we knew that if you make a language model large enough it appears to become a little guy who sometimes solves open math problems and sometimes makes you insane.” These language models are built upon humanity’s collective, cultural intelligence, and I believe they should thus be open and accessible to everyone.

But what “open” exactly means is tricky. A laudable example of an open corpus model is Olmo from Ai2. Their model report details all of the data used. For pretraining, they use a mix of data from Wikipedia and Wikibooks, web pages extracted by Common Crawl, academic papers sourced from arXiv papers uploaded with LaTeX, code curated from GitHub repos with flexible licenses, and math webpages from FineMath 3. Earlier versions of the Dolma corpus also include Reddit threads, papers from Semantic Scholar, and public-domain books from Project Gutenberg. All of this data is available to everyone.

Now, here’s a question for the purists out there. FineMath 3 is generated using annotations from the Llama LLM. On the one hand, technically speaking, Llama is not an open corpus model. On the other hand, the FineMath dataset is free to download. I’d argue this still counts.

Even if you grant me that one, you’ll find a lot more use of LLMs in the data pipeline in the Olmo tech report. For instance, to generate some of the math training data in the later stages of training, the team uses Qwen. Qwen is not an open-corpus model. For some of the more complex reasoning, they use thinking traces from GPT4. That’s not an open model in any capacity. If you are using a closed-corpus model to generate training data for your open-corpus model, have we ended our game for full openness?

I’m not a purist, but the vague world of distillation is genuinely complicated. Distillation is not a cleanly defined action, but roughly describes the practice of collecting the text outputs from one language model to serve as the training set for another. What we’re allowed to use and not use is incredibly confusing. Even if we just go back to pure text, it’s hard to say what training data is actually legally acceptable under “the law.”

The law is confusing and unsettled. If you buy a physical book, scan it, run OCR, and add it to your training corpus, that counts as “fair use.” If you buy the exact same text as an ebook and add it to your training corpus, that’s violating the e-book licensing agreement. The fact that there is a distinction between these two actions is absurd and stupid. Stupidity is unavoidable in our complex legal code. It doesn’t get less stupid when you try to understand how distillation meshes with the terms of service for use of LLMs.

I’m thinking out loud and consequence free here on the newsletter. I’m happy to admit that it’s complicated. But we’re going to have to change or fight laws that prevent us from just outcomes. If we want to prevent a concentration of power at OpenAI or Anthropic, we need to think about what laws are just and right to prevent that.

Anthropic CEO Dario Amodei, in his typically blindered, insufferable way, chimed into the open models debate on Monday, arguing that the US should “ban industrial-scale distillation” but that he’s not calling for banning open-weight models. His letter is riddled with contradictions like this. I don’t care about his tortured reasoning because it’s still the case that the far more defensible position is banning closed-weight models.

Closed models are indefensible. Sure, we should give Alex Radford, Ilya Sutskever, Sam Altman, and Dario Amodei some credit because I would have never guessed that the models would be as useful as they are today. As Fraser said, there’s no going back to the time before we knew that. However, you don’t have to give them too much credit because you could also argue they should be in jail. If you think that is hyperbole, I’d like you to read the wikipedia page of Aaron Swartz. Or read this in-depth article in the Financial Times about the online libraries used to train our current language machines. The librarians are hunted across the globe by the FBI. The LLM entrepreneurs are gazillionaires and can pay billion-dollar settlements to cover their asses. We can have long, pedantic quibbles about what’s legal and what’s not. We can also ask, “What is right?” and “What is just?” The current situation where the best American models remain closed is deeply wrong.

Subscribe now

By Ben Recht

Authors: Gilberto Gil F. G. Passos, Eber Assis Schmitz, Sildenir Alves Ribeiro

This article presents the development and validation of an artificial market for Brazilian Real Estate Investment Trusts (REITs), known as Fundos de Investimento Imobiliario (FIIs), using agent-based modeling methodology. The central contribution of this work is the integration, within a single multi-agent system, of the FII value chain, from the generation of real estate revenues subject to vacancy and operational costs, through dividend distribution, to the trading of shares by heterogeneous investors mediated by a double auction mechanism with an order book. The model incorporates endogenous macroeconomic variables, such as the Selic, the Brazilian benchmark interest rate, and inflation, and represents agent heterogeneity through a behavioral decomposition into fundamentalist, speculator, and noise trader components, modulated by individual financial literacy levels. The model was calibrated using the Method of Simulated Moments applied to the historical series of the IFIX index, the Brazilian REIT market index, between 2021 and 2025. The validation results, obtained using two distinct methods, demonstrate that the model reproduces the main stylized facts observed in the real market: (i) the coverage rate of calibrated moments exceeds 75 percent; (ii) 96 percent of simulated trajectories are structurally indistinguishable from real IFIX periods according to the nearest-neighbor criterion; and (iii) stylized facts such as the power law of autocorrelations of absolute returns and aggregational Gaussianity emerge spontaneously, without being incorporated into the calibration objective function. The results of the validation process indicate that the artificial market captures structural dynamics of the FII market, opening perspectives for its use as a computational laboratory for the analysis of regulatory policies and pricing mechanisms.

Authors: Michael A. Bekos, Eleni Katsanou, Philipp Kindermann, Aikaterini Maria Ntasiou, Maria Eleni Pavlidi, Soeren Terziadis

While drawing planar graphs with few slopes and few bends is a well-studied problem, corresponding extensions to beyond-planar graphs still remain mostly unexplored. Motivated by this observation, in this work, we provide bounds on the slope number of biconnected $1$-planar graphs when two bends are allowed along each edge. Our contribution is an incremental drawing algorithm that produces $2$-bend $1$-planar drawings of biconnected $1$-plane graphs with maximum degree $Δ$ using any prescribed set of $Δ$ pairwise distinct slopes.

Authors: Pengbo Li, Haowen Yan, Xiaomin Lu, Binbin Lin

Cartographic generalization is essential for generating multiscale map representations by balancing information preservation and cartographic readability. However, automated generalization remains challenging because existing approaches often treat spatial similarity evaluation, cartographic constraints, and parameter optimization as separate processes, limiting adaptive and interpretable control across scales. This study formulates cartographic generalization as a constrained multiscale similarity optimization problem and proposes a similarity-driven framework for adaptive generalization control. The framework integrates multiscale spatial similarity as an optimization objective to quantify representation consistency between original and generalized data, while incorporating cartographic constraints to regulate readability, smoothness, and geometric validity. A unified objective function is optimized to automatically identify scale-dependent parameter configurations for different generalization algorithms. Experiments using multiple line simplification algorithms, target scales, and similarity measures, including geometric, structural, and learning-based metrics, demonstrate that the proposed framework achieves an effective balance between similarity preservation and cartographic abstraction. The results further show that combining similarity optimization with cartographic constraints provides more consistent and interpretable parameter control than relying on similarity evaluation alone. This study provides a unified optimization perspective that connects similarity assessment, constraint modeling, and algorithm control, contributing to adaptive and automated cartographic generalization.

Authors: Jérôme Michaud, Sergey Korotov

We define a mesh refinement algorithm based on the rule of dividing the largest angles of triangular elements of planar partitions in focus into $n$ equal parts, and analyse the (geometric) properties of triangulations generated by this technique. This largest-angle $n$-section rule is compared with the classical longest-edge $n$-section rule, where it is the longest edges which are split into $n$ equal parts. The longest-edge bisection and trisection are known to produce nondegenerate triangulations (possibly with hanging nodes), but the longest-edge $n$-sections with $n\geq 4$ always produce (infinite) sequences of triangles with minimum angles tending to zero (moreover, their relevant maximum angles tend to $π$), thus breaking the minimum and maximum angle conditions. We show that this degeneration effect is not a consequence of $n$-section itself. For every $n\geq 2$, the largest-angle $n$-sections produce partitions satisfying the minimum angle condition (and, therefore, the maximum angle condition). More precisely, if the initial triangle has its smallest angle $γ_0>0$, then all descendant triangles have angles bounded below by $m_n=\min\left\{γ_0,\fracπ{3n}\right\},$ and, correspondingly, bounded above by $π-2m_n<π$. We also show that the recursive largest-angle $n$-section algorithm always produces a family of triangular partitions, i.e. the maximum diameter of level-$k$ descendants tends to zero as $k \to \infty$.

Authors: Charles Wade, Devon Beck, Robert MacCurdy

Functional gradients control part behavior by varying structure, material, or process conditions across an object. Yet functionally graded fabrication is usually framed as grading geometry or material distribution rather than the slicing and fabrication process itself. In material-extrusion printing, many functional effects arise from slicer-controlled mechanisms, including local toolpath planning, surface treatment, material assignment, color mixing, and printer state. Mainstream FFF slicers expose these mechanisms as settings, but users must manually reconstruct heterogeneous intent as assigned mesh regions. We present slicer project compilation, an automated workflow that lowers heterogeneous implicit designs into slicer-native .3MF projects containing sub-meshes, settings, recipes, and process-state assignments. The compiler partitions spatial attributes into finite regions, extracts aligned sub-meshes, and serializes them into the target slicer's project dialect while preserving native toolpath planning, preview, support generation, and printer profiles. We demonstrate the approach across three parameter classes: settings meshes, virtual extrusion, and color or material halftoning. We also introduce calibrated translation models for temperature-responsive foaming TPU and PLA, allowing high-level density and Shore-hardness fields to drive fabrication-ready process fields. Printed examples include graded toolpath settings, foaming-filament properties, combined texture and process-state control, and color or material-mixture halftoning, replacing more than 2,500 repetitive manual slicer interactions. Our open-source implementation connects heterogeneous design representations to existing slicer ecosystems and provides a reusable foundation for automated, scalable functionally graded FFF fabrication.

Authors: Kelvin Luu, Csaba D. Tóth

For $n$ points in the plane and an $\varepsilon>0$, we construct a $(1+\varepsilon)$-spanner with $O(n/\varepsilon)$ edges in which every edge has $\tilde{O}(1/\varepsilon^3)$ crossings, hence the total number of crossings is $\tilde{O}(n/\varepsilon^4)$, furthermore the ratio between the lengths of any two crossing edges is $O(1/\varepsilon^2)$. Our spanner construction substantially improves on the previous upper bound for the number of crossings in a $(1+\varepsilon)$-spanner, and it is the first spanner construction that ensures $O(1)$ crossings per edge for any constant $\varepsilon>0$. In contrast, we construct: $n$ points in the plane for which every $(1+\varepsilon)$-spanner has $Ω(n/\varepsilon^3)$ crossings, $n$ points for which every $(1+\varepsilon)$-spanner has an edge with $Ω(1/\varepsilon^{5/2})$ crossings, and 4 points for which every $(1+\varepsilon)$-spanner contains two crossing edges where one is $Ω(1/\varepsilon)$ times longer than the other.

Authors: Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Gabriele Farina

We study the simultaneous approximation of constant-degree polynomials over convex sets. For any family of $m$ degree-$d$ polynomials and any convex set ${H} \subseteq \mathbb{R}_{\ge0}^n$, we construct an $ε$-Cover of the joint value set $\{(f_1(x), \dots, f_m(x)) : x \in {H}\}$ in the $\ell_\infty$-norm. This cover is of size $n^{O(\log(mn)/ε^2)}$, provided the polynomials have constant range over the smallest $\ell_1$-ball inscribing ${H}$. Our approach extends classical net-based sparsifications for linear functions (e.g., Lipton, Markakis, and Mehta [2003]) to arbitrary families of constant-degree polynomials over general convex sets. We use a two-step scheme: first, we construct a quasi-polynomial pre-cover of the family on the smallest $\ell_1$-ball containing ${H}$ by using a concentration argument and leveraging a connection between Bernstein approximation and multinomial distributions; we then compress the pre-cover to ${H}$ by using a recursive degree reduction and feasibility programs anchored at points of the pre-cover. The existence of these covers immediately yields a unified framework for Quasi-Polynomial Time Approximation Schemes (QPTAS) across a wide range of a problems, including fixed-degree polynomial minimization over polyhedral sets, Constraint Satisfaction Problems (CSPs), Free Games, variational inequalities with polynomial operators (which implies guarantees for local Nash equilibria in polynomial games), and additive approximation for normalized densest $k$-subhypergraph on $O(1)$-uniform hypergraphs.

Authors: Ran Ben Basat

For integers $k\le n$, let $L_{k,n}$ be the set of words over $[n]$ of length at most $k$ in which no symbol is repeated. We present a nondeterministic finite automaton (NFA) of size $3.918^k n^{O(1)}$, improving on the $4^{k+o(k)}n^{O(1)}$ construction of Ben-Basat, Gabizon, and Zehavi. Our proof organizes several classical ingredients---product automata, hashing, and coefficient estimates---into a gadget-amplification framework: We take the product of many copies of a small local NFA gadget, whose language is a subset of $L_{r,c}$, and hash the $k$ input symbols to copies and local colors. The hash family guarantees that, for every repetition-free input, some hash sends at most $r$ symbols to each copy such that the resulting projection in every copy is accepted by the local gadget. Taking the nondeterministic union of the corresponding product NFAs yields a global NFA. Amplifying a $200$-state gadget for $L_{6,11}$ obtained from the small Witt design $S(4,5,11)$, this framework gives a $3.967^k n^{O(1)}$-size NFA. We then introduce the compose-and-compress technique, which deletes the expensive middle layers of these products and replaces paths across the deleted bands with sound one-symbol shortcut transitions. We apply it twice, once for enhancing the amplification framework and again for the local gadget, obtaining the stated result.

Authors: Giordano Andreola, Susanna Caroppo, Giordano Da Lozzo, Marco D'Elia, Giuseppe Di Battista, Fabrizio Frati, Fabrizio Grosso, Maurizio Patrignani

The Partial Drawing Extensibility problem, for short PDE, takes as input a triple $\langle G,H,Γ_H\rangle$, where $G$ is a planar graph, $H$ is a subgraph of $G$, and $Γ_H$ is a straight-line planar drawing of $H$, and asks whether $Γ_H$ can be extended to a straight-line planar drawing of $G$. Patrignani [Int. J. Found. Comput. Sci. (2006)] proved that the PDE problem is NP-hard, exploiting instances in which $H$ is highly disconnected. In this paper, we study the PDE problem under the requirement that the initial partial drawing $Γ_H$ is biconnected. We show that PDE remains NP-hard even for instances in which $H$ is a biconnected graph with faces of bounded size, $G$ is subcubic, and the part of $G$ that is not in $H$ consists of length-$2$ paths. The complexity of PDE remains however open when $H$ is connected (or even biconnected) if $G$ has a fixed embedding. In this setting both a polynomial-time algorithm or an NP-hardness proof seem to be elusive targets. As a step towards tackling this problem, we study instances of PDE in which $H$ is biconnected, $G$ has a fixed embedding, and the rest of the graph consists of $p$ length-2 paths, and present an $O(p^2 n)$-time algorithm, a result in sharp contrast with the NP-hardness of the variable embedding setting. Moreover, with an approach based on the Existential Theory of the Reals, we show that, if $H$ is biconnected, the problem is FPT parameterized by the vertex cover number of $G$, both in a fixed and in a variable embedding setting.

Authors: Or Zamir

We prove that $k$-coloring on $n$-vertex graphs has a randomized algorithm running in time $(2-\varepsilon_k)^n$, where $\varepsilon_k>0$ for every fixed $k$. Previously, only the cases $k\leq 6$ were known to have faster solutions than the general $O^\star\bigl(2^n\bigr)$ time algorithm of [Björklund, Husfeldt, Koivisto, SICOMP 2009] that computes the chromatic number. We resolve this long-standing open problem by generalizing and combining tools from the $(k+2)$-coloring to $k$-list-coloring reduction of [Zamir, ICALP 2021] and the hypergraph-containers based approach in [Zamir, STOC 2023]. Together with new algorithms for list-coloring instances mixing long and short color lists, this yields an iterable reduction from $(k+1)$-list-coloring to $k$-list-coloring over fixed palettes.

Authors: Chandra Chekuri, Rhea Jain

We study length-constrained generalizations of Directed Steiner Tree (DST) and Directed Steiner Forest (DSF) in planar digraphs. In both problems, the input is a directed graph with edge costs. DST asks for a min-cost subgraph connecting a root to a given set of terminals, and DSF asks for a min-cost subgraph connecting each of a given set of source-sink terminal pairs. In the length-constrained setting, each edge has both a cost and a length, and the input includes a length bound $h$; the goal is to find a min-cost subgraph connecting each terminal pair via a path of length at most $h$. Our work is motivated by a recent line of results showing that several network design problems that are traditionally hard in directed graphs admit polylogarithmic approximation ratios in planar digraphs. We give polylogarithmic bicriteria approximation algorithms for length-constrained analogues of DST and DSF in planar digraphs. Our approximation ratios match the best known for DST and DSF in planar digraphs, with an $O(\log k)$ violation of the length constraint, where $k$ denotes the number of terminals (or terminal pairs). As corollaries, we obtain polylogarithmic approximations for buy-at-bulk DST and DSF in planar digraphs.

Authors: Binhong Jiang, Gehao Wang

In this paper, we consider the problem of updating the directed minimum spanning tree (DMST), when the given sample tree is subject to the weight changes, edge deletions and edge insertions. We present an implementation for updating the tree to a DMST using the weighted matroid intersection algorithm. Our algorithm focuses on maintaining a dynamic auxiliary graph, which plays a central role in the matroid intersection algorithm, and governs the iterations from the given tree to a DMST. Each iteration is guaranteed to yield an improved solution. We also provide an implementation of this algorithm and some experimental analysis.

Authors: David Alemán Espinosa, Naveen Garg, Sharat Ibrahimpur, Neil Olver, Chaitanya Swamy

We introduce a novel variant of stochastic load balancing that enables a quantitative tradeoff between the practical benefits of non-adaptive policies and their performance limitations. Our model describes a solution in two stages. In the first stage, given only job-size distributions, we reserve a set of at most k machines for each job (a k-reservation). In the second stage, after observing job-size realizations, we assign each job to one of its reserved machines (a consistent assignment). The goal is to minimize the expected makespan. If k=1, we get the standard stochastic load balancing problem of finding a non-adaptive assignment with minimum expected makespan. If k is equal to the number of machines, then we obtain an all-powerful omniscient optimum that can tailor the assignment arbitrarily to the job-size realizations. We give a number of results that quantify this tradeoff. Most saliently, we show that in the setting of identical machines, a 2-reservation suffices to achieve a constant-factor approximation to the omniscient optimum, establishing a "power-of-two-choices" result for stochastic load balancing. We also show that this no longer holds true in the more challenging setting of related machines. Nonetheless, we give a number of positive algorithmic results for this setting: a true O(log m/log log m)-approximation; a bicriteria O(1)-approximation by reserving twice as many machines per job relative to an optimal k-reservation; and a 2-reservation whose cost is within a constant factor of what the adaptive optimum can achieve.

Authors: Yves Baumann, Gernot Zöcklein

We present a new solver-free parallel spectral sparsification algorithm for weighted graphs that relies only on parallel low-diameter decompositions and independent sampling. This yields the first algorithmic improvement over prior, solver-free parallel sparsification approaches since Koutis (2014) and, for the first time for a practical algorithm, eliminates any dependence on the target approximation accuracy $ε$ in the algorithm's work and depth. Our algorithm works by sub-sampling edges according to their robust connectivity, as introduced by Kapralov and Panigrahy (2012). We show how to estimate the robust connectivities of $G$ in an extremely simple manner: we create multiple random sub graphs $G_p$, where each edge in $G$ is sub-sampled independently with probability $p_e = \min \{w_e \cdot p, 1\}$. Then, we run a Low Diameter Decomposition in each of the graphs. If $u$ and $v$ often share a cluster in the LDDs, then this provides us with an upper bound on the robust connectivity of the edge $e = (u,v)$. Carefully invoking this procedure for $O(\log n)$ different values of the probabilities $p$ then allows us to obtain sufficiently good estimates for sub-sampling. We additionally complement the theory with an experimental evaluation demonstrating strong performance across relevant graphs and sparsity regimes.

Authors: Francesco Tosoni, Gabriele Mencagli

Grammar-compressed matrices (the mm-repair family) store a matrix's non-zero structure as a RePair straight-line program (SLP), supporting matrix-vector products in time and space proportional to the compressed size. We target the regime where this is decisive on a GPU: when the uncompressed matrix exceeds device memory, so footprint (not floating-point throughput) is the binding constraint. Our SLP is a directed acyclic graph (DAG) of out-degree 2, and the right product $y=Mx$ is a single bottom-up sweep (leaves to roots): a conflict-free gather. We make the grammar properly layered (every nonterminal child one level below its parent) via pass-through completion, which inserts identity nodes to carry values upward until consumed. This yields a streaming evaluation in which each level reads only the level below and writes the next, so the live set fits in two alternating read-only/write-only buffers instead of scaling with the whole grammar; the per-level width equals the live set. On genotype matrices, where a polygenic score is exactly the right product $y=Gβ$, a CUDA implementation shows a clear space advantage: a device footprint 4 to 8 times smaller than a materialized cuSPARSE CSR baseline, single-vector times within a small factor of cuSPARSE, and consistently lower energy. Because the sweep needs only an associative combine, the same engine and schedule evaluate any monoid homomorphism over the grammar by swapping a small leaf/combine/emit policy; the same reachability sweep then scales to the billion-edge Software Heritage graph ($261$ TB dense and unmaterializable, $21\times$ smaller serialized than CSR), where the memory argument holds. We frame this as an algorithm-engineering case study: structural metrics (depth, live-set width, completion cost) are measured, architecture-independent grammar properties, whereas time and energy are profiled on a single board.

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.