Theory of Computing Report

There is a lot of anxiety about ai wiping off mathematics, including theoretical computer science. It’s funny that we wanted ai to cut *their* jobs, and instead it’s *our* jobs that are cut (maybe). My expectation of what is going to happen is rather flat, and I am open to various scenarios. Still I wanted to make some points.

First, at the moment of this writing, I am not so worried about ai killing the field. There are so many problems in math, and the literature is so unmanageably vast and technical, that I am not particularly shocked that using massive resources one can solve *some* problems. It is very different if the resources can solve *the* problems. For example I, and I am sure many others, have tried to use ai to solve problems in computational complexity and so far didn’t get much. I do find ai to be a very useful assistant, but so are many other things. It may be that the next level of solving target problems (as opposed to finding targets) may prove the most difficult to reach.

I want to suggest an option for the community to put ourselves in a position of strength, in case one really fears the impact of ai. I think ai can easily enough be “frozen” and made much less useful for future research. The way to do this is simple: We could stop feeding it. It was humiliating enough to post papers online only to be asked later by the publisher to pay for “gold open access.” But now that there is this new way to exploit, plagiarize, and monetize our creations on a massive scale, it may be too much. Suppose starting immediately all new math is communicated in ways that ai can’t easily scrape. There are many ways to do this; we could still put papers online, but allow only much more limited access, compatible with human beings but not ai scraping. It coud be similar to what is done for example at the Internet archive, where you can read a book but not easily download it. I am not going to go more in details. While ai would remain very useful for things on the table until that moment, I think it would quickly become much less useful for new lines of research, series of papers building on each other, etc. This would put the community in a position of strength as keeper of knowledge. After a while, things could be reassessed.

We should not forget that the models can do math only because back then we chose to be nice and so taught them how to do it for free.

By Manu

Tenure-track position in theoretical computer science. Two course per semester teaching load, competitive salary. UNF’s School of Computing offers BS, MS, and PhD degrees in Computing. Candidates must have earned Ph.D. by start date of August 2, 2027.

Website: https://unf.wd5.myworkdayjobs.com/unfjobs/job/Jacksonville-FL/Professor—Computing–Open-Rank-_JR103390
Email: indika.kahanda@unf.edu

By shacharlovett

Authors: Hung Mai, Hai Nguyen, Luong Doan, Ngoc Vu, Khanh Nguyen, Nhung Duong, Tuan Do

In this paper, we formulate three communication tasks for empirical optimal transport: distributed coupling sampling, cost-evaluable coupling output, and scalar value-certified sampling. Our main result is a field-code compiler: any communicated transport field approximating an optimal empirical Monge map to error $η$ can be completed by sparse target-cell residuals into an exact-marginal value-certified sampler with scalar certificate $W_1(μ,ν)\leq U\leq W_1(μ,ν)+2Δ$, where $Δ$ is the public target-partition diameter. The certificate accuracy is controlled by $Δ$ alone. The field error $η$ controls residual communication under a cell-margin condition; without a margin, $η$ alone does not bound residuals. We instantiate the compiler via adaptive local-affine and tensor-product spline codes with $d(m+1)^db$ field bits in the spline case, plus residual lists charged separately. For lower bounds, exact Gap-Hamming embeddings prove certified output is hard, including a smooth cell-packing diffeomorphism family requiring $Ω(\varepsilon^{-2d/(d+4)})$ communication for any cost-evaluable, cost-certified, or value-certified protocol. The same gadgets admit zero-communication samplers, formally separating the sampler and certificate-bearing output models. These results identify the transport field as the right communicated object whenever a field code is available, primarily as a residual-sparsity tool.

Authors: Igor S. Sergeev

It is shown that the $\mathsf{OR}$-rank (covering rank) of the $2^n \times 2^n$ unique disjointness matrix is $n^{O(1)}(3/2)^n$, hence the known lower bound $1.5^n$ turns out to be essentially tight. By the way, an upper bound $1.89^n$ is obtained for the $\mathsf{SUM}$-rank (partition rank) of this matrix.

Authors: Ramin Javadi, Hossein Shokouhi

Given a graph $G=(V,E)$, a (proper) $k$-coloring for $G$ is a vertex coloring with $k$ colors such that every two adjacent vertices receive different colors. Suppose that the vertex set $V$ is partitioned into some groups, a proper coloring is called fair if for every color class, the difference between the number of vertices in any two groups does not exceed a given threshold. In this paper, we investigate the parameterized complexity of the fair coloring problem with respect to the structural parameters of the input graph. In particular, we prove that the problem is W[1]-hard with respect to the number of groups for forests and also graphs of modular-width two, even when the number of colors is equal to two. On the positive side, we prove that when the number of colors is equal to two, then the problem is FPT with respect to neighborhood diversity of the input graph. Moreover, in general, the problem is FPT with respect to neighborhood diversity and the number of groups. As a by-product, we prove that unary vector bin packing problem is W[1]-hard with respect to the dimension.

Authors: Fangqi Dong, Alex Lombardi, Fermi Ma

The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every $n$-qubit unitary $U$ is computable by efficient quantum circuits relative to some classical oracle $f = f_U$ depending on $U$. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly$(n)$ parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of variants of unitary synthesis. Our results include: (1) 1-query vs. 2-query unitary synthesis: we prove 1-query lower bounds for synthesizing random permutation unitaries $P\lvert x\rangle = \lvert π(x)\rangle$, as well as random alternating-basis phase unitaries $F_2 \cdot H^{\otimes n} \cdot F_1$. This gives 1-query lower bounds for "explicit" families of unitaries that have efficient (even 2-query) synthesis algorithms. (2) Upper bound for complex phase unitaries: we also consider complex phase unitaries $\lvert x\rangle\mapsto α_x \lvert x\rangle$, which have a clean 2-query synthesis algorithm with no obvious 1-query algorithm. In this case, we prove an upper bound: there are 1-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our lower bounds, we introduce and analyze two new cryptographic games: the oracle state search game and the oracle Choi state game. Compared to prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not "fully random". Finally, we also use the search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between 1-query unitary synthesis and quantum programs.

Authors: Theodoros Yianni, Nyan Raess, Farid Shahandeh

Generalized contextuality is a canonical distinguishing property of nonclassical generalized probabilistic theories, in particular quantum mechanics. Methods for certification and characterization of generalized contextuality of a given generalized probabilistic theory are well developed for prepare-measure and single-stage prepare-transform-measure scenarios. In a recent work [arXiv:2512.10000], a bottom-up, statistics-first linear-algebraic framework for contextuality in prepare-measure scenarios was introduced. We extend this approach to operational scenarios with sequential transformations with an arbitrary number of stages. We give a full decision procedure for contextuality of such scenarios within operational theories and analyze its computational complexity. In particular, our decision procedure has a complexity linearly exponential in the minimum generalized probabilistic theory (GPT) dimension, and polynomial in the number of procedures. We demonstrate our framework and approach through multiple examples, including Spekkens' toy theory and the 8-state single-qubit stabilizer theory. In particular, we construct an operational theory in which contextuality manifests itself only in the sequential structure of the transformations. Our findings thus shed new light on the significant role of compositional structures in the phenomenon of generalized contextuality.

Authors: Tomoyo Kikuchi, Takashi Kanai

Convex Collision-Free Regions (CCFR) is a collision handling method that explicitly represents local convex feasible regions to enforce non-penetration. Each feasible region is constructed from surrounding mesh primitive configurations, including edge-edge and vertex-face interactions. The resulting convex region represents admissible non-penetrating vertex displacements at the current configuration. Existing collision handling methods for deformable body simulation have largely relied on implicit representations of feasibility, resulting in either compromised robustness for secondary collisions and codimensional contacts or tight coupling with specific nonlinear optimization schemes. Our formulation constructs feasible regions independently for each vertex, defined prior to penetration, inherently accounts not only for primary collisions but also for secondary collisions and codimensional contacts, enabling highly scalable and parallelizable collision handling. These feasible regions encode geometric non-penetration constraints independently of physical contact response models. CCFR does not rely on nonlinear optimization and is compatible with simulation frameworks such as Extended Position-Based Dynamics (XPBD) that do not explicitly maintain interior feasibility during iterative updates. The effectiveness of CCFR is demonstrated across cloth, hair, wire, particle systems, and codimensional contact scenarios, showing versatile and efficient collision handling.

Authors: Chris Kapulkin, Kyle Koyanagi

We show stability of persistent path homology of path complexes. As a consequence, we deduce the stability of persistent path homology of hypergraphs and of sequence hypergraphs, and recover the known stability result for digraphs, originally due to Chowdhury and Mémoli.

Authors: Angelos Pelecanos, Jack Spilecki, Ewin Tang, John Wright

We give an algorithm which, given $n = O(d^2 \cdot (\log\log(d)/\log(d))^2)$ copies of $ρ$, estimates the eigenvalues of $ρ$ to constant error in total variation distance. Thus, we can learn the eigenvalues of a quantum state with fewer copies than the $Θ(d^2)$ needed to run full state tomography. This is the first improvement to spectrum estimation over the influential Keyl-Werner algorithm, which uses $n = Θ(d^2)$ copies, thereby resolving a question raised by Keyl and Werner in 2001 and refuting a 2016 conjecture of Wright. Our main technical tool is a new tomography guarantee, where the error of tomography in a particular direction $|w\rangle$ scales with $\langle w | ρ|w\rangle$ for all directions simultaneously. From this stronger "relative-error" bound, we recover better algorithms for principal component analysis in Bures distance and tomography in $χ^2$-divergence as corollaries.

Authors: Xiaobin Ren, Hans L. Bodlaender

A graph is outer k-planar if it admits a straight-line drawing in which all vertices lie on a circle and every edge is crossed by at most k other edges. We study the parameterized complexity of a broad collection of graph problems on outer k-planar graphs, with k as the parameter. Many graph problems are known to be XALP-hard when parameterized by treewidth or outerplanarity, and XNLP-hard when parameterized by pathwidth. We show that only a few such problems, including Binary CSP and Scattered Set, remain intractable on outer k-planar graphs, whereas a large class of the others become fixed-parameter tractable in this setting, assuming that an outer k-planar drawing of the input graph is given. These include List Coloring, Capacitated Dominating Set, Capacitated Vertex Cover, Target Outdegree Orientation, and Target Set Selection, among others. In addition to the algorithmic and complexity results, we establish several structural results. We show that outer k-planar graphs have mim-width at most k+2, that graphs of cut-width at most k are outer 2k-planar, and that graphs of feedback edge set number at most k are outer 6k-planar. We also show that many graph parameters are incomparable with outer k-planarity, thereby clarifying its position within the graph parameter hierarchy.

Authors: Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, Shlomo Tauber

Graph $k$-coloring is one of the classic NP-complete problems. Previous work has studied its average time complexity, defined to be the average runtime of computing a $k$-coloring over the set of all $k$-colorable graphs on $n$ vertices. A highly influential result of Dyer-Frieze from 1989 gave an algorithm with $O(n^2)$ average runtime for constant $k$. This quadratic runtime appeared natural (and possibly even optimal) since almost all $k$-colorable graphs have $Θ(n^2)$ edges, so one needs at least this time in order to read the (entire) input. However, this was later improved by Kučera in 1995 to average runtime $O(n^2/k)$ for every $k \leq n^{c}$ where $c \in (0, 1)$. Nevertheless, in the most interesting case of $k = O(1)$, the best-known bound remained quadratic in $n$. The true average complexity of the $k$-coloring problem has remained elusive for the last three decades. We break the longstanding quadratic barrier. Our main result in this paper shows that the exact average-case complexity of this fundamental problem is $Θ(nk)$ for every $k \leq n^{c'}$ and some $c' \in (0, 1)$. For $k = O(1)$, this reveals the average sublinear nature of $k$-colorability: the average-case complexity is linear in $n$, and thus sublinear in the size of the input. We further show that our $Θ(nk)$ average runtime is optimal, since a simple bound proves that every algorithm that correctly $k$-colors all $k$-colorable graphs requires $Ω(n k)$ average runtime. Our proofs draw on ideas from sublinear and local algorithms and also yield a local computation algorithm (LCA) for $k$-coloring with average-case probe complexity $\text{poly}(k)$. A key new ingredient in our algorithm is a method for certifying the unique colorability of random subgraphs, using tools from the theory of graph regularity.

Authors: Venkatesan Guruswami, Xuandi Ren, Shaoxuan Tang

The Unique-Machine Precedence Scheduling (UMPS) problem, introduced by [DKRSTZ22], seeks a makespan-minimizing schedule of precedence-constrained jobs when each job has a unique eligible machine. On the one hand, UMPS generalizes job shop scheduling by allowing the precedence graph to be an arbitrary DAG rather than a disjoint union of chains. On the other hand, UMPS admits approximation-preserving reductions to scheduling problems with communication delays, including the job-job delay model [DKRSTZ22] and the job-machine delay model [RSY23]. Despite its central role, the approximability of UMPS has remained poorly understood: even for unit-length jobs, known scheduling techniques do not seem to yield a non-trivial approximation, and the existence of a polylogarithmic approximation was left open by [DKRSTZ22]. On the hardness side, the previous best lower bound for unit-length jobs was only the 5/4 inherited from job shop scheduling [WHHHLSS97]. We prove that unit-length UMPS is NP-hard to approximate within any constant factor. We further show that, assuming NP is not in quasi-polynomial time, unit-length UMPS admits no polynomial-time $(\log n)^γ$-approximation for some constant $γ>0$. Via the known reductions from UMPS, these lower bounds also transfer to the corresponding unit-length communication-delay scheduling models. Our proof proceeds via a reduction from a hypergraph coloring promise problem. In the yes case, the input hypergraph admits a balanced coloring, while in the no case, the hypergraph has no large independent set. Instantiating this reduction with the hardness of [GL18] gives arbitrary constant-factor inapproximability, while combining the $4$-colorable $4$-uniform hypergraph coloring hardness of [GHHSV17] with a certain composition operation for hypergraphs yields the polylogarithmic factor inapproximability.

Authors: Huck Bennett, Matthew Fox, Bryant Morrell

Two linear error-correcting codes $\cal{C}_1, \cal{C}_2 \subseteq \mathbb{F}_q^n$ are called linearly equivalent if there is a linear isometry mapping $\cal{C}_1$ to $\cal{C}_2$. In this work, we generalize the notion of linear equivalence and study the minimum distortion $\cal{D}(\cal{C}_1, \cal{C}_2)$ of a linear mapping between codes $\cal{C}_1, \cal{C}_2 \subseteq \mathbb{F}_q^n$, which quantifies how similar $\cal{C}_1$ and $\cal{C}_2$ are. We introduce and study the Code Distortion Problem (CDP), which asks to find a minimum distortion mapping between two input codes $\cal{C}_1$ and $\cal{C}_2$. CDP generalizes the Linear Code Equivalence Problem (LCE), which is essentially the special case of CDP where $\cal{D}(\cal{C}_1, C_2) = 1$ and which is well-studied because of its role in cryptography. We prove that (decisional) CDP is $\mathsf{NP}$-hard to approximate to within any constant factor, and that it is in $Σ_2^P$. We also give a single-exponential-time $k^2$-approximation algorithm for CDP, where $k$ is the dimension of the input codes. Furthermore, we give a single-exponential-time $\big(\frac{2k + 1}{3})^2$-approximation algorithm for a natural special case of CDP, and we show that our analysis is tight in this case. We use techniques from analogous work on the Lattice Distortion Problem (LDP) by Bennett, Dadush, and Stephens-Davidowitz (ESA, 2016). We also introduce or study a number of additional concepts that might be of independent interest. These include an adaptation of the celebrated reduction of Goldreich, Micciancio, Safra, and Seifert (IPL, 1999) from the Shortest Vector Problem (SVP) to the Closest Vector Problem (CVP) on lattices to the analogous problems on codes; successive minima bases for codes; and the matrix $0 \to 0$ "norm" on subspaces.

Authors: Kuldeep S. Meel, N. V. Vinodchandran, Sourav Chakraborty

We study estimating the size of the union of sets $S_1,\dots,S_M$, where each $S_i\subseteqΩ$ is presented implicitly and arrives in a stream. We introduce Delphic sets, a class of streaming problems in which membership, sampling, and counting queries to each set are efficient, and show that this notion captures three well-known problems: Klee's measure problem (discrete version), test coverage estimation in combinatorial testing, and model counting of DNF formulas. Our primary contribution is a simple and efficient sampling-based algorithm that outputs an $(\varepsilon,δ)$-approximation of the cardinality of the union of Delphic sets in the streaming setting. It has space complexity $O(R\log|Ω|)$ and update time $O(R\log R\cdot\log(M/δ)\cdot\log|Ω|)$, where $R=O(\log(M/δ)\cdot\varepsilon^{-2})$. For the streaming Klee's measure problem, this gives the first algorithm whose update time depends linearly on the dimension $d$ for $d>1$, settling an open problem of Tirthapura and Woodruff (PODS 2012), and it directly yields efficient streaming algorithms for coverage estimation and DNF model counting. We further show that the space for coverage estimation can be made near-optimal at the cost of an update procedure in $\mathrm{P}^{\mathrm{NP}}$, revealing a time-space trade-off. A key strength of our approach is the simplicity of both the algorithm and its analysis, which makes it amenable to practical implementation. In this revised version, the algorithm and its correctness analysis have additionally been formalized and machine-checked in Lean 4. (Shortened for Arxiv)

Authors: Kevin Pratt

We show that for all $k$, there exists $\varepsilon_k > 0$ such that graph $k$-coloring can be solved by a randomized algorithm with one-sided error in time $O((2-\varepsilon_k)^n)$. Prior to this work and independent concurrent work of Zamir [arXiv, 2026], exponential improvements over the $2^n \cdot \mathrm{poly}(n)$-time algorithm of Björklund, Husfeldt, and Koivisto [SIAM Journal on Computing, 2009] were only known for $k \le 6$.

Authors: Xue Chen, Shengtang Huang, Xin Li

Min-wise hashing and its $k$-min-wise extension are fundamental tools in sampling, sketching, and similarity estimation. A standard approach to constructing such families is bounded independence. For ordinary min-wise hashing, the required degree of independence is fully understood: $Θ(\log 1/δ)$-wise independence is both sufficient and necessary. For $k$-min-wise hashing, however, the best previous result only showed that $O(k\log\log1/δ+\log1/δ)$-wise independence suffices, with no matching lower bound. We give a tight characterization of the amount of bounded independence required for $k$-min-wise hashing, proving that $Θ(k+\log1/δ)$-wise independence is both sufficient and necessary. This improves the previous upper bound and provides a matching lower bound. Consequently, the standard construction of bounded-independent hash families has seed length $O\big((k+\log1/δ)\log(N/δ)\big)$. In particular, for any polynomially small error $δ$ and any $k=Ω(\log N)$, it achieves the optimal seed length $O(k\log N)$. We also study random affine hash functions over $\mathbb{F}_2$ and show that, despite being pairwise independent, they may incur multiplicative error $Ω(\log n)$ even for ordinary min-wise hashing.

Authors: Or Stern, Or Zamir

In a seminal result of Yuster and Zwick, they showed that for any fixed $k$, the even cycle $C_{2k}$ can be detected in an $n$-vertex graph in time $O(n^2)$. For $4$-cycles, a folklore algorithm extends to listing: for any $t$, we can list $t$ different $4$-cycles, if such exist, in $O(n^2+t)$ time. Recently, Jin, Vassilevska-Williams, and Zhou obtained similar bounds for listing $6$-cycles. In this work, we generalize the above to cycles of sizes $8, 10, 12, 14,$ and $16$; we show that for all $k\leq 8$, we can list $t$ distinct $2k$-cycles in $\tilde{O}(n^2+t)$ time. In fact, our algorithm gives enumeration with pre-processing time $\tilde{O}(n^2)$ and delay $\tilde{O}(1)$. Additionally, for any fixed $k$, we present an optimal enumeration (and hence also listing) algorithm for all cycles of size at most $2k$. More generally, for any fixed $k$ and any $3\le i\le \frac{4k}{3}$, we present an algorithm with preprocessing time $\tilde{O}(n^2)$ and delay $\tilde{O}(1)$ that enumerates all cycles of sizes in the range $[i,2k]$.

Authors: Frederik Glitzner

Many fundamental problems in multi-agent systems involve the arrangement of agents, who have preferences over each other, on a target graph. These problems include, for example, Stable Matching, Seat Arrangement, and Coalition Formation. However, guaranteeing game-theoretically desirable properties such as exchange-stability or envy-freeness is difficult, as such solutions may not exist, and even if they do, they are often intractable to find, even in highly constrained settings such as path or cycle target graphs. In this paper, we challenge the classical setup and investigate what can be achieved when the structure of the target graph is a designable object for the central planner, rather than a fixed part of the input. We study this in the context of a natural pairwise stability criterion, which is similar to having spare seats. In particular, we introduce a highly flexible framework to efficiently design approximately optimal target graphs and associated pairwise-stable agent arrangements. Our model assumes that agents have (weak or strict) ordinal preferences over other agents. We show that classical results from stable matching theory can be extended and adapted to this much more general setting and can serve as a useful tool for navigating the trade-off between stability and computational efficiency. Our results highlight strict boundaries between tractability and intractability, and between local and global optimality. We also uncover intriguing connections to classical computational problems such as subgraph isomorphism, disjoint path partitioning, and bin-packing.

Authors: Konrad Anand, Alistair Benford, Heng Guo

We present a linear time approximation algorithm of the total variation distance between two product distributions. The main algorithm was found using ChatGPT 5.6 Sol Ultra.

Authors: Jiale Chen, Torsten Hoefler, Dan Alistarh

Adaptive rounding methods such as GPTQ, or equivalently Babai's nearest plane algorithm, round a real matrix to integers under a quadratic metric. They process the entries in a fixed order, one at a time, propagating each rounding error to the entries not yet processed through a triangular feedback matrix. We study the two-sided version of this task, in which fixed nonsingular basis matrices act on both the left and the right of the residual; the familiar one-sided case is the special case of an identity right basis. Vectorizing the matrix turns the two-sided objective into a quadratic metric whose Gram matrix is a Kronecker product, so the one-dimensional algorithm applies verbatim, but takes quartic time in the matrix dimension. We present GPTQ-2D, which produces the identical rounded matrix in cubic time. It rounds the entries anti-diagonal by anti-diagonal; entries on the same anti-diagonal are independent and are rounded in parallel.

Authors: Alex Zihan Xu, Stephen Jing Chick

We present the first in-place comparison-based sorting algorithm that sorts an array of $n$ elements using $n\lg n + O(n)$ comparisons with exponentially high probability and always $O(n)$ moves. This matches the information-theoretic lower bound up to an additive linear term despite making only linear moves and working in-place. For the worst-case, we present an algorithm that makes $n\lg n + O(n\lg^{(t)}n)$ comparisons and $O(tn)$ data moves, where $t$ is an integer parameter satisfying $2 \leq t \leq \lg^{*}n - 1$ and $\lg^{(t)}n$ denotes the $t$-time iterated logarithm, improving over the previous upper bound of $n\lg n + O(n\lg\lg n)$ comparisons and $O(n)$ moves when using constant $t>2$. We thus achieve the ultimate goal of minimal move in-place sorting via randomization whilst narrowing the gap to this goal in the worst-case. This advance primarily relies on a novel ordered set structure that supports searches in an optimal $\lg n + O(1)$ comparisons for $n$ elements.

Authors: Eros De Simone, Giuseppe Bifulco, Lorenza Di Mauro, Antonio Policicchio, Raoul Heese

We propose a sparse computational-basis encoding of voxelized molecular geometries that converts molecular reconstruction from full-state tomography into support recovery by computational-basis sampling. To realize the encoding scheme, the molecular space is discretized into a 3D grid, and each atom's position and chemical species is mapped to a single computational basis state. This discretization introduces spatial quantization at the voxel-resolution scale. The molecule is then encoded as an equal superposition over this sparse set of occupied states, where we assume that a suitable state preparation method exists. In contrast to full state tomography, which requires on the order of $\mathcal{O}(3^n \times 10^{2\text{--}3})$ measurement shots, where $n$ is the number of qubits, our proposed encoding scheme reduces to a coupon-collector sampling problem in the computational basis. Complete recovery of an $A$-atom molecule requires $\mathcal{O}(A\log A)$ shots on noise-free hardware. On noisy hardware, the required number of shots increases. We demonstrate the method on the 156-qubit IBM Kingston device using 8-qubit circuits to reconstruct the discretized geometry of a 10-atom ethylamine molecule with high mean reconstruction recall using only $\mathcal{O}(10^2)$ shots despite substantial hardware noise. These results demonstrate that our proposed encoding scheme is a practical, readout-efficient representation for molecular geometries on near-term devices.

Authors: Ben Bals, Matei Tinca, Yasamin Nazari

In the cut-query model, we have access to a (directed) graph via an oracle and we can query the size of the (directed) cut of a given subset of the vertices. One of the most elementary tasks in this model is to decide if there is a path two fixed vertices $s$ and $t$. While many results are known for undirected graphs, much less in understood for directed graphs in the cut query model. Even for the basic task of $s$-$t$ reachability, the best known randomized algorithm, is to reconstruct the entire graph with a technique by Grebinski and Kucherov using $O(n^2 / \log n)$ queries [Grebinski and Kucherov, 2000]. We restrict our attention to directed acyclic graphs (DAGs) and obtain a deterministic single-source reachability algorithm using $O(n \sqrt{n \log n})$ queries. The result is based on a topological sort algorithm, and can also be adapted to compute single-source shortest paths in DAGs.

Authors: Rahul Vaze

Adaptive conformal inference (ACI) of Gibbs and Cand{è}s and its variants are the standard approach to online conformal prediction under distribution shift, but they suffer from three fundamental limitations. First, their guarantees control only the \emph{signed} long-run coverage error: persistent miscoverage in one direction can be masked by compensating errors later, so a method can satisfy the theoretical guarantee while being badly wrong for extended periods. Second, existing guarantees say nothing about prediction-set size, so validity can be achieved trivially at the cost of unduly wide prediction sets. Third, the efficiency guarantees that do exist compare against a \emph{fixed} predictor chosen in hindsight, a benchmark that becomes increasingly less meaningful once the data-generating distribution shifts, since the very notion of an optimal threshold then changes over time. We consider a unified online learning framework that simultaneously controls absolute, non-cancelling coverage violation and prediction-set efficiency against a dynamically evolving benchmark for three important models. In the fully adversarial setting, exploiting the fact that the standard ACI update is exactly projected online gradient descent on the pinball loss, we derive simultaneous coverage and efficiency guarantees for arbitrary monotone Lipschitz efficiency objectives, with no distributional or {\it convexity} assumptions. In the stochastic setting with full-score feedback, we propose a sliding-window quantile tracker and establish a matching minimax lower bound showing our algorithm is rate-optimal. In the covariate-dependent stochastic setting, we develop a partitioned ACI algorithm that tracks a function-valued oracle threshold, and derive simultaneous coverage and efficiency guarantees.

Authors: Georgii Kashintsev

Practitioner summary. Do not copy Java's threshold of eight alone: when bins grow long, hybrid-batch (convert after load) still walks lists during insert, while hybrid-incremental (convert as soon as a bin hits k) matches always-tree. Prefer hybrid-incremental or always-tree for overloaded bins; reserve hybrid-batch for pure bulk load then query when chains stay short after resize. Hybrid-incremental approximates Java conversion timing, not a HashMap port. Lead metrics below are strcmp counts and heap - more stable than long-list wall-clock. When individual hash buckets grow long, linked-list separate chaining incurs linear per-bucket cost. We show that when conversion runs (hybrid-batch finalize vs. hybrid-incremental) dwarfs the choice of threshold k for C implementers. Using one C separate-chaining API, we compare policies under uniform-hash FNV (including a fixed-m probe at alpha ~ 122), forced-bucket chaining stress, and a moderate-load same-API scale run (alpha = 16). Under stress, list lookup averages ~31,250 comparisons vs ~15 once treeified; mid-load probes need ~37M comparisons under hybrid-batch vs ~46k under hybrid-incremental; final post-load comparisons converge (~15). Tree buckets use about 1.7x more heap than lists. Stress wall-clock for long lists is illustrative and run-noisy; we therefore headline comparisons and memory. Replaying real trigram posting-list lengths through the same policies yields the same ranking. At alpha ~ 122 without resize, some tree wins are really deferred rehash - resize first when m is simply too small.

Authors: George Alex Dumitrescu, Paul Flavian Diac

Prominence is one of the most important measurements in topography and mountaineering. This paper describes an efficient, almost linear time algorithm for computing mountain prominence for all peaks on Earth using digital elevation models (DEMs). It builds on top of a classic algorithm and leverages the observation that only a few peaks have their prominence determined by a relatively distant other mountain. Thus, the classic algorithm can be adapted to memorize and use less information without the loss of correctness. The algorithm is demonstrated using 3 arcsecond real-life data from SRTM datasets. Its importance is underscored by the increasing accuracy of Earth mapping methods and the corresponding growth in the amount of data that must be processed to compute prominence.

Authors: Shinsaku Sakaue, Kaito Fujii, Soh Kumabe, Yuichi Yoshida

Voting rules aggregate individual preferences into collective decisions, but the rankings they receive contain only ordinal information. The metric distortion framework studies ordinal voting rules in settings where voters and candidates are embedded in an unknown metric space. Deterministic rules have optimal worst-case distortion $3$, while recent randomized rules break the $3$ barrier. We study whether such improvements can coexist with low worst-case sensitivity with respect to the Wasserstein distance of lotteries under one-voter deletion and approximate differential privacy under one-voter replacement. On the sensitivity side, we give a randomized rule with distortion at most $3-\varepsilon$ for an absolute constant $\varepsilon>0$ and, for $m$ candidates and $n$ voters, a worst-case sensitivity bound of $O((\log m+1)/n)$. On the privacy side, for every $δ\in(0,1)$ and all $n$ above an absolute constant, we construct a variant rule whose mechanism releasing a single sampled winner has distortion at most $3-\varepsilon$ and is $(O((\log m+\log(1/δ)+1)/n),δ)$-differentially private. Both constructions use the same family of Gibbs distributions over constant-size candidate lists, with only the temperature parameter differing between the sensitivity and differential-privacy guarantees. Our analysis builds on the biased-metric viewpoint behind the recent improvement over the $3$ barrier and proves a stability property for the biased-metric ratio.

Authors: Vaclav Rozhon

The $k$-means++ algorithm is a standard and widely used seeding method for $k$-means clustering, but for a fixed number $k$ of centers its worst-case expected approximation ratio is $Θ(\log k)$. We consider the same algorithm when an adversary first fixes the dataset and some $K$; the number of centers $k$ is then chosen uniformly from $\{K,\ldots,2K-1\}$. We prove that $k$-means++ is an $O(1)$-approximation with constant probability in this budget-smoothed setup.

We prove new exponential monotone circuit lower bounds for detecting perfect matchings. We show that $\exp(\widetilde{\Omega}(n^{1/2}))$ gates are required to detect bipartite perfect matchings in $n$-vertex graphs. Our lower bounds are based on a new spread matching lemma.

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: Malach Obisa Amonga

Software architecture has evolved considerably in response to the increasing complexity of modern software systems, particularly those based on cloud computing, microservices, artificial intelligence (AI), and distributed computing environments. This literature review synthesizes recent studies published between 2024 and 2025 to examine emerging trends, challenges, and future directions in software design and architecture. The review adopts a thematic synthesis approach to analyse contemporary research across five major areas: architectural modelling and representation, software quality attributes and self-adaptive architectures, architectural evolution and complexity management, artificial intelligence-assisted architectural decision-making, and existing research gaps. The findings indicate that modern software architecture extends beyond traditional structural design to support continuous architectural governance, stakeholder communication, runtime observability, resilience, and intelligent decision support throughout the software lifecycle. Furthermore, the reviewed studies demonstrate that multiple architectural views, continuous monitoring, domain-driven decomposition, and AI-assisted design techniques contribute significantly to improving scalability, maintainability, adaptability, and long-term software sustainability. Despite these advances, several research gaps remain, including limited empirical validation of proposed approaches, insufficient integration of security and privacy into architectural decision-making, inadequate exploration of emerging paradigms such as edge and serverless computing, and the absence of standardized frameworks for trustworthy AI-assisted architecture.

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.