Theory of Computing Report

Authors: Pravesh K. Kothari, Andrew D. Lin

We formulate an approximate Cauchy-Schwarz inequality and show that it is satisfied by solutions to the Sherali-Adams linear programming hierarchy (interpreted as ``pseudo-distributions''). As a consequence, we resolve a question left open by the work of O'Donnell and Schramm [OS19] that they had explicitly attributed to the lack of such an inequality. A Cauchy-Schwarz inequality is exactly satisfied by pseudo-distributions satisfying the constraints of the sum-of-squares semidefinite programming hierarchy and already has scores of applications. However, the proof there requires global positive semidefiniteness. Our approximate version, on the other hand, relies only on local positive semidefiniteness satisfied by the Sherali-Adams pseudo-distributions. Our formulation loses an additive error that scales with the L1 norm of the coefficients of the constituent polynomials, and this loss is asymptotically tight. Our proof is elementary and relies on a simple sampling argument. As an application, we resolve a question left open in the work of O'Donnell and Schramm that gives a trade-off between constraint density and the Sherali-Adams degree for refuting random constraint satisfaction problems. Specifically, for odd arity CSPs, we show that the constraint density requirement for a given degree can be improved by a polynomial factor in $n$. Along the way, we observe that by a simple extension, the results in their work extend to a more general semirandom setting.

Authors: Eva Deltl, Christian Komusiewicz, Jurek Rostalsky, Johannes Schröder, Luca Pascal Staus

In bus routing, the task is to plan a bus route in a network with several agents, each of whom wants to travel from a starting point to a destination. A bus route should account for several factors, including agents' cost for reaching the bus stops, their travel time, or the energy consumption of the buses. We study the complexity of several variants of this problem, focusing on how the objective function and the models for agents' walking costs influence the problem complexity. After observing that even the simplest agent cost model leads to hardness on general networks, we consider networks with tree structure. Our main findings are as follows. First, allowing agent-specific cost models leads to hardness even on extremely limited trees such as stars. Second, consistent agent models (where agents differ only in their starting points and destinations) make the problem easier in some cases. Finally, allowing agents to choose between using the bus and walking directly can make the problem considerably harder. Most of our hardness results show not only classical NP-hardness but also parameterized intractability for the natural parameter $k$, the number of bus stops.

Authors: Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard

We give the simplest known algebraic proof of the PCP theorem, involving only ingredients like code concatenation, polynomial interpolation, and polynomial multiplication. Specifically, we prove that graph 3-coloring has a polynomial-sized proof that can be verified by a verifier tossing logarithmically many coins and querying a constant number of bits in the proof. In particular, our proof does not involve any PCP compositions; notably, it does not invoke the NP-completeness of any fixed problem, such as SAT or 3-coloring, in the construction of the verifier. The main innovation in our work is a clean, coding theoretic, way to encode univariate polynomials that allows us to implement ``low-degree testing'' using just a constant number of bits of queries. Insights from recent attempts to simplify the PCP proof by the authors (STOC 2026) and Goldreich (ECCC 2025) allow us to observe that low-degree was the key bottleneck in converting previous algebraic constructions of the PCP verifier into a constant query PCP. Thus, by overcoming this bottleneck, we get the full PCP verifier using elementary and self-contained steps. As concrete support for the claimed simplicity, we include the full pseudocode of the PCP verifier, assuming finite field arithmetic, and a full description of the completeness (aka ``honest'') prover, assuming multivariate polynomial arithmetic including interpolation and evaluation, that fit in about a page each.

Authors: Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer

For a prime $p\geq 3$, a somewhat restricted $3$-AP in $\mathbb{F}_p^n$ is a triplet $(x,x+a,x+2a)$, where $x\in\mathbb{F}_p^n$ and $a\in \{0,1,2\}^n$. We prove a counting lemma for somewhat restricted $3$-APs in dense sets in $\mathbb{F}_p^n$. More precisely, we prove that for all $α>0$, there exists $β>0$, such that for sufficiently large $n$, if a set $A\subseteq \mathbb{F}_p^n$ has density at least $α$, then it contains at least $β$ fraction of all somewhat restricted $3$-APs. Our proof builds on recently developed machinery from [Bhangale, Khot, Minzer, 2026]. Our main new ingredient is an arithmetic regularity lemma for patterns such as somewhat restricted 3-APs. This result is in the spirit of arithmetic regularity lemmas from the theory of Gowers uniformity norms [Green, Tao, 2010] and may be of independent interest.

Authors: Louay Bazzi, Georges Khater

Efficient decoding is essential for the practical realization of fault-tolerant quantum computers. We study the computational complexity of minimum-weight decoding for topological quantum codes. For surface codes under the depolarizing channel, we consider Minimum-Weight decoding, which seeks a minimum-weight Pauli error consistent with both the $X$- and $Z$-syndromes. For color codes under independent $X$- and $Z$-error models, we consider Separate Minimum-Weight decoding. Assuming $P\neq NP$, we establish polynomial additive inapproximability gaps for these problems. Specifically, for the toric code and the $4.8.8$ color code on the torus, no polynomial-time algorithm can always produce a solution whose weight is within $Ω(N^{1/14})$ of the optimum, where $N$ is the number of qubits. For the planar surface code, we obtain an $Ω(N^{1/18})$ gap. Our inapproximability results use Håstad's hardness of approximation for MAX-3SAT. Our reduction develops a general, modular framework for embedding logical constraints into coupled primal--dual join problems on a lattice. A key ingredient is a localization argument that controls unintended interactions between different parts of the construction.

Authors: Christopher Williamson

For every $n\geq 9$ that is a multiple of 3, we construct an explicit access structure on $n$ participants. In every perfect secret-sharing scheme realising this access structure, if $S$ denotes the random secret, then the sum of the share entropies is at least $\left(\frac{n^2}{9}+\frac{2n}{3}\right)H(S)$, and some participant has share entropy at least $\left(\frac{n}{6}+\frac12\right)H(S)$. After normalisation by $H(S)$, these are respectively $Ω(n^2)$ and $Ω(n)$ lower bounds and also give the same asymptotic lower bounds on the total and largest expected binary lengths of the shares. This improves by a logarithmic factor the longstanding general lower bounds of $Ω(n^2/\log n)$ for total share size and $Ω(n/\log n)$ for maximum share size due to Csirmaz. The proof uses only elementary Shannon inequalities, together with some averaging arguments. The Shannon-information method has universal $O(n^2)$ and $O(n)$ ceilings for the total and maximum normalised entropy lower bounds it can certify, so our construction reaches both ceilings up to constant factors.

Authors: JiYe Liu, Wenkai Wang, Qiang Tian, Wenjun Wang

The cluster graphs on $n$ vertices, the disjoint unions of complete graphs, have the integer partitions of $n$ as their isomorphism classes, and the quotient edit distance $q^*(λ,μ)=\min_{σ\in S_n}|E(G_λ)\triangleσE(G_μ)|$ makes that set a metric space. Its metric geometry and its computational complexity both issue from one identity: $q^*$ is an affine function of the maximum of $\lVert X\rVert_F^2$ over the contingency tables with margins $λ$ and $μ$. Combinatorially, it yields two explicit $\ell_1$ models: the vertex-mass metric $δ_1$ on sorted degree sequences, with $\frac12δ_1\le q^*<\frac32δ_1$ and both constants optimal, and the block-energy metric $B$ on the vectors $\bigl(\binom{λ_i}2\bigr)_i$, with $q^*\le B\le2q^*-1$ by a per-table refinement measuring how far an alignment is from a block bijection. Hence $c_1(\mathcal K_n)\le2$, and an $O(n\log n)$-time algorithm returns an alignment of cost below $2q^*$ with the certificate $q^*\in[\lceil(B+1)/2\rceil,B]$. The Euclidean distortion of the class is $c_2(\mathcal K_n)=Θ(n^{1/4})$; against it we measure the weighted dyadic sums $F^{(γ)}$ of the Ferrers staircase, of dimension below $4n$ and computable in $O(n)$ time. The unweighted member has distortion exactly $Θ(n^{1/4}\sqrt{\log n})$, while the critical weight $γ=\frac14$ improves this unconditionally to $O(n^{1/4}(\log n)^{1/4})$ through an inverse energy inequality proved from the quantization of staircase jumps; removing the residual $(\log n)^{1/4}$ is reduced to one inverse inequality on the realizable cone. Computationally, the same identity gives a classification: deciding $q^*(λ,μ)\le Q$ is strongly NP-complete, evaluation is strongly NP-hard and admits no FPTAS unless $\mathrm P=\mathrm{NP}$, while the farthest alignment is polynomial-time solvable.

Authors: Anton Herrmann

We show that Integer Quadratic Programming is W[1]-hard parameterized by the number of variables. Thus, under standard complexity assumptions, Integer Quadratic Programming cannot be solved in f(n)|I|^{O(1)} time for any computable function f where |I| is the size of the encoding and n is the number of variables.

Authors: Philip Bille, Johannes Fischer, Inge Li Gørtz, Filippo Lari

We study the data structure version of the \emph{element distinctness problem}: preprocess an array of $n$ elements from an alphabet of size $σ$ to answer \textsc{All-Distinct} queries, asking whether a given range contains only distinct elements. We first focus on \emph{uniformly random arrays}: in the encoding model, where access to the input at query time is not allowed, we prove a lower bound on the expected space; for instance, the lower bound is $n$, $1.3627n$, $1.5153n$, $1.5824n$ bits for $σ= 2,3,4,5$, and approximately $n\sqrt{π/(2σ)}\,\logσ$ bits for $σ=ω(1)$. We complement this by designing different average-case optimal encodings, supporting \textsc{All-Distinct} queries in worst-case time $O(1)$, $o(\log^{2}{\log{n}})$, or $O(\log\log{n})$ depending on $σ$, and $O(1)$ expected time for any $σ= ω(1)$. We then switch to worst-case (non-random) arrays: in the indexing model, where access to the input is allowed, we prove a cell-probe space-time tradeoff lower bound showing that any index using $n/b$ bits must have $Ω(b/\log{b})$ query time. We conclude by presenting a simple index almost matching this lower bound.

Authors: Paweł Rzążewski

We study the parameterized complexity of $k$-Coloring in $H$-free graphs, when $H$ is a linear forest (i.e., a disjoint union of paths) as an induced subgraph. We show two hardness results: * $k$-Coloring is W[1]-hard in $2P_2$-free graphs when parameterized by $k$. * $3$-Coloring is W[1]-hard in $P_t$-free graphs when parameterized by $t$. Moreover, assuming the ETH, these problems admit no algorithms solving $n$-vertex instances in time $f(k) \cdot n^{o(k)}$ and $f(t) \cdot n^{o(t/\log t)}$, respectively, for any computable function $f$. The first result resolves in a strong form a long-standing open problem, originally posed by Hoàng, Kamiński, Lozin, Sawada, and Shu [Algorithmica, 2010]. The second result answers a question of Golovach, Johnson, Paulusma, and Song [Journal of Graph Theory, 2017].

Authors: Jason Li, Alex Wice

We show that the balancing weights technique of Li (2026) actually produces an approximate *pseudo-circulation* of a directed, capacitated graph in $m^{1+o(1)}$ time. Together with standard flow techniques, we obtain an $m^{1+o(1)}$ time maximum flow algorithm that avoids the interior-point method framework of recent almost-linear time algorithms (Chen et al. FOCS 2022, van den Brand et al. FOCS 2024).

Authors: Indraveni Chebolu, Bhavani Singh Rajpurohit, Arnab Mallick

Recent multi-scale nearest-source methods give polynomially sublinear girth approximations in CONGEST. We isolate the direct black-box route for making this framework exact: sequential calls to the same estimator on fresh exchangeable source sets, with source cardinalities and nearest-source capacities chosen adaptively from previous scalar outputs and with an adaptive stopping rule. On a bounded-degree, logarithmic-diameter family $H_t$ with $n_t$ vertices and a unique girth-$g_t=Θ(\log n_t)$ cycle, exactness requires a sampled cycle source to survive at an antipodal edge despite a linear number of strictly closer competitors. For any such exactification $\mathcal A$, a permutation-rank argument yields the implementation-independent workload bound $\Pr[\mathcal A(H_t)=g_t]\leq(3g_t/n_t)\,\mathbb E[\sum_{j=1}^{T}\min\{Q_j,k_j\}]$, where $T$ is the number of executed calls, $Q_j$ is the source-set cardinality, and $k_j$ is the nearest-source capacity of call $j$. Thus constant exactness probability requires $Ω(n_t/g_t)=Ω(n_t/\log n_t)$ expected retained-source workload. We formally show that retuning the recent multi-scale template solely through its scale count/order, Bernoulli or fixed-cardinality sampling, capacities, and scalar-output stopping rules lies in this class. For the standard sequential packetized estimator realization, the workload theorem gives an $Ω(n_t/\log n_t)$ expected-round corollary. This is a barrier to a defined black-box exactification strategy, not a lower bound for unrestricted exact girth in CONGEST.

As part of Mind-IL.- Israel’s Science and Academia Week (which also is around the Israeli election) there would be a special conference in honor of Michael Rabin with some fantastic lecturers.

By Boaz Barak

For a prime $p\geq 3$, a somewhat restricted $3$-AP in $\mathbb{F}_p^n$ is a triplet $(x,x+a,x+2a)$, where $x\in\mathbb{F}_p^n$ and $a\in \{0,1,2\}^n$. We prove a counting lemma for somewhat restricted $3$-APs in dense sets in $\mathbb{F}_p^n$. More precisely, we prove that for all $\alpha>0$, there exists $\beta>0$, such that for sufficiently large $n$, if a set $A\subseteq \mathbb{F}_p^n$ has density at least $\alpha$, then it contains at least $\beta$ fraction of all somewhat restricted $3$-APs. Our proof builds on recently developed machinery from [Bhangale, Khot, Minzer, 2026]. Our main new ingredient is an arithmetic regularity lemma for patterns such as somewhat restricted 3-APs. This result is in the spirit of arithmetic regularity lemmas from the theory of Gowers uniformity norms [Green, Tao, 2010] and may be of independent interest.

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$.

Authors: Ian D'Ambrosio

Huang, Lou, and Xiao introduced Dynamic Mixture-of-Experts Serving and gave an O(sqrt(log k))-competitive randomized algorithm for its integral primal problem, where k is the number of replica GPUs beyond the mandatory copy of each expert. Their matching lower barrier applies to an auxiliary dual and leaves the primal order open. We prove that the randomized primal competitive ratio is in fact Theta(1) for arbitrary numbers of experts. The upper bound reduces reciprocal-max service costs to chasing positive bodies with covering row sparsity two. A finite tangent envelope approximates each reciprocal epigraph within a constant factor, summable positive resets convert accumulated service into movement, and a nonexpansive balanced projection removes the positive-body algorithm's resource augmentation. Combining the resulting fractional path with Lazy Threshold Rounding gives E[ALG] <= 10 C_PB OPT + (5 C_PB + 2) k + 16, where C_PB is the absolute constant from Chasing Positive Bodies at resource augmentation one and covering sparsity two. The full reduction, rounding composition, and quantified main theorem are machine-checked in Lean 4 relative to exact formal interfaces for the two cited source theorems. Deterministic rational controls and a fresh independent replay accompany the formal proof.

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