Theory of Computing Report

Authors: Guy Emerson

The motivation for this paper is the investigation of the trade-offs implicit in probabilistic models used in machine learning. Models are often used to make predictions in the form of conditional probabilities. However, a pair of conditional distributions p(x|y) and p(y|x) may not be compatible with any joint distribution p(x,y). Given two such conditionals, determining if there exists a compatible joint is known as the compatibility problem. For discrete random variables, when the conditionals are encoded as probability tables, the compatibility problem has a known solution, which is computationally tractable. In this paper, we formalise and study a succinct version of the problem, encoding conditional distributions as arithmetic circuits. This is applicable to practical applications of probabilistic modelling in high-dimensional settings, including neural network models. We show that, for succinct circuit representations of conditionals, the compatibility problem is intractable. In the case that all probabilities are non-zero, the problem is co-NP-complete. In the case that probabilities can be zero, we give examples to demonstrate that several notions of compatibility can be distinguished, and we prove that multiple versions of the problem are PSPACE-complete. Furthermore, we show that, assuming the polynomial hierarchy does not collapse, there exist compatible succinct conditionals whose joint cannot be expressed succinctly. Implications of these results for probabilistic modelling and machine learning are discussed.

Authors: Guy Emerson

The motivation for this paper is the investigation of the trade-offs implicit in probabilistic models used in machine learning. Models are often used to make predictions in the form of conditional probabilities. However, a pair of conditional distributions p(x|y) and p(y|x) may not be compatible with any joint distribution p(x,y). Given two such conditionals, determining if there exists a compatible joint is known as the compatibility problem. For discrete random variables, when the conditionals are encoded as probability tables, the compatibility problem has a known solution, which is computationally tractable. In this paper, we formalise and study a succinct version of the problem, encoding conditional distributions as arithmetic circuits. This is applicable to practical applications of probabilistic modelling in high-dimensional settings, including neural network models. We show that, for succinct circuit representations of conditionals, the compatibility problem is intractable. In the case that all probabilities are non-zero, the problem is co-NP-complete. In the case that probabilities can be zero, we give examples to demonstrate that several notions of compatibility can be distinguished, and we prove that multiple versions of the problem are PSPACE-complete. Furthermore, we show that, assuming the polynomial hierarchy does not collapse, there exist compatible succinct conditionals whose joint cannot be expressed succinctly. Implications of these results for probabilistic modelling and machine learning are discussed.

Tuesday, September 01 2026, 00:00

An Optimal Separation Between Certificate Complexity and Approximate Degree

Authors: Kaspars Balodis

We prove that certificate complexity can be quartically larger than approximate degree. More precisely, we construct a family of total Boolean functions $G$ with $$ C(G) = \tildeΩ(\tilde{deg}(G)^4), $$ where $C$ denotes certificate complexity and $\tilde{deg}$ denotes $1/3$-approximate degree. This is optimal up to polylogarithmic factors, since every total Boolean function $f$ satisfies $C(f)\le O(\tilde{deg}(f)^4)$ by the classical block-sensitivity bounds of Nisan and Nisan--Szegedy. Thus the result closes the gap between these two measures and improves the previously best known separation $C(f)=\tildeΩ(\tilde{deg}(f)^3)$ by Balodis, Ben-David, Göös, Jain, and Kothari. The construction starts from the partial function they used to quadratically separate $0$-certificate complexity from unambiguous $1$-certificate complexity. It already has the required certificate hardness, but its $0$-certificates are unstructured, which blocks the derivation of a low-degree verifier. We keep its $1$-condition and restrict the $0$-inputs to those certified by a structured family whose validity admits a low-degree approximant, while preserving the quadratic hardness. The partial function with its low-degree verifier is then fed through the cheat-sheet framework to yield the total function $G$ with the claimed separation. The main technical ingredient is an approximate polynomial that verifies the certificate in degree $\tilde{O}(\sqrt n)$. The verifier forms a low-degree count $W$ of the candidate $1$-certificates that remain compatible with the asserted $0$-certificate, and tests whether this count is zero. Crucially, the construction ensures that $W$ never exceeds $\tilde{O}(n)$, instead of the $Θ(n^2)$ candidate pairs it counts bringing the verification down to degree $\tilde{O}(\sqrt n)$.

Authors: Kaspars Balodis

We prove that certificate complexity can be quartically larger than approximate degree. More precisely, we construct a family of total Boolean functions $G$ with $$ C(G) = \tildeΩ(\tilde{deg}(G)^4), $$ where $C$ denotes certificate complexity and $\tilde{deg}$ denotes $1/3$-approximate degree. This is optimal up to polylogarithmic factors, since every total Boolean function $f$ satisfies $C(f)\le O(\tilde{deg}(f)^4)$ by the classical block-sensitivity bounds of Nisan and Nisan--Szegedy. Thus the result closes the gap between these two measures and improves the previously best known separation $C(f)=\tildeΩ(\tilde{deg}(f)^3)$ by Balodis, Ben-David, Göös, Jain, and Kothari. The construction starts from the partial function they used to quadratically separate $0$-certificate complexity from unambiguous $1$-certificate complexity. It already has the required certificate hardness, but its $0$-certificates are unstructured, which blocks the derivation of a low-degree verifier. We keep its $1$-condition and restrict the $0$-inputs to those certified by a structured family whose validity admits a low-degree approximant, while preserving the quadratic hardness. The partial function with its low-degree verifier is then fed through the cheat-sheet framework to yield the total function $G$ with the claimed separation. The main technical ingredient is an approximate polynomial that verifies the certificate in degree $\tilde{O}(\sqrt n)$. The verifier forms a low-degree count $W$ of the candidate $1$-certificates that remain compatible with the asserted $0$-certificate, and tests whether this count is zero. Crucially, the construction ensures that $W$ never exceeds $\tilde{O}(n)$, instead of the $Θ(n^2)$ candidate pairs it counts bringing the verification down to degree $\tilde{O}(\sqrt n)$.

Tuesday, September 01 2026, 00:00

Exact quantum splitting and the structure of finite algebras

Authors: Muhammad Imran

Berlekamp's algorithm factors a squarefree polynomial $f\in\mathbb{F}_q[x]$ by deterministic linear algebra, reducing the problem to splitting an explicit commutative algebra $B\cong\mathbb{F}_q^r$ into its $r$ simple factors. For large odd $q$, the standard efficient splitting step is randomized, while known derandomizations are conditional on the Extended Riemann Hypothesis. We give an unconditional exact quantum implementation in a circuit model permitting single-qubit rotations through efficiently computable angles. The construction uses an unconditional counting argument. For a block containing $s\ge2$ irreducible factors, a quadratic-character test in odd characteristic and an absolute-trace test in characteristic $2$ yield a nonconstant test element with probability $p_{q,s}\ge\tfrac12$, known exactly in advance and depending only on $q$ and $s$, not on the unknown factorization. Exact amplitude amplification therefore converts each randomized test into a procedure succeeding with certainty after one amplification iteration. The resulting algorithm uses exactly $r-1$ quantum splitting rounds and $O(n^3\log q)$ quantum $\mathbb{F}_q$-operations and $O(n^3)$ classical operations, requiring no primitive root, quadratic non-residue, or distinct-degree preprocessing. The method also splits arbitrary finite-dimensional separable commutative $\\mathbb{F}_q$-algebras given by structure constants. Combined with R'onyai's classical structure theory, which computes the radical deterministically and reduces the remaining tasks deterministically to polynomial factorization, it yields the radical and the Wedderburn decomposition of $A/\mathrm{Rad}(A)$ into minimal two-sided ideals, with certainty, for any $n$-dimensional associative $\mathbb{F}_q$-algebra given by structure constants, using $O(n^4\log q)$ quantum $\mathbb{F}_q$-operations.

Authors: Muhammad Imran

Berlekamp's algorithm factors a squarefree polynomial $f\in\mathbb{F}_q[x]$ by deterministic linear algebra, reducing the problem to splitting an explicit commutative algebra $B\cong\mathbb{F}_q^r$ into its $r$ simple factors. For large odd $q$, the standard efficient splitting step is randomized, while known derandomizations are conditional on the Extended Riemann Hypothesis. We give an unconditional exact quantum implementation in a circuit model permitting single-qubit rotations through efficiently computable angles. The construction uses an unconditional counting argument. For a block containing $s\ge2$ irreducible factors, a quadratic-character test in odd characteristic and an absolute-trace test in characteristic $2$ yield a nonconstant test element with probability $p_{q,s}\ge\tfrac12$, known exactly in advance and depending only on $q$ and $s$, not on the unknown factorization. Exact amplitude amplification therefore converts each randomized test into a procedure succeeding with certainty after one amplification iteration. The resulting algorithm uses exactly $r-1$ quantum splitting rounds and $O(n^3\log q)$ quantum $\mathbb{F}_q$-operations and $O(n^3)$ classical operations, requiring no primitive root, quadratic non-residue, or distinct-degree preprocessing. The method also splits arbitrary finite-dimensional separable commutative $\\mathbb{F}_q$-algebras given by structure constants. Combined with R'onyai's classical structure theory, which computes the radical deterministically and reduces the remaining tasks deterministically to polynomial factorization, it yields the radical and the Wedderburn decomposition of $A/\mathrm{Rad}(A)$ into minimal two-sided ideals, with certainty, for any $n$-dimensional associative $\mathbb{F}_q$-algebra given by structure constants, using $O(n^4\log q)$ quantum $\mathbb{F}_q$-operations.

Tuesday, September 01 2026, 00:00

A note on the $Σ_2^P$-completeness of the Frobenius number

Authors: Thomas Rothvoss

Given a finite set $A$ of natural numbers whose greatest common divisor is one, the Frobenius number $g(A)$ is the largest integer that is not a non-negative integer combination of the numbers in $A$. In a 2016 preprint, Matsubara states that given $A$ and $k$, deciding if $g(A) \geq k$ is $Σ_2^P$-complete. A decade has passed since without peer-reviewed publication of this result. At the same time, the community has found it difficult to verify this result. In this note, we give a write-up of the completeness proof based on Matsubara (2016).

Authors: Thomas Rothvoss

Given a finite set $A$ of natural numbers whose greatest common divisor is one, the Frobenius number $g(A)$ is the largest integer that is not a non-negative integer combination of the numbers in $A$. In a 2016 preprint, Matsubara states that given $A$ and $k$, deciding if $g(A) \geq k$ is $Σ_2^P$-complete. A decade has passed since without peer-reviewed publication of this result. At the same time, the community has found it difficult to verify this result. In this note, we give a write-up of the completeness proof based on Matsubara (2016).

Tuesday, September 01 2026, 00:00

On the Complexity of Bayesian Signal Processing

Authors: Yi Liu

We develop a computational framework for Bayesian decision-making. We show that as long as no action is optimal in every state, Bayes-optimal choice is intractable. This hardness need not arise from large action, state, or signal spaces, nor from a complicated represented utility function: extracting enough information from a hard-to-interpret signal to act optimally can itself be computationally hard. We also characterize tractability across approximation notions and identify their sources of difficulty. Under the probably approximately correct criterion, sample-based Bayesian learning is tractable if and only if the signal support is bounded. Our results provide justifications for bounded rationality, costly Bayesian inference, and sample-based Bayesian learning.

Authors: Yi Liu

We develop a computational framework for Bayesian decision-making. We show that as long as no action is optimal in every state, Bayes-optimal choice is intractable. This hardness need not arise from large action, state, or signal spaces, nor from a complicated represented utility function: extracting enough information from a hard-to-interpret signal to act optimally can itself be computationally hard. We also characterize tractability across approximation notions and identify their sources of difficulty. Under the probably approximately correct criterion, sample-based Bayesian learning is tractable if and only if the signal support is bounded. Our results provide justifications for bounded rationality, costly Bayesian inference, and sample-based Bayesian learning.

Tuesday, September 01 2026, 00:00

The Complexity of Coverability-Like Problems in Elementary Object Systems: Data-Nets to the Rescue

Authors: Francesco Di Cosmo, Soumodev Mal, Tephilla Prince

Elementary Object Systems (EOSs) are a model in the nets-within-nets (NWNs) paradigm, where tokens in turn can host standard Petri nets. We study the complexity of coverability-like problems, including termination and boundedness, over EOSs. Since coverability and boundedness are undecidable in general on EOSs, we focus on the relevant fragment of conservative EOSs (cEOSs). Our technique interprets cEOSs into the framework of data nets, whose tokens carry data from an infinite domain, thus bridging the nesting and the data-aware paradigms. Specifically, we show that cEOS coverability-like problems are equivalent to the coverability-like problems over an interesting fragment, called channel-$ν$PNs (c-$ν$PNs), of data nets that extends $ν$PN (featuring globally fresh name creation) with restricted forms of transfers with renaming. c-$ν$PNs remain less expressive than Unordered Data Nets, which feature lossy name creation as well as powerful forms of whole-place operations and broadcasts. These reductions allow us to analyze cEOS coverability taking advantage of known results on data nets. We conclude that the complexity of cEOS coverability is double-Ackermanian, $\mathcal{F}_{ω2}$-complete, while termination and boundedness are non-primitive recursive.

Authors: Francesco Di Cosmo, Soumodev Mal, Tephilla Prince

Elementary Object Systems (EOSs) are a model in the nets-within-nets (NWNs) paradigm, where tokens in turn can host standard Petri nets. We study the complexity of coverability-like problems, including termination and boundedness, over EOSs. Since coverability and boundedness are undecidable in general on EOSs, we focus on the relevant fragment of conservative EOSs (cEOSs). Our technique interprets cEOSs into the framework of data nets, whose tokens carry data from an infinite domain, thus bridging the nesting and the data-aware paradigms. Specifically, we show that cEOS coverability-like problems are equivalent to the coverability-like problems over an interesting fragment, called channel-$ν$PNs (c-$ν$PNs), of data nets that extends $ν$PN (featuring globally fresh name creation) with restricted forms of transfers with renaming. c-$ν$PNs remain less expressive than Unordered Data Nets, which feature lossy name creation as well as powerful forms of whole-place operations and broadcasts. These reductions allow us to analyze cEOS coverability taking advantage of known results on data nets. We conclude that the complexity of cEOS coverability is double-Ackermanian, $\mathcal{F}_{ω2}$-complete, while termination and boundedness are non-primitive recursive.

Tuesday, September 01 2026, 00:00

Separating Parsing Expression Grammars using Cell-Probe Lower Bounds

Authors: Jungyeom Kim, Jihyeok Park

We resolve three open problems concerning parsing expression grammars (PEGs). We construct a single language $C$ satisfying $C\in\mathsf{LIN}\cap\mathsf{PEG}$ and $C^R\in\mathsf{LIN}\setminus\mathsf{PEG}$. This proves that some linear context-free language is not a PEG language and that PEG languages are not closed under reversal, confirming a conjecture of Loff, Moreira, and Reis. Factoring the same witness resolves the concatenation-closure problem of Rubtsov and Chudinov negatively, in the strong form $\mathsf{PEG}\cdot\mathsf{REG}\not\subseteq\mathsf{PEG}$ despite $\mathsf{REG}\cdot\mathsf{PEG}\subseteq\mathsf{PEG}$. It also refutes closure under Kleene star, homomorphisms, and substitutions. Our main technique converts scaffolding automata (SCAs), which characterize reversals of PEG languages, into dynamic data structures in the cell-probe model. For any suitably local serialization of a problem with preprocessing, updates, and a final Boolean query, an SCA recognizer yields an exact deterministic cell-probe data structure whose operation costs are proportional to the corresponding encoding lengths. Cell-probe lower bounds can therefore prove SCA non-membership and, by reversal, PEG non-membership. We apply this transfer to Multiphase Inner Product using one-symbol update blocks and a query suffix of length $O(\log n)$, while keeping both the language and its reversal linear context-free. Ko's cell-probe lower bound then yields the witness above. The arguments are additionally formalized in Lean 4.

Authors: Jungyeom Kim, Jihyeok Park

We resolve three open problems concerning parsing expression grammars (PEGs). We construct a single language $C$ satisfying $C\in\mathsf{LIN}\cap\mathsf{PEG}$ and $C^R\in\mathsf{LIN}\setminus\mathsf{PEG}$. This proves that some linear context-free language is not a PEG language and that PEG languages are not closed under reversal, confirming a conjecture of Loff, Moreira, and Reis. Factoring the same witness resolves the concatenation-closure problem of Rubtsov and Chudinov negatively, in the strong form $\mathsf{PEG}\cdot\mathsf{REG}\not\subseteq\mathsf{PEG}$ despite $\mathsf{REG}\cdot\mathsf{PEG}\subseteq\mathsf{PEG}$. It also refutes closure under Kleene star, homomorphisms, and substitutions. Our main technique converts scaffolding automata (SCAs), which characterize reversals of PEG languages, into dynamic data structures in the cell-probe model. For any suitably local serialization of a problem with preprocessing, updates, and a final Boolean query, an SCA recognizer yields an exact deterministic cell-probe data structure whose operation costs are proportional to the corresponding encoding lengths. Cell-probe lower bounds can therefore prove SCA non-membership and, by reversal, PEG non-membership. We apply this transfer to Multiphase Inner Product using one-symbol update blocks and a query suffix of length $O(\log n)$, while keeping both the language and its reversal linear context-free. Ko's cell-probe lower bound then yields the witness above. The arguments are additionally formalized in Lean 4.

Tuesday, September 01 2026, 00:00

It's Hard to PArcK

Authors: Kyle Burke, Jeffrey Leman, Craig Tennenhouse

We show that Partizan Arc Kayles (PArcK), a generalization of Domineering to graphs, is PSPACE-complete via a reduction from Positive CNF and with recently-discovered techniques for creating PArcK positions with high temperature. The reduction uses only red and blue edges.

Authors: Kyle Burke, Jeffrey Leman, Craig Tennenhouse

We show that Partizan Arc Kayles (PArcK), a generalization of Domineering to graphs, is PSPACE-complete via a reduction from Positive CNF and with recently-discovered techniques for creating PArcK positions with high temperature. The reduction uses only red and blue edges.

Tuesday, September 01 2026, 00:00

Algorithmic threshold for high-dimensional projection pursuit I: general theory

Authors: Brice Huang, Mark Sellke, Nike Sun

We study a null model of high-dimensional projection pursuit: we are given $M$ points sampled i.i.d. from a standard gaussian in $N$ dimensions, where $M,N\to\infty$ with $M/N\toα\in(0,\infty)$. Our goal is to characterize the possible empirical distributions of these points' projections along a data-dependent direction $x$, which ranges over either the sphere $S_N=\sqrt{N}\mathbb{S}^{N-1}$ or cube $Σ_N=\{-1,+1\}^N$. We consider this problem in an algorithmic setting, where $x$ must be the output of an algorithm with dimension-free Lipschitz dependence on the input; this class of algorithms includes general gradient-based methods such as Langevin dynamics and approximate message passing (AMP). Our main result exactly characterizes the set of empirical distributions attainable by this class in terms of a one-dimensional stochastic control problem. As a consequence of our main result, we obtain exact algorithmic thresholds for optimizing the Hamiltonian of a spherical or Ising perceptron model with general bounded continuous activation. For the spherical problem, independent work of Montanari and Zhou (2024) characterized the empirical distributions attainable by a related two-stage AMP algorithm, also in terms of stochastic control. Our proof of hardness builds on the branching overlap gap property introduced in earlier work by the first two authors. Our main innovation is to develop stochastic control theory within the branching OGP framework, significantly expanding the settings in which it locates an exact algorithmic threshold. Notably, our methods apply even though the non-algorithmic problem of characterizing all feasible projections remains a major outstanding challenge. For the matching algorithmic result, we construct a new incremental AMP algorithm that acts on a Brownian-bridge revelation of the gaussian disorder and simulates the same family of controlled SDEs.

Authors: Brice Huang, Mark Sellke, Nike Sun

We study a null model of high-dimensional projection pursuit: we are given $M$ points sampled i.i.d. from a standard gaussian in $N$ dimensions, where $M,N\to\infty$ with $M/N\toα\in(0,\infty)$. Our goal is to characterize the possible empirical distributions of these points' projections along a data-dependent direction $x$, which ranges over either the sphere $S_N=\sqrt{N}\mathbb{S}^{N-1}$ or cube $Σ_N=\{-1,+1\}^N$. We consider this problem in an algorithmic setting, where $x$ must be the output of an algorithm with dimension-free Lipschitz dependence on the input; this class of algorithms includes general gradient-based methods such as Langevin dynamics and approximate message passing (AMP). Our main result exactly characterizes the set of empirical distributions attainable by this class in terms of a one-dimensional stochastic control problem. As a consequence of our main result, we obtain exact algorithmic thresholds for optimizing the Hamiltonian of a spherical or Ising perceptron model with general bounded continuous activation. For the spherical problem, independent work of Montanari and Zhou (2024) characterized the empirical distributions attainable by a related two-stage AMP algorithm, also in terms of stochastic control. Our proof of hardness builds on the branching overlap gap property introduced in earlier work by the first two authors. Our main innovation is to develop stochastic control theory within the branching OGP framework, significantly expanding the settings in which it locates an exact algorithmic threshold. Notably, our methods apply even though the non-algorithmic problem of characterizing all feasible projections remains a major outstanding challenge. For the matching algorithmic result, we construct a new incremental AMP algorithm that acts on a Brownian-bridge revelation of the gaussian disorder and simulates the same family of controlled SDEs.

Tuesday, September 01 2026, 00:00

Unconditional $V^0_1$-independence of a certified hitting-set principle

Authors: Martin Kolář

We show that a certified formalization of the hitting-set-existence axiom of Atserias and Tzameret, instantiated on the parity-based Nisan-Wigderson compression class of Khaniki, is independent of the two-sorted theory $V^0_1$ of $\mathrm{AC}^0$-reasoning, unconditionally: $V^0_1$ proves neither it nor its negation. The same holds for the corresponding certified dual weak pigeonhole principle, whose refutation is witnessed by a single seed that certified-computes every string of the model simultaneously. The mechanism is a bounded-arithmetic transfer of Atserias-Tzameret's reduction from hitting sets to the dual weak pigeonhole principle: the amplification half of that reduction, the sole source of its NP-oracle, is unnecessary at the native stretch of the Nisan-Wigderson map, and the compression half becomes a $V^0_1$-provable implication once circuit evaluation is replaced by its certified $Σ^B_0$ unfolding. This is, to our knowledge, the first independence result for a derandomization-flavoured existence principle at the $\mathrm{AC}^0$-reasoning level, and it makes explicit the bridge between the Khaniki Nisan-Wigderson line and the Atserias-Tzameret reverse mathematics of hitting sets.

Authors: Martin Kolář

We show that a certified formalization of the hitting-set-existence axiom of Atserias and Tzameret, instantiated on the parity-based Nisan-Wigderson compression class of Khaniki, is independent of the two-sorted theory $V^0_1$ of $\mathrm{AC}^0$-reasoning, unconditionally: $V^0_1$ proves neither it nor its negation. The same holds for the corresponding certified dual weak pigeonhole principle, whose refutation is witnessed by a single seed that certified-computes every string of the model simultaneously. The mechanism is a bounded-arithmetic transfer of Atserias-Tzameret's reduction from hitting sets to the dual weak pigeonhole principle: the amplification half of that reduction, the sole source of its NP-oracle, is unnecessary at the native stretch of the Nisan-Wigderson map, and the compression half becomes a $V^0_1$-provable implication once circuit evaluation is replaced by its certified $Σ^B_0$ unfolding. This is, to our knowledge, the first independence result for a derandomization-flavoured existence principle at the $\mathrm{AC}^0$-reasoning level, and it makes explicit the bridge between the Khaniki Nisan-Wigderson line and the Atserias-Tzameret reverse mathematics of hitting sets.

Tuesday, September 01 2026, 00:00

Curves of constant width and Lebesgue's covering problem

Authors: Ujjwal Mishra

A universal cover is a convex set in the plane that contains a congruent copy of every planar set of diameter one. Lebesgue asked in 1914 for one of least area, and the value is not known. We prove that every convex universal cover has area at least 0.8344, improving on 0.832, published in 2005, and 0.833, in a 2026 preprint, both of which come from a disc together with an equilateral triangle and a regular pentagon. Our test sets are instead curves of constant width: the disc, the Reuleaux triangle and the Reuleaux pentagon. Each contains the regular polygon it is built on, so the family is strictly larger at the same number of bodies and the same number of placement parameters, and we show that the classical configuration admits an arrangement whose hull has area below 0.8336, so no bound drawn from those three sets by this argument reaches ours. Curves of constant width were proposed for this role, and explored numerically, by Gibbs in 2014; what is added here is a proof. It consists of an analytic reduction followed by one finite computation. The reduction bounds the hull area from below over an entire box of placements at once, by eroding each Reuleaux polygon to a fixed set contained in every placement that box allows. The computation is an exhaustive subdivision of the resulting five-dimensional space, recorded as a certificate of 486,799,600 nodes and checked by a verifier independent of the search, with a rigorous bound on its floating point error some thousands of times smaller than the margin the verification attains.

Authors: Ujjwal Mishra

A universal cover is a convex set in the plane that contains a congruent copy of every planar set of diameter one. Lebesgue asked in 1914 for one of least area, and the value is not known. We prove that every convex universal cover has area at least 0.8344, improving on 0.832, published in 2005, and 0.833, in a 2026 preprint, both of which come from a disc together with an equilateral triangle and a regular pentagon. Our test sets are instead curves of constant width: the disc, the Reuleaux triangle and the Reuleaux pentagon. Each contains the regular polygon it is built on, so the family is strictly larger at the same number of bodies and the same number of placement parameters, and we show that the classical configuration admits an arrangement whose hull has area below 0.8336, so no bound drawn from those three sets by this argument reaches ours. Curves of constant width were proposed for this role, and explored numerically, by Gibbs in 2014; what is added here is a proof. It consists of an analytic reduction followed by one finite computation. The reduction bounds the hull area from below over an entire box of placements at once, by eroding each Reuleaux polygon to a fixed set contained in every placement that box allows. The computation is an exhaustive subdivision of the resulting five-dimensional space, recorded as a certificate of 486,799,600 nodes and checked by a verifier independent of the search, with a rigorous bound on its floating point error some thousands of times smaller than the margin the verification attains.

Tuesday, September 01 2026, 00:00

Proximity3D: Shape from Capacitive Proximity on Sensing Manifold

Authors: Hao Chen, Chenming Wu, Chun Ping Lam, Xiangjia Chen, Guoxin Fang, Charlie C. L. Wang, Yeung Yam, Juncong Lin, Chengkai Dai

Most shape reconstruction methods assume measurements defined over planar sensing domains, such as RGB images or depth maps. In this paper, we use a curved capacitive textile as a shape sensor, treating its surface as a non-planar sensing manifold. Each scan is represented as a capacitive proximity field on this manifold, induced by the interaction between the curved electrode layout and nearby object geometry. We introduce a multi-view feedforward reconstruction model that aggregates these fields across known sensor views and recovers the observed object shape. Simulated and physical experiments demonstrate robust reconstruction from capacitive proximity signals acquired on curved sensing surfaces, pointing toward a new route to robotic near-field geometric awareness via embodied sensing.

Authors: Hao Chen, Chenming Wu, Chun Ping Lam, Xiangjia Chen, Guoxin Fang, Charlie C. L. Wang, Yeung Yam, Juncong Lin, Chengkai Dai

Most shape reconstruction methods assume measurements defined over planar sensing domains, such as RGB images or depth maps. In this paper, we use a curved capacitive textile as a shape sensor, treating its surface as a non-planar sensing manifold. Each scan is represented as a capacitive proximity field on this manifold, induced by the interaction between the curved electrode layout and nearby object geometry. We introduce a multi-view feedforward reconstruction model that aggregates these fields across known sensor views and recovers the observed object shape. Simulated and physical experiments demonstrate robust reconstruction from capacitive proximity signals acquired on curved sensing surfaces, pointing toward a new route to robotic near-field geometric awareness via embodied sensing.

Tuesday, September 01 2026, 00:00

Unfolding Overlaps of the Exceptional Regular Polytopes

Authors: Satyan L. Devadoss, Matthew Harvey, David Richter

We find explicit ridge unfoldings of the three exceptional 4D polytopes (24-cell, 120-cell, 600-cell) that result in overlaps of their facets. These failures bring an end to the full classification of regular polytopes with the all-net property.

Authors: Satyan L. Devadoss, Matthew Harvey, David Richter

We find explicit ridge unfoldings of the three exceptional 4D polytopes (24-cell, 120-cell, 600-cell) that result in overlaps of their facets. These failures bring an end to the full classification of regular polytopes with the all-net property.

Tuesday, September 01 2026, 00:00

A unified geometric design framework for kirigami structures

Authors: Qinghai Jiang, Gary P. T. Choi

In recent years, kirigami metamaterials have been widely studied and applied in science and engineering. While various two- and three-dimensional kirigami design methods have been developed, most of them are only applicable to a limited class of kirigami structures. In this work, we develop a unified framework for kirigami design that encompasses a wide range of 2D-to-2D, 2D-to-3D, and 3D-to-3D shape-morphing effects, as well as additional geometric and physical properties such as compact reconfigurability and rigid deployability. In particular, by reformulating the design task as a length-based constrained optimization problem and solving it simultaneously for multiple target states of the kirigami structure, our unified design framework enables greater design flexibility and stronger theoretical support. Experimental results with a wide range of shape-morphing effects are presented to demonstrate the effectiveness of our framework. We further present a rigorous theoretical analysis of several key aspects of kirigami design, covering inertia transposition, aspect-ratio law, and angle defects, thereby elucidating important design rules and limitations. Altogether, our work paves a new way for the design of shape-morphing mechanical metamaterials.

Authors: Qinghai Jiang, Gary P. T. Choi

In recent years, kirigami metamaterials have been widely studied and applied in science and engineering. While various two- and three-dimensional kirigami design methods have been developed, most of them are only applicable to a limited class of kirigami structures. In this work, we develop a unified framework for kirigami design that encompasses a wide range of 2D-to-2D, 2D-to-3D, and 3D-to-3D shape-morphing effects, as well as additional geometric and physical properties such as compact reconfigurability and rigid deployability. In particular, by reformulating the design task as a length-based constrained optimization problem and solving it simultaneously for multiple target states of the kirigami structure, our unified design framework enables greater design flexibility and stronger theoretical support. Experimental results with a wide range of shape-morphing effects are presented to demonstrate the effectiveness of our framework. We further present a rigorous theoretical analysis of several key aspects of kirigami design, covering inertia transposition, aspect-ratio law, and angle defects, thereby elucidating important design rules and limitations. Altogether, our work paves a new way for the design of shape-morphing mechanical metamaterials.

Tuesday, September 01 2026, 00:00

Combinatorial maps for hierarchical splines

Authors: Caleb B. Goates, Kendrick M. Shepherd, Derek C. Thomas

Hierarchical splines are an important part of multiscale and adaptive isogeometric analysis formulations. The Bézier meshes of these splines are an essential part of their definition and of several important hierarchical spline algorithms, such as adaptive refinement and Bézier extraction. Topological data associated with the Bézier mesh-such as adjacency information-can be used to improve the performance of many of these algorithms as well as downstream applications of the splines, but typical hierarchical spline formulations do not compute the topological data, storing instead just a list of elements. In this work we present algorithms to build a performant topological data structure, namely the combinatorial map, to represent Bézier meshes of hierarchical splines over cubical cell complexes where the refinement levels have conforming Bézier meshes. This includes hierarchical and truncated hierarchical B-splines, as well as subsets of other hierarchical spline formulations. We show the performance characteristics of the construction algorithms of these hierarchical combinatorial maps, as well as an example use case, showing that the topological information can provide up to an order of magnitude reduction in computation time in downstream applications of the splines.

Authors: Caleb B. Goates, Kendrick M. Shepherd, Derek C. Thomas

Hierarchical splines are an important part of multiscale and adaptive isogeometric analysis formulations. The Bézier meshes of these splines are an essential part of their definition and of several important hierarchical spline algorithms, such as adaptive refinement and Bézier extraction. Topological data associated with the Bézier mesh-such as adjacency information-can be used to improve the performance of many of these algorithms as well as downstream applications of the splines, but typical hierarchical spline formulations do not compute the topological data, storing instead just a list of elements. In this work we present algorithms to build a performant topological data structure, namely the combinatorial map, to represent Bézier meshes of hierarchical splines over cubical cell complexes where the refinement levels have conforming Bézier meshes. This includes hierarchical and truncated hierarchical B-splines, as well as subsets of other hierarchical spline formulations. We show the performance characteristics of the construction algorithms of these hierarchical combinatorial maps, as well as an example use case, showing that the topological information can provide up to an order of magnitude reduction in computation time in downstream applications of the splines.

Tuesday, September 01 2026, 00:00

Elastic Triangle Splatting

Authors: Tian Shi, Shenhan Qian, Daniel Cremers

While neural rendering methods such as 3D Gaussian Splatting achieve remarkable visual fidelity, traditional polygonal meshes remain the backbone of established graphics pipelines. Triangle splatting bridges this gap by optimizing triangle primitives as differentiable splats, producing representations that are closer to mesh-based workflows. Central to these methods is the kernel function that softens triangle boundaries to propagate gradients to vertex positions. Existing triangle splatting methods make inconsistent choices of kernel functions, and analysis of these kernels' optimization behavior has been limited to unstructured triangle soups for novel-view synthesis. In this work, we consider triangle splatting as a generic tool for photometric optimization, comparing kernel properties through two complementary tasks: mesh optimization for shape reconstruction and triangle soup optimization for novel-view synthesis. Along with the analysis, we introduce an elastic kernel function that features bilateral gradient support across the boundary and an adaptive boundary value, which are shown to be essential for robust optimization. Under isolated comparison, our elastic kernel outperforms existing kernels on shape reconstruction and in the majority of novel-view synthesis benchmarks, demonstrating the importance of kernel design in the effectiveness and versatility of triangle splatting.

Authors: Tian Shi, Shenhan Qian, Daniel Cremers

While neural rendering methods such as 3D Gaussian Splatting achieve remarkable visual fidelity, traditional polygonal meshes remain the backbone of established graphics pipelines. Triangle splatting bridges this gap by optimizing triangle primitives as differentiable splats, producing representations that are closer to mesh-based workflows. Central to these methods is the kernel function that softens triangle boundaries to propagate gradients to vertex positions. Existing triangle splatting methods make inconsistent choices of kernel functions, and analysis of these kernels' optimization behavior has been limited to unstructured triangle soups for novel-view synthesis. In this work, we consider triangle splatting as a generic tool for photometric optimization, comparing kernel properties through two complementary tasks: mesh optimization for shape reconstruction and triangle soup optimization for novel-view synthesis. Along with the analysis, we introduce an elastic kernel function that features bilateral gradient support across the boundary and an adaptive boundary value, which are shown to be essential for robust optimization. Under isolated comparison, our elastic kernel outperforms existing kernels on shape reconstruction and in the majority of novel-view synthesis benchmarks, demonstrating the importance of kernel design in the effectiveness and versatility of triangle splatting.

Tuesday, September 01 2026, 00:00

Bellman--Shoreline Search in Arbitrary Dimension: Exponential Vector Oscillators, Active Memory, Precession, and Effective Computability

Authors: Florentin Koch

We study online search for an unknown affine hyperplane in $\mathbb{R}^D$, for arbitrary fixed finite dimension. Building on a companion self-similar cell reduction and support-function formulation, we ask how the mechanism changes as the normal space grows from $\mathbb{S}^0$ to $\mathbb{S}^{D-1}$. In $D=1$, alternation and productivity yield an equal-ripple principle and the exact stationary constant $9$. In $D=2$, the analogous relative equilibrium is a logarithmic spiral whose bottleneck chord imposes tangency and selects the pitch. For exponential orbits $Γ(σ)=e^{κσ}ω(σ)$, we develop log-directional geometry, exponentially discounted memory, gauges, and recursive hyperspherical parametrizations. Without a shape ansatz, the bottleneck admits a certificate supported by at most $D$ historical suppliers, and at globally worst phases the current point lies on the active face. Within regular chambers we derive exact variation, tangency, pitch, age, and, in $D=3$, delay-system identities. Odd-dimensional obstructions, antipodal subclasses, and harmonic towers provide constraints and explicit candidate families but are not claimed globally optimal. Finally, the N-COMP theorem shows that $C_D^*$ is a computable real for every fixed finite $D$ and that algebraic polygonal $\varepsilon$-optimal cells can in principle be synthesized. Numerical screening through $D=10$ is kept separate from the proved results.

Authors: Florentin Koch

We study online search for an unknown affine hyperplane in $\mathbb{R}^D$, for arbitrary fixed finite dimension. Building on a companion self-similar cell reduction and support-function formulation, we ask how the mechanism changes as the normal space grows from $\mathbb{S}^0$ to $\mathbb{S}^{D-1}$. In $D=1$, alternation and productivity yield an equal-ripple principle and the exact stationary constant $9$. In $D=2$, the analogous relative equilibrium is a logarithmic spiral whose bottleneck chord imposes tangency and selects the pitch. For exponential orbits $Γ(σ)=e^{κσ}ω(σ)$, we develop log-directional geometry, exponentially discounted memory, gauges, and recursive hyperspherical parametrizations. Without a shape ansatz, the bottleneck admits a certificate supported by at most $D$ historical suppliers, and at globally worst phases the current point lies on the active face. Within regular chambers we derive exact variation, tangency, pitch, age, and, in $D=3$, delay-system identities. Odd-dimensional obstructions, antipodal subclasses, and harmonic towers provide constraints and explicit candidate families but are not claimed globally optimal. Finally, the N-COMP theorem shows that $C_D^*$ is a computable real for every fixed finite $D$ and that algebraic polygonal $\varepsilon$-optimal cells can in principle be synthesized. Numerical screening through $D=10$ is kept separate from the proved results.

Tuesday, September 01 2026, 00:00

Bellman Search in Arbitrary Finite Dimension: A Self-Similar Cell Theorem and Effective Computability of Planar Shoreline Search

Authors: Florentin Koch

A shoreline-search path starts at the origin and must meet an unknown affine line, without knowing either its normal or its distance. We first establish a self-similar reduction theorem for homogeneous search problems whose historical information is a record profile updated by pointwise maximum. Two quasi-returns of the normalized state delimit a block that renews the required profile by itself; a short connector closes this block into a cell. Every finite-ratio path can therefore be approximated, with arbitrarily small loss, by repetitions of a single cell at all scales. The main chain is then made effective. A finite coding of the state space computably bounds the scale factor and normalized length of a nearly optimal cell. For planar Shoreline search, the support function of the convex hull gives an exact cell functional. A one-sided polygonalization then reduces the problem to a computable number of vertices, after which quantifier elimination decides whether a polygonal cell exists below a rational threshold. It follows that the optimal deterministic planar Shoreline value $C_2^*$ is a computable real: for every rational $ε>0$, an algorithm terminates with a rational interval of width at most $ε$ containing $C_2^*$. Additional results---sliding memory, Bellman transitions, deadlines, geometric filters, and relative equilibria---are presented separately as a toolbox for certified computation and for the study of spiral rigidity; they are not used in the computability proof.

Authors: Florentin Koch

A shoreline-search path starts at the origin and must meet an unknown affine line, without knowing either its normal or its distance. We first establish a self-similar reduction theorem for homogeneous search problems whose historical information is a record profile updated by pointwise maximum. Two quasi-returns of the normalized state delimit a block that renews the required profile by itself; a short connector closes this block into a cell. Every finite-ratio path can therefore be approximated, with arbitrarily small loss, by repetitions of a single cell at all scales. The main chain is then made effective. A finite coding of the state space computably bounds the scale factor and normalized length of a nearly optimal cell. For planar Shoreline search, the support function of the convex hull gives an exact cell functional. A one-sided polygonalization then reduces the problem to a computable number of vertices, after which quantifier elimination decides whether a polygonal cell exists below a rational threshold. It follows that the optimal deterministic planar Shoreline value $C_2^*$ is a computable real: for every rational $ε>0$, an algorithm terminates with a rational interval of width at most $ε$ containing $C_2^*$. Additional results---sliding memory, Bellman transitions, deadlines, geometric filters, and relative equilibria---are presented separately as a toolbox for certified computation and for the study of spiral rigidity; they are not used in the computability proof.

Tuesday, September 01 2026, 00:00

The (Parameterized) Complexity of Ordering a Graph While Avoiding a Forbidden Pattern

Authors: Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Martin Nöllenburg, Marie Diana Sieper

In this paper, we study the Pattern Avoidance problem of determining whether a given graph $G$ admits a linear vertex order which avoids a given pattern $P$, i.e., a vertex sequence with some forced and forbidden edges, on every suborder. Such patterns form a natural ordered counterpart to induced subgraphs in the order-invariant setting, and it is known that Pattern Avoidance captures a broad variety of graph problems including Bandwidth, Vertex Coloring, Queue Number, and extends to vertex-deletion problems such as Odd Cycle Transversal. We show that Pattern Avoidance is $Σ_2^{\textsf{P}}$-complete and furthermore remains intractable (in both the classical and parameterized sense) even under a variety of severe restrictions to both the pattern $P$ and the graph $G$. As our main contributions, we complement these lower bounds with the following tractability results, which provide a unifying framework for recognizing pattern-definable graph classes: - a fixed-parameter algorithm w.r.t. the vertex integrity of $G$ plus $|V(P)|$, - a fixed-parameter algorithm w.r.t. the neighborhood diversity of $G$ plus $|E(P)|$, and - a polynomial algorithm for Pattern Avoidance on forests for almost all constant-sized patterns.

Authors: Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Martin Nöllenburg, Marie Diana Sieper

In this paper, we study the Pattern Avoidance problem of determining whether a given graph $G$ admits a linear vertex order which avoids a given pattern $P$, i.e., a vertex sequence with some forced and forbidden edges, on every suborder. Such patterns form a natural ordered counterpart to induced subgraphs in the order-invariant setting, and it is known that Pattern Avoidance captures a broad variety of graph problems including Bandwidth, Vertex Coloring, Queue Number, and extends to vertex-deletion problems such as Odd Cycle Transversal. We show that Pattern Avoidance is $Σ_2^{\textsf{P}}$-complete and furthermore remains intractable (in both the classical and parameterized sense) even under a variety of severe restrictions to both the pattern $P$ and the graph $G$. As our main contributions, we complement these lower bounds with the following tractability results, which provide a unifying framework for recognizing pattern-definable graph classes: - a fixed-parameter algorithm w.r.t. the vertex integrity of $G$ plus $|V(P)|$, - a fixed-parameter algorithm w.r.t. the neighborhood diversity of $G$ plus $|E(P)|$, and - a polynomial algorithm for Pattern Avoidance on forests for almost all constant-sized patterns.

Tuesday, September 01 2026, 00:00

Upper and lower bounds on the OBDD-width of a special integer multiplication

Authors: Tong Qin

We consider the Boolean function ${\rm SMul}_{n-1}^n(\boldsymbol{x},\boldsymbol{y})$, which computes the middle bit of the multiplication of two natural numbers represented as $n$-bit binary strings $\boldsymbol{x}$ and $\boldsymbol{y}$, drawn from a restricted domain. We investigate the width of OBDDs computing ${\rm SMul}_{n-1}^n$. We introduce a combinatorially defined function $s_*(n)$ and show that the width of such OBDDs is $Θ(2^{s_*(n)})$.

Authors: Tong Qin

We consider the Boolean function ${\rm SMul}_{n-1}^n(\boldsymbol{x},\boldsymbol{y})$, which computes the middle bit of the multiplication of two natural numbers represented as $n$-bit binary strings $\boldsymbol{x}$ and $\boldsymbol{y}$, drawn from a restricted domain. We investigate the width of OBDDs computing ${\rm SMul}_{n-1}^n$. We introduce a combinatorially defined function $s_*(n)$ and show that the width of such OBDDs is $Θ(2^{s_*(n)})$.

Tuesday, September 01 2026, 00:00

Unrestricted Boolean Multiplicative Complexity of Four-Term Binary Polynomial Multiplication: Rational Places, Hasse Jets, and the Failure of Nonlinear Feedback

Authors: Gregory Morse

Classical lower bounds show that multiplying two degree-three polynomials over $\mathbb F_2$ requires nine scalar products in bilinear or quadratic models. They do not settle unrestricted Boolean multiplicative complexity: an XOR--AND circuit may reuse nonlinear intermediate wires, and Boolean equality is taken modulo $x_i^2=x_i$, so a multiplication can lower algebraic degree. Let $\operatorname{Mul}_4:\mathbb F_2^8\to\mathbb F_2^7$ output the seven coefficients of the product of two four-term binary polynomials. We prove that its unrestricted XOR--AND multiplicative complexity is exactly nine. This resolves, for a natural vector-valued quadratic function, the Boyar--Find question of whether a quadratic-circuit lower bound can persist against unrestricted nonlinear reuse. The proof is structural rather than exhaustive. A useful purely quadratic prefix is forced onto the three rational places of $\mathbb P^1(\mathbb F_2)$. In a hypothetical eight-AND circuit, the unique non-useful gate must carry a cubic high part. Any useful continuation then forces a rational tangent and exposes a first Hasse jet, while exterior jet separation together with Boolean idempotence prevents the same defect from exposing the second Hasse jet. The required useful suffix therefore cannot exist. A complete Lean 4 formalization verifies the Boolean-ANF semantics, the unrestricted circuit model, and the exact theorem; it uses no project-specific axiom or native decision procedure. The same zero-defect flag argument gives multiplicative complexity six for three-term multiplication, and the method isolates the multi-defect obstruction for five terms.

Authors: Gregory Morse

Classical lower bounds show that multiplying two degree-three polynomials over $\mathbb F_2$ requires nine scalar products in bilinear or quadratic models. They do not settle unrestricted Boolean multiplicative complexity: an XOR--AND circuit may reuse nonlinear intermediate wires, and Boolean equality is taken modulo $x_i^2=x_i$, so a multiplication can lower algebraic degree. Let $\operatorname{Mul}_4:\mathbb F_2^8\to\mathbb F_2^7$ output the seven coefficients of the product of two four-term binary polynomials. We prove that its unrestricted XOR--AND multiplicative complexity is exactly nine. This resolves, for a natural vector-valued quadratic function, the Boyar--Find question of whether a quadratic-circuit lower bound can persist against unrestricted nonlinear reuse. The proof is structural rather than exhaustive. A useful purely quadratic prefix is forced onto the three rational places of $\mathbb P^1(\mathbb F_2)$. In a hypothetical eight-AND circuit, the unique non-useful gate must carry a cubic high part. Any useful continuation then forces a rational tangent and exposes a first Hasse jet, while exterior jet separation together with Boolean idempotence prevents the same defect from exposing the second Hasse jet. The required useful suffix therefore cannot exist. A complete Lean 4 formalization verifies the Boolean-ANF semantics, the unrestricted circuit model, and the exact theorem; it uses no project-specific axiom or native decision procedure. The same zero-defect flag argument gives multiplicative complexity six for three-term multiplication, and the method isolates the multi-defect obstruction for five terms.

Tuesday, September 01 2026, 00:00

Hardness of Approximation of Rank Aggregation on Ulam Metric

Authors: Sk Ruhul Azgor, Diptarka Chakraborty, Le Van Cuong, Debarati Das, Tien Long Nguyen

We study the approximability of rank aggregation under the Ulam metric. In the \emph{Ulam median} problem, the goal is to find a permutation minimizing the sum of its Ulam distances to the input permutations, while in the \emph{Ulam center} problem the objective is to minimize the maximum such distance. Both problems are known to be NP-hard, but no explicit approximation hardness was previously known. We prove that, for every $\varepsilon>0$, it is NP-hard to approximate either Ulam median or Ulam center within a factor of $51/50-\varepsilon$, even when the input consists of only four permutations. We further show that unless P = NP, neither problem admits a polynomial-time additive approximation scheme. The hardness result for Ulam median is established via a reduction from MAX-E3-LIN-2. The corresponding hardness for Ulam center is then obtained through a reduction from Ulam median.

Authors: Sk Ruhul Azgor, Diptarka Chakraborty, Le Van Cuong, Debarati Das, Tien Long Nguyen

We study the approximability of rank aggregation under the Ulam metric. In the \emph{Ulam median} problem, the goal is to find a permutation minimizing the sum of its Ulam distances to the input permutations, while in the \emph{Ulam center} problem the objective is to minimize the maximum such distance. Both problems are known to be NP-hard, but no explicit approximation hardness was previously known. We prove that, for every $\varepsilon>0$, it is NP-hard to approximate either Ulam median or Ulam center within a factor of $51/50-\varepsilon$, even when the input consists of only four permutations. We further show that unless P = NP, neither problem admits a polynomial-time additive approximation scheme. The hardness result for Ulam median is established via a reduction from MAX-E3-LIN-2. The corresponding hardness for Ulam center is then obtained through a reduction from Ulam median.

Tuesday, September 01 2026, 00:00

Parameterized Complexity of Edge-Constrained Graph Partitioning

Authors: Ajinkya Gaikwad, Jan Pokorný, Tomáš Valla

We study the Edge-Constrained Graph Partitioning Problem (ECGP), which asks whether the vertices of a graph can be partitioned into r parts, each inducing at least gamma edges. We also consider a balanced variant (BECGP), requiring equal-sized parts, and signed variants, where the utility of a part is the difference between its numbers of positive and negative edges. We show that ECGP and BECGP remain NP-hard for fixed gamma, while BECGP is also NP-hard for fixed r. For the natural parameterization r+gamma, both problems admit polynomial kernels. We obtain FPT algorithms for ECGP and BECGP parameterized by maximum leaf number, vertex deletion distance to a clique, cluster vertex deletion number plus gamma, and vertex integrity. Furthermore, ECGP is FPT parameterized by vertex deletion distance to stars plus gamma and vertex deletion distance to paths plus gamma. On the negative side, ECGP and BECGP are W[1]-hard when parameterized by r together with several structural parameters. In particular, hardness holds for feedback edge set, vertex deletion distance to stars or paths, and modular width even when the corresponding parameter is zero. The problems are also W[1]-hard parameterized by cluster vertex deletion number plus r, and by clique-width even when gamma=3. For signed graphs, both variants are NP-hard even when r+gamma=3 and the input is a disjoint union of two cliques. Finally, the balanced signed variant is W[1]-hard parameterized by treedepth plus r, even when gamma=0.

Authors: Ajinkya Gaikwad, Jan Pokorný, Tomáš Valla

We study the Edge-Constrained Graph Partitioning Problem (ECGP), which asks whether the vertices of a graph can be partitioned into r parts, each inducing at least gamma edges. We also consider a balanced variant (BECGP), requiring equal-sized parts, and signed variants, where the utility of a part is the difference between its numbers of positive and negative edges. We show that ECGP and BECGP remain NP-hard for fixed gamma, while BECGP is also NP-hard for fixed r. For the natural parameterization r+gamma, both problems admit polynomial kernels. We obtain FPT algorithms for ECGP and BECGP parameterized by maximum leaf number, vertex deletion distance to a clique, cluster vertex deletion number plus gamma, and vertex integrity. Furthermore, ECGP is FPT parameterized by vertex deletion distance to stars plus gamma and vertex deletion distance to paths plus gamma. On the negative side, ECGP and BECGP are W[1]-hard when parameterized by r together with several structural parameters. In particular, hardness holds for feedback edge set, vertex deletion distance to stars or paths, and modular width even when the corresponding parameter is zero. The problems are also W[1]-hard parameterized by cluster vertex deletion number plus r, and by clique-width even when gamma=3. For signed graphs, both variants are NP-hard even when r+gamma=3 and the input is a disjoint union of two cliques. Finally, the balanced signed variant is W[1]-hard parameterized by treedepth plus r, even when gamma=0.

Tuesday, September 01 2026, 00:00

Structural Corrections to the Bethe Approximation of the Permanent

Authors: Ijay Narang, Will Perkins

We study deterministic approximation algorithms for the permanent of a nonnegative matrix through the Bethe permanent, an approximation computable in polynomial time. The tight analysis of Anari and Rezaei gives a universal comparison between the permanent and the Bethe permanent within a factor $(\sqrt 2)^n$. The simple example of the unweighted $4$-cycle $C_4$ (or a union of disjoint $C_4$'s) shows that this bound is tight. We show that such $4$-cycle obstructions can be identified and exploited algorithmically. Given a Bethe optimizer, our algorithm identifies nearly isolated weighted $2\times2$ blocks and peels off a vertex-disjoint family of them. If the total weighted correction is large, we can improve the Bethe approximation; if it is small, we show that the Bethe permanent is within a factor of $(\sqrt2 - \varepsilon)^n$ of the truth. Combining these facts, we obtain a deterministic polynomial time $(\sqrt2-\varepsilon)^n$-approximation algorithm for the permanent of an arbitrary nonnegative $n\times n$ matrix, where $\varepsilon>0$ is some absolute constant.

Authors: Ijay Narang, Will Perkins

We study deterministic approximation algorithms for the permanent of a nonnegative matrix through the Bethe permanent, an approximation computable in polynomial time. The tight analysis of Anari and Rezaei gives a universal comparison between the permanent and the Bethe permanent within a factor $(\sqrt 2)^n$. The simple example of the unweighted $4$-cycle $C_4$ (or a union of disjoint $C_4$'s) shows that this bound is tight. We show that such $4$-cycle obstructions can be identified and exploited algorithmically. Given a Bethe optimizer, our algorithm identifies nearly isolated weighted $2\times2$ blocks and peels off a vertex-disjoint family of them. If the total weighted correction is large, we can improve the Bethe approximation; if it is small, we show that the Bethe permanent is within a factor of $(\sqrt2 - \varepsilon)^n$ of the truth. Combining these facts, we obtain a deterministic polynomial time $(\sqrt2-\varepsilon)^n$-approximation algorithm for the permanent of an arbitrary nonnegative $n\times n$ matrix, where $\varepsilon>0$ is some absolute constant.

Tuesday, September 01 2026, 00:00

Breaking the Exponential Barrier: The First Polynomial-Time Algorithm for the Győri-Lovász Theorem

Authors: Mohammad T. Hajiaghayi, Mahdi JafariRaviz, Alireza Kaviani, Soheil Mohammadkhani

We give the first polynomial-time algorithm, after half a century, for the celebrated Győri-Lovász theorem, which resolved a conjecture of Frank (1975). The theorem, one of the simplest existential theorems to explain, states that every $k$-connected graph can be partitioned into $k$ disjoint connected subgraphs of arbitrary prescribed positive sizes. This is a fundamental structural result with broad applications, such as flexible allocation of connected subnetworks of prescribed sizes in sufficiently connected cloud infrastructures. While Lovász (1977) gave a highly non-constructive proof for a stronger directed version using algebraic topology, Győri's original constructive proof (1976) requires exponential time. Despite more than 50 years of effort, no polynomial-time algorithm was known even for $k>4$. Determining the computational complexity of the Győri-Lovász theorem---whether it admits even a sub-exponential-time algorithm or is computationally hard (in particular, PLS-complete or PPAD)---has remained one of the central open problems in algorithmic graph theory. In this paper, we finally resolve this long-standing problem by a fundamentally new proof of the existential theorem via introducing the novel concept of \emph{flow-essential assignment}, which genuinely marries matching and cut structures and yields the first polynomial-time constructive algorithm for the Győri-Lovász theorem. In fact, we obtain a polynomial-time algorithm for Lovász's stronger directed version, whose proof was non-constructive even for DAGs; for DAGs, we further obtain a near-linear-time algorithm. We also develop polynomial-time algorithms for weighted generalizations where the seminal work of Chen, Kleinberg, Lovász, Rajaraman, Sundaram, and Vetta (JACM'07) on confluent flows established only existential non-constructive results.

Authors: Mohammad T. Hajiaghayi, Mahdi JafariRaviz, Alireza Kaviani, Soheil Mohammadkhani

We give the first polynomial-time algorithm, after half a century, for the celebrated Győri-Lovász theorem, which resolved a conjecture of Frank (1975). The theorem, one of the simplest existential theorems to explain, states that every $k$-connected graph can be partitioned into $k$ disjoint connected subgraphs of arbitrary prescribed positive sizes. This is a fundamental structural result with broad applications, such as flexible allocation of connected subnetworks of prescribed sizes in sufficiently connected cloud infrastructures. While Lovász (1977) gave a highly non-constructive proof for a stronger directed version using algebraic topology, Győri's original constructive proof (1976) requires exponential time. Despite more than 50 years of effort, no polynomial-time algorithm was known even for $k>4$. Determining the computational complexity of the Győri-Lovász theorem---whether it admits even a sub-exponential-time algorithm or is computationally hard (in particular, PLS-complete or PPAD)---has remained one of the central open problems in algorithmic graph theory. In this paper, we finally resolve this long-standing problem by a fundamentally new proof of the existential theorem via introducing the novel concept of \emph{flow-essential assignment}, which genuinely marries matching and cut structures and yields the first polynomial-time constructive algorithm for the Győri-Lovász theorem. In fact, we obtain a polynomial-time algorithm for Lovász's stronger directed version, whose proof was non-constructive even for DAGs; for DAGs, we further obtain a near-linear-time algorithm. We also develop polynomial-time algorithms for weighted generalizations where the seminal work of Chen, Kleinberg, Lovász, Rajaraman, Sundaram, and Vetta (JACM'07) on confluent flows established only existential non-constructive results.

Tuesday, September 01 2026, 00:00

Test or Run? Scheduling Jobs of Unknown Length

Authors: Václav Rozhoň

A machine faces many jobs whose lengths are hidden. Spending one unit of time to inspect a job may reveal a short job that should be finished now, or it may reveal nothing useful while every other job waits. When should the machine keep looking, and when should it start working? We study natural variants of this question and provide optimal algorithms in both the worst-case and instance-optimal frameworks. The resulting algorithms are often quite simple, which may make them useful in practice.

Authors: Václav Rozhoň

A machine faces many jobs whose lengths are hidden. Spending one unit of time to inspect a job may reveal a short job that should be finished now, or it may reveal nothing useful while every other job waits. When should the machine keep looking, and when should it start working? We study natural variants of this question and provide optimal algorithms in both the worst-case and instance-optimal frameworks. The resulting algorithms are often quite simple, which may make them useful in practice.

Tuesday, September 01 2026, 00:00

The Cayley Completion of a Graph

Authors: Rigobert Fokam Souop, Laurent Bitjoka

A finite connected graph is rarely a Cayley graph. We measure how far it is from being one: given $G$ with $n$ vertices and $m$ edges, how few edges must be added, or added and deleted, before the result is a Cayley graph of an abelian group of order $n$ on the same vertex set? This defines two invariants, the completion number $γ^{+}$ (additions only) and the Cayley edit distance $γ_{\triangle}$ (both), each normalized by $m$. We show that deciding the edit version is NP-complete already for a fixed cyclic host, by a reduction from Hamiltonian Cycle in which the edit cost of a labeling is $n+m-2k$ when it realizes a longest path with $k$ edges; the optimal cost is $m-n+2pp(G)$, bounded in polynomial time by the matching number. We prove that irregularity alone forces $γ^{+}(G)\ge nΔ^{*}/(2m)-1$, where $Δ^{*}$ is the least $d\geΔ$ with $nd$ even, computable in linear time from the degree sequence; we characterize equality exactly. It is attained on the star, where $γ^{+}(K_{1,q})=(q-1)/2$ and the star maximizes $γ^{+}$, while $γ_{\triangle}$ stays bounded by an absolute constant. We determine paths and grids exactly, $γ^{+}(P_n)=γ^{+}(P_n\,\square\,P_n)=1/(n-1)$, and show $γ_{\triangle}(K_{1,q})\to 2$, not the $3/2$ suggested by the additive case. We report an exhaustive certified census of all $995$ connected graphs on at most seven vertices. The degree bound is attained on $89.4\%$ and the two invariants separate strictly on $84.7\%$, though both rates vary sharply with order: attainment $100\%,100\%,84.8\%,89.7\%$ and separation $0\%,61.9\%,73.2\%,87.7\%$ for $n=4,5,6,7$, dominated by the $853$ graphs on seven vertices. The star uniquely maximizes both. Edit count and the bi-Lipschitz distortion of the completed host are independent, moving oppositely on stars and paths.Data and certificates at doi:10.5281/zenodo.21852006.

Authors: Rigobert Fokam Souop, Laurent Bitjoka

A finite connected graph is rarely a Cayley graph. We measure how far it is from being one: given $G$ with $n$ vertices and $m$ edges, how few edges must be added, or added and deleted, before the result is a Cayley graph of an abelian group of order $n$ on the same vertex set? This defines two invariants, the completion number $γ^{+}$ (additions only) and the Cayley edit distance $γ_{\triangle}$ (both), each normalized by $m$. We show that deciding the edit version is NP-complete already for a fixed cyclic host, by a reduction from Hamiltonian Cycle in which the edit cost of a labeling is $n+m-2k$ when it realizes a longest path with $k$ edges; the optimal cost is $m-n+2pp(G)$, bounded in polynomial time by the matching number. We prove that irregularity alone forces $γ^{+}(G)\ge nΔ^{*}/(2m)-1$, where $Δ^{*}$ is the least $d\geΔ$ with $nd$ even, computable in linear time from the degree sequence; we characterize equality exactly. It is attained on the star, where $γ^{+}(K_{1,q})=(q-1)/2$ and the star maximizes $γ^{+}$, while $γ_{\triangle}$ stays bounded by an absolute constant. We determine paths and grids exactly, $γ^{+}(P_n)=γ^{+}(P_n\,\square\,P_n)=1/(n-1)$, and show $γ_{\triangle}(K_{1,q})\to 2$, not the $3/2$ suggested by the additive case. We report an exhaustive certified census of all $995$ connected graphs on at most seven vertices. The degree bound is attained on $89.4\%$ and the two invariants separate strictly on $84.7\%$, though both rates vary sharply with order: attainment $100\%,100\%,84.8\%,89.7\%$ and separation $0\%,61.9\%,73.2\%,87.7\%$ for $n=4,5,6,7$, dominated by the $853$ graphs on seven vertices. The star uniquely maximizes both. Edit count and the bi-Lipschitz distortion of the completed host are independent, moving oppositely on stars and paths.Data and certificates at doi:10.5281/zenodo.21852006.

Tuesday, September 01 2026, 00:00

On the maximum weight convex problem for some geometric graph-convexities

Authors: Fariza Aklouche, Pierre Bergé, Michel Habib

For a given geometric graph-convexity on a graph $G$ equipped with a weight function on the vertices with value in $\mathbb{Z}$, the Max Weight Convex Set problem consists in determining the convex set $S$ with maximum weight (sum of the weight of the vertices in $S$). Although the problem is NP-complete in general, it remains polynomial for particular cases. After a survey of known results, our main contribution uses a generalisation of the maximum subsequence problem to laminar trees. Then we derive a linear algorithm for proper interval graphs and a quadratic one for interval graphs. Both improve the state of the art.

Authors: Fariza Aklouche, Pierre Bergé, Michel Habib

For a given geometric graph-convexity on a graph $G$ equipped with a weight function on the vertices with value in $\mathbb{Z}$, the Max Weight Convex Set problem consists in determining the convex set $S$ with maximum weight (sum of the weight of the vertices in $S$). Although the problem is NP-complete in general, it remains polynomial for particular cases. After a survey of known results, our main contribution uses a generalisation of the maximum subsequence problem to laminar trees. Then we derive a linear algorithm for proper interval graphs and a quadratic one for interval graphs. Both improve the state of the art.

Tuesday, September 01 2026, 00:00

Gate-Efficient Implementation of the Query-Optimal Time-Dependent Hamiltonian Simulation

Authors: Boyang Chen, Minbo Gao, Zhengfeng Ji, Tongyang Li, Xinzhao Wang, Shuo Zhou

The query-optimal algorithm of [CGWZ26] for general time-dependent Hamiltonian simulation uses $$ q = O\left( αT + \frac{\log(1/\varepsilon)}{\log\left(e + \log(1/\varepsilon)/(αT) \right)} \right) $$ queries to $\mathrm{HAM\mbox{-}T}$ within $\varepsilon$ error for a Lipschitz-continuous time-dependent Hamiltonian $H(t)$ on $[0,T]$ satisfying $\left\lVert H(t)\right\rVert\leqα$. However, its direct circuit implementation incurs a substantially larger gate overhead. In this note, we give an implementation of the same algorithm that retains its optimal query complexity and uses $$ O\left[ q \left( a + \log\left(1 + \frac{T(α+ βT)}{\varepsilon} \right) \right) \right] $$ one- and two-qubit gates, where $a$ is the number of block-encoding ancilla qubits and $β$ is the Lipschitz constant of $H$. The main ingredient is an exact dyadic factorization of the ordered update product in the underlying one-query transducer.

Authors: Boyang Chen, Minbo Gao, Zhengfeng Ji, Tongyang Li, Xinzhao Wang, Shuo Zhou

The query-optimal algorithm of [CGWZ26] for general time-dependent Hamiltonian simulation uses $$ q = O\left( αT + \frac{\log(1/\varepsilon)}{\log\left(e + \log(1/\varepsilon)/(αT) \right)} \right) $$ queries to $\mathrm{HAM\mbox{-}T}$ within $\varepsilon$ error for a Lipschitz-continuous time-dependent Hamiltonian $H(t)$ on $[0,T]$ satisfying $\left\lVert H(t)\right\rVert\leqα$. However, its direct circuit implementation incurs a substantially larger gate overhead. In this note, we give an implementation of the same algorithm that retains its optimal query complexity and uses $$ O\left[ q \left( a + \log\left(1 + \frac{T(α+ βT)}{\varepsilon} \right) \right) \right] $$ one- and two-qubit gates, where $a$ is the number of block-encoding ancilla qubits and $β$ is the Lipschitz constant of $H$. The main ingredient is an exact dyadic factorization of the ordered update product in the underlying one-query transducer.

Tuesday, September 01 2026, 00:00

Beating Quadratic Time--Message Trade-off in Distributed Minimum Spanning Tree Construction

Authors: Taisuke Izumi, Naoki Kitamura, Toshimitsu Masuzawa

We present a new distributed algorithm for computing a minimum spanning tree (MST) in the \textsf{CONGEST-KT$_{1}$} model, where messages are limited to $O(\log n)$ bits and each vertex initially knows the identifiers of its neighbors. Our algorithm exposes a two-parameter time--message trade-off: for any $0 \leq λ\leq κ\leq 1/2$, it runs in $\tilde{O}(n^λD_G + n^{1 - κ- λ} + n^{1 - 2κ+ λ} + n^{1/2})$ rounds and uses $\tilde{O}(\min\{m, n^{1 + κ}\})$ messages, where $n$, $m$, and $D_G$ are the number of vertices, edges, and thenetwork diameter, respectively. In particular, setting $(κ, λ) = (1/3, 1/6)$ yields an MST algorithm running in $\tilde{O}(n^{1/2} + n^{1/6}D_G)$ rounds with only $\tilde{O}(n^{4/3})$ messages. Under the mild assumption $D_G = O(n^{1/3})$, this is round-optimal while improving the best known message bound of $\tilde{O}(n^{3/2})$. More broadly, our algorithm breaks the quadratic time--message trade-off barrier $\mathrm{\# rounds} \cdot \mathrm{\# messages} = \tildeΩ(n^2)$, which no previous MST algorithm in the \textsf{CONGEST-KT$_{1}$} model has been able to overcome, and it does so for almost the entire range of the diameter $D_G$. As a byproduct, we also obtain new low-message broadcast, spanning-tree, and leader-election algorithms.

Authors: Taisuke Izumi, Naoki Kitamura, Toshimitsu Masuzawa

We present a new distributed algorithm for computing a minimum spanning tree (MST) in the \textsf{CONGEST-KT$_{1}$} model, where messages are limited to $O(\log n)$ bits and each vertex initially knows the identifiers of its neighbors. Our algorithm exposes a two-parameter time--message trade-off: for any $0 \leq λ\leq κ\leq 1/2$, it runs in $\tilde{O}(n^λD_G + n^{1 - κ- λ} + n^{1 - 2κ+ λ} + n^{1/2})$ rounds and uses $\tilde{O}(\min\{m, n^{1 + κ}\})$ messages, where $n$, $m$, and $D_G$ are the number of vertices, edges, and thenetwork diameter, respectively. In particular, setting $(κ, λ) = (1/3, 1/6)$ yields an MST algorithm running in $\tilde{O}(n^{1/2} + n^{1/6}D_G)$ rounds with only $\tilde{O}(n^{4/3})$ messages. Under the mild assumption $D_G = O(n^{1/3})$, this is round-optimal while improving the best known message bound of $\tilde{O}(n^{3/2})$. More broadly, our algorithm breaks the quadratic time--message trade-off barrier $\mathrm{\# rounds} \cdot \mathrm{\# messages} = \tildeΩ(n^2)$, which no previous MST algorithm in the \textsf{CONGEST-KT$_{1}$} model has been able to overcome, and it does so for almost the entire range of the diameter $D_G$. As a byproduct, we also obtain new low-message broadcast, spanning-tree, and leader-election algorithms.

Tuesday, September 01 2026, 00:00

Socially Fair Clustering: Parameterized Approximation and Local Search

Authors: Aditya Anand, Yury Makarychev, Liren Shan

We study the Socially Fair Clustering problem introduced by Abbasi, Bhaskara, and Venkatasubramanian (2021) and Ghadiri, Samadi, and Vempala (2021), along with its extension, the $(p,q)$-Socially Fair Clustering problem. This problem generalizes $k$-medians and $k$-means to settings where data points are partitioned into $\ell$ groups, and the goal is to find a fair clustering that is simultaneously good for all groups. We present several algorithms for this problem. For $\ell_p$-Socially Fair Clustering, we give the first constant-factor FPT-approximation parameterized by the number of groups $\ell$, resolving the open question raised by Ghadiri, Singh, and Vempala (2022). Our main ingredient is a new algorithm for closing additional centers in parameterized time inspired by local search. We then turn to the more general $(p,q)$-Socially Fair Clustering problem. The known algorithm for this problem, proposed by Chlamtáč, Makarychev, and Vakilian (2022) achieves a very good approximation but is complex, slow and difficult to implement. We analyze the performance of a simple local search algorithm and show that it provides an $O(q)$ approximation in the worst case. Finally, we design approximation algorithms for the facility location variant of the problem, where the number of facilities (centers) is not fixed in advance, and opening each facility incurs an opening cost. Unlike in previous work, we do not assume these opening costs are the same for all groups.

Authors: Aditya Anand, Yury Makarychev, Liren Shan

We study the Socially Fair Clustering problem introduced by Abbasi, Bhaskara, and Venkatasubramanian (2021) and Ghadiri, Samadi, and Vempala (2021), along with its extension, the $(p,q)$-Socially Fair Clustering problem. This problem generalizes $k$-medians and $k$-means to settings where data points are partitioned into $\ell$ groups, and the goal is to find a fair clustering that is simultaneously good for all groups. We present several algorithms for this problem. For $\ell_p$-Socially Fair Clustering, we give the first constant-factor FPT-approximation parameterized by the number of groups $\ell$, resolving the open question raised by Ghadiri, Singh, and Vempala (2022). Our main ingredient is a new algorithm for closing additional centers in parameterized time inspired by local search. We then turn to the more general $(p,q)$-Socially Fair Clustering problem. The known algorithm for this problem, proposed by Chlamtáč, Makarychev, and Vakilian (2022) achieves a very good approximation but is complex, slow and difficult to implement. We analyze the performance of a simple local search algorithm and show that it provides an $O(q)$ approximation in the worst case. Finally, we design approximation algorithms for the facility location variant of the problem, where the number of facilities (centers) is not fixed in advance, and opening each facility incurs an opening cost. Unlike in previous work, we do not assume these opening costs are the same for all groups.

Tuesday, September 01 2026, 00:00

FirstFit online coloring in the random order model

Authors: Xinyu Ye, Yuechuan Xu, Zixuan Wang, Jiaying Zheng, Yaqiao Li

The average performance of FirstFit online coloring on trees in the random order model is completely determined in recent works of Frei et al. and Bosek et al., showing $Θ(\log n /\log\log n)$ number of colors, improving the $Θ(\log n)$ colors in the adversarial model. We provide a few further results on slightly more general graph classes. Firstly, we extend their method to obtain a simple path-counting principle for sparse graph classes, which immediately yields for example that cactus graphs and uniform hypertrees exhibit a similar improvement. We then show that FirstFit uses only $O(1)$ colors on crown graphs, a standard example where adversarial arrival forces $Θ(n)$ colors. We further show that density alone (even linear minimum degree) is insufficient to guarantee $O(1)$ colors even on bipartite graphs. Finally, we identify graph classes, including unit interval graphs and some graphs of high chromatic number, for which random arrival provides only limited improvement. We end with some open problems.

Authors: Xinyu Ye, Yuechuan Xu, Zixuan Wang, Jiaying Zheng, Yaqiao Li

The average performance of FirstFit online coloring on trees in the random order model is completely determined in recent works of Frei et al. and Bosek et al., showing $Θ(\log n /\log\log n)$ number of colors, improving the $Θ(\log n)$ colors in the adversarial model. We provide a few further results on slightly more general graph classes. Firstly, we extend their method to obtain a simple path-counting principle for sparse graph classes, which immediately yields for example that cactus graphs and uniform hypertrees exhibit a similar improvement. We then show that FirstFit uses only $O(1)$ colors on crown graphs, a standard example where adversarial arrival forces $Θ(n)$ colors. We further show that density alone (even linear minimum degree) is insufficient to guarantee $O(1)$ colors even on bipartite graphs. Finally, we identify graph classes, including unit interval graphs and some graphs of high chromatic number, for which random arrival provides only limited improvement. We end with some open problems.

Tuesday, September 01 2026, 00:00

Adversarial Online Classification with a Preview

Authors: Roi Livni, Sahil Singla

Worst-case online classification is governed by sequential complexity, such as Littlestone dimension, and can be impossible even for statistically simple classes, such as thresholds of VC dimension one. We study a preview model in which an oblivious adversary fixes an entire labeled sequence of length $T$, a uniformly random subset of size $pT$ is revealed before prediction begins, and the remaining $(1-p)T$ examples are then presented in their original adversarial order. Against the best full-sequence hypothesis evaluated on the unrevealed examples, we characterize the dependence on the preview rate $p$: for binary classes of VC dimension $d$, the optimal excess loss is $Θ(d/p+\sqrt{dT})$, up to the trivial cap at $T$; for multiclass classes we obtain the corresponding $\widetilde O(d_{\rm DS}/p+\sqrt{d_{\rm Nat}T})$ bound with no dependence on the number of labels. Thus a random preview can replace worst-case sequential complexity by classical statistical dimensions without randomizing the online order. To achieve the sharp binary bound, our ChainedPrediction algorithm uses an online analogue of chaining, implemented as a multiscale aggregation algorithm rather than only as an analytic argument.

Authors: Roi Livni, Sahil Singla

Worst-case online classification is governed by sequential complexity, such as Littlestone dimension, and can be impossible even for statistically simple classes, such as thresholds of VC dimension one. We study a preview model in which an oblivious adversary fixes an entire labeled sequence of length $T$, a uniformly random subset of size $pT$ is revealed before prediction begins, and the remaining $(1-p)T$ examples are then presented in their original adversarial order. Against the best full-sequence hypothesis evaluated on the unrevealed examples, we characterize the dependence on the preview rate $p$: for binary classes of VC dimension $d$, the optimal excess loss is $Θ(d/p+\sqrt{dT})$, up to the trivial cap at $T$; for multiclass classes we obtain the corresponding $\widetilde O(d_{\rm DS}/p+\sqrt{d_{\rm Nat}T})$ bound with no dependence on the number of labels. Thus a random preview can replace worst-case sequential complexity by classical statistical dimensions without randomizing the online order. To achieve the sharp binary bound, our ChainedPrediction algorithm uses an online analogue of chaining, implemented as a multiscale aggregation algorithm rather than only as an analytic argument.

Tuesday, September 01 2026, 00:00

Scheduling to Maximize Weighted Throughput with an Active-Time Budget

Authors: Susanne Albers, G. Wessel van der Heijden

We study the active-time scheduling problem with weighted throughput maximization. In this setting, a set of $n$ jobs $J$ arrive at integer release times, each with an integer processing time and integer deadline. Jobs may be preempted at integer time slot boundaries. A schedule assigns jobs to time slots, with at most $m$ jobs assigned to the same time slot. A slot is called \emph{active} if at least one job is scheduled in it. Instead of scheduling all jobs to minimize the number of active time slots, we consider the more general variant of \emph{weighted throughput} with an active-time budget $K$, where each job $j\in J$ has a weight $w_j$. The objective is to maximize the total weight of \emph{completed} jobs using at most $K$ active time slots. This means that partially scheduled jobs do not count towards the objective. The classical active-time minimization problem is recovered by asking whether all jobs can be completed within a given active-time budget. We give hardness, approximation, and exact algorithmic results. For general intervals with unbounded parallelism, we prove NP-hardness, rule out an FPTAS unless $\mathrm{P}=\mathrm{NP}$, and give a pseudo-polynomial time $Ω(1/\log K)$-approximation. For proper intervals, we prove a canonical structural lemma and obtain an exact $(nK)^{O(m)}$-time algorithm. For laminar intervals, we give an exact $f(K,m)\cdot n^{O(1)}$-time algorithm.

Authors: Susanne Albers, G. Wessel van der Heijden

We study the active-time scheduling problem with weighted throughput maximization. In this setting, a set of $n$ jobs $J$ arrive at integer release times, each with an integer processing time and integer deadline. Jobs may be preempted at integer time slot boundaries. A schedule assigns jobs to time slots, with at most $m$ jobs assigned to the same time slot. A slot is called \emph{active} if at least one job is scheduled in it. Instead of scheduling all jobs to minimize the number of active time slots, we consider the more general variant of \emph{weighted throughput} with an active-time budget $K$, where each job $j\in J$ has a weight $w_j$. The objective is to maximize the total weight of \emph{completed} jobs using at most $K$ active time slots. This means that partially scheduled jobs do not count towards the objective. The classical active-time minimization problem is recovered by asking whether all jobs can be completed within a given active-time budget. We give hardness, approximation, and exact algorithmic results. For general intervals with unbounded parallelism, we prove NP-hardness, rule out an FPTAS unless $\mathrm{P}=\mathrm{NP}$, and give a pseudo-polynomial time $Ω(1/\log K)$-approximation. For proper intervals, we prove a canonical structural lemma and obtain an exact $(nK)^{O(m)}$-time algorithm. For laminar intervals, we give an exact $f(K,m)\cdot n^{O(1)}$-time algorithm.

Tuesday, September 01 2026, 00:00

A Simplified Analysis of the Good-Bad $3/2$-Approximation Algorithm for Some Minimum-Cost Graph Problems

Authors: Shayan Ranjbarzadeh, David P. Williamson, Hannane Yaghoubizade

In this paper, we consider an easy greedy approximation algorithm, the good-bad algorithm, introduced by Couëtoux for finding a minimum-cost set of edges such that every connected component has at least $k$ vertices. Couëtoux proves that the good-bad algorithm achieves a $3/2$-approximation for this problem. Davis and Williamson extend this result to the more general problem of finding a minimum-cost edge set that contains at least one edge from every cut $S\subseteq V$ satisfying $h(S) = 1$ where $h:2^V \rightarrow \{0,1\}$ is downward monotone; that is, $h(S) = 1$ implies $h(T) = 1$ for every nonempty subset $T \subseteq S$. The original problem corresponds to $h(S) =1$ when $|S|

Authors: Shayan Ranjbarzadeh, David P. Williamson, Hannane Yaghoubizade

In this paper, we consider an easy greedy approximation algorithm, the good-bad algorithm, introduced by Couëtoux for finding a minimum-cost set of edges such that every connected component has at least $k$ vertices. Couëtoux proves that the good-bad algorithm achieves a $3/2$-approximation for this problem. Davis and Williamson extend this result to the more general problem of finding a minimum-cost edge set that contains at least one edge from every cut $S\subseteq V$ satisfying $h(S) = 1$ where $h:2^V \rightarrow \{0,1\}$ is downward monotone; that is, $h(S) = 1$ implies $h(T) = 1$ for every nonempty subset $T \subseteq S$. The original problem corresponds to $h(S) =1$ when $|S|

Tuesday, September 01 2026, 00:00

Parameterized Complexity of Connected Network Microaggregation: The Role of Cluster Size

Authors: Ajinkya Gaikwad, Dušan Knop, Tomáš Valla

Network microaggregation is a fundamental technique in statistical disclosure control, where vertices of a graph are partitioned into clusters satisfying size constraints and admitting a center within bounded distance. We study the parameterized complexity of the \emph{unweighted Connected Network Microaggregation} problem, focusing on structural parameters and natural clustering parameters such as the distance bound $d$ and cluster size gap $u-\ell$. We show that, unlike the weighted variant, the unweighted connected problem is fixed-parameter tractable when parameterized by neighborhood diversity, and hence by vertex cover. In contrast, it remains $\mathrm{W[1]}$-hard for more general structural parameters, including vertex deletion to paths, stars, and cliques. These hardness results hold even for every $d\ge 2$ and any fixed gap $u-\ell$, showing that these clustering parameters do not overcome the structural hardness. We further show that adding the cluster size bound $u$ restores tractability for structural parameters such as treewidth and cluster vertex deletion. Moreover, $u$ is essential: the problem remains $\mathrm{W[1]}$-hard when these structural parameters are considered alone. For kernelization, we prove that the problem has no polynomial kernel parameterized by vertex cover unless $\mathrm{coNP}\subseteq\mathrm{NP/poly}$, even when the distance constraint is vacuous. Adding $u$ yields a polynomial kernel for vertex cover, while kernelization remains unlikely for more general structural parameters even when combined with $u$. Finally, we show that the problem is NP-hard on graphs of bounded clique-width.

Authors: Ajinkya Gaikwad, Dušan Knop, Tomáš Valla

Network microaggregation is a fundamental technique in statistical disclosure control, where vertices of a graph are partitioned into clusters satisfying size constraints and admitting a center within bounded distance. We study the parameterized complexity of the \emph{unweighted Connected Network Microaggregation} problem, focusing on structural parameters and natural clustering parameters such as the distance bound $d$ and cluster size gap $u-\ell$. We show that, unlike the weighted variant, the unweighted connected problem is fixed-parameter tractable when parameterized by neighborhood diversity, and hence by vertex cover. In contrast, it remains $\mathrm{W[1]}$-hard for more general structural parameters, including vertex deletion to paths, stars, and cliques. These hardness results hold even for every $d\ge 2$ and any fixed gap $u-\ell$, showing that these clustering parameters do not overcome the structural hardness. We further show that adding the cluster size bound $u$ restores tractability for structural parameters such as treewidth and cluster vertex deletion. Moreover, $u$ is essential: the problem remains $\mathrm{W[1]}$-hard when these structural parameters are considered alone. For kernelization, we prove that the problem has no polynomial kernel parameterized by vertex cover unless $\mathrm{coNP}\subseteq\mathrm{NP/poly}$, even when the distance constraint is vacuous. Adding $u$ yields a polynomial kernel for vertex cover, while kernelization remains unlikely for more general structural parameters even when combined with $u$. Finally, we show that the problem is NP-hard on graphs of bounded clique-width.

Tuesday, September 01 2026, 00:00

Games Done Quick

from Sophie Huiberts

I was at GDQ. Some reflections.

Speedrunning is when you play a videogame as fast as possible. It's a hobby where you get to spend countless hours making small improvements to your results, develop jargon unparseable to outside observers, and become an expert recognized by your community of (a few dozen) peers. In other words, it is a lot like academia.

Speedrunning is even more like computer science academia. Speedrunners optimize, they solve traveling salesperson problems, and they are perhaps the only part of civil society interested in computing lower bounds. What's more, is that speedrunning too has a sort of conference system.

This weekend I got to perform at Games Done Quick (GDQ), perhaps the world's biggest stage for playing videogames fast. It is every speedrunner's dream to be on that stage.

Just like an academic conference, you can submit your best work, and a program committee will decide which submissions will be included in the event. This year GDQ had its event in Europe, at Gamescom in Cologne Germany. Because of that proximity, I submitted a run together with my friend Chelsea. Our submission was a run of Hades II (Supergiant Games, 2025) in the Fresh File category. As an extra hurdle, we played this single player game with two players on one controller (2P1C). I press most of the buttons, Chelsea does everything else including movement and aiming.

I was more nervous about this submissions than any paper I ever submitted, but we got accepted! What's more, our run was being highlighted in the Gamescom promotional emails.

Screenshot from Gamescom 2026 promo email advertising their hosting a special edition of GDQ. Out of all accepted submissions, 4 are mentioned in the email (in order): Hades II (thats us), TLOZ:OOT Any% (Defeat Ganon) Blindfolded, Grand Poo World 3 Any% Race, and Pokemon Red/Blue Reverse Badge Order.

Unlike an academic conference, your performance at the event is the only part that counts. And unlike in practice, you only get 1 shot at it. After the notification came in early June, we had just 3 months to prepare. Chelsea and I live in different countries, so finding practice time was an undertaking. However we are an experienced duo, having 2P1C runs on the official leaderboards in 4 different categories^[1]^[2]^[3]^[4].

To give the best possible show, we prepared a host of things. We procured two mods for the game: one to respawn us in place if we died (its a difficult game but the show must go on), and a second one to rig the first crucial coin flip in our favor. Besides that, we strategized lots. Which boons do we want to see, and which ones should we exclude because of their added unpredictability and cognitive load? Which flashy strategies can we try to show off, and where do we need to prepare dedicated safe strategies instead? Hades II is a roguelike game, which means that randomness can make or break your day. We needed to have a plan for every eventuality.

Sophie (left) and Chelsea (right) are excited that GDQ is about to start in 7 minutes and 30 seconds. The room is still quite empty, a lot of chairs are free. Sophie and Chelsea are posing in a way that references animal advocate John Oberg's famous photo with KFC's Beyond Meat chicken.

Last week was Gamescom, with GDQ taking place friday through sunday. GDQ gave us runners free tickets for all three days. Chelsea and I would play on sunday, so we had two days to simply watch and experience the event. Gamescom itself, I did not care for. It is unbelievably crowded, not a good time. But attending GDQ in-person (instead of through the usual live stream) was a joy. When you're there in the audience, everything hits that much more. The clutch moves are that much more exciting. The funny bits are that much funnier. (And to be honest, seeing that the other runs didn't always go perfectly did a lot to soothe our nerves about our own run.)

Chelsea and Sophie pose with a Melinoe cosplayer. Melineo is the main character in Hades II. Chelsea wears a shirt that says "Chelsea plays left hand" with the outline of the left side of a Playstation controller. Sophie wears a matching tshirt saying "Sophie players right hand".

Just like an academic conference, meeting the people in your community makes everything more fun.

On sunday it was our turn. After Donkey Kong Country and Skylar & Plux, before Silksong and OOT Blindfolded. The GDQ staff was amazing, they are a well-oiled operation handling all the complexities of audio, video, computers, German internet connections and livestreaming. After we were in place with all the setup, it was time to play. The game had it out for us, but Chelsea and I were able to put on a good show with the help of our commentator Dr Omega. Check out our show in the embed below or at this link.

I am super grateful to Chelsea for playing with me and being such a good friend, to GDQ for coming to Europe and for the opportunity to have a dream come true, and to Dr Omega for the stellar commentary.

[1]	Hades 1 Fresh File

[2]	Hades 1 Loyalty Card (Routed)

[3]	Hades 2 Fresh File (early access patch 3)

[4]	Hades 2 Fresh File (release version)

Tuesday, September 01 2026, 00:00

Linkage with two research problems

from David Eppstein

In case you’ve been worrying that the recent publicity blitz of LLM solutions to open mathematics problems is causing us to run short, there are two more mixed in among my usual links here. Because I haven’t solved them, they are not very precisely formulated, and I don’t know how difficult or interesting they are nor even whether someone else might have already considered them; that’s often the way at the start of research.

I think maybe I need to start bringing my DSLR along again when I go to the beach ($\mathbb{M}$) rather than relying on my cell phone camera (Pixel 6 Pro, yes I know it’s getting old now). Here’s what it thinks a crashing wave looks like, without additional processing except for a bit of a crop. To me it more resembles the kind of molded privacy glass that one uses for a bathroom window.
Amazon buys rare books to destructively scan them for AI training ($\mathbb{M}$).
An abbreviation of abbreviation, misspelling of misspelling, and more of the kind from the depths of Wiktionary.
Rotating points on four circles form a polygon of constant length by Jim Propp, inspired by Chuck Hoberman’s “Nested Loops” exhibit at the Museum of Mathematics.
A cursed triangle in the Moulton plane.
If you’ve been working with tagged pdf files in Adobe Acrobat ($\mathbb{M}$), you may have noticed an annoying banner that it displays at the top of the window whenever it opens a tagged pdf file: “This file claims compliance with the PDF/A standard and has been opened read-only to prevent modification”. If this banner were only in the default view of Acrobat it might be more easily ignored, but it has no checkbox to make it go away and remains visible even in presentation mode (like, if you’re trying to present a lecture using a tagged pdf file). The only obvious way to make it go away is to click a button labeled “enable editing”, which you might think you don’t want to do.

It turns out that you can disable these banners entirely. In the preferences window for Acrobat, go to the “Documents” page and change the setting for “PDF/A View Mode” from “Only for PDF/A documents” to “Never”. I suspect that this also disables the automatic read-only setting for these files but I don’t think that’s a problem.
Editorial board of Games and Behavior, the journal of the Game Theory Society, resigns ($\mathbb{M}$), after its publisher Elsevier replaces its editor-in-chief without consultation with the board, for “closer alignment with Elsevier strategic priorities”. The link leads me to wonder: where is the involvement of the society itself in these decisions?
I created this image over a year ago for my CCCG 2025 talk “Decremental greedy polygons and polyhedra without sharp angles” ($\mathbb{M}$), but I don’t think I posted it (or the talk slides) online until now. This is what you get from the following process: start with the infinite set of integer points in the positive quadrant, and then repeatedly clip off the point that makes the sharpest angle on the convex hull. As you do this, at certain points you will reach curves for which the sharpest angle is less sharp than for any earlier curve; those are the ones shown in blue. The yellow quarter-circle is added separately for comparison.

Research problem 1: I don’t understand why the blue curves are so irregularly spaced nor why some of them appear so visually close to quarter-circles. Explain?
Physics papers are written in LaTeX ($\mathbb{M}$), video by Angela Collier. I doubt anyone here doesn’t already know all this, but it’s a good explainer of why researchers in mathematics/physics/theoretical computer science/linguistics etc. almost universally prefer LaTeX to Word, how the two differ, and why you can infer that a paper in Word was probably not written by a professional. Also with an entertaining rant about why Word is bad, how it’s getting both worse and more expensive, and why you should not pay for it.
Digit Party: Three years of lying about high scores ($\mathbb{M}$), and how authors Robert Brignall and Vince Vatter switched to integer linear programming in order to finally compute exact high scores for their online digit-clustering puzzle, digit.party.
A set of five 60-sided go-first dice ($\mathbb{M}$, via), found in 2023 by Paul Meyer through efforts coordinated by Auburn University lecturer Eric Harshbarger. These are five dice, labeled so that no two include the same numbers, with equal probabilities of rolling the highest number in all combinations of up to five dice. More strongly Wikipedia states that these dice are “permutation fair”: each permutation of the rolling players is equally likely. Now their discovery is commemorated by a giant set of these dice installed in the Auburn University STEM + Agricultural Sciences Complex.
Tsuidoku ($\mathbb{M}$),a sudoku variant in which you must fill in the usual 9x9 sudoku grid with both nine digits and nine colors, and must end up with one of each digit-color combination.

To me the biggest drawback is that the solved puzzles tend to have a stripy pattern like the patterns visible in the sudoku grids packed with 3x3 Latin squares from my recent blog post (both in their colors and digits) and when you detect this pattern it makes the puzzle much easier to solve. Also I’m not a fan of the style of gameplay that announces your mistakes immediately and lets you correct them; I think it makes puzzles trickier (and therefore more interesting) when you have to figure out that you’ve made a mistake yourself and undo back to where you made it. I checked that the nine colors appear distinguishable under the most common form of color blindness (at least to my normal vision eyes using a simulator) but their color contrast was not great, and there are three pairs of indistinguishable colors under blue-blind color blindness (tritanopia).

All that said, I think the higher levels are tricky enough to be interesting. And (research problem 2) I am intrigued by the question of whether the stripiness is an implementation flaw or a necessary emergent feature of these game rules at this board size.
Video on the motion and rigidity of hyperboloids made from sticks ($\mathbb{M}$), by Sabetta Matsumoto, Tim Reinhardt, Jürgen Richter-Gebert, and Henry Segerman, in part centered on a large public artwork with this form, Mae West in Munich.
Hyperchoreography ($\mathbb{M}$), solutions for $n$-body problems in more than three dimensions.

By David Eppstein

Monday, August 31 2026, 16:24

Who is the public?

from Ben Recht

Open problems and fundamental limitations of public feedback for AI (evals)

Hi there, argmin readers! As the fall semester picks up, posting volume will, too. So I’m going to commit to writing short descriptive headers to help you sort through the different threads.

Today’s post is by Jessica Dai, writing up her thoughts on the microconference on “public feedback for AI and beyond” that she ran at UC Berkeley in August. -Ben

Much of the conversation on A(G)I’s “risks and opportunities” centers on as-yet unrealized near- (or far-) future possibilities. Yet AI is already changing the world; its societal impact is already being felt in real time by real people. There’s a yawning gap between “AI elites” — frontier labs and academics and the online AI commentariat — and everyone else, in both beliefs and priorities. I think this is bad — medium- and long-term outcomes will also depend on how society experiences the near-term.1

My vision for dealing with this is something I’ve started calling “public feedback for AI.” The logic goes something like this:

Proposition 1. “The public” has interesting and important things to say about their experiences with AI, but are not typically listened to by decision makers.

Proposition 2. “Evaluations” — and aggregated information, more broadly — are useful, in the sense that they can influence consequential decisions.

Corollary. AI evaluations from public feedback can be a meaningful way to “do something” about the emergent misalignment between those who control AI development and literally everyone else.

I’ve spent the past few years working on this from various angles — trying to articulate why this might be a good idea, methods work for concrete audit instantiations, finding empirical evidence that user-generated content can tell us something useful about AI safety. But the more I think about these problems, the clearer the gaps in my own knowledge; there are many people who are smarter than me, who have worked on related problems for longer than I have, or who have new and different perspectives than those I’m exposed to in my local circles. And while there are a wide range of research questions that I find intellectually interesting, this clearly can’t remain a thought experiment.

Thus, microconference. (You can see a blurb, agenda, and list of attendees at publicfeedback.ai.)

I had a lot of fun at this workshop because while there were some fundamental philosophical questions threaded throughout the two days, everyone was ultimately interested in doing things beyond sending PDF preprints around to one another. And I’m really grateful for everyone’s engagement, because it helped me refine my thinking around each of the foundational ‘propositions’ underpinning the broader vision.

This write-up will be structured around the two ‘propositions’ I outlined above (rather than following the agenda directly). Additionally, I’ll stick closely to what was actually discussed at the workshop, so there is certainly lots of relevant literature that I’m not including here. Editorializing here is mostly mine, and if something is stupid or upsetting, blame me and not whichever speaker I’m referencing!

The first major question I wanted to cover is a core tension that ‘Proposition 1’, as written, glosses over: Who is the public?

While I won’t attempt to do armchair democratic theory here — though if there are any political philosophers reading this, I would love to chat — having clearer and better-motivated answers to this question seems important, because who is considered relevant also directly affects what concerns are substantively important, and also how their views can be understood.

Users?

I started us off on Monday by sharing a few plots from my paper analyzing r/ChatGPT, where we argue that anonymous Reddit data can help us understand broader societal impact; the claim is that the population of “r/ChatGPT posters” can help us simultaneously access a true “population of ChatGPT users” and something about the topics they cared about. I think this was broadly true for the time period we analyzed, but “ChatGPT users” is a very particular choice for defining a “public.”

Nevertheless, if we think AI impacts are largely realized through their users, then usage data is critical to measuring that impact. To this point, the first half of Shayne Longpre’s talk covered the newly launched AI Observatory project, a heroic effort to pull together as many real transcripts as one might reasonably find available on the internet, and to release and analyze them together as a corpus of usage data. Still, there are fundamental challenges with trying to reconstruct proprietary data from the outside; I’m cautiously optimistic about Anthropic’s (very new! Hot off the presses!) data release program.

Study participants or poll respondents?

A common adjective I’ve seen people use to describe chatlogs and other usage data is naturalistic: it reflects the real context in which users were engaging with the AI product. But this data has limitations; it is purely observational, which makes representativeness concerns all the more salient, and cannot provide context beyond the interaction itself (e.g., motivation or outcomes of usage). Instead, the typical approach to “human data collection” in academic contexts is to run more structured studies: recruitstudy participants and ask them to answer survey questions or complete tasks. While this allows researchers the ability to study more detailed questions, these studies have their own limitations; Serina Chang’s talk traced this tradeoff explicitly, with naturalism and control substituting directly for one another.

One issue that came up in discussion was about who these study participants were. Why should we expect that the data they generate is in any way “representative” of the constructs that researchers are trying to measure? A typical academic study promises a pay rate of up to $10/hour (the current standard recruitment platform is Prolific); this is below minimum wage in 30 US states. While $10 USD can be significant in a global context, we were unsure how to reason about the impact of this pay rate on the people who choose to participate.

This is a fundamental problem shared by public opinion polling (which is one reason why Ben hates it), and while it’s probably best not to read into more than one sigfig of poll results, there is reason to believe polls can be useful for coarse-grained judgments of vibe — especially when the vibes are off. Emma Pierson opened her talk with poll results showing the divergence between AI experts/ Claude users, who are generally positive about AI, and a demographically representative sample of the American population, who are generally negative. Jasmine Sun’s datacenter reporting was also motivated in part by national polls showing new datacenter construction polling on par with, or worse than, nuclear and coal. This stood in stark contrast to the SF tendency to dismiss datacenter opposition as merely a problem of misinformation.

Anyone who wants to report?

The approaches described above begin by recruiting people, then gathering their feedback within the explicit context and scope of a study (or poll). An alternative is an inversion of that paradigm: waiting for people to organically share feedback of their own volition, so that ‘the public’ is itself defined by the act of submitting a report. The second half of Shayne’s talk covered a flaw- reporting workflow that lets anyone create a report for an AI-related flaw, vulnerability, or incident, broadly construed, then sends it off to relevant parties. In terms of reporting accessibility, this system rhymes with a public incident reporting portal administered by the California Office of Emergency Services. As Deb Raji explained, this was created as part of SB53’s implementation. While this legislation was mainly directed at companies to self-report severe incidents (more on that later), there is also a provision for enabling public reporting.

Neither of these portals have shared the submissions received thus far, but they have similar design decisions that I suspect also lead to similar challenges (Algorithmic Justice League also has a harm reporting portal, and also hasn’t shared findings, as far as I can tell). Since literally anyone with the link can submit reports, these portals are likely susceptible to ‘low-quality’ submissions or spam. On the other hand, I would guess that overall submission volume is low, since awareness that these platforms exist is also low. I didn’t know about the SB53 portal until Deb’s talk, even though this is kind of my whole thing right now!

Start with an explicitly scoped community in mind, and go talk to them directly.

All three notions of ‘public’ described above involve a very convenient slippage between “public feedback” and “data collection”: they require configuring “the public” as a generic, anonymous mass from which data points can be sampled, and for which summary statistics can be computed. I don’t think this is always a bad thing, but it was striking to me that some of the most compelling case studies for effectively capturing “public feedback” started with an explicitly scoped community, and gathered information by having conversations with individuals within that community.

HCI researcher Samantha Dalal spoke about her work with the Workers’ Algorithm Observatory, which builds tools with gig workers to help identify, measure, and contest algorithmic systems. They bootstrapped worker outreach by collaborating with unions — existing legal entities with corresponding social networks. However, it was still necessary to have face-to-face conversations with workers to build trust and understand their needs.

Humphrey Obuobi shared his work with BLOOM, a nonprofit that is actively facilitating community dialogues in three counties in central Oregon. In this case, while BLOOM develops its own deliberative platform, I see the substance of their work as downstream of the specific, situated collaborations with local civic organizations which — like the unions in Samantha’s work — naturally scope participants to a more specific community.

Finally, Jasmine’s datacenter reporting was focused on understanding the popular backlash; this meant traveling to locations where backlash was visible or brewing. Of course, she talked to local elected officials, who were broadly responsible for decisions at the level of contracts and permitting, as well as activists who were leading more organized opposition. But she also spent a lot of time hanging out at county fairs and beer gardens, talking to people for whom datacenters may not have been the absolutely most salient issue in their lives, but who, nevertheless, turned out to have opinions when asked.

But wait, what about “unknown unknowns”?

I’ve often claimed that the major practical benefit of “public feedback” is the ability to support harm discovery — i.e., to surface unknown unknowns that a centralized decisionmaker (policymaker, company, etc.) might otherwise never think to look for. This seems, to some extent, at odds with the provocation above: doesn’t starting with a specific community in mind inevitably constrain the content of “public feedback” to known unknowns?

One reasonable response is that unknown unknowns exist even within well-scoped communities; prespecifying what groups of people one might be interested in doesn’t necessarily also require committing to particular outcomes or topics, especially if individuals are given the space to express their perspectives in their own voices (e.g., via semi-structured interviews instead of, or in addition to, providing yes/no answers or numerical ratings).

On the other hand, bottom-up community formation can and does already happen. Social media platforms are a natural and well-studied example: networks of like-minded people find each other through a mixture of organic encounters, algorithmic nudges, and moderation choices. For instance, after the initial release of GPT-5, a decentralized campaign to “bring back 4o” emerged on social media (mostly Reddit and Twitter); The Human Line is a research and advocacy group for survivors of AI spirals that emerged from initial encounters on Reddit.

Therefore, if working within communities (rather than a generic abstraction of “users” or “recruited participants”) can be uniquely effective, then perhaps we should try to build systems that explicitly help guide the development of communities based on common concerns. One of the projects covered in Wesley Deng’s talk was an end-user auditing tool called WeAudit, which intentionally included a deliberative and semi-social element that helped individuals contextualize their observations with other user-auditors. A similar motivation is behind an early-stage study shared by Eve Fleisig, where participants see other people’s experiences and can explicitly compare them to their own. In the universe of these projects, the community itself might emerge as an unknown unknown.

The other thing about “community” is that it’s likely of some intrinsic value to a participant — a very different source of motivation from the $10/h paid by Prolific. I’ll write more on the question of “what someone might get out of participating” in the next post.

Subscribe now

1

If you disagree, we should talk, but the goal of this post is not to convince you otherwise.

By jessica dai

Monday, August 31 2026, 14:03

Claude and Colorblind Questions

from Computational Complexity

BILL: Lance, I have a question and a meta question:

a) List all the presidents and vice presidents who were colorblind.

b) Do you know this sort of thing since you are colorblind, and hence

might have looked this up in the past?

LANCE: (b) No. And if Marco Rubio runs for president in 2028 he will need to earn my vote. He won't get it just for being colorblind. As for (a) I asked Claude.

Only one case is reasonably well documented, and it isn't a vice president. Bill Clinton is red-green colorblind: during the 1996 presidential debates, both Clinton and Bob Dole needed a modified cue-light system, since individual colored lights would have been hard for either of them to read, so a three-light arrangement was used instead — an anecdote that traces back to the Encyclopedia of Genetic Disorders and Birth Defects. Dole, of course, was Ford's running mate in 1976 and lost, so he never made it to the vice presidency.

Eisenhower is the other plausible case. His grandson David wrote that Ike confused browns and greens, sometimes asking for a brown suit when he meant green, and couldn't tell what color his golf balls were — someone had to write "DDE" on them. That's a family recollection rather than a diagnosis, but it's the kind of detail people don't invent.

Everything else you'll find online — Madison, Chester Arthur, Washington failing to distinguish crimson from scarlet, Lincoln calling lavender blue — comes from content-farm pages that cite nothing checkable, and I'd treat it as noise. Lincoln's documented eye problem was strabismus (eyes do not line up), not color vision.

As for vice presidents: I can't find a single one with any credible claim. That's a bit surprising statistically — roughly 8% of men of Northern European descent are red-green deficient, and with fifty-odd vice presidents you'd expect several. The explanation is almost certainly that nobody was looking. Color blindness is invisible unless someone asks, the Ishihara test only dates to 1917, and a nineteenth-century politician had no occasion to disclose it. Clinton's case surfaced only because television lighting forced the issue.

BILL: They left out Hubert Humphrey whose colorblindness was well known and well documented. It was why he was unable to serve in WW II. His not serving was used against him early in his career.

LANCE: I asked Claude about that and here is what it said:

Good catch — that's the vice-presidential case I missed, and it's better documented than anything on the presidential side. Humphrey tried to enlist after Pearl Harbor and was turned down three times, twice by the Navy and once by the Army, on account of color blindness along with other physical problems. Biographical accounts add that he also had a double hernia and lung scarring, possibly from unpasteurized milk.

This one holds up because it left a paper trail: military induction physicals in the 1940s included Ishihara-style screening, so his condition was formally tested and recorded rather than inferred from someone's recollection about suits or golf balls. It also mattered politically — the failed enlistment dogged him, since he was a young man of draft age who spent the war teaching and working for the WPA, and opponents used it against him in his early Minneapolis campaigns.

So the honest tally is one vice president (Humphrey), one president (Clinton), plus Eisenhower as a plausible unconfirmed case. Which, incidentally, undercuts the "nobody was looking" explanation I gave a moment ago — the real filter was that the condition surfaces only when an institution forces a test, and the military did that for exactly the cohort of politicians who came of age around the world wars.

BILL: SO, why did it get it wrong? This is not something obscure which requires guesswork like speculating on whether Washington was colorblind (I can't tell scarlet from Crimson either).

LANCE: Google AI did even worse.

♦
BILL-AI can solve Erdős problems, but it can't track down that Hubert Humphrey was colorblind. Why is that?

LANCE- Claude was just too lazy to check over the military records of every vice-president. AI are people too!

By gasarch

BILL: Lance, I have a question and a meta question:

a) List all the presidents and vice presidents who were colorblind.

b) Do you know this sort of thing since you are colorblind, and hence

might have looked this up in the past?

LANCE: (b) No. And if Marco Rubio runs for president in 2028 he will need to earn my vote. He won't get it just for being colorblind. As for (a) I asked Claude.

Only one case is reasonably well documented, and it isn't a vice president. Bill Clinton is red-green colorblind: during the 1996 presidential debates, both Clinton and Bob Dole needed a modified cue-light system, since individual colored lights would have been hard for either of them to read, so a three-light arrangement was used instead — an anecdote that traces back to the Encyclopedia of Genetic Disorders and Birth Defects. Dole, of course, was Ford's running mate in 1976 and lost, so he never made it to the vice presidency.

Eisenhower is the other plausible case. His grandson David wrote that Ike confused browns and greens, sometimes asking for a brown suit when he meant green, and couldn't tell what color his golf balls were — someone had to write "DDE" on them. That's a family recollection rather than a diagnosis, but it's the kind of detail people don't invent.

Everything else you'll find online — Madison, Chester Arthur, Washington failing to distinguish crimson from scarlet, Lincoln calling lavender blue — comes from content-farm pages that cite nothing checkable, and I'd treat it as noise. Lincoln's documented eye problem was strabismus (eyes do not line up), not color vision.

As for vice presidents: I can't find a single one with any credible claim. That's a bit surprising statistically — roughly 8% of men of Northern European descent are red-green deficient, and with fifty-odd vice presidents you'd expect several. The explanation is almost certainly that nobody was looking. Color blindness is invisible unless someone asks, the Ishihara test only dates to 1917, and a nineteenth-century politician had no occasion to disclose it. Clinton's case surfaced only because television lighting forced the issue.

BILL: They left out Hubert Humphrey whose colorblindness was well known and well documented. It was why he was unable to serve in WW II. His not serving was used against him early in his career.

LANCE: I asked Claude about that and here is what it said:

Good catch — that's the vice-presidential case I missed, and it's better documented than anything on the presidential side. Humphrey tried to enlist after Pearl Harbor and was turned down three times, twice by the Navy and once by the Army, on account of color blindness along with other physical problems. Biographical accounts add that he also had a double hernia and lung scarring, possibly from unpasteurized milk.

This one holds up because it left a paper trail: military induction physicals in the 1940s included Ishihara-style screening, so his condition was formally tested and recorded rather than inferred from someone's recollection about suits or golf balls. It also mattered politically — the failed enlistment dogged him, since he was a young man of draft age who spent the war teaching and working for the WPA, and opponents used it against him in his early Minneapolis campaigns.

So the honest tally is one vice president (Humphrey), one president (Clinton), plus Eisenhower as a plausible unconfirmed case. Which, incidentally, undercuts the "nobody was looking" explanation I gave a moment ago — the real filter was that the condition surfaces only when an institution forces a test, and the military did that for exactly the cohort of politicians who came of age around the world wars.

BILL: SO, why did it get it wrong? This is not something obscure which requires guesswork like speculating on whether Washington was colorblind (I can't tell scarlet from Crimson either).

LANCE: Google AI did even worse.

BILL-AI can solve Erdős problems, but it can't track down that Hubert Humphrey was colorblind. Why is that?

LANCE- Claude was just too lazy to check over the military records of every vice-president. AI are people too!

By gasarch

Monday, August 31 2026, 02:18

Discrepancy of geometric incidences

Authors: Azem Adibelli, István Tomon

We study the combinatorial (red-blue) discrepancy of finite point sets with respect to hyperplanes and, more generally, bounded-complexity affine algebraic sets. We prove that every $n$-point set in a real Euclidean space admits a red-blue coloring for which every affine algebraic set of dimension at most $D$ and degree at most $k$ has discrepancy at most $n^{\frac12-\frac{1}{2(D+1)}-\varepsilon}$ for some $\varepsilon=\varepsilon(D,k)>0$. This gives a polynomial improvement over the straightforward VC-dimension bound $\tilde O(n^{\frac12-\frac{1}{2(D+1)}})$. In the opposite direction, we construct $n$-point sets in $\mathbb R^d$ whose discrepancy with respect to hyperplanes is $\tildeΩ(n^{\frac12-\frac{1}{d+1}}),$ extending the point-line discrepancy lower bound of Chazelle and Lvov. We present further applications of our methods in communication complexity, concerning separation between randomized communication cost and deterministic communication cost with access to equality oracle.

Authors: Azem Adibelli, István Tomon

We study the combinatorial (red-blue) discrepancy of finite point sets with respect to hyperplanes and, more generally, bounded-complexity affine algebraic sets. We prove that every $n$-point set in a real Euclidean space admits a red-blue coloring for which every affine algebraic set of dimension at most $D$ and degree at most $k$ has discrepancy at most $n^{\frac12-\frac{1}{2(D+1)}-\varepsilon}$ for some $\varepsilon=\varepsilon(D,k)>0$. This gives a polynomial improvement over the straightforward VC-dimension bound $\tilde O(n^{\frac12-\frac{1}{2(D+1)}})$. In the opposite direction, we construct $n$-point sets in $\mathbb R^d$ whose discrepancy with respect to hyperplanes is $\tildeΩ(n^{\frac12-\frac{1}{d+1}}),$ extending the point-line discrepancy lower bound of Chazelle and Lvov. We present further applications of our methods in communication complexity, concerning separation between randomized communication cost and deterministic communication cost with access to equality oracle.

Monday, August 31 2026, 00:00

Improved Subexponential Upper Bounds for $3$-Restricted Matching Vector Families

Authors: Sidhant Saraogi

Matching Vector families (MVFs) are defined by two ordered lists of vectors in $\mathbb{Z}_m^n$ whose inner products satisfy specific residue patterns modulo an integer $m$. Most famously, restricted MVFs are used to construct the best-known constant-query Locally Decodable codes (LDCs). We prove an upper bound of $2^{O\left(\sqrt{n\log n \log m}\right)}$ on the size of $3$-restricted MVFs in $\mathbb{Z}_m^n$ for $m \leq \sqrt{n}$, substantially improving on the previous best bound of $2^{O(n/\log n)}$ by Bhowmick, Dvir and Lovett (STOC'13, SICOMP'14). Our proof relies on a new polynomial method argument that controls collisions in sumsets of matching vectors.

Authors: Sidhant Saraogi

Matching Vector families (MVFs) are defined by two ordered lists of vectors in $\mathbb{Z}_m^n$ whose inner products satisfy specific residue patterns modulo an integer $m$. Most famously, restricted MVFs are used to construct the best-known constant-query Locally Decodable codes (LDCs). We prove an upper bound of $2^{O\left(\sqrt{n\log n \log m}\right)}$ on the size of $3$-restricted MVFs in $\mathbb{Z}_m^n$ for $m \leq \sqrt{n}$, substantially improving on the previous best bound of $2^{O(n/\log n)}$ by Bhowmick, Dvir and Lovett (STOC'13, SICOMP'14). Our proof relies on a new polynomial method argument that controls collisions in sumsets of matching vectors.

Monday, August 31 2026, 00:00

Improved $\ell_0$-Isoperimetry for Convex Bodies via Mass Transport

Authors: Manuel Fernandez

We study $\ell_0$ isoperimetry for a convex body $K\subset \mathbb{R}^n$, $n\ge2$. For a Borel set $S\subset K$, let $\partial_0^K S$ be the set of points in $K \setminus S$ that can be reached from $S$ by changing at most one coordinate (i.e. the $\ell_0$ boundary of $S$). Suppose that, for some unconditional convex body $Q \subset \mathbb{R}^n$, numbers $r,R>0$, and possibly different centers $x_0,y_0$, \[ x_0+rQ \subset K\subset y_0+RQ. \] Writing $s=\text{vol}(S)/\text{vol}(K)$, we prove that whenever $0 0$ is an absolute constant. Consequently, the associated $\ell_0$-isoperimetric coefficient is at least $cr/(n^2R)$. Previous direct lower bounds were only known for $\ell_2$ and $\ell_\infty$ regularity whereas our lower bound holds directly for any $Q$-regularity, where $Q$ is an unconditional convex body. Compared to $\ell_2$ and $\ell_\infty$ regularity, our lower bound result improves upon the previously best known lower bounds, for any $s$, by a factor of $n$. As an application of our result, we give improved mixing time bounds for the Coordinate Hit and Run walk (CHAR). Our proof of the lower bound is based on a modification of the method of canonical paths applied to a continuous Hamming graph over our convex body. Our construction of canonical paths can be viewed as a suitable coordinate discretization of certain mass transport maps from $S$ to $S^c$. We also give complementary upper-bounds for any $Q$-regularity, with an overall factor of $n$ gap between the two.

Authors: Manuel Fernandez

We study $\ell_0$ isoperimetry for a convex body $K\subset \mathbb{R}^n$, $n\ge2$. For a Borel set $S\subset K$, let $\partial_0^K S$ be the set of points in $K \setminus S$ that can be reached from $S$ by changing at most one coordinate (i.e. the $\ell_0$ boundary of $S$). Suppose that, for some unconditional convex body $Q \subset \mathbb{R}^n$, numbers $r,R>0$, and possibly different centers $x_0,y_0$, \[ x_0+rQ \subset K\subset y_0+RQ. \] Writing $s=\text{vol}(S)/\text{vol}(K)$, we prove that whenever $0 0$ is an absolute constant. Consequently, the associated $\ell_0$-isoperimetric coefficient is at least $cr/(n^2R)$. Previous direct lower bounds were only known for $\ell_2$ and $\ell_\infty$ regularity whereas our lower bound holds directly for any $Q$-regularity, where $Q$ is an unconditional convex body. Compared to $\ell_2$ and $\ell_\infty$ regularity, our lower bound result improves upon the previously best known lower bounds, for any $s$, by a factor of $n$. As an application of our result, we give improved mixing time bounds for the Coordinate Hit and Run walk (CHAR). Our proof of the lower bound is based on a modification of the method of canonical paths applied to a continuous Hamming graph over our convex body. Our construction of canonical paths can be viewed as a suitable coordinate discretization of certain mass transport maps from $S$ to $S^c$. We also give complementary upper-bounds for any $Q$-regularity, with an overall factor of $n$ gap between the two.

Monday, August 31 2026, 00:00

Optimal exponential memory for sequential Euclidean connection: edge-power costs and phase transitions

Authors: Pedro M. M. de Castro

We consider an online geometric connection rule that stores one point of state. After processing $p_i$, the state is updated by $x_i=γx_{i-1}+(1-γ)p_i$, and the two segments from $x_{i-1}$ to $x_i$ and from $x_i$ to $p_i$ are retained. The design parameter $γ$ controls the persistence of the state. We minimize the sum of the $α$-powers of the resulting edge lengths under independent uniform input and under arbitrary input sequences. For uniform points in the unit ball, the stationary problem has a transition at $α=1$. Its continuous extension is minimized at the boundary for $0<α\leq1$, and every global minimizer is interior for $α>1$. The main result determines the finite optimizer in the joint window $α_N=1+\varepsilon_N$, $\varepsilon_N\log N\toλ$. Below an explicit threshold it lies on the $N^{-1/2}$ scale. At the threshold its scale is $\sqrt{\log N/(N\log\log N)}$, and above the threshold it approaches an explicit stationary root with two computable corrections. A second threshold identifies which correction governs the location, and differentiated estimates prove eventual uniqueness. At $α=3d+8$, the linear coefficient at the stationary endpoint changes sign and a branch of strict local maxima enters the parameter interval. Under arbitrary input sequences, the optimal parameter and asymptotic worst-case edge-power cost per processed point are explicit for $0<α\leq3$. At high powers, periodic blocks and a separation argument show that this optimized cost is asymptotic to $2\log2/\logα$. Exact results for powers two and four, a rational recursion for all even powers, and a high-dimensional expansion provide additional descriptions of the optimizer.

Authors: Pedro M. M. de Castro

We consider an online geometric connection rule that stores one point of state. After processing $p_i$, the state is updated by $x_i=γx_{i-1}+(1-γ)p_i$, and the two segments from $x_{i-1}$ to $x_i$ and from $x_i$ to $p_i$ are retained. The design parameter $γ$ controls the persistence of the state. We minimize the sum of the $α$-powers of the resulting edge lengths under independent uniform input and under arbitrary input sequences. For uniform points in the unit ball, the stationary problem has a transition at $α=1$. Its continuous extension is minimized at the boundary for $0<α\leq1$, and every global minimizer is interior for $α>1$. The main result determines the finite optimizer in the joint window $α_N=1+\varepsilon_N$, $\varepsilon_N\log N\toλ$. Below an explicit threshold it lies on the $N^{-1/2}$ scale. At the threshold its scale is $\sqrt{\log N/(N\log\log N)}$, and above the threshold it approaches an explicit stationary root with two computable corrections. A second threshold identifies which correction governs the location, and differentiated estimates prove eventual uniqueness. At $α=3d+8$, the linear coefficient at the stationary endpoint changes sign and a branch of strict local maxima enters the parameter interval. Under arbitrary input sequences, the optimal parameter and asymptotic worst-case edge-power cost per processed point are explicit for $0<α\leq3$. At high powers, periodic blocks and a separation argument show that this optimized cost is asymptotic to $2\log2/\logα$. Exact results for powers two and four, a rational recursion for all even powers, and a high-dimensional expansion provide additional descriptions of the optimizer.

Monday, August 31 2026, 00:00

Condorcet-Winning Sets and Peer Selection in Planar Metric Elections

Authors: Gabriel de Azevedo, Ulysse Hennebelle

In ranked-choice voting, a Condorcet-winning set is a group of candidates for which no outside candidate is preferred to every member of the group by a majority of voters. We study Condorcet-winning sets in planar metric elections, where voters rank candidates according to their distance under a given norm. We formulate general metric elections, peer selection, and the one-round Voronoi game as instances of a two-player Stackelberg game and place these problems in a common hierarchy. We also introduce a new variant, which we call strong peer selection. Our main result concerns peer selection under the $\ell_1$ and $\ell_\infty$ norms. We prove that every planar instance admits a Condorcet-winning set of size at most three, even under strong peer selection. This follows from a new result for strong rectangular $\varepsilon$-nets. We show that, for every set of points in the plane, one can choose at most three input points that intersect every axis-parallel rectangle containing more than half of the points, improving the previous threshold of $9 / 16$ due to Ashok et al. Under the $\ell_2$ norm, we prove that every planar metric election admits a Condorcet-winning set of size at most four, improving on the general bound of five due to Song et al. Finally, we give new norm-independent bounds for the one-round Voronoi game.

Authors: Gabriel de Azevedo, Ulysse Hennebelle

In ranked-choice voting, a Condorcet-winning set is a group of candidates for which no outside candidate is preferred to every member of the group by a majority of voters. We study Condorcet-winning sets in planar metric elections, where voters rank candidates according to their distance under a given norm. We formulate general metric elections, peer selection, and the one-round Voronoi game as instances of a two-player Stackelberg game and place these problems in a common hierarchy. We also introduce a new variant, which we call strong peer selection. Our main result concerns peer selection under the $\ell_1$ and $\ell_\infty$ norms. We prove that every planar instance admits a Condorcet-winning set of size at most three, even under strong peer selection. This follows from a new result for strong rectangular $\varepsilon$-nets. We show that, for every set of points in the plane, one can choose at most three input points that intersect every axis-parallel rectangle containing more than half of the points, improving the previous threshold of $9 / 16$ due to Ashok et al. Under the $\ell_2$ norm, we prove that every planar metric election admits a Condorcet-winning set of size at most four, improving on the general bound of five due to Song et al. Finally, we give new norm-independent bounds for the one-round Voronoi game.

Monday, August 31 2026, 00:00

Tight Bounds for Memory Allocation With and Without Request Fragmentation

Authors: Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, William Kuszmaul, Nicole Wein

The classical memory-allocation problem captures the task of placing objects of different sizes in memory, while minimizing the so-called memory high-water mark. It has been known since the early 1970s that the optimal competitive ratio for any deterministic online allocator is $Θ(\log M)$, where $M$ is the volume high-water mark of the underlying request sequence. This paper begins with a simple observation: many real-world allocators seem to bypass the 1971 lower bound by adopting a slightly different model for memory allocation. These allocators use what we call $k$-aggregate request fragmentation, meaning that the memory allocator is permitted to break requests into multiple fragments, so long as the all-time maximum number of simultaneous fragments is at most $k$ times the all-time maximum number of simultaneous requests. We consider the following basic question: Does request fragmentation fundamentally change the problem of memory allocation, and if so, how? Our results come with several surprises. Among these, we find that even using $k = 1 + o(1)$ request fragmentation, the optimal competitive ratio---which was $Θ(\log M)$ in the classical setting---collapses to $Θ(\log \log M)$. This result is shown to be tight with matching upper and lower bounds, applying to both deterministic and randomized algorithms.

Authors: Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, William Kuszmaul, Nicole Wein

The classical memory-allocation problem captures the task of placing objects of different sizes in memory, while minimizing the so-called memory high-water mark. It has been known since the early 1970s that the optimal competitive ratio for any deterministic online allocator is $Θ(\log M)$, where $M$ is the volume high-water mark of the underlying request sequence. This paper begins with a simple observation: many real-world allocators seem to bypass the 1971 lower bound by adopting a slightly different model for memory allocation. These allocators use what we call $k$-aggregate request fragmentation, meaning that the memory allocator is permitted to break requests into multiple fragments, so long as the all-time maximum number of simultaneous fragments is at most $k$ times the all-time maximum number of simultaneous requests. We consider the following basic question: Does request fragmentation fundamentally change the problem of memory allocation, and if so, how? Our results come with several surprises. Among these, we find that even using $k = 1 + o(1)$ request fragmentation, the optimal competitive ratio---which was $Θ(\log M)$ in the classical setting---collapses to $Θ(\log \log M)$. This result is shown to be tight with matching upper and lower bounds, applying to both deterministic and randomized algorithms.

Monday, August 31 2026, 00:00

An Exposition of the $\widetilde{O}(\log^{1/4} n)$ Bound for the Komlós Problem