Theory of Computing Report

Authors: Anurag Anshu, Nikolas P. Breuckmann, Louis Golowich, Quynh T. Nguyen, Umesh Vazirani

We show how to compile an arbitrary classical circuit into a fault-tolerant circuit, which performs the desired computation even when an almost-linear number of bits are adversarially chosen and corrupted in each timestep. Using a variant of this fault-tolerance scheme that only detects (rather than corrects) corruptions, we give a new construction of probabilistically checkable proofs (PCPs) for NP with polylogarithmic query complexity. This PCP construction from fault-tolerance presents a promising candidate for quantization by the work of Anshu, Breuckmann, and Nguyen (STOC'24), who provided a roadmap for constructing quantum PCPs via fault-tolerance.

Authors: Nikolas P. Breuckmann, Louis Golowich, Umesh Vazirani

We prove a fault-tolerance theorem for quantum computation against adversarial noise. For every quantum circuit on $\bar{N}$ logical qudits of depth $\bar{T}$, we construct a fault-tolerant circuit on $N=\text{poly}(\bar{N})$ physical qudits of depth $\bar{T}\cdot\bar{N}^{o(1)}$, which is robust against an adversary who may arbitrarily choose and corrupt an almost-linear number $N^{1-o(1)}$ of physical qudits at each time step. This robustness significantly improves upon prior fault-tolerance theorems, which assumed corruptions were either local and stochastic, or else only act on a polynomially vanishing fraction of qudits. Our fault-tolerance scheme addresses a key bottleneck towards constructing quantum PCPs via the circuit-to-Hamiltonian mapping of Anshu, Breuckmann, and Nguyen (STOC'24). More fundamentally, our result demonstrates that fault-tolerant quantum computation remains possible under noise models that are global, worst-case, and non-Markovian over the full duration of the computation, directly countering concerns that correlated noise could fundamentally undermine quantum fault tolerance. Our construction is based on a new family of subsystem product codes we develop, which have large dimension and distance along with low-weight parity-checks, and which support transversal non-Clifford gates. We show how to perform single-shot fault-tolerant error correction on these codes using a Floquet-like procedure based on the local testability of classical tensor codes. We then obtain a universal fault-tolerance scheme using repeated code switching in a hypercubic qudit architecture. Finally, we recursively compose our scheme with itself to reduce an initially exponential qudit dimension down to a constant.

Authors: Francesco d'Amore, Henrik Lievonen

We show that, on trees, any locally checkable labeling problem (LCL) $Π$ that can be solved by an $n^{o(1)}$-dependent distribution can also be solved by an $O(\log n)$-round deterministic LOCAL algorithm. The result is obtained through a rake-and-compress-style decomposition of the input tree, and local simulations of the bounded dependent distribution on the components of the decomposition. As a corollary to our result, any LCL problem on trees can either be solved by an $O(\log n)$ deterministic LOCAL algorithm, or requires $n^{Ω(1)}$ rounds to solve by a quantum-LOCAL algorithm.

Authors: Zhengyang Liu

Budget-constrained advertisers commonly rely on two control mechanisms: pacing scales bids, whereas throttling randomizes participation. We prove that, in second-price auctions, these two different mechanisms share the same sharp approximation-hardness threshold. For pacing, computing a $γ$-approximate equilibrium is $\mathsf{PPAD}$-hard for every constant $γ\in[0,1)$. For throttling, computing a $δ$-approximate equilibrium is $\mathsf{PPAD}$-hard for every constant $δ\in(0,1)$. At parameter $1$, the complementarity requirement becomes vacuous and the all-zero solution is feasible. That is, approximation does not eliminate the fixed-point barrier at any nontrivial parameter value.

Authors: Hardik Jain

The tensor rank of a bilinear map is the least number of multiplications any bilinear algorithm needs to compute it; for the multiplication of an algebra it measures how cheaply the algebra can be multiplied at all. For the even-dimensional real normed division algebras it is $3$ for the complex numbers and $8$ for the quaternions, both classical, while for the octonions $\mathbb{O}$ only a range was known: at least $15$ (Fiduccia and Zalcstein, 1977) and at most $30$ (Cariow and Cariowa). We prove $$18 \le \operatorname{R}_{\mathbb{R}}(T_{\mathbb{O}}) \le 25.$$ The lower bound peels the eight slices of $T_{\mathbb{O}}$ down to two and bounds the rank of the surviving pencil through the octonion norm. Nothing in it is special to dimension $8$: the same steps give $\operatorname{R}_{\mathbb{R}}(T_A) \ge \frac{5}{2}n - 2$ for every real normed division algebra $A$ of even dimension $n$, sharp for $\mathbb{C}$ and $\mathbb{H}$ and the best bound we know for $\mathbb{O}$. The upper bound is a separate construction, an explicit rank-$25$ decomposition certified by a Krawczyk argument, in exact rational arithmetic, to sit within $10^{-6}$ of an exact one. The same two arguments pin down the rank of a smaller three-slice quaternion tensor $τ$, giving $\operatorname{R}_{\mathbb{R}}(τ) = 7$. The Lean 4 kernel checks the lower bounds and the Krawczyk existence principle; the accompanying scripts check the certificate's finitely many exact-rational inequalities.

Authors: Rafael Pass

In a world where valuable artifacts are increasingly created, completed, or processed by LLMs, the central economic question is not only what the LLM can produce, but what \emph{value} remains in the inputs (i.e., the prompts) we provide to it. Given a prompt, hint, critique, problem statement, or partial solution that helps an LLM produce an artifact $z$---a proof, program, design, or scientific hypothesis---how should we measure the value of that input? Intuitively, an input is valuable when it makes the target artifact easier for the model to generate: either by increasing its sampling probability, or by reducing the thinking time needed to find it. We propose a computational Levin--Kolmogorov complexity approach to this problem, by appropriately replacing the universal Turing machine in the classical definitions by the LLM itself. Concretely, we introduce an LLM-relative notion of \emph{probabilistic Levin--Kolmogorov complexity} $pKt$---treating the model's thinking as the random tape of the program, and charging logarithmically for it in Levin's manner---and define prompt value as algorithmic mutual information with respect to $pKt$. This captures the intuition above: a prompt having $b$ bits of value for an artifact $z$ makes $z$ $2^b$ times ``easier to obtain'', by multiplying the success probability by $2^b$, by dividing the required computation by $2^b$, or by any corresponding tradeoff between probability and computation. In contrast to the classical notion of algorithmic mutual information, ours is efficiently estimable. We additionally show that, under a natural reproduction experiment, a prompt value of \(b\) bits means that reproducing \(z\) without the prompt has median token cost \(2^b\) times that of reproducing it with the prompt.

Authors: Pahan Dewasurendra, Subhashini Jayawardhana

Input-convex neural networks permit globally tractable minimization over their inputs, so one might expect their global regularity to be tractable in low input dimension. We prove exact and accuracy-sensitive barriers to this expectation. Given a bias-free one-hidden-layer ReLU network $f(x)=\sum_{r=1}^n \mathrm{ReLU}(a_r^\top x)$ with unit positive output weights, deciding whether its global Euclidean Lipschitz constant is at least a rational threshold is NP-complete and W[1]-hard when parameterized by the input dimension $d$. The same holds on the unit ball and with integral first-layer weights having at most nine nonzeros. More sharply, no deterministic multiplicative approximation scheme runs in $g(d)\mathrm{poly}(\mathcal B,1/\varepsilon)$ time unless FPT equals W[1]. Under the Exponential Time Hypothesis, no such algorithm runs in $g(d)(\mathcal B+1/\varepsilon)^{o(d/\log d)}$ time. Thus accuracy cannot have a polynomial dependence separated from dimension. The exact result resolves the Euclidean case of an open problem posed at COLT 2025 and left open by the ICLR 2026 parameterized hardness theory for general two-layer networks. The approximation barrier is specific to generator-presented zonotopes, complementing known $(1/\varepsilon)^{O(d)}$-time schemes and an analogous barrier for halfspace-presented polytopes. Our lifted-selector reduction has an inverse-polynomial radial gap, proved through a quantitative theorem for rational cyclic zonogons. Equivalently, the results apply to Euclidean zonotope radius and positive-semidefinite binary quadratic maximization parameterized by rank. Convexity makes minimization easy, but it does not make global sensitivity fixed-parameter tractable or permit a dimension-separated fully polynomial accuracy guarantee.

Authors: Dorsa Fathollahi, Noga Ron-Zewi, Mary Wootters

In the theory of error correcting codes, list-decoding refers to the following problem. Given a code $C \subseteq Σ^N$ and a received word $y \in Σ^N$, find all codewords $c \in C$ so that $δ(c,y) \leq ρ$, where $δ$ is relative Hamming distance and $ρ\in (0,1)$. Codes that approach the optimal trade-off between the rate $R := \log_{|Σ|}(|C|) / N$ and the list-decoding radius $ρ$ are said to achieve capacity.By now, there are constructions of capacity-achieving list-decodable codes with fast near-linear-time list-decoding algorithms, but most existing work has not considered space complexity. In a recent line of work, Cook and Moshkovitz (2024, 2025, 2026) initiated the study of low-space deterministic algorithms for error correcting codes. In particular, in their 2026 paper, they gave a construction of list-decodable codes with deterministic near-linear-time and sublinear space list-decoding algorithms. However, these codes were far from achieving capacity. In this paper, we present list-decodable codes approaching capacity with deterministic time- and space-efficient list-decoding algorithms. More precisely, for any $R \in (0,1)$ and any arbitrarily small constant $τ> 0$, we present a family of codes $C\subseteq Σ^N$ with rate $R$ that are deterministically list-decodable up to radius $ρ= 1 - R - τ$, in time $N^{1 + τ}$ and space $N^τ$ with constant output list size and constant alphabet size. Our results can be extended to capacity-achieving list-recoverable codes.

Authors: Birindwa Prisca Hondi, Chinoso Philip Nwishienyi, Charity Wanja Mwaura, Alia Teto, Jema David Ndibwile

This paper is a failure analysis of the representation layer underlying GNN-based smart contract vulnerability detectors. These systems convert source code into graphs before any learning takes place; if the graph fails to capture the code's semantics, no model improvement can compensate. We investigate GNNSCVulDetector and identify four failures. First, structurally different contracts produce byte-for-byte identical graphs, constituting a concrete evasion attack. Second, graph construction is governed by a hardcoded 47-entry variable whitelist (including one duplicate entry), which constrains what the extractor can recognise. As a consequence, identical vulnerabilities with different variable names produce inconsistent graphs, graph quality degrades as naming diverges from the whitelist, and when no entry matches the pipeline produces structural output not grounded in source variables. Third, the C node (the graph element representing the external caller that triggers a reentrancy attack) is absent from even the most canonical vulnerable contract in the literature. Fourth, a controlled experiment confirms this as a direct misclassification: a fully exploitable contract is labelled safe because the C -> W edge is never constructed. All four failures are demonstrated experimentally. Current accuracy figures in the literature are measured under conditions that do not expose these failures. We demonstrate one confirmed case of misclassification caused directly by a representation-layer failure; the prevalence of such failures in real-world contract populations remains an open empirical question.

Authors: Shuichi Hirahara, Kazuki Ogitsuka

\emph{Locally dense lattices} are central gadgets used to prove the hardness of the Shortest Vector Problem and related lattice problems. Informally, a locally dense lattice is a lattice $\mathcal{L}$ that contains exponentially many lattice vectors inside some $\ell_p$ ball centered at $\vec{s}$ with radius at most an $α< 1$ fraction of the length of its shortest nonzero lattice vector. In this paper, taking a ``meta'' viewpoint on locally dense lattices, we introduce the \emph{Locally Dense Lattice Problem} (LDLP), the decision problem of determining whether a given input specifies a locally dense lattice. Our main result is that LDLP in $\ell_p$ norms for all finite $p \geq \log_2 3$ and for the infinity norm is complete for the second level of the polynomial hierarchy. We also compare two standard definitions of local density that appear in prior work. Micciancio's original definition (FOCS 1998 and SICOMP 2001) uses integer coefficient vectors, while later work by Micciancio (ToC 2012) and by Bennett and Peikert (RANDOM 2023) uses short vectors in a shifted coset. We show that the corresponding promise problems are mutually reducible in deterministic polynomial time, which shows that the two formulations are robust.

Authors: Chenghua Liu, Boning Meng

In a landmark JACM paper recognized with the 2021 G{ö}del Prize, Cai and Chen established a complete complexity dichotomy for counting CSPs over arbitrary finite domains with algebraic complex weights. Its polynomial-time side is characterized by three conditions---Block Orthogonality, Type Partition, and preservation by a common Mal'tsev operation---quantified over the countably infinite family $W_{\mathcal{F}}$ generated from arbitrary $\#\mathrm{CSP}(\mathcal{F})$ instances by partial summation. They asked whether these infinitary conditions are decidable from the finite language $\mathcal{F}$ alone---equivalently, whether the polynomial-time side of this complete fixed-language classification is uniformly recognizable. We settle this problem by giving, for every nonempty finite domain $D$ and every finite exactly encoded algebraic-complex language $\mathcal{F}$, a total exact algorithm that decides all three conditions on the full unbounded family $W_{\mathcal{F}}$. Beyond decidability, we prove that Block Orthogonality alone forces both Type Partition and the existence of a single Mal'tsev operation preserving all generated support and row-equivalence relations. Thus the three-condition characterization collapses to Block Orthogonality, and the finite input $(D,\mathcal{F})$ determines which side of the dichotomy applies. The same framework decides the corresponding conditions in the dichotomy theorem for degree-multiple counting CSP proved by Lin.

Authors: Xinyuan Xie, Haonan Zhang

For each $N\geq1$, consider the normalized König bilinear form $B_{\mathrm K}:L_\infty(\mathbb R^N)\times L_\infty(\mathbb R^N)\to\mathbb R$ given by \[ B_{\mathrm K}(f,g):=\frac{1}{(\sqrt{2}π)^N} \iint_{\mathbb R^N\times\mathbb R^N} f(x)g(y)e^{-(\lVert x\rVert^2+\lVert y\rVert^2)/2} \sin\langle x,y\rangle\,\mathrm d x\,\mathrm d y, \] We define the König constant by \[ \mathfrak K_{\mathrm K}:=\sup_{N\geq1}\sup_{\substack{f,g:\mathbb R^N\to\{\pm1\}\\ f,g\ \mathrm{measurable}}}B_{\mathrm K}(f,g). \] The study of this bilinear form arose from efforts to determine the exact value of the Grothendieck constant. König~\cite{KONIG} conjectured that the sharp value should instead be given by the one-dimensional half-spaces $B_{\mathrm K}(\operatorname{sgn}(x_1),\operatorname{sgn}(x_1))=\frac{2}π\log(1+\sqrt{2})$. A positive answer to this conjecture, together with a classical upper bound of Krivine \cite{KRIVINE}, would determine the exact value of the Grothendieck constant. In a breakthrough~\cite{BMMN}, Braverman, Makarychev, Makarychev, and Naor disproved König's conjecture already in dimension two and used their counterexamples to obtain the first strict improvement over Krivine's bound. One question in \cite{BMMN} attempts to determine the Grothendieck constant through alternating Krivine rounding schemes arising from König's bilinear form in high dimension. More recently, Li et al.~\cite{LISK} constructed high-dimensional examples showing that $\mathfrak K_{\mathrm K}\ge 0.59357$. An elementary Fourier argument gives $\mathfrak K_{\mathrm K}\le 1$ and excludes equality for every finite-dimension. In this paper, we prove that $\mathfrak K_{\mathrm K}=1$ by constructing a family of Boolean pairs in high dimensions. In particular, this gives a negative answer to the high-dimensional aspect of the question in \cite{BMMN}.

Authors: Yang Cao, Haoran Qi, Hanzhi Wang

We study $\ell_p$-norm maximization over zonotopes given by rational generators, with input length $L$. For fixed $p=a/b>1$, the exact Turing baseline runs in $n^{O(d)}b^{O(d)}\mathrm{poly}(L)$ time, but fixed-parameter tractability in the ambient dimension $d$ was open [FGHS25]. We prove W[1]-hardness and, under the Exponential Time Hypothesis (ETH), exclude $ρ_p(d)L^{o(d)}$ time, even for $5$-sparse generators, by encoding binary CSP constraints with normalized positive cap generators. We also give a deterministic $(1-\varepsilon)$-approximation with $\varepsilon^{-(d-1)/2}$ dependence and, among algorithms with fixed-degree polynomial dependence on $L$, rule out $(1/\varepsilon)^{o(d)}$ dependence under ETH. Support-function duality transfers the results to positive-output two-layer ReLU networks.

Authors: E. Alkin, Yu. Khromin, A. Skopenkov

We recall definitions of linking numbers and Wu--Simon numbers for spatial graphs. We expose a `converse' to the Conway--Gordon--Sachs theorem (i.e. description of linking functions for embeddings $K_6\to\mathbb{R}^3$), and some results on Wu--Simon numbers. We conjecture and discuss a generalization of the Conway--Gordon--Sachs theorem to multiple linking. The exposition is based on plane diagrams, so no knowledge of spatial geometry is required.

Authors: Vishesh Jain, Duan Tu

We consider the problem of graphically local metric embedding, i.e. embedding points from an arbitrary finite metric space into a target metric space while preserving, up to a small distortion, only a subset of the pairwise distances specified by a bounded degree graph $G$. We provide a general reduction showing that, in many cases, this is no easier than embedding the points while approximately preserving all pairwise distances. As an illustration of our general reduction, we show that there exists a Euclidean metric space $X$ on $n$ points along with a graph $G = (X,E)$ of maximum degree $3$ such that any embedding of $X$ into $\ell_2^m$ which only preserves distances specified by $E$ up to a relative error of $(1+\varepsilon)$ must satisfy $m = Ω(\varepsilon^{-2}\log n)$. Our lower bound matches the upper bound on the dimension coming from the Johnson-Lindenstrauss lemma for approximately preserving all pairwise distances; previously, such a lower bound was known only for the class of noncontracting embeddings [Schechtman-Shraibman, Discrete & Computational Geometry, 2009]. Moreover, the condition that the maximum degree of the graph is $3$ is best possible: for graphs $G$ of maximum degree $2$ (or more generally, treewidth at most $2$), any metric space embeds $G$-isometrically into any two-dimensional normed space.

Authors: Philip Caplan

Boundary-conforming four-dimensional meshes are essential for being able to run spacetime numerical simulations about complex, moving three-dimensional geometries. Specifically, a mesh of pentatopes is needed in which the tetrahedral faces of this mesh conform to the boundary of the domain. In the three-dimensional setting, a common approach consists of generating a constrained Delaunay tetrahedralization. Implementations of this approach are mature, but it is unclear how it extends to the four-dimensional setting, particularly in how the local mesh operations are scheduled to recover the constraints. This paper develops a new algorithm for recovering boundary constraints which is simple to implement in any dimension. The algorithm is primarily an advancing-front approach and uses a constrained cavity operator to incrementally insert constraints into the mesh. Compared to existing advancing-front approaches, which advance from a front of $(d-1)$-simplices (faces), the proposed approach advances from a front of $(d-2)$-simplices, called ridges. Steiner vertices can be added to the boundary when the front stalls and several examples in $3d$ demonstrate the ability of this algorithm to recover a complete representation of the input surface. For the four-dimensional geometries studied here, the algorithm generally recovers at least 99% of the input tetrahedralization with this advancing ridge procedure. For some simpler domains, complete conformity with the input tetrahedralization is achieved by adding Steiner vertices, thereby demonstrating the ability to produce boundary-conforming four-dimensional meshes. The design and efficiency of the underlying cavity operator implementation is also evaluated, showing that 30 million pentatopes can be created in about 1.5 minutes, and 300 million pentatopes in about 15 minutes on a workstation laptop.

Authors: Emilien Dupont, Marvin Eisenberger, Borislav Kozlovskii, Abbas Mehrabian, Francisco J. R. Ruiz, Abigail See, Renfei Zhou, Josh Alman, Virginia Vassilevska Williams, Matej Balog

The current best bounds on the matrix multiplication exponent $ω$ are obtained through a refinement of the laser method called combination loss analysis (Duan et al., 2022; Williams et al., 2024; Alman et al., 2025). In this note, we address the optimization problem at the core of this approach and propose several improvements. First, we reformulate the optimization problem allowing us to solve it in a larger setting than was previously possible. Second, we leverage recent advances in machine learning to design a new optimization algorithm for this problem. Finally, we refine the resulting optimization algorithm with AlphaEvolve. Our combined approach yields an upper bound of $ω$ < 2.371177, improving the previous best bound of 2.371339.

Authors: Shahin Kamali, Saba Yazdani

Burning is a discrete-time model for propagation in which a new fire starts in each round, while each existing fire expands by one unit of distance along the underlying metric. In geometric burning, the input is a finite point set, and the goal is to burn all points in as few rounds as possible. Equivalently, burning a point set in $k$ rounds corresponds to covering it with metric balls of distinct radii in $\{0,1,\ldots,k-1\}$; the objective is to minimize $k$. Previous work has studied the problem mainly under the Euclidean metric. In this paper, we study geometric burning under the $L_1$ and $L_\infty$ metrics. The problem remains NP-hard in both settings. The $L_1$ and $L_\infty$ metrics provide additional geometric structure, which allows us to obtain improved approximation guarantees, especially for anywhere burning. We first present a simple $(2+\varepsilon)$-approximation for both anywhere burning and point burning. We then improve the anywhere burning approximation to $7/4+\varepsilon=1.75+\varepsilon$, and give a $(3151/1620+\varepsilon)$-approximation for point burning, where $3151/1620<1.9451$. We also extend the anywhere burning result under $L_\infty$ to every fixed dimension $d\ge 3$ to achieve a $\left(2-\frac{1}{2^{d+1}}+\varepsilon\right)$-approximation. Finally, using standard comparisons between planar $L_p$ distances, we transfer our $L_1$ and $L_\infty$ algorithms, together with known Euclidean burning algorithms, to obtain approximation guarantees for every fixed $1\le p\le\infty$.

Authors: Yunbum Kook, Santosh S. Vempala

For any convex body $\mathcal{K}\subset\mathbb{R}^{n}$ containing a unit ball, the spectral gap of Hit-and-Run is $Ω(1/(n^2 C_{\mathsf{PI}}))$, where $C_{\mathsf{PI}}$ is the Poincaré constant of the uniform distribution $π$ over $\mathcal{K}$. This implies that Hit-and-Run converges to a distribution within $χ^2$-divergence $\varepsilon$ of the uniform distribution $π$ in $O(n^2 C_{\mathsf{PI}}\log(M/\varepsilon))$ steps from any starting distribution $π_0$ with $M=χ^2(π_{0}\,\|\,π)$, thus refining the known bound of $O(n^2 R^2 \log(M/\varepsilon))$ by Lovász and Vempala (2004) in terms of the outer radius $R$; for nearly isotropic bodies, together with progress on the KLS conjecture, the complexity is $O(n^2\log n\log(M/\varepsilon))$, improving the dimension dependence from cubic to nearly quadratic while maintaining logarithmic dependence on the initial distance. It was an open problem to connect the convergence of Hit-and-Run to Poincaré/KLS constants as was done for the Ball walk by Kannan, Lovász and Simonovits (1997). Unlike Hit-and-Run, the Ball walk has an unavoidable linear dependence on (a stronger notion) of the initial warmness. We directly bound the spectral gap of the Hit-and-Run Markov chain by connecting it to functional isoperimetric constants, inspired by the recent analysis of In-and-Out. Rewriting the spectral gap in terms of dual certificates leads to the Babuška--Aziz constant studied in the analysis of PDEs; it is asymptotically bounded by the improved Poincaré constant, which we show can be bounded in terms of the usual Poincaré constant. The proof is based on duality and calculus, unlike known proofs of convergence for Hit-and-Run which are based on bounding the conductance. The same technique can be applied to Coordinate Hit-and-Run, resulting in a much improved mixing time of $O(n^3C_{\mathsf{PI}}\log(M/\varepsilon))$.

Authors: Kaito Harada, Taisuke Izumi

In the replacement paths (RP) problem, we are given a graph $G = (V, E)$ with $n = |V|$ and $m = |E|$, together with two vertices $s, t \in V$, and are asked to compute the shortest-path distance from $s$ to $t$ in $G \setminus e$ for every failed edge $e \in E$. The multiple source replacement paths (MSRP) problem is its natural generalization: given a set $S \subseteq V$ of $σ$ sources, compute the replacement path distances for all pairs in $S \times V$. In this paper, we present a randomized combinatorial algorithm that solves MSRP on unweighted directed graphs in $\tilde{O}(m\sqrt{σn} + σn^2)$ time, with all the output distances correct with high probability. This improves the best known bound $\tilde{O}(m\min\{σ\sqrt{n}, n\} + σn^2)$ for directed graphs, which is obtained either by running the single source RP algorithm of Chechik and Magen [ICALP'20] from each source separately or by constructing and querying the all-pairs distance sensitivity oracle of Bernstein and Karger [STOC'09]. Our running time is essentially tight among combinatorial algorithms because Gupta, Jain, and Modi [PODC'20] proved a lower bound of $m{(σn)}^{1/2-o(1)}$ for such algorithms, which holds even on undirected graphs, and the additive term $σn^2$ is proportional to the time needed to write down the $Θ(σn^2)$ output distances. The algorithm is also remarkably simple.

Authors: Thatchaphol Saranurak, Kaiyang Xie, Zhaienhe Zhou

We give the first incremental algorithm for directed global minimum cut. Given a directed graph with $n$ vertices undergoing $m$ edge insertions, our deterministic algorithm explicitly maintains a global minimum cut or certifies that its value is at least $k$ in $O(km\log n)$ total update time. Prior work required either that $k\le2$ or that the graph is undirected. Our algorithm is a strict incremental extension of Gabow's state-of-the-art static algorithm (JCSS 1995), with no asymptotic loss in running time over the entire insertion sequence.

Authors: Anna Bernasconi, Valentina Ciriani, Alessio Conte, Alberto L'Episcopo, Giulia Punzi

In this paper, we address several problems concerning vector spaces enclosed in a given set. Let V be a vector space over a finite field of cardinality c, and let $S \subseteq V$ be a set of vectors. A space enclosed in S is a vector subspace W of V that is also contained in S: $W \subseteq S$. We focus on enumeration problems, where the task is to list all solutions, and we first provide an algorithm to enumerate all spaces that are enclosed in S. Our algorithm is further adapted to solve two more problems: the enumeration of (inclusion-)maximal enclosed spaces, and the problem of finding an enclosed space of maximum dimension. The latter problem arises in the context of Boolean functions' regularity detection. It can also be seen as a dual version of the well-known linear span: indeed, the span is the minimum-dimension vector space that contains a given set of vectors S, and it is a fundamental concept in linear algebra. Our proposed algorithms are based on the binary partition paradigm, and have total time complexity $e^{\frac{1}{2\ln c}\ln^2 n - Θ(\log n \log \log n)}$, where $n= |\inputset|$. The first version, for enumerating all enclosed spaces, also achieves a delay (time between consecutive outputs) of O(n). Our algorithms provide a quadratic speed-up with respect to a brute-force approach, although the speed-up appears even greater in our experimental evaluation on boolean vector spaces.

Authors: Zhewei Wei, Mingji Yang

Local graph clustering aims to find a well-connected cluster near a given seed node without exploring the entire graph. A key step in the classic local clustering algorithm of Andersen, Chung, and Lang (ACL; Internet Math. 2007) is to approximate the PageRank vector from the seed node. Their local push method computes an ACL $\varepsilon$-approximate PageRank vector with teleportation parameter $α$ in $O\bigl(1/(α\varepsilon)\bigr)$ time. We give an algorithm that computes an ACL $\varepsilon$-approximate PageRank vector in $\widetilde{O}\bigl(1 / \varepsilon^2\bigr)$ time with high probability. This bound is independent of the graph size and has only a polylogarithmic dependence on $1 / α$, albeit with a quadratic dependence on $1 / \varepsilon$. As a direct consequence, we obtain a new running-time tradeoff between the target conductance and target volume in local graph clustering. Our method also applies to the optimization problem of $\ell_1$-regularized PageRank and computes an additive approximate minimizer with a polylogarithmic dependence on $1/α$, improving the $1/\sqrtα$ dependence in the previous bound of Martínez-Rubio, Wirth, and Pokutta (COLT 2023). Our algorithm is based on an intuitive process that maintains a growing active set of nodes: it performs push operations on the current set until convergence and then expands the set and repeats the process if necessary. We show that for each active set, the corresponding limiting state is the solution to a symmetric diagonally dominant (SDD) linear system on the set. We apply nearly-linear-time SDD solvers to these systems and prove that the approximation preserves the properties of the push process.

Authors: Rajath Rao K. N., Jens Schlöter, Sami Davies, Amira Ouchene, Yasamin Nazari

Correlation clustering is a fundamental unsupervised learning problem. On complete graphs, both the min-disagreement and min-max objectives admit constant-factor approximations, yet on general (non-complete) graphs, the best guarantees blow up to $O(\log n)$ and $O(\sqrt{n})$. This gap between the two regimes motivates the following question: are there classes of incomplete graphs that circumvent the lower bounds on general graphs and admit approximation guarantees approaching those attainable on complete graphs? We study a natural class of graphs obtained by randomly subsampling a complete signed graph $G$, where each edge is independently deleted with probability $q$. For such graph instances both for the min-max and the min-disagreement objectives, we prove approximation guarantees (depending on $q$) that are substantially better than the bounds achievable for general graphs. We supplement our theoretical results with experiments that also suggest that the approximation ratios of our algorithm are close to those of the complete graph and better than the worst-case bounds for general (non-complete) graphs.

Authors: Yu Cong, Chao Xu, Yajie Zhao

Karger's randomized contraction algorithm finds a minimum-weight cocircuit of a matroid whenever the cogirth-density ratio is bounded. We prove that the same hypothesis yields a deterministic algorithm with the same exponent. If every contraction minor of rank at least $r_0$ of a matroid $M$ has cogirth-density ratio at most $c$, then a minimum-weight cocircuit of $M$ is computable deterministically in $m^{O(r_0)} n^{O(c)}$ time when the contraction minors of bounded rank have at most $m$ parallel classes, by an algorithm that knows neither $r_0$ nor $c$. As a consequence, we give a deterministic algorithm computing the cogirth of rank-$p$ perturbed graphic matroids in $2^{O(p^2)} n^{O(1)}$ time, fixed-parameter tractable in $p$, settling the cogirth side of a question of Geelen and Kapadia (2018). The extensions of the contraction method carry over deterministically: enumerating all near-minimum 1-cocycles, computing a minimum-weight $k$-cocycle, and computing the Pareto frontier under several positive criteria.

Authors: Trevor Vaughn

Let $A, B \in \mathbb{Z}_{\ge 0}^n$ be nonnegative vectors and let $t = |\operatorname{supp}(A \star B)|$. We give a Las Vegas algorithm that computes $A \star B$ in $O(t \log t)$ expected time. More generally, for every $0 < δ\le \frac{1}{2}$, the algorithm terminates within $O(t \log t \log \frac{1}δ)$ time with probability at least $1 - δ$. The algorithm uses dense convolution, linear hashing, and the length reduction of \cite{BFN22}. Its main ingredient is a carry-free representation of the indices as vectors of constant dimension $d$ whose coordinates have size $O(t / \log t)$. We can then take our hash function to be the inner product with a random element of $\mathbb{F}_p^d$ for a prime $p$ of size $Ω(t / \log t)$: this preserves addition and gives collision probability exactly $1/p$, while identities regarding the moments of the vectors identify and recover the isolated terms as in \cite{BFN22}. Our expected running time matches that of Jin and Xu~\cite{JX24} while using substantially different tools and yielding a simpler algorithm. Note that their algorithm also terminates within $O(t \log t)$ time with probability at least $1 - \frac{1}{t}$, while our tail bound is weaker.

Authors: Tatsuhito Yamagata, Hanna Sumita

We study fair division of indivisible goods when agents' valuations are accessed only through ordinal comparisons between bundles, with arbitrary tie-breaking. In this model, even deciding whether a given allocation is envy-free up to one good (EF1) can be impossible. This suggests explicit fairness certificates as a natural algorithmic object. Our main contribution is a certificate-preserving scaling framework, which recursively contracts goods, solves a smaller instance, and expands the solution while repairing an explicit envy-eliminating witness certificate. For arbitrary identical monotone valuations, this yields a certified EF1 allocation for $n$ agents and $m$ goods using $O(n \log n \log(m/n))$ comparison queries, within an $O(\log n)$ factor of the $Ω(n \log (m/n))$ communication lower bound. For identical additive valuations, we additionally obtain a $1/2$-MMS guarantee within the same query complexity. For non-identical additive valuations, exploiting our EF1+$1/2$-MMS algorithm, we accelerate the existing matching-based PROP1+$1/2$-MMS framework, improving the query complexity from $O(n^4\log m)$ to $O(n^3\log m)$. Finally, we study the structure of such certificates through $k$-witness EF1, a hierarchy between EF1 and EFX.

Authors: Marcel Jackiewicz, Adam Kasperski, Pawel Zielinski

In this paper, the recoverable robust representative selection problem is considered, where uncertain second-stage costs are modeled using interval uncertainty with a continuous budget. While the variant under a discrete uncertainty budget is known to be NP-hard, we show that transitioning to a continuous budget fundamentally alters the computational complexity landscape. Specifically, by exploiting the structural properties of the problem under the continuous budget model, we design a strongly polynomial-time algorithm for the general case. Furthermore, we propose an even more efficient strongly polynomial-time algorithm for an important special case.

Authors: Yuhao Zhang

The maximin share (MMS) is a central fairness benchmark for allocating indivisible goods and chores. We study additive valuations in the personalized bivalued setting, where each agent assigns one of two agent-specific values to every item. Whether exact MMS allocations always exist in this setting has remained a major open question, as highlighted by Ebadian, Peters, and Shah and by Garg, Huang, and Segal-Halevi. We answer this question affirmatively: we prove that exact MMS allocations always exist for both goods and chores and can be computed in polynomial time. Our proof combines a quota-based reformulation with an envelope relaxation, a sparse extreme-point construction, and flow-based rounding that controls the total rounding loss.

Authors: Weitian Tong, Yao Xu

We study the problem of minimizing total weighted completion time on unrelated parallel machines with machine-independent job weights. The best previous approximation guarantee for this problem is arbitrarily close to 1.36, due to Li [SODA 2025], who developed a configuration-LP and iterative-rounding framework based on randomly shifted geometric size classes and a computer-assisted final analysis. We improve the approximation guarantee to arbitrarily close to 1.3168. The scheduling algorithm retains Li's configuration-LP and iterative-rounding framework, with a different fixed geometric class ratio. The improvement comes from a new analysis of the random geometric shift. For each machine and Smith prefix, we normalize the physical prefix before averaging over the shift, so that its normalized size distribution and configuration moments remain fixed across all shifts. A scale-dependent configuration bound and a cross-shift averaging argument then reduce the approximation analysis to a one-dimensional certificate. The final certificate is computer assisted and reproducible. Its rational data are verified exactly where possible, while the remaining continuous inequalities are certified using directed interval arithmetic. This yields the first improvement over Li's guarantee for the machine-independent-weight model.

Authors: Deniz Elbek, Yiğit Manafi, Zeynep Gürdal, Sinan Yıldırım, Kamer Kaya

Rasmussen's permanent estimator is a simple and unbiased estimator for the permanent of a binary matrix, but its practical performance can be limited by trajectories that terminate before completing a perfect matching. These failed trajectories, together with dispersion among the surviving weights, can substantially reduce the effective sample size. Although the literature leverages techniques such as matrix scaling to improve proposal balance and support filtering to remove structurally infeasible choices, using these at every step can substantially increase the trajectory cost. Furthermore, they do not directly address the choice of the next vertex. This paper uses the classical minimum-degree ordering in sparse matrix algorithms to select the next vertex with O(n + m) total bucket-maintenance work per trajectory, where n is the number of rows/columns in the matrix and m is the number of nonzeros. The proposed estimator uses adaptive schedules to invoke the more expensive scaling and filtering operations only when needed. The experiments show that it is competitive with the state of the art on the tested small matrices and scales effectively to large sparse matrices.

Authors: Benny Kimelfeld, Ester Livshits

If a table violates its required set of functional dependencies (FDs), what is the minimum number of cell changes needed to restore consistency? This fundamental problem, known as finding an optimal update repair (U-repair), is known to admit polynomial-time algorithms only for a small number of specific FD sets. Whether additional tractable cases exist has remained open. The only established hardness result for this problem is due to Kolahi and Lakshmanan (2009); subsequent attempts to prove hardness for additional cases have failed, leaving these cases unresolved. In this work, we make substantial progress on this open problem by completely resolving the case of unary FDs, in which every FD has a single attribute on its left-hand side. We show that every set of unary FDs either falls into one of the previously known tractable classes or makes the problem of finding an optimal U-repair NP-hard.

Authors: Yi-Chun Akchen, Kaan Cakiroglu, Felipe Caro, Jacob Feldman

In apparel retail and other applications, when a customer's preferred size is unavailable, demand may shift to nearby sizes. This substitution creates new assortment and inventory optimization challenges by coupling product availability and demand across sizes. We introduce the consider-fit-then-choose (CFTC) model to capture such size-dependent choice behavior. Products may be offered in multiple sizes, which affect customer preferences and consideration sets through fit, measured by distance from the customer's ideal size. We study assortment optimization and show-all inventory selection, in which the retailer chooses initial inventory and subsequently offers every in-stock product. We show that assortment optimization under the CFTC model is NP-hard and develop a PTAS when customers deviate by at most $O(1)$ sizes from their ideal size. Combined with the recent black-box framework of Fu et al. (2026), this yields a nearly $0.272$-approximation for show-all inventory selection. We next exploit the specific choice dynamics of the CFTC model. By stocking only every other size, we decouple demand across stocked sizes and reduce CFTC to a special class of mixed multinomial logit models that we prove satisfies the convex chain decomposition (CCD) property of Goyal et al. (2023). For the fluid problem, we develop a polynomial-time $(1/2-ε)$-approximation under adjacent-size substitution and a mild condition on preference weights. For the stochastic problem, we establish an asymptotic $1/2$-approximation using a new coupling argument connecting the stochastic inventory process to its fluid counterpart. Numerical experiments calibrated using footwear data show small optimality gaps across a broad range of substitution patterns and problem settings.

Authors: Sander Borst, Golnoosh Shahkarami, Rohit Vaish

We study interval scheduling from the perspective of fair allocation. There are $m$ identical machines and a set of intervals, each specified by a start time, an end time, and a nonnegative weight. A schedule assigns a subset of the intervals to the machines so that no two intervals on the same machine overlap, and the goal is to maximize the total weight of scheduled intervals. Viewing machines as agents and intervals as goods, we require the schedule to be envy-free up to one item (EF1), and we measure efficiency against the offline optimum without fairness. In the offline setting, we give an algorithm that computes an EF1 schedule whose loss is at most a factor of $3/2$ in the unweighted regime, and we prove lower bounds of $\frac{3m-2}{2m-1}$, approaching $3/2$, in both the unweighted and the unit-length weighted regimes, so the price of fairness is $3/2$ in the limit. In the online setting, intervals arrive in nondecreasing order of start times; an arriving interval must be accepted or rejected, rejections are irrevocable, and an accepted interval may be revoked, and lost, at any time before it ends. For the unweighted regime we present Greedy-Balanced, a simple algorithm that maintains EF1 at every point in time and is $(2-\tfrac{1}{m})$-competitive against the offline optimum without fairness, and we prove a matching lower bound for every deterministic algorithm; the optimal deterministic fair competitive ratio is thus exactly $2-\tfrac{1}{m}$. Experiments on real-world benchmark instances show that Greedy-Balanced performs well beyond its worst-case guarantee, with an observed ratio never exceeding $1.306$.

Soddy’s hexlet consists of a ring of six spheres, tangent to each other consecutively around the ring, and another ring of three consecutively-tangent spheres, so that all the spheres in the first ring are tangent to all the spheres in the second ring. If you keep one ring fixed, you can rotate the other ring continuously, possibly changing the sizes of some of the spheres as they rotate but keeping the pattern of tangencies unchanged. Here’s a nice animation I found on Wikipedia, where the ring of six spheres rotates continuously while the other ring of three spheres (the central blue one and the two green planes, considered as degenerate spheres tangent at infinity) stays fixed. The larger red sphere is not part of this configuration and I don’t know why the author of this animation included it.

We can describe the graph of tangencies of these nine spheres by using the join operation on graphs, which combines two graphs by adding edges from all vertices of one graph to all vertices of the other. With a cycle of \(k\) vertices denoted as \(C_k\) and the join denoted as \(+\), the graph of Soddy’s hexlet is \(C_3+C_6\).

A few years ago I wrote here about an analogous system of spheres in two rings, with four spheres in each ring. (I vaguely recall seeing some mention of this in a paper from the 1950s by Coxeter but now I can’t find it again; it’s closely related to his 1954 “Arrangements of equal spheres in non-Euclidean spaces”.) Below again are two perpendicular views of a symmetric realization with one ring consisting of four congruent spheres, and the other ring consisting of two planes (degenerate spheres) and two more spheres of half the radius of the first ring. The two planes are tangent at infinity. As a join the graph of tangencies of these eight spheres is \(C_4+C_4\) but you might be more familiar with the same graph as \(K_{2,2,2,2}\).

But these two examples are not the only systems of tangent spheres whose tangencies form a join of cycles! If we allow non-consecutive spheres within a single ring to cross through each other rather than requiring them to stay separated, we can also realize the graphs \(C_5+C_{10}\), \(C_7+C_{14}\), \(C_8+C_8\), \(C_9+C_{18}\), \(C_{11}+C_{22}\), \(C_{12}+C_{12}\), etc.

The realizations depicted above, where one of the two rings consists of congruent spheres with their centers at the vertices of a regular polygon, may seem symmetric enough, but to describe these additional joins of cycles as tangent spheres it is helpful to reach an even more symmetric point of view (but one that is unfortunately difficult to visualize because it involves a fourth dimension): use stereographic projection to lift the Euclidean space \(\mathbb{R}^3\) in which these tangent spheres live, to the unit \(3\)-dimensional hypersphere

\[\mathbb{S}^3=\{(x,y,z,w)\mid x^2+y^z+z^2+w^2=1\}\subset\mathbb{R}^4.\]

This lifting process takes spheres to spheres, preserves their tangencies, and is reversible, so that any system of tangencies that can be realized in \(\mathbb{R}^3\) can be realized in \(\mathbb{S}^3\) and vice versa. In \(\mathbb{S}^3\), Soddy’s hexlet has a particularly nice realization in which the ring of six spheres has its centers on a regular hexagon in the plane \(z=w=0\), with radii \(\tfrac{\pi}{6}\) (measuring these radii as great-circle distances on \(\mathbb{S}^3\), or equivalently angles as viewed from the origin). This radius is chosen so that the sum of the diameters of the spheres is exactly \(2\pi\), the length of the equator of \(\mathbb{S}^3\) in this plane. Correspondingly, the ring of three spheres has its centers on an equilateral triangle in the perpendicular plane \(x=y=0\), with radii \(\tfrac{\pi}{3}\). Again their diameters sum to \(2\pi\). Because the six-sphere ring and the three-sphere ring lie in perpendicular planes, the centers of the spheres from different rings are all at angular distance exactly \(\tfrac{\pi}{2}\) from each other. Because their radii \(\tfrac{\pi}{6}\) and \(\tfrac{\pi}{3}\) sum to the distance \(\tfrac{\pi}{2}\) between their centers, the spheres are tangent. Rotating \(\mathbb{S}^3\) around one of these two perpendicular planes and then projecting into \(\mathbb{R}^3\) induces the rotation of the rings of spheres within \(\mathbb{R}^3\) that we have already seen.

But now instead of a hexagon of sphere centers on \(\mathbb{S}^3\) with radius \(\tfrac{\pi}{6}\) in one plane, and a triangle of sphere centers with radius \(\tfrac{\pi}{3}\) in a perpendicular plane, we can consider four integer parameters \(a\), \(b\), \(c\), and \(d\), a \(b\)-gon of sphere centers with radius \(\tfrac{a\pi}{b}\) in one plane, and a \(d\)-gon of sphere centers with radius \(\tfrac{c\pi}{d}\) in the other perpendicular plane. As long as \(a\) is coprime to \(b\), the \(b\)-gon of spheres will have tangencies that form a ring of spheres, wrapping around the \(z=w=0\) equator \(a\) times. And correspondingly, as long as \(c\) is coprime to \(d\), the \(b\)-gon of spheres will have tangencies that form a ring of spheres, wrapping around the \(x=y=0\) equator \(a\) times. (If they are not coprime, then we instead get multiple separate rings, and if we try non-integer parameters then the rings of spheres will not be tangent or will not close up after finitely many steps.) And finally, the spheres from the first ring will be tangent to the spheres in the second ring whenever \(\tfrac{a\pi}{b}+\tfrac{c\pi}{d}=\tfrac{\pi}{2}\), which is to say whenever \(\tfrac{a}{b}+\tfrac{c}{d}=\tfrac{1}{2}\).

So what are the solutions of \(\tfrac{a}{b}+\tfrac{c}{d}=\tfrac{1}{2}\)? To sum to \(\tfrac{1}{2}\), the least common denominator of the two fractions on the left hand side must be even, \(2k\) for some \(k\). The two numerators for the common denominator must sum to \(k\). If \(k\) is odd, one of the numerators is even and one is odd, and we get a solution of the form \(\tfrac{j}{k}+\tfrac{k-2j}{2k}=\frac{1}{2}\). If \(k\) is even, both of the numerators must be odd (else \(2k\) would not be the least common denominator) and we get a solution of the form \(\tfrac{j}{2k}+\tfrac{k-j}{2k}=\frac{1}{2}\). And of course both numerators must be positive. Plugging in \(k=2,3,4,5,\dots\) gives \(\tfrac{1}{4}+\tfrac{1}{4}=\frac{1}{2}\) (the quadlet of my previous post), \(\tfrac{1}{3}+\tfrac{1}{6}=\frac{1}{2}\) (the hexlet), \(\tfrac{1}{8}+\tfrac{3}{8}=\frac{1}{2}\) (two rings of eight spheres, one overlapping and wrapping three times around), \(\tfrac{1}{5}+\tfrac{3}{10}=\frac{1}{2}\), \(\tfrac{2}{5}+\tfrac{1}{10}=\frac{1}{2}\) (two different ways of realizing \(C_5+C_{10}\)), etc. Each of these fractional equations gives us two tangent rings of overlapping spheres on \(\mathbb{S}^3\) and, by stereographic projection, in \(\mathbb{R}^3\).

(Discuss on Mastodon)

By David Eppstein

I ended my last post with a call for action. I stated, without evidence, that if we’re unhappy with the status quo, we can choose to do something else. I’m hoping this semester I can instead lead by doing (sorry that’s corny) and be a weird freak out in public on this blog. Let me start today by sharing something I’ve been working on: a plan to create alternative systems for generating, evaluating, and sharing knowledge.

While academia has exploded in size in the post-war period, the ideal size of a conference has remained constant. Small workshops with one or two dozen participants have consistently launched big ideas, forged multidisciplinary connections, and set new standards across fields. Look at the history of artificial intelligence (a marketing term I continue to loathe with every ounce of my being but one that is unfortunately useful given its current cultural dominance). The field was conceived at a small conference held at Dartmouth. Societal implications and multidisciplinary connections were hashed out at the Macy Conferences. The ICML conference began as a small workshop of AI researchers at CMU, a splinter group that reclaimed and rebranded the term machine learning. NeurIPS began as small workshops organized at Caltech, called “Hopfest,” where John Hopfield brought together neuroscientists, physicists, and computer engineers to rethink information processing. These workshops each had 10 to 30 people, were cross-disciplinary, aimed at bridging disciplinary boundaries, and focused on brewing creative, new ideas.

Machine learning conferences like ICML and NeurIPS now draw tens of thousands of participants. Somewhere along the way, computer scientists convinced themselves that conference proceedings should be valued as highly as journal publications in other disciplines. A combination of industrial interest and metric-maximizing left AI conferences as an undignified mix of job fairs and “vetting” of “publications” for CV padding. The evaluation is indistinguishable from coin tossing, and no particular result ever stands out. It’s more likely that a mishap at an industry party will get attention than a paper will change the field. This situation is unfortunate and untenable.

Of course, the small workshops—mocking scale, let’s call them microconferences—live on. A professor with a little initiative can put together an ad hoc meeting. There are non-profit institutions dedicated to hosting these sorts of events, including mathematics research institutes like the Institute for Pure and Applied Mathematics at UCLA, computing research institutes like the Simons Institute at UC Berkeley, and institutes that grew to define an entire field like the Santa Fe Institute. However, microconferences are considered luxury goods, something everyone wants to do all the time, but is only allowed to do after their paper writing, teaching, reviewing, and committee work. For some reason, in the modern calculus of the curriculum vitae, a refereed conference paper is more valuable than inspiring a new research direction at a small meeting. This is absurd.

The funniest part about the quantification trap is how we forget that the quantities were ad hoc and artificial in the first place. What makes a Science paper count as prestigious is nothing more than the salivation of a bunch of annoying academics who want Science papers for themselves. If enough of us just want “well-curated microconference proceedings,” then we can value these just as highly.

How could we go about increasing the value and worth of these meetings? I don’t propose constructing an elaborate counting mechanism to have microconferences register as yet another notch on a publication list. And I know we can’t break down our current system of bureaucratic accounting overnight. Deans will still rely on stodgy metrics, scholars will need to produce legible artifacts to appease said deans, and historical institutional prestige will still signal more than it should. Nonetheless, I’d like to offer an initial path for fields to return to the days when small-scale but intense evaluations were valued more than large-scale but cursory selection processes.

Valuing the outputs of small workshops wouldn’t be a departure from our academic traditions. Most of our publication system traces back to reading papers before the Royal Society of London. A paper was only considered published after it had been read aloud and debated in person. Oftentimes, people read other people’s papers and debated these. Lots of our modern systems try to carry on this legacy of debate. In statistics, a main contributed paper is accompanied by “discussions” by other authors and a rejoinder by the contributed paper’s authors. In economics, the working paper serves as a way to gather feedback before official publication, which can take years. Many fields use “special issues” to compile talks from their conferences into proceedings. These are all great ideas! We should draw from the best of these traditions.

One of the hardest things to avoid is making hard-and-fast rules. Mission statements are always forgotten in giant bureaucratic systems, leaving behind a fossilized set of rules and conventions that people assume have been there since time immemorial. These systems then invite the same old gaming and goal displacement. Fully aware that this is the case, let me first state some values I’ve compiled in discussions with friends and colleagues. I’ll offer a few guidelines after.

1. What: Microconferences are where the best ideas are debated. Some things do not and cannot scale.

2. Who: Microconferences should bring together people who didn’t know each other before. You can invite friends, but you can’t only invite your friends. Sometimes you need to get different people in the room and see what happens.

3. When: The turnaround time from conception to microconference should be as short as possible.

4. Organization: While a parent institution for these microconferences can streamline logistics for microconference organizers, it should not require a permanent home or dedicated staff. Its leadership should be minimal and rotate over time. It should be easy to organize a microconference.

5. Output: Not all outputs of a microconference need to be a publication, but sharing findings and insights with others is part of what academics do. While not everything needs to be written down, and ephemeral conversation is important, participants should err on the side of more documentation.

For this final bullet, I envision a documentation structure similar to what organizations like the aforementioned IPAM and Simons Institute currently maintain: a webpage. The Proceedings of Machine Learning Research (PMLR) provides an ideal model. Inspired by the minimal elegance of the Journal for Machine Learning Research, Neil Lawrence cooked up a GitHub repo to compile and curate conference proceedings. It does exactly what is needed and nothing more. The main page will cleanly list past events, and you’ll be able to search by title or participant. Individual microconference webpages could include a list of participants, a photo of the gathering, and a documentary record that links to slides, videos, or papers. What is archived and how it is archived would be up to the organizers.

In the style of arXiv overlay journals, these pages could signify the “blessing” of a particular version of arXiv papers by the participants, demarcating that a paper has been legitimately peer-reviewed. People might dismiss such peer review as cronyism, but if you see the names of participants, you can judge for yourself what credence you want to give to the review.

I am not claiming that microconferences solve all problems. One glaring example is the widespread belief that computer science graduate students need papers. What is a PhD if not a bunch of papers stapled together? Yikes. The obsession with using conferences as a proxy for grad student education is a mistake we are paying for dearly. This proposal does not fix the problem. That said, having microconferences all over the place would be nothing but a boon for graduate students. There will always be one near their university that they can apply to attend. And nothing in this model prevents them from organizing their own microconferences.

Whatever the case, the current situation is untenable. Conferences are impossibly overrun, and their publications fully depreciated. A framework for microconferences offers something else. It is not a replacement. It is a new path to credentialing and cultivating expertise. Will it also end up a bureaucratic mess in a few years? Probably so! But I hope you’ll join me in trying it out before declaring defeat.

Subscribe now

By Ben Recht

Authors: Shuichi Hirahara, Kazuki Ogitsuka

It is notoriously difficult to obtain deterministic reductions for the Minimum Distance Problem (MDP) and the Shortest Vector Problem (SVP). Under two-sided-error randomized reductions, Bennett, Cheraghchi, Guruswami, and Ribeiro (STOC 2023) proved parameterized hardness of approximation for these problems. We partially derandomize their reductions and present one-sided-error randomized reductions: MDP is W[1]-hard to approximate within an arbitrary constant factor under FPT many-one one-sided-error randomized reductions; For every $p \ge 1$, SVP in the $\ell_p$ norm is W[1]-hard to approximate within an arbitrary constant factor below $2^{1/p}$. We demonstrate the usefulness of one-sided-error randomized reductions by showing that they can be conditionally derandomized when the target problem has an OR function. Under a standard hardness-vs-randomness assumption, namely a plausible lower-bound assumption against nondeterministic circuits, we prove a general theorem formalizing this derandomization. Here, an OR function combines several instances into one instance that preserves their disjunction. We construct such OR functions for the relevant MDP and SVP gap problems, and thereby obtain deterministic W[1]-hardness for approximating MDP over every fixed finite field within every constant factor, and for approximating SVP in $\ell_p$ norms for every fixed integer $p$ within every factor below $2^{1/p}$. Applying the same framework to Micciancio's one-sided-error randomized reduction (ToC 2012) yields, under the same circuit lower-bound assumption, deterministic polynomial-time NP-hardness of approximating Euclidean SVP within every constant factor.

Authors: Daniel Klötzl, Daniel Weiskopf

We present an uncertainty-aware Jacobi set computation method. In general, Jacobi sets are topological descriptors that capture the gradient alignments of two scalar fields, as, e.g., used for multi-field visualization. We adopt and reformulate an existing computational approach that relies on an edge-based identification of Jacobi set edges on a given triangulation. Our extension to uncertainty visualization builds upon a versatile, spatially coherent uncertainty model for pairs of scalar fields based on multivariate normal distributions. We propagate the uncertainty analytically, thereby lifting the original Jacobi set computation to uncertain inputs. Furthermore, we present an overlay of visual mappings specifically designed to show the Jacobi sets along with different facets of uncertainty information. Both the uncertainty model and uncertainty-aware method are validated against a Monte Carlo approach on an analytic dataset and applied to two use cases from fluid dynamics and weather ensembles.

Authors: Vishesh Jain

The Johnson--Lindenstrauss lemma asserts that every set of $n$ points in $d$-dimensional Euclidean space embeds into $O(\varepsilon^{-2}\log n)$-dimensional Euclidean space with distortion at most $1+\varepsilon$. Larsen and Nelson conjectured that the optimal target dimension throughout the full range of the parameters $n,d, \varepsilon$ is \[ Θ\left(\min\left\{d,n-1,\frac{\log(2+\varepsilon^2n)}{\varepsilon^2}\right\}\right). \] We resolve this conjecture in the affirmative. In fact, we prove the stronger statement that the upper bound is attained by a linear map. The matching lower bound, due to Larsen--Nelson and Alon--Klartag, holds even for nonlinear embeddings.

Authors: Simon Raßmann, Pascal Schweitzer

The tournament isomorphism problem is one of the two fundamental bottlenecks to designing better algorithms for the graph isomorphism problem. Though the problem has been investigated for more than five decades, compared to graphs, there are only very few results on the isomorphism problem of tournaments. For most classes of tournaments neither hardness nor polynomial-time solvability is known. Tournaments of bounded VC dimension are such a class for which no results are available, even though the VC dimension is arguably one of the most robust and central notions of combinatorial tameness. Resolving an open problem of Neuen and Grohe, we show that the isomorphism problem for tournaments of VC dimension $d$ can be decided in time $n^{O(d\log d)}$. Consequently, automorphism groups of tournaments of bounded VC dimension can be computed in polynomial time. To this end, we develop a new method to isomorphism-invariantly decompose tournaments. To facilitate recursion, we introduce the notion of a patched tournament and analyze bounded VC dimension in patched tournaments. We design a recursive algorithm that balances the size of the decomposed pieces against their number and makes use of the structure of near twins. In an orthogonal direction, it is known that a hereditary class of tournaments has unbounded VC dimension if and only if it contains all 2-colorable tournaments. As a second result, we show that also this class does not form an obstruction towards polynomial-time isomorphism testing and indeed show that isomorphism of tournaments of bounded chromatic number is polynomial-time decidable.

Authors: Yi Li

For $d \geq 2$, $p \geq 1$ and $ε> 0$, let $N_p(d,ε)$ be the smallest integer $N$ such that for every integer $n$ and every $A\in\mathbb{R}^{n\times d}$, there exists a matrix $Φ\in\mathbb{R}^{N\times n}$ satisfying $(1-ε)\lVert Ax\rVert_p\leq \lVertΦA x\rVert_p\leq (1+ε)\lVert Ax\rVert_p$ for all $x\in\mathbb{R}^d$. For every constant $p\geq 1$ with $p\not\in 2\mathbb{Z}$, when $d\gtrsim_p \log(1/ε)$, the bound \[ N_p(d,ε) \gtrsim_{p} \frac{d}{ε^2 \operatorname{polylog}(d/ε)} \] is established. This improves the previous lower bound $Ω(1/(ε^2\operatorname{polylog}(1/ε)))$ due to Li et al. (SICOMP 2021) and is optimal up to logarithmic factors for $1\leq p<2$. The central technical idea originated from ChatGPT 5.6 Sol.

Authors: Wing-Kai Hon, Dominik Köppl, Jun-Hong Wang

We study a tie-breaking variant of the longest common subsequence problem on run-length encoded strings. Given two strings, the goal is first to maximize the number of equal aligned character pairs, as in the classical longest common subsequence problem, and then, among all such alignments, to minimize the alignment length. Equivalently, after maximizing the number of equal pairs, we minimize the number of insertions and deletions. We show that this problem admits a simple block-boundary dynamic program. If the input strings have lengths $N$ and $M$, and their run-length encodings have $n$ and $m$ runs, respectively, the algorithm runs in $O(mN+nM)$ time using $O(nm)$ space. The algorithm treats every pair of runs as a homogeneous block with an explicit transfer function and stores dynamic-programming values only on run boundaries.

Authors: Kristóf Bérczi, Siyue Liu, Victor Reis, Jakub Tarnawski

We prove weighted matroid equitability. Let $M=(E,\mathcal{I})$ be a matroid whose ground set can be partitioned into $k$ bases, and assign a nonnegative weight to every element. Then $E$ has a partition into $k$ bases such that the weights of any two bases differ by at most the largest element weight. We present two proofs based on the localized exchange theorem of Akrami, Liu, Raj, and Végh. The first is existential, while the second is constructive and leads to a strongly polynomial-time algorithm. As applications, we obtain an additive guarantee for matroid-constrained makespan minimization for identical machines and a strongly polynomial-time algorithm for finding an EF1 allocation under a matroid constraint and identical additive valuations. We further generalize the Beck--Fiala framework in discrepancy theory to settings with matroid constraints. Given a nonnegative matrix of column sparsity $Δ$, we show that a fractional basis can be rounded to a basis of no larger cost while preserving every row sum within additive error $2Δ$ times the largest matrix entry. Motivated by the $2$-sparse prefix Beck--Fiala conjecture, we formulate a conjecture on prefix-constrained matroid bases and prove a discrepancy bound $O(\log n)$. Finally, we give a counterexample to the weighted carpooling conjecture, thereby also disproving a conjecture by Morell and Skutella on single-source unsplittable flows with two-sided discrepancy bounds.

Authors: Hiroshi Hirai

In this paper, we address a semi-infinite LP relaxation of the vector-subspace packing problem. This is a higher-dimensional generalization of the fractional linear matroid parity problem and is closely related to Brascamp-Lieb polytopes. We show that the dual of this LP can be formulated as ``linear programming on a Euclidean building," namely, the problem of minimizing a Busemann function over an intersection of horoballs. This provides a natural example of horospherically convex optimization, recently introduced by Goodwin et al. (2026) and Criscitiello and Kim (2025). By applying the incremental Busemann subgradient method, we obtain an additive FPTAS for the problem. As applications, we obtain a new and simpler polynomial-time algorithm for fractional linear matroid parity, and new algorithms for the membership problem of Brascamp-Lieb polytopes.

Authors: Yongjie Guan

Near capacity, a cuckoo filter may reject an insertion even though a legal placement still exists: the table remains structurally feasible, but a bounded policy fails to find an augmenting path. Random kick-out keeps each step cheap but leaves no persistent direction; breadth-first search recovers direction by expanding a frontier and maintaining table-scaled state. CavityRank exploits a resource already present in four-slot packed buckets. Lookup observes only the fingerprint multiset, so query-equivalent lane orders can encode two comparison bits without widening the 64-bit bucket or changing the two-bucket query. The bits form a four-level ordinal residual rank. Insertion follows a minimum-rank edge and re-encodes each modified bucket from its outgoing edges after relocation, propagating the rank actually realized by the packed word. An exact capacity-four orientation oracle separates structural infeasibility from bounded-search loss. In a paired 4,096-bucket XOR16 ladder, CR2 closes 86.47% of Random CF's oracle gap and CavityRank leaves 1.39% of that original gap. A canonical-tie CR2-versus-CavityRank ablation isolates the second implicit bit, which closes 89.95% and 90.69% of CR2's residual gap; the corresponding closures at 65,536 buckets are 83.95% and 84.27%. A separate packed implementation study at 64 MiB and 97.75% load records 42.53 logical reads per insertion, versus 62.67 for explicit labels and 355.74 for depth-10 BFS, with zero extra bytes per bucket and no table-scaled workspace. CavityRank therefore occupies a practical design point between unguided eviction and frontier search.

Authors: Jason Li, Trevor Vaughn

A spectral sparsifier of a weighted graph is a reweighted subgraph whose Laplacian quadratic form approximates that of the original graph. Let $G$ be a positively weighted $n$-vertex, $m$-edge multigraph, let $0<\varepsilon\le1/2$. Assuming $m,\varepsilon^{-1}\le n^{O(1)}$ and the ratio of maximum to minimum weight is polynomially bounded, we deterministically construct a $(1\pm\varepsilon)$-spectral sparsifier with \[ O\!\left(n\varepsilon^{-2}\log^{24+o(1)}n\right) \] edges in \[ m^{1+o(1)}+O\!\left(n^2\varepsilon^{-9/2}\log^{113/2+o(1)}n\right) \] time. The construction has two main ingredients. First, we sparsify an approximately regular expander by partitioning its edges into few matchings and viewing their normalized Laplacians as an isotropic family of positive semidefinite matrices. Rather than sample from this family and apply matrix Chernoff, we select matchings deterministically using a pessimistic estimator. We evaluate the resulting conditional-expectation scores in two ways to produce two algorithms: using dense matrix multiplication and sparsely using polynomial approximations to the inverse square root and matrix exponential. Deterministic expander decomposition, along with replacing vertices by fixed expander graphs to achieve approximate regularity, extends these algorithms to general graphs. Second, a recursive blocking scheme applies the dense algorithm to smaller subgraphs and the sparse algorithm to their union, balancing their costs. Reusing the resulting algorithm as the dense algorithm gives $α_{r+1}=3-1/(α_r-1)$, starting from $α_0=ω$. After $O(\log n)$ levels, the exponent is $2+O(1/\log n)$, yielding $m^{1+o(1)}+\widetilde O_{\varepsilon}(n^2)$ time.

Friend-of-the-blog (well, mainly just friend) Adi Akavia has asked me to publicize that she’s helping to organize an exciting CS conference called Mind-IL at Tel Aviv University on October 26, in memory of the Israeli-American Turing Award winner Michael O. Rabin, who passed away in April. Please note that October 26 is the day before the Israeli election, for any Israeli citizenship holders living abroad who might want an academic excuse to come to Israel and vote.

By Scott

Lance has posted about his, and around 160 others, being laid off from IIT here.(IIT stands for Illinois Institute of Technology which is where Lance was employed.)

Hence I looked into what is happening at IIT to see if there is a lesson for us all.

I) I wondered why IIT had declining enrollment. I wondered which of the two reasons below  was the issue (and of course there are other reasons). 

--The enrollment cliff.  (See here)

--International students have declined in number. Why? (1) Having getting student visas, (2)  They think they are not welcome here (3) Schools in their home country getting better. Note that I am just guessing.

Rather than speculate I asked ChatGPT for the data on both enrollment and on international enrollment from 2015 to 2025. Here is the data: here.

a) 2015 had an enrollment of 7792. It went down in 2020 (COVID?) but then came up again and it was 8838 in 2024.  In all the years for which there is data international students were about half of the students.

b) 2024: 8838 students, of which 4596-International (52%), 4242-Americans

   2025: 7502 students, of which 2141-International (42%), 5361-Americans

So it looks like the enrollment cliff was not a problem since more Americans came, but the decline in international students is a problem.

I think that international students pay more, so their decline creates more of a financial pinch.

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

II) I wondered if other schools had massive layoffs so  I asked Google AI what other schools had laid off more than 30 professors in the last two years. It had an issue with that since schools combine faculty and staff.  Even so, the main fact is that (a) it is happening at other schools, and (b) 160 is more than usual. 

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

III) Challenges facing Universities

a) The enrollment cliff. This will be a real problem for small schools.  For big schools it may be an opportunity to have smaller classes.  This issue cannot be stopped.

b) Less international students means less money. This may change since this or a later administration may change the rules. However, changing the rules might not help much since other countries have fine schools and international students may feel they are not welcome here.

c) Grants are drying up. Again, this may change.

d) AI and cheating. This may make us rethink the entire point of education.

e) Does college exist to create an educated public who can make decisions and vote intelligently, or are colleges vocational? It's getting harder to do both.

f) Fads: The hot topics in CS now are Quantum, ML, and Quantum ML. What will they be in 10 years?How do we adjust? Do other fields have this problem? ML (or more broadly AI) is hot in that students want to take it because it both sounds interesting and sounds employable. Quantum is hot for grant money and some students think its going to be cool. (In this context `Hot' and `Cool' are not opposites.) 

g) Tuition keeps going up. The business model may be broken.

h) A while back online education seemed like it might be an alternative for some students (MOOCS were hot). That hasn't happened yet but it might.

i) This is a far bigger subject than the points above. Maybe Lance can write a book on the topic now that he has some free time.

By gasarch

We give a randomized algorithmic version of the Balog--Szemer\'edi--Gowers theorem for sets of integers. Let $A\subseteq[N]$ have size $n:=|A|\geq2$, let $1\leq K\leq n$, and suppose that its additive energy satisfies $E(A)\geq n^3/K$. Reiher and Schoen proved existentially that, for every fixed $\epsilon \in (0,1/2)$, there is a subset $A'\subseteq A$ satisfying $|A'|\geq(1-\epsilon)n/\sqrt K$ and $|A'-A'|\leq O_{\epsilon}(K^4)|A'|$; the size scale $n/\sqrt K$ is essentially optimal. We give an algorithmic counterpart: with probability at least $1-n^{-10}$, our algorithm runs in time $nKN^{o(1)}$ and returns a subset $A'\subseteq A$ satisfying $|A'|\geq cn/\sqrt K$ and $|A'-A'|\leq CK^4|A'|$, where $c,C>0$ are absolute constants. Thus the output attains the essentially optimal subset-size scale and the best-known $K^4$ dependence for the normalized difference set.

The line--versus--point test asks the following local-to-global question. Suppose a function $f\colon\mathbb{F}_q^m\to\mathbb{F}_q$ is, on average over a random affine line $L$, correlated with some degree-$d$ polynomial on $L$. Must $f$ then be globally correlated with a single multivariate polynomial of degree at most $d$? Beyond being a natural combinatorial question, this test and its variants have played a central role in the construction of PCPs. Generally, one is most interested in the soundness of the test: the smallest expected local agreement from which one can still deduce nontrivial global agreement. We revisit the line--versus--point test and prove the following cubic threshold. If \[ \Pr_{L,,x\in L}\bigl[P_L(x)=f(x)\bigr]\ge C\left(\frac{d}{q}\right)^{1/3}, \] then there is a polynomial $Q\in\mathbb{F}_q[X_1,\ldots,X_m]$ of total degree at most $d$ such that \[ \Pr_{x\in\mathbb{F}_q^m}[Q(x)=f(x)]\ge c\cdot \Pr_{L,,x\in L}\bigl[P_L(x)=f(x)\bigr], \] for absolute constants $C,c>0$ and over every finite field $\mathbb{F}_q$. The prior state of the art, due to [HKSS24], had an inexplicit exponent in their soundness, which we estimate to be $\Omega\left((d/q)^{1/48}\right)$ in the $m>2$ case and $\Omega\left((d/q)^{1/7}\right)$ in the $m=2$ case. We believe our proof is comparatively direct and isolates the combinatorial and algebraic mechanisms responsible for the improved soundness.