OPML feed of all feeds.
Subscribe to the Atom feed, RSS feed to stay up to date.
Thank you to arXiv for use of its open access interoperability.
Note: the date of arXiv entries announced right after publication holidays might incorrectly show up as the date of the publication holiday itself. This is due to our ad hoc method of inferring announcement dates, which are not returned by the arXiv API.
Powered by Pluto.
Source on GitHub.
Maintained by Nima Anari, Arnab Bhattacharyya, Gautam Kamath.
from ECCC Papers
from ECCC Papers
from ECCC Papers
Authors: Farzad Didehvar, Saman Farhat
We watch a computation only at moments chosen by a random clock that can leap ahead, pause, or step back, and we count looks rather than steps. How far can such a clock reliably see with polynomially many looks, and does stepping back help? Rare long leaps reach exponential and doubly exponential time, with infinitely many levels between polynomial and exponential time. A clock that tends to fall back sees only the start of the input, and below polynomial time we find infinitely many incomparable levels. Stepping back can help decisively. For clocks whose long leaps occur only at rare positions, no forward-only clock goes beyond polynomial time, while even single steps back raise the reach to exponential time. Stepping back cannot help, however, when the clock's leaps ignore its position.Authors: Kuan Cheng, Shengtang Huang, Ruiyang Wu
Cheng and Wang (CCC' 24) showed that BPL is contained in logspace uniform AC$^1$ (denoted as L-AC$^1$). We upgrade their result by showing that $\#$SAC functions (i.e., functions computed by logspace-uniform polynomial-size positive semi-unbounded arithmetic circuits) can be approximately computed by L-AC circuits with high precision. In particular, approximations of $\#$SAC$^1$ functions can be computed in L-AC$^1$ with multiplicative error $2^{-\mathrm{poly}\log n}$. Previously, approximations of $\#$SAC$^1$ functions are known to be in $\mathsf{NC}^2$ via its exact computation given by Vinay (CCC' 91). A main corollary of our result is that BPAuxPDMs and Read-$k$-BPL are computable by L-AC$^1$ with multiplicative error $2^{-\mathrm{poly}\log n}$. Notice that multiplicative error approximations can be used directly to decide non-deterministic computations. So our L-AC$^1$ circuits can automatically be used to decide non-deterministic AuxPDMs and hence NL. We note that recently OpenAI announced that BPL $=$ L. Even if we only consider derandomizing BPL, our L-AC$^1$ computation has the advantage that the error can be $2^{-\mathrm{poly}\log n}$ and can be multiplicative.Authors: Xiaotie Deng, Ningyuan Li, Zihe Wang, Jie Zhang
For every fixed $\varepsilon\in(0,1)$ and $η\in[0,1)$, we prove that computing an $(\varepsilon,η)$-weak approximate Nash equilibrium requires quasipolynomial time assuming deterministic PPAD-ETH, even in symmetric binary-payoff games with a constant number of players. The games are given by complete payoff tables, and the player count depends only on the tolerances. The weak approximate Nash equilibrium allows at most an $η$ fraction of players to gain more than $\varepsilon$ by deviating unilaterally. The main technical result is an unconditional error-amplification reduction from bimatrix games. For every fixed $δ\in(0,1)$, it transforms a rational bimatrix game with payoffs in $[0,1]$ into a symmetric binary-payoff game with a polynomial-size complete table and a player count depending only on $δ,\varepsilon,η$. Every $(\varepsilon,η)$-weak approximate equilibrium of the constructed game yields a $δ$-approximate Nash equilibrium of the bimatrix game. Construction and recovery take polynomial time in their explicit inputs. Combining this reduction with the bimatrix hardness result of Rubinstein [FOCS 16] gives a deterministic worst-case running-time lower bound of $N^{(\log N)^{1-o(1)}}$, where $N$ is the constructed table's binary encoding length.Authors: Karthik Viswanathan, Plamen Dimitrov, Stefano Rocca, Sarayu Sirikonda
Multi-head attention is a central component of the transformer architecture, yet how its expressivity depends on the number of heads remains poorly understood. We study a one-layer, attention-only transformer with additive positional embeddings and define the head complexity $H^\ast(f)$ of a Boolean function $f$ as the minimum number of attention heads required to represent it. We derive an exact linear-fractional normal form for head complexity, prove a general threshold-degree lower bound, and give an explicit ten-bit function for which this bound is strict. For symmetric Boolean functions, we independently show that head complexity equals the number of times the function changes value between consecutive Hamming-weight levels, even when positional embeddings are allowed. This agrees with the concurrent characterization of Hsu and Xu (arXiv:2608.04243) in a model without positional embeddings. The symmetric lower bound combines our general threshold-degree bound with the classical result of Aspnes et al. (1994). These results were discovered and formalized by a frontier model through conjecture generation, theorem proving, and machine verification, while human researchers asked the high-level questions and reviewed the generated theorems. We make the Lean formalization and research traces publicly available to support agent-assisted theorem proving and formal verification in mechanistic interpretability. This work provides a proof of concept for using the capabilities of frontier models, grounded by formal verification, to develop an understanding of transformer architectures.Authors: Markus Bläser, Radu Curticapean, Sagnik Dutta, Gorav Jindal
For a partition $\boldsymbolλ = (λ_1,\ldots,λ_r)$ and $n\ge r$, the monomial symmetric polynomial is defined as $$m_{\boldsymbolλ}(x_1,\ldots,x_n) := \sum x_{i_1}^{λ_1} x_{i_2}^{λ_2} \cdots x_{i_r}^{λ_r},$$ where the sum ranges over all distinct monomials obtained by assigning the parts of $\boldsymbolλ$ to pairwise distinct variables. We establish an almost-complete dichotomy for the complexity of the monomial symmetric polynomials $m_{\boldsymbolλ}$: If a family of partitions contains polynomially many distinct parts, then the corresponding monomial symmetric polynomials (on sufficiently many variables) are VNP-complete. If the number of distinct parts is constant, the family admits polynomial-size circuits. Thus the only remaining gap concerns the intermediate regime where the number of distinct parts grows subpolynomially. As part of our proof, we use combinatorial properties of matching polynomials to establish VNP-hardness of the perfect matching polynomial for blow-up graphs; these are graphs with non-generic edge-weights that are obtained by "blowing up" a smaller graph. We reduce these matching polynomials to monomial-symmetric polynomials by combining classical techniques from algebraic complexity theory with structural properties of Sidon sets.Authors: Dmytro Gavinsky
We exhibit a bipartite language with a poly-logarithmic quantum communication protocol and polynomial Merlin-Arthur communication complexity.Authors: Guoliang Xu, Haoran Zhang, Mengfan Wu, Songyao Xue, Mingke Liu
Let \(f = \text{EXACT}^5_{3,4}\) be the Boolean function that equals 1 exactly on inputs of Hamming weight 3 or 4. Earlier numerical studies reported success probabilities close to one using three queries, but the existence of an exact three-query algorithm had remained unresolved. This paper settles this problem by proving that the exact quantum query complexity of \(f\) is \(4\). For the lower bound, we express every three-query algorithm through layer-by-layer Gram matrices of low-degree Fourier coefficients. We then construct a fixed rational dual certificate whose slack matrices are all positive definite. This certificate separates the necessary Gram-matrix region from the exact-output condition and therefore rules out every exact algorithm using at most three queries in the stated model. The positivity verification reduces to five small rational matrices and Sylvester's criterion. For the upper bound, we invoke the previously known four-query algorithm for the seven-bit function \(\text{EXACT}^7_{3,4}\) and apply the standard padding reduction. To quantify the near-exact behavior, we use the same certificate to derive a valid, though not claimed tight, lower bound \(\frac{25600}{43779488192449}>0\) on the worst-case error of every algorithm using at most three queries. This positive error gap is compatible with the near-unit success probabilities reported in earlier numerical studies, which do not establish exact computation.Authors: Michael C. Thumann, David Soloveichik
Computational dissipation may arise from both information erasure and finite-time operation, although both contributions can in principle be avoided in the absence of space and time constraints. Logically reversible computation can replace erasure with ancilla cleanup, and slow adiabatic protocols can eliminate any excess finite-time dissipation. Under limited memory and in finite time, however, choosing reversible cleanup over erasure requires additional dissipative operations, creating a semi-reversible energy--memory--time tradeoff. We formulate this tradeoff at a fixed operating point of an externally clocked thermally coupled computer, where reversible checkpoint moves and local irreversible erasures have specified effective prices $ε_R$ and $ε_I$. Their ratio $λ=ε_I/ε_R$ selects an energy-optimal semi-reversible schedule under a checkpoint-memory bound by trading reversible moves against erasures. For a sequential computation whose dependency graph is a line, we derive an exact separator recurrence and prove that an asymptotically optimal schedule repeats a strictly reversible block followed by one local erasure. Coupling this scheduling theorem to a stochastic-thermodynamic constitutive model shows how temperature, primitive duration, memory, and device-dependent operation costs determine whether the optimal schedule uses reversible cleanup, elective erasures, or erasure at every disposal.Authors: Nanase Sato, Wei Wu, Mutsunori Yagiura
We study the problem of deciding the feasibility of pressure-driven hydrogen charging from supply cylinders to demand cylinders without replenishment, asking whether an order of transfers allows every demand cylinder to reach its target pressure. Hydrogen can be transferred from a cylinder to another only when the supply cylinder has higher pressure than the demand cylinder. The charging to each demand cylinder must be completed before starting another, and each transfer continues until the connected cylinders reach equal pressures or the demand cylinder reaches its target. We consider equal-capacity supply cylinders and arbitrary positive rational demand cylinder capacities. Let $n$ be the number of demand cylinders and $L$ the binary input length. With one supply cylinder, feasibility is decidable in polynomial time; with two, it is NP-complete even with cylinder capacities equal to $1$ and nonnegative integer pressures. We prove that feasibility is preserved even if the supply cylinders are always used in non-decreasing order of their current pressures when filling each demand cylinder. We also show that majorization of residual supply cylinder pressure states justifies discarding majorized states in dynamic programming over sets of completed demand cylinders without losing any feasible remaining demand cylinder order. With two supply cylinders, one state per completed demand cylinder set suffices, yielding $2^n\operatorname{poly}(L)$ time and space. With three, the exponential time hypothesis (ETH) excludes deterministic $2^{o(n\log n)}\operatorname{poly}(L)$-time algorithms. This lower bound is tight in the exponent because the rule for order of supply cylinders allows feasibility to be decided in $n!\operatorname{poly}(L)$ time by enumerating only demand cylinder orders.Authors: Jun Liu, Ivan O. Shevchenko
Sontag conjectured in 1988 that global controllability of polynomial control systems with rational coefficients is undecidable, but that the controllable systems form a recursively enumerable set. We prove the first part of the conjecture and disprove the second. For every homogeneous polynomial vector field $F$ of odd degree with rational coefficients, we construct an explicit polynomial control system $Σ_F$, with one more state than $F$, that is globally controllable if and only if the origin is \emph{not} globally asymptotically stable for $\dot x=F(x)$. By a recent result, the homogeneous polynomial vector fields with a globally asymptotically stable origin form a set that is recursively enumerable but not decidable. Consequently, global controllability of polynomial systems is undecidable, and the controllable polynomial systems are not recursively enumerable. The same conclusions hold for systems of the form $\dotξ=f(ξ)+Bu$ with a polynomial drift and a constant input matrix.Authors: Panagiotis Kanellopoulos, Themistoklis Melissourgos
Generalized circuits are a fundamental tool for establishing PPAD-hardness and membership of approximate equilibrium problems. Despite their importance, the complexity of finding approximate solutions has remained unresolved for a wide range of approximation parameters. We settle this question by establishing a tight threshold at $\varepsilon=1/6$. Specifically, we prove that $\varepsilon$-GCircuit is PPAD-complete for every constant $0<\varepsilon<1/6$, even when restricted to four gate types, and polynomial-time solvable for every constant $\varepsilon\ge1/6$. This closes the gap between the previously known hardness bound of $1/10$ and the polynomial-time solvability bound of $1/2$. We further investigate the relaxation in which a fraction $δ$ of the gates may be violated. We establish polynomial-time solvability of $(\varepsilon,δ)$-GCircuit for every constant $\varepsilon>0$ and $δ>1/5$, and of the fan-out-one formulations of $δ$-Pure-Circuit for every constant $δ>1/8$. These results follow from a decomposition theorem for directed graphs of maximum in-degree two and establish that the PCP-for-PPAD conjecture cannot be true for the aforementioned values of $\varepsilon$ and $δ$, unless PPAD = P. To showcase the contribution of our positive results, we apply them to a variety of problems in algorithmic game theory, including public goods games, financial networks, Bayesian, polymatrix, and graphical games, and obtain improved approximation guarantees.Authors: Masashi Aono
On ranked directed acyclic graphs coupled by vertex conflicts we study exact-arrival multi-agent path finding (departure and arrival pinned in place and time) posed as a distributed output task: every cell must emit its own bit of a valid joint path-support mask. The machines are cellular: one automaton per cell, state factored over cells, communication only along a fixed local fabric, synchronous rounds, a query-independent output round, no central decoder, and a per-topology transition code. "Necessary" here means: on an explicit hard topology, over all its feasible queries, no universally correct local-only architecture can renounce either temporal orientation; with global flags, impossibility becomes a bandwidth-round trade-off. The class is not vacuous: a flooding machine solves every instance in as many rounds as the diameter of the local fabric. The bound survives two concessions: we supply every agent's exact individual cavity, which alone solves the single-agent problem in zero rounds and makes the single-agent direction theorem vacuous; and we allow $k$ one-bit global aggregate flags. On a twelve-cell, two-agent, depth-three topology no forward-only machine with $k=0$ is correct on two feasible queries, for any number of rounds; the time-reversed topology does the same to backward-only machines. Placing $p$ copies side by side gives, for forward-only machines, $J_R+kR\ge p$ at constant depth, where $J_R$ measures how much of the query reaches the targets' cones and is $0$ here. A backward-only machine solves that family in constant rounds and a flag-streaming one in $\lceil p/k\rceil+O(1)$, so the bound is tight in order; on the composite family neither orientation can be renounced. The finite lemmas of the gadget and the pair-invariance contradictions are checked in Lean 4; the semantic bridge, the cone lemma and the counting are paper proofs. We report no benchmarks.Authors: Manon Blanc
Dynamical systems are a widely used model of computation and an intuitive representation of many natural phenomena in many applied fields. The last decades have seen an impressive use of computers in studying and analysing them, with several visible theoretical breakthroughs. The question of reachability for dynamical systems is central: given two points, is there a trajectory between them in the dynamical system? Reachability, in particular over the reals, is undecidable in the general case: it is only computably enumerable, even under reasonable hypotheses, e.g. for a computable dynamics in general. But it is known to become decidable, and even lies in PSPACE, under suitably quantified robustness assumptions. In this paper, we focus on PSPACE-completeness results over the reals, in the sense of computable analysis, regarding discrete-time and continuous-time robust dynamical systems. We prove that, under some additional and rather reasonable hypotheses, the reachability relation becomes even PSPACE-complete for both classical and second-order complexity second-order complexity, for an adapted notion of reduction. As a side-effect, we also prove an improvement of an algebraic Ordinary Differential Equations-based characterisation of PSPACE, removing one of the base functions of the algebra. By doing so, we link results from dynamical systems and complexity over the reals, including the models of computable analysis and second-order complexity.Authors: Robert Bredereck, Eva Deltl, Till Fluschnik
Allocating renewable resources fairly requires accounting for how present decisions affect future availability. We introduce Sustainable and Envy-Free Multi-Period Allocation, in which agents are assigned over multiple periods to renewable resources whose quantities evolve over time according to renewal functions. An allocation must respect viability and capacity constraints while being envy-free over the whole time horizon. We study the computational and parameterized complexity of finding such allocations, with a focus on the three dimensions of the problem: the numbers of agents, resources, and periods. We show that finding such an allocation is NP-hard already for unary encoding and any single one of them being fixed to a constant. Whether two small dimensions suffice for tractability depends on the pair, the class of renewal functions, and the numerical encoding. For few resources and periods, binary-encoded instances remain hard in general, whereas unary encoding yields XP-time algorithms. For few resources and agents, binary-encoded instances also remain hard in general but become XP-time solvable when all renewal functions are translations. Few agents and periods yield fixed-parameter tractability, but no polynomial kernel under standard complexity assumptions.Authors: Alec Shelley, Daniel Tartakovsky
We consider the problem of calculating the volume of the union of translates of a strictly convex body $K\subset\mathbb{R}^d$. When $K$ is a ball, it is possible to simplify the inclusion-exclusion formula by summing over only a small subset of all terms. This subset corresponds to intersecting cells in the Voronoi diagram of the ball centers. We prove that the same simplification is valid for every strictly convex $K$ if and only if $d\leq 2$. Moreover, in three dimensions and when $K$ is $C^4$, we use the Fubini-Pick affine invariant to show that the topological identity underlying this technique holds if and only if $K$ is an ellipsoid.Authors: Adrian Dumitrescu, Zsolt Lángi
Given a finite planar point set $X=\{x_1,\ldots,x_n\}$, let $a_10$ such that for any set $X$ of $n$ points in the plane, and set $D$ of size $k$, there exists a subset $X' \subseteq X$ of size $|X'| \geq c_k |X|$ in which no pair of points is at some distance in $D$ (we say that $X'$ avoids distances in $D$). Such a set can be found efficiently. (B) (i) There is a subset of $X$ of size $n/2$ that avoids the maximum distance; this bound cannot be improved. (ii) There is a subset of $X$ of size $8n/47$ that avoids both the minimum and maximum distance; on the other hand, there exists $X$ such that at most $5n/16$ points can be retained with this property. (iii) There is a subset of $X$ of size $n/7$ whose diameter is at most half the original diameter; on the other hand, there exists $X$ such that at most $n/6$ points can be retained with this property. (C) (i) For any $\varepsilon>0$, a $(1-\varepsilon)$-approximation for \textsc{MIS} in the minimum distance graph of $n$ points in the plane can be found in $2^{O(1/\varepsilon)} n^{O(1)}$ time. (ii) Given a set $X$ of $n$ points in the plane, a maximum independent set in the graph of diameters can be computed in $O(n^2)$ time. The techniques used to handle the planar case can be extended to $\mathbf{R}^d$ for any fixed dimension $d$.Authors: Bo Pang, Shaojing Zhang, Chengliang Tian
The shortest vector problem (SVP) under the infinity norm ($\ell_\infty$-norm) is an important lattice problem with applications in lattice-based cryptography. In particular, the security analysis of the post-quantum signature standard ML-DSA highlights the importance of finding short solutions satisfying infinity-norm constraints, rather than only Euclidean norm bounds. However, most existing lattice reduction algorithms are developed for the Euclidean norm, while dedicated studies under the infinity norm remain limited. In this work, we focus on rank-two lattices in $\mathbb{R}^n$ and introduce a new notion of reduced basis under the infinity norm. Based on this definition, we propose an efficient lattice basis reduction algorithm that performs a multi-dimensional analogue of Euclidean division using a dominant coordinate of the basis vectors. Each non-terminal iteration guarantees a factor-two decrease of the maximum infinity norm of the basis vectors. We prove that the algorithm terminates and achieves a bit complexity of $O(nT^2)$, matching the asymptotic complexity order of the classical Lagrange--Gauss reduction. Moreover, the proposed algorithm saves at least $2n$ multiplications per iteration compared with the classical approach. Experiments demonstrate significant runtime improvements, especially for high-dimensional lattices. This work provides a foundation for developing lattice reduction techniques under the infinity norm.Authors: Nikita Muravya, Aleksandr Bespalov, Anna Vozianova
A finite metric space with $N$ points admits an exact representation in a pseudo-Euclidean space of dimension at most $N-1$. We study the minimum dimension required for relative-error approximation of squared distances. Our main result gives an upper bound for arbitrary metrics in terms of local distance ratios: for $4/5<\varepsilon<1$, dimension $O((N/k)\log N+kρ_k^4\log N/(\varepsilon-4/5)^2)$ suffices, where $ρ_k$ is the largest ratio, over all points, between the distance to the $k$th closest point (counting the point itself) and the nearest-neighbour distance. The proof combines a low-rank landmark approximation with a sparse correction controlled by its factorization norm. For metrics with distances in $[1,Φ]$, where $Φ\ge5$ is fixed, the worst-case dimension is $Θ(N)$ for $0<\varepsilon<4/5$, lies between $Ω(\sqrt N)$ and $O(\sqrt N\log N)$ for $4/5<\varepsilon<12/13$, and is $Θ(\log N)$ for $\varepsilon>(Φ^2-1)/(Φ^2+1)$. For $Φ>5$, an intermediate range remains without matching bounds. Sign-pattern counting yields the $Ω(\sqrt N)$ lower bound for $4/5<\varepsilon<12/13$, while Hadamard matrices give explicit linear lower bounds for $\varepsilon<4/5$ via a known approximate-rank estimate. We also construct configurations with null squared intervals whose minimum representation dimension remains $N-1$ for every $\varepsilon<1$. Finally, for every fixed $0<\varepsilon<3/5$, we show that the quadratic dependence on the parameter $C$ in the dimension bound derived from Deng et al.'s pseudo-Euclidean Johnson-Lindenstrauss lemma is necessary up to a logarithmic factor.Authors: Jadwiga Czyżewska, Karolina Drabik, Marek Sokołowski, Karol Węgrzycki
The class $\mathsf{PPP}$ captures fundamental total search problems, for which a solution is guaranteed to exist by the pigeonhole principle and the main challenge is to find it. We ask whether problems in this class admit significantly faster algorithms in the \emph{dense regime}. More concretly, we study \emph{binary collision Short Integer Solution} (SIS): given a matrix $A\in\mathbb{Z}_q^{n\times m}$ with $m>n\log q$, the goal is to find distinct $\underline{\mathbf{x}},\underline{\mathbf{y}}\in\{0,1\}^m$ with $A\underline{\mathbf{x}}=A\underline{\mathbf{y}}\pmod q$. Brute-force enumeration can be used to find a collision in $q^{\mathcal{O}(n)} \operatorname{poly}(|I|)$ time, and no significantly faster algorithm for that problem is known. We present an algorithm running in time $q^{o(n)}\cdot\operatorname{poly}(|I|)$ whenever the density parameter $δ:= m/(n\log q)$ is $ω(1)$.\footnote{All logarithms are in base $2$, and $|I|$ is the binary input length.} Building on reductions of Sotiraki et al.~(FOCS~2018), we obtain corresponding algorithms for dense variants of weak constrained SIS, Equal Vector Sums, Minkowski, and Blichfeldt. Our algorithm adapts techniques of Bhati et al.~(FOCS~2026), who gave a subexponential algorithm for Equal Sums in the dense regime and proved a tight conditional lower bound. Their conditional lower bound easily transfers to SIS and shows that the running time of our algorithms is essentially optimal.Authors: Shachar Lovett
We give a deterministic quasi-polynomial time algorithm for approximating the largest independent set in a graph. We show that if an $N$-vertex graph contains an independent set of size $2^{-t} N$, then we can find an independent set of size $2^t$ in quasi-polynomial time, for all $t$ up to a constant factor of $(\log N)^{1/3}$. This gives an approximation factor of $N / \exp((\log N)^{1/3})$, which has the same shape as known hardness results for quasi-polynomial time algorithms, up to a different exponent of the logarithm. The algorithm builds on a structural principle: a graph containing a large independent set must also contain a large sparse structured set, and such a set can be found efficiently. A greedy algorithm then extracts an independent set from it. Our proof draws on tools in additive combinatorics, in particular spreadness and sifting, to obtain the combinatorial structural results. We then convert these to efficient algorithms using pseudo-marginals obtained by semidefinite programming.Authors: Sergio Thoumi
We study promise graph coloring in one pass insertion-only adversarial streams. We give a randomized algorithm that distinguishes 3-colorable graphs from graphs that are not 6-colorable using $O(n^{3/2}\log(n/\varepsilon)\log n)$ bits of space. This provides a truly subquadratic space algorithm for a constant coloring gap, answering an open problem posed by Assadi, Sundaresan, and Yazdanyar [SODA 2026] for $q=3$. Combining this algorithm with the vertex-sampling lemma of Assadi et al.\ yields, for any $144\lceil\log_2 n\rceil\le Q\le n$, a one-pass decision algorithm distinguishing $3$-colorable graphs from graphs that are not $Q$-colorable using $O((n/Q)^{3/2}\log^5 n)$ bits of space. This improves upon the $\widetilde{O}((n/Q)^2)$ bound achievable via dynamic streaming techniques. Setting $Q=\lceil n^{1/3}\rceil$ yields a semi-streaming decision algorithm, answering the decision version of another open problem posed by Assadi et al. On the negative side, we prove that distinguishing $χ(G)\le q$ from $χ(G)\ge(q-1)^2$ requires $Ω(n^2/q^5)$ bits of space, improving upon the previously established $q^2/4$ threshold using the same space complexity.Authors: Adelmo Morrison Orozco, Nathan Sheffield, Ryan Williams
We show that adding "catalytic space" (which starts full and must have its original contents restored at the end of computation) provably speeds up time-and-space-bounded computation. In a natural output model, with $O(\log(n))$ free space and poly($n$) catalytic space, we give algorithms for sorting and the discrete Fourier transform running in time $n^{1+o(1)}$, and an algorithm for matrix multiplication running in time $n^{ω+ o(1)}$. In the same output model, without additional catalytic space, sorting and DFT are known to require time-space product $Ω(n^2)$, and matrix multiplication is known to require time-space product $Ω(n^3)$ [Borodin and Cook, 1982] [Beame, 1991] [Yesha, 1984] [Abrahamson, 1991]. This is the first unconditional demonstration that (uniform, non-relativized) catalytic logspace algorithms can outperform their (non-catalytic) logspace counterparts. We give several further results relevant to fast catalytic algorithm design. We observe that many applications of sorting, FFT, and fast matrix multiplication (e.g., kSUM, integer multiplication, and clique counting) can be performed catalytically, giving catalytic logspace algorithms matching (up to subpolynomial factors) the best known unbounded-space runtimes. Furthermore, we give a fast and simple catalytic algorithm for evaluating low-depth threshold circuits, improving the previously known runtime bound from $\widetilde O(|C|4^df)$ to $\widetilde O(|C|2^d)$, where $|C|$ is the total size (i.e. number of wires) of the circuit, $d$ is the depth, and $f$ is the maximum fan-in.Authors: Chengyuan Deng, Jie Gao, Kuijun Liu, Kevin Lu, Feng Luo, Puheng Weng, Cheng Xin
A directed graph on a point set $P$ in a metric space $(X,d)$ is navigable if for every ordered pair of distinct points $s,t \in P$, $s$ has an out-neighbor $v$ with $d(v,t) < d(s,t)$, so greedy routing always reaches the destination. Existing work on sparse navigable graphs mostly assumes bounded doubling dimensions. In this paper, we show that constant-dimensional hyperbolic spaces that do not have bounded doubling dimension also admit sparse navigable graphs. Specifically, for an $n$-point set in $\mathbb H^k$ with a constant $k$, we construct a navigable graph of size $O_k(n)$ with Steiner points, where each node has constant out-degree. We also show that Steiner points can be removed: every $n$-point set in $\mathbb H^k$ admits a navigable graph on the input points alone with $O_k(n)$ edges, though a single vertex may have out-degree $Ω(n)$. Furthermore, with a refined construction with $O_k(n\log n)$ edges and an accompanying greedy routing algorithm, we can obtain routing paths of expected $O(\log ^2 n)$ in both settings with or without Steiner points. With Steiner points, the maximum out-degree is bounded by $O_k(\log n)$. We complement these upper bounds with matching lower bound results. In the hyperbolic plane, there are point sets for which every navigable graph requires maximum out-degree $Ω(n)$, so the maximum linear out-degree above is unavoidable and constant out-degree is only possible with Steiner points. Next, we show that for every constant $α>1$, an $α$-navigable graph may require $Ω(n^2)$ edges, which rules out the standard route of using $α$-navigability to obtain greedy paths of bounded hops. Last, once the dimension $k$ reaches $Ω(\log n)$, there are point sets for which every navigable graph may require $n^{3/2-o(1)}$ edges, matching the upper bounds for general metrics.Authors: Dario Moschetti, Adam Polak, Jonas Schmidt
We present a near-linear time algorithm to find a maximum clique in circular arc graphs, the intersection graphs of arcs on the circumference of a circle, answering a 30-year-old open question posed by Bhattacharya and Kaller [J. Algorithms 1997] and Tiskin [CPM 2006]. Our algorithm runs in time $O(n\log^2 n)$, given $n$ circular arcs, where the graph is implicit. Previous approaches take at least quadratic time (unless the implicitly given graph is sparse). To overcome the quadratic barrier, we solve (structured and related) instances of bipartite matching by interpreting them as a single, offline 2D dominance problem, which in turn we model as a shortest paths problem in a planar grid graph. This allows for the final step, which builds on the theory of Monge matrices to obtain sparse representation and efficient distance computations in the grid graph. Additionally, we provide an observation about the structure of circular arc cliques that leads to an algorithm for the weighted version of the problem with a new parameter, the minimum load $d$, which we define as the minimum, over all points on the circle, of the number of arcs containing that point. The algorithm runs in time $O(dn\log\log n + n\log n)$. This is always at least as good as the previous best maximum weight clique algorithm, which runs in time $O(m\log\log n + n\log n)$, where $m$ denotes the number of edges in the implicit intersection graph, because the minimum load satisfies $d \le 2m/n$. [Abstract shortened to meet arXiv's requirements.]Authors: Lin Chen, Yuchen Mao, Guochuan Zhang
We study integer programs in standard form $\min\{\mathbf{c}^{\mathsf{T}}\mathbf{x}:A\mathbf{x}=\mathbf{b},\ \mathbf{l}\leq\mathbf{x}\leq\mathbf{u},\ \mathbf{x}\in\mathbb{Z}^n\}$, where $A\in\mathbb{Z}^{d\times n}$ and all entries of $\mathbf{b},\mathbf{c},\mathbf{l},\mathbf{u}$ are integers. Let $N$ be an upper bound on the absolute values of the entries of $A$. We give a deterministic algorithm running in time \[ \operatorname{poly}(L_{\rm in})+ f(d)\,N^{O(d)}\bigl(1+\log(c_{\max}+1)\bigr)^{O(1)}, \] where $c_{\max}$ bounds the absolute values of the costs and $L_{\rm in}$ is the input length. Prior to our work, the best known running time was $N^{O(d^2)}$ [Eisenbrand \& Weismantel'20], and it has been a fundamental open problem whether the exponent $O(d^2)$ can be improved to one linear in $d$. We answer this question affirmatively.Authors: András Czégel
The minimum Birkhoff decomposition problem asks for a representation of a doubly stochastic matrix as a convex combination of as few permutation matrices as possible. This NP-hard problem arises in the scheduling of switches in data centers and satellite systems, in random assignments in economics and in the statistics of rankings. We consider doubly stochastic matrices whose entries are given with a fixed number of decimal digits and look for exact decompositions whose weights have the same precision. We propose a parallel method with three parts. For matrices built from few permutation matrices, the first part reads the weights from the frequencies of the entries and places them on the matrix positions by a rule that, given the correct weights, never fixes a position wrongly. The second part computes lower bounds from pairs of rows or columns, which remain valid for real weights, and from certificates of a satisfiability solver. For matrices built from many permutation matrices, the third part runs a beam search over steps that each make at least one entry zero. On 375 test instances with up to 100 rows, the method proves optimality for 208 instances, and 197 of these proofs also hold for real weights. Of the 190 instances built from few permutation matrices, 187 are solved to proven optimality, 180 of them within one second. Compared with the best exact decompositions known before, the new decompositions are shorter for 278 instances and never longer.Authors: Mingxuan Sun, Zhiqiang Xu
Using the Hadamard matrix for dimension reduction can accelerate the computation due to the fast Hadamard transform. However, the previous target dimension bounds in terms of the Gaussian width depend on the ambient dimension. In this paper, we obtain the following ambient dimension free bound using three Hadamard-diagonal blocks. Let $H\in\mathbb R^{d\times d}$ be the normalized Walsh-Hadamard matrix, and let $D_1,D_2,D_3\in\mathbb R^{d\times d}$ be independent Rademacher diagonal matrices. We prove that for any symmetric set $T\subset \mathbb{S}^{d-1}$, \[ \mathbb P\left\{\sup_{\boldsymbol t\in T}\big|\frac dm\|P_ΩHD_3HD_2HD_1\boldsymbol t\|_2^2-1\big|\le\varepsilon\right\} \ge1-δ\] whenever \[ m\gtrsim\varepsilon^{-2}w(T)^2\log^2\frac eδ\,\log^4\!\left(e+\frac{w(T)}\varepsilon\log\frac eδ\right). \] Here $w(T)$ is the Gaussian width of $T$, and $Ω$ is a set of $m$ distinct coordinates chosen uniformly. This is the first ambient dimension free bound on the target dimension using Hadamard transforms, for an arbitrary symmetric set in terms of its Gaussian width. We also prove that it is impossible to obtain an ambient dimension free bound for an arbitrary set in terms of its Gaussian width using two Hadamard-diagonal blocks.Authors: Dariusz Dereniowski, Boting Yang
We consider graph search models, in which an invisible, omniscient and fast intruder can hide anywhere in the graph, and the goal is to design a \emph{search strategy} composed of a sequence of movements of \emph{searchers} that guarantees the capture of the intruder regardless of its actions. Our point of departure is the connected search model in which the cleared subgraph is always connected during the search process. In this paper, we initiate the study of the subgraph searching problems which arise from the following question: what happens if the number of searchers available is not sufficient to clear a given graph $G$? We propose an approach in which one wants to clear in a connected way as large subgraph as possible with the given $k$ searchers. In this context we study two problems: one problem, called the \emph{subgraph search}, is to find the maximum-sized subgraph whose search number is at most $k$, and the other one, called the \emph{protected subgraph search}, is to perform a partial search on $G$ leading to as many cleared edges as possible. Informally speaking, the difference lies in the fact that in the latter a recontamination may come from an edge never to be cleared and hence the partial search strategy needs to avoid such recontaminations. Having proved that both problems are computationally hard in general, we give efficient algorithms for $n$-vertex trees: an $\bigo(\min\{kn, n \log n\})$ time algorithm for the subgraph search and an $\bigo(\min\{2^{6k}kn, n^{8.571} \log n\})$ time algorithm for the protected subgraph search.Authors: Vishvajeet N, Shrinidhi Teganahally Sridhara
We study a natural synchronous greedy matching process in Erdős-Rényi random graphs $\mathbb{G}(n,p)$ and give a rigorous analysis of this parallel stochastic dynamics. The process evolves as follows: in each round, every unmatched vertex proposes to a uniformly random neighbour, and mutually proposing pairs are matched and removed from the graph, after which the process repeats on the residual graph. We consider the density regime $p=Θ(\log^{1+ε} n/n)$ for any constant $ε>0$, which lies just above the threshold for the existence of a perfect matching. We show that, with high probability, for $Θ(\log^{1+ε} n)$ rounds, every unmatched vertex keeps a constant fraction of its initial degree in the residual graph, simultaneously for all vertices and all rounds. By then, the process has matched a constant fraction of the vertices. Our analysis tracks fine-grained invariants that control the evolution of individual vertex degrees, rather than directly tracking the global degree distribution. At the local level, we analyze the per-round degree loss of a vertex via a neighbourhood-exposure martingale. We show that structural sparsity of $\mathbb{G}(n,p)$ yields $O(1)$ variance and thus the per-round degree loss is strongly concentrated around its conditional expectation. At the global level, these local concentration bounds control the increments of a martingale tracking cumulative degree loss over many rounds, allowing us to show that vertex degrees remain stable for $Ω(\log^{1+ε} n)$ rounds.Authors: Omri Ben-Eliezer, Tomer Even
The problem of Permutation Pattern Matching (PPM) asks, given a permutation $π:[n]\to[n]$, viewed as the point set $P=\{(i,π(i)):i\in[n]\}$, and a pattern $σ$ of small length $k$, whether $P$ contains an order-isomorphic copy of $σ$. The PPM problem and its (exact and approximate) counting variants have been studied extensively in the literature. We consider a preprocessing-query version: after preprocessing $P$, one must determine whether a query $P'\subseteq P$ contains $σ$, where $P'$ is obtained by intersecting $P$ with a geometric shape (e.g., an axis-aligned rectangle or $k$ such rectangles). This naturally generalizes the classical range query problem in computational geometry, which corresponds to the case $|σ|=1$. We extend the study of this problem from patterns of length $2$ to patterns of length $3$ (and in some cases beyond), and prove new fine-grained equivalences, separations, and applications: (1) Single rectangle: For all patterns of length $3$, detection can be done with $\tilde{O}(n)$ preprocessing and $\tilde{O}(1)$ query time. The proof goes through a new tool of independent interest: reductions from rectangle queries to a simpler family of slab queries. (2) Multiple rectangles: For $σ=132$, detection is equivalent to the online set disjointness problem; we also show connections to online $k$-set disjointness. To our knowledge, this is the first equivalence between a PPM-type problem and online set disjointness, a problem playing a fundamental role in fine-grained complexity. (3) Counting: As applications, we obtain an $O(n^{1.725})$ time algorithm for exact counting of $5$-patterns based on the rectangle-to-slab reduction, improving upon [Beniamini and Lavee, ICALP 2025], and an $\tilde{O}(n^{7/4})$ approximate counting algorithm for $6$-patterns, the first to break the $O(n^2)$ barrier for $6$-patterns.Authors: Alina Ene, Huy L. Nguyen
We give a strongly polynomial time algorithm for submodular function minimization with overall running time $\widetilde{O}(n^{2}\mathsf{EO}+n^{3})$ time, where $\mathsf{EO}$ is the running time of a single evaluation of the function. Our algorithm improves upon the previously fastest strongly polynomial algorithms of Lee et al. (FOCS 2015), Dadush et al. (SODA 2018), and Jiang et al. (SODA 2024) that run in time $\widetilde{O}(n^{3}\mathsf{EO}+n^{4})$. Similarly to prior works, our work combines a cutting plane algorithm with the combinatorial arc-finding framework of Fleischer et al. (JACM 2001). We achieve our faster running time by developing an algorithm that runs the cutting plane method end to end, without restarting after discovering arcs and contracting strongly connected components.Authors: Zhidan Li, Kuan Yang
We study the mixing time of the single-site Glauber dynamics for sampling proper \(q\)-colorings on sparse Erdős-Rényi random graphs \(\mathcal{G}(n, d/n)\). We prove that, whenever \(q \ge (1 + o_d(1))d\), Glauber dynamics mixes in polynomial time with high probability over \(\mathcal{G}(n, d/n)\) for all sufficiently large integer \(n\). This improves the previous bound \(q = (α^* + o_d(1))d\) where \(α^* = 1.7632...\) is the unique solution of \(x = \exp(1/x)\) on \([1, \infty)\) by Efthymiou, Hayes, Štefankovič, and Vigoda (SODA, 2018) and asymptotically matches the uniqueness threshold on infinite regular trees. Our proof has three main ingredients. First we establish logarithmic bounds on the spectral and coupling independence constants of the Gibbs distribution by extending the tree analysis of Chen, Liu, Mani, and Moitra (J. ACM, 2026). Second, we extend the entropy-factorization framework for two-spin systems on random graphs, developed by Bezáková, Galanis, Goldberg, and Štefankovič (TALG, 2024), to proper colorings by introducing a buffer around high-degree vertices. Finally, we compare the resulting heat-bath block dynamics with the single-site Glauber dynamics.Authors: Dani Dorfman, Uri Zwick
Mean-Payoff Games (MPGs) form an interesting family of deterministic, infinite-duration, zero-sum, turn-based games played by two players on a finite weighted directed graph. The goal of the players is to minimize, respectively maximize, the $\textit{limiting average}$ of the costs of the edges on an infinite path constructed by the two players. The complexity of solving MPGs is a long-standing open question. The decision problem associated with these games is known to be in $\text{NP}\cap \text{co-NP}$, and even $\text{UP}\cap \text{co-UP}$, yet the problem is not known to be in $\text{P}$. This is one of the simplest combinatorial problems with such a status. A full solution of an MPG gives the $\textit{value}$ of each vertex of the game, along with a pair of $\textit{optimal strategies}$ for the two players. (Each player has a succinct $\textit{positional}$ optimal strategy.) The problem of finding optimal strategies for the players given the values of all vertices is known as the $\textit{strategy recovery}$ problem. We describe a simple reduction from the problem of solving MPGs to the strategy recovery problem for MPGs. This shows that the strategy recovery problem for MPGs is essentially as hard as solving MPGs from scratch, i.e., without knowing the values. The reduction uses simple $\textit{game transformations}$ and simple $\textit{self-reducibility}$ and $\textit{peeling}$ arguments. This answers a question of Andersson and Miltersen. Mamino obtained a similar result for $\textit{stochastic}$ games with a limiting average objective, but his technique does not extend to deterministic games such as MPGs. We go one step further and show that finding an optimal strategy for one of the players of an MPG remains hard even if an optimal strategy of the second player, and hence all the values, are known.Authors: Edith Cohen, Uri Stemmer
Linear sketches estimate properties of high-dimensional inputs from a fixed low-dimensional projection. At constant accuracy, randomized Euclidean-norm sketches, notably the Johnson-Lindenstrauss transform, support exponentially many nonadaptive queries in sketch dimension $k$. For adaptive black-box queries, known privacy-based defenses guarantee $\widetildeΩ(k^2)$ and it remained open whether stronger guarantees were possible. Prior attacks used more queries, restricted the responder, or provided weaker failure guarantees. We show that the quadratic guarantee is optimal up to logarithmic factors, even with a computationally unbounded responder that knows the matrix, attack algorithm, history, and query distributions and may change its randomized rule after every query. For every fixed hidden $A\in\mathbb{R}^{k\times n}$ with $n>40k$ and target accuracy $α\in (0,1]$, our black-box attack uses $O(k+α^2k^2\log(2+α^2k))$ queries in $\widetilde{O}(1+α^2k)$ adaptive rounds to force, with constant probability, a round in which a constant fraction of answers have $Ω(α)$ relative error. Our results clarify the limits of defending a fixed compressive linear representation by adapting the prediction rule.Authors: Krishnakumar Balasubramanian, Siddharth Bhandari, Shiva Prasad Kasiviswanathan
We study quantization for inner-product estimation when storage and reading have separate budgets. In the static bit-probe model [Yao, 1981], an encoder stores $w$ bits about $x$ before seeing a query $y$, and a reader probes at most $rAuthors: Sunny Atalig, Marek Chrobak, Petr Kolman, Claire Mathieu, Hans Raj Tiwary
In the \emph{connected multicut problem for weighted trees}, the instance is an edge-weighted tree $T = (V,E,ω)$, a set of terminals $Γ\subseteq V$, and a set of pairwise ``conflicts'' between these terminals represented by edges of a conflict graph $\mathcal{C} = (Γ,\mathcal{F})$. A \emph{connected multicut} for this instance is a partition $\mathcal{M}$ of the vertex set $V$ into subsets called the \emph{components of $\mathcal{M}$}, where each component induces a subtree of $T$, contains at least one terminal, but does not contain any conflicting terminal pair. Two cost functions for multicuts are considered: in the min-sum variant, we minimize the total weight of the edges between different components of $\mathcal{M}$, and in the min-max variant, we minimize the maximum, over all components, of the total weight of edges leaving the component. In the first part of the paper, we focus on algorithms for the min-max variant, for which we give a $2$-approximation algorithm for the unweighted case, a $(2+ε)$-approximation algorithm for the general case, and a mildly exponential exact algorithm for the unweighted case. In the second part of the paper, we study algorithms that take advantage of the structure of the conflict graph. We first give a polynomial-time exact algorithm for the min-max variant when $\mathcal{C}$ is a clique (the variant referred to in the literature as the \emph{multiway cut}). Next, we generalize this result by providing polynomial-time exact algorithms, for both variants, for instances whose conflict graph has constant \emph{split complexity} --- a new parameter that refines the concept of neighborhood diversity previously studied in the context of parameterized complexity. This unifies and generalizes previous results for the min-sum variant when conflict graphs are complete multipartite graphs or unions of cliques.Authors: Batya Kenig
A potential maximal clique (PMC) of a graph $G$ is a nonempty vertex set that forms a maximal clique in some minimal triangulation of $G$. Listing the PMCs of a graph is a key step in exact algorithms for computing treewidth, minimum fill-in, and related graph parameters. We present a deterministic algorithm that enumerates all PMCs of cardinality at most $k$ in an $n$-vertex graph $G$, without repetition, with delay $2^{O(k^3)}n^4\log n$. This bound also covers the preprocessing time before the first output, the time from the last output to termination, and the total running time when no such PMC exists. At the core of our enumeration algorithm is a procedure that solves the following constrained search problem within the same time bound: given sets of required and excluded vertices $I,O\subseteq V(G)$, find a PMC $Ω$ of size at most $k$ satisfying $I\subseteqΩ$ and $Ω\cap O=\emptyset$, or determine that none exists. Our enumeration algorithm directly supports these inclusion and exclusion constraints as well. Our approach builds on the \emph{recursive understanding} technique of Chitnis et al.~\cite{chitnis2016} and the reduction to unbreakable graphs of Lokshtanov et al.~\cite{lokshtanov2018}. A graph is $(q,k)$-unbreakable if no removal of at most $k$ vertices leaves two disjoint unions of connected components that each contain more than $q$ vertices. We first solve constrained PMC search on $(q,k)$-unbreakable graphs, and then apply this procedure to replace separated subgraphs with graphs of size $2^{O(k^2)}$ that preserve the existence of a constrained solution for every graph attached along the shared boundary.Authors: Kaito Harada, Tatsuya Terao
We study the replacement paths problem in unweighted directed graphs with $n$ vertices and $m$ edges under one or two edge failures. We give simpler and faster algorithms for both settings. Both algorithms are based on a new technique, which we call \emph{modulo-layer hitting sets}. For the single-failure setting, we obtain a simple deterministic combinatorial algorithm running in $O(m\sqrt{n})$ time, which is nearly optimal under the combinatorial Boolean Matrix Multiplication (BMM) conjecture. In addition to removing the logarithmic overhead of the deterministic $\tilde{O}(m\sqrt{n})$-time algorithm of Alon, Chechik, and Cohen~[ICALP'19], our algorithm admits a much simpler implementation and analysis. For the dual-failure setting, we obtain a randomized combinatorial algorithm running in $\tilde{O}(n^{3-1/4})$ time. This improves upon the previous $\tilde{O}(n^{3-1/18})$-time combinatorial algorithm of Chechik and Zhang~[ICALP'24].Authors: Yilong Feng, Yaonan Jin, Xiaowei Wu, Xinyue Xiang
We study mean-based algorithms for single-choice prophet inequalities: the algorithm knows the number of variables and the mean of their maximum, but not their distributions. For arbitrary independent variables in a fixed order, we can already achieve the optimal $1/2$ competitive ratio using only this mean. For i.i.d. variables and prophet secretary, however, we previously knew only a $1-1/e$ guarantee, which is far away from the ratios with full distribution information. We improve the guarantees in both settings using a simple and natural algorithm: we fix a continuous decreasing threshold function that depends only on the mean and accept the first variable exceeding its threshold. For i.i.d. variables, we prove a $0.7419$ competitive ratio. For the prophet secretary, we prove a $0.6902$ competitive ratio.Authors: Julian Born, Yann Disser, Linda Thelen
We give an O(log k)-competitive randomized algorithm for weighted paging with delay. This improves upon the O(log k log n)-competitive algorithm of Gupta, Kumar, and Panigrahi (STOC 2020, SICOMP 2022) by removing the dependence on the number n of pages. Without delay, the optimal competitive ratio of randomized algorithms is Theta(log k), and since the lower bound carries over, our bound is tight. Our algorithm is fractional and combines mirror descent, used by Bubeck et al. (STOC 2018) for weighted paging without delay, with preemptive service, introduced by Azar et al. (STOC 2017) for online service with delay: when a request is served, an increase in the mirror descent potential is offset by preemptive service to other pending requests, with a budget derived from the mirror descent path. To obtain a randomized algorithm, we use the online rounding of Bansal, Buchbinder, and Naor (FOCS 2007) from classical paging.Authors: Siyuan Chen, Suixiang Gao, Zheyu Jiang, Wenguo Yang
We give a randomized combinatorial \((1/2 - \varepsilon)\)-approximation for nonnegative non-monotone \(k\)-submodular maximization under a fixed number \(d\) of knapsack constraints, for \(k \ge 2 \). The algorithm selects whole elements and follows the proportional top-2 rule of Chen et al. \cite{chen2026}: it samples from the two labels with the largest marginal gains, with probabilities proportional to the positive parts of these gains. Extending their single-knapsack Bellman analysis, we construct a common resource potential and associated resource weights, with potential losses charged to greedy gains. Since these weights depend on the unknown optimum, we discretize their defining coefficients and enumerate monotone guesses over phases determined by resource consumption. This yields an algorithm using at most $\mathcal{A}(d,\varepsilon)(nk+1)^{H+2}$ value queries, where $n$ is the number of elements, $\mathcal{A}(d,\varepsilon)$ depends only on $d$ and $\varepsilon$, and $H=O(d \log(2d) / \varepsilon^2)$. The approximation ratio can be made arbitrarily close to the optimal oracle threshold for \( k=2 \) and is asymptotically tight as \(k \to \infty\).Authors: Mohammad Afzali, Hassan Ashtiani, Adam Smith
We study differentially private black-box evaluation of arbitrary high-dimensional functions. Given a dataset $S$ and query access to a function $f$---whose sensitivity may be unknown or unbounded---the goal is to privately output an approximation to $f(S)$. The black-box evaluator can only query the value of $f$ over a down neighborhood of $S$ (i.e., those subsets of $S$ that are obtained by removing a bounded number of elements from $S$). We design generic black-box evaluators for both pure and approximate differential privacy through a reduction to high-dimensional private quasi-concave optimization (QCO). Our black-box evaluator enjoys a geometric notion of utility. Consider the vectors obtained by applying $f$ on sets in a down neighborhood of $S$. With high probability, the evaluator's output is guaranteed to be in the convex hull of these vectors. Our work generalizes the result of Linder et al. [LRSS25] for real-valued function evaluation to high dimensions. It also recovers the private center-point guarantees of Beimel et al. [BMNS19], with an explicit additive approximation to maximum Tukey depth. We also apply our evaluators to user-level quasi-concave and convex optimization, showing how they can improve upon the sample-and-aggregate baseline of Nissim et al. [NRS07] by replacing the multiplicative data overhead with an additive overhead. Finally, we show that our formulation of high dimensional black-box evaluation and high dimensional private QCO are equivalent up to a factor of the dimension: the hardest private evaluation instances already arise from the cases that $f$ is a (non-private) quasi-concave optimizer.Authors: Gabriel Chen, Yu Cheng, Alice Wang
We consider the metric distortion framework for voting, where $n$ voters and $m$ candidates are embedded in an unknown metric space. A voting rule selects a candidate using only voters' ordinal preferences, and its distortion is the worst-case ratio between the social cost of the selected candidate and the minimum social cost. We study how round complexity trades off against total communication in deterministic voting protocols with low distortion. Deterministic rules can achieve the optimal distortion of $3$ in one round by eliciting complete rankings using $Θ(nm\log m)$ bits, while a direct sequential implementation of PluralityVeto achieves the same distortion using only $O(n\log m)$ bits but requires $Θ(n)$ rounds. Our main result is TreePluralityVeto, a deterministic voting protocol that, for every $r\ge 2$, achieves distortion at most $2r-1$ using at most $r$ rounds and $O(n\log m+n s^{1/(r-1)}\log s)$ bits of total communication, where $s = \min\{n, m\}$. The protocol runs PluralityVeto on a hierarchical partition of the voters, collecting restricted rankings in parallel at each level. The branching factor controls the tradeoff between rounds and communication, and a matching-based analysis shows that each level increases the distortion bound by at most $2$.Authors: Kourosh Mirsohi, Melika Gorgi, Erfan Hajihashemi
Exact forward triangle listers orient each edge of a graph by a vertex order. The order does not change the output, but it changes the work. For the adaptive lister, which scans the smaller of the two forward neighborhoods, the number of candidate tests is a known sum of minima of forward degrees, but how to optimize it had not been characterized. We show that this work is a concave function of the forward degrees, so choosing an order is concave minimization over the orientation polytope, whose vertices are the forward-degree vectors of orders. A single sort therefore rounds any point of the polytope, including the out-degree vector of any orientation, to an order with no more work, with a computable lower bound on the improvement. Minimizing the work is nevertheless NP-hard and APX-hard on triangle-free graphs of maximum degree three, and under the Unique Games Conjecture it has no polynomial-time constant-factor approximation. We also analyze logistic score relaxations and the large-graph limit of degree-based orders; on random cubic graphs, the expected work of every degree-based order is asymptotically at least $2.43$ times the expected optimum. Tangent refinement followed by iterated local search reduces the work by \HeldTIKMean\% on average on nine held-out networks fixed by a pre-registered protocol, and by \NSFrozenTILSMean\% in a supplementary rescoring, specified in advance, against a stronger reference that adds the published Neigh local search. The gains are in candidate tests; we observe no reproducible wall-clock speedup.Authors: Filippo di Gravina
We give a deterministic worst-case algorithm for exact Batched Range Mode on an arbitrary array of length n and a batch of Q intervals. The algorithm returns the mode frequency and the smallest mode identifier for each query in time (n+Q)^(tau+o(1)), where tau = 5 - sqrt(13) = 1.394448724536... . The algorithm combines virtual occurrence windows and block-boundary snapping with a query-restricted min-plus product whose first operand is column-monotone and whose second operand is row-monotone. A deterministic modular verifier uses geometric and query potentials to bound the same active regions; false modular matches are corrected by offline orthogonal range updates. The final analysis uses the sharper rectangular exponent curve of Uznanski (2026), together with exact rational parameter balancing and a transfer to prime fields. The analysis covers every frequency scale and arbitrary batch sizes. Exact frequencies and the smallest mode identifiers are recovered without increasing the exponent.Authors: Thomas Bläsius, Max Göttlicher, Martin Schirneck
The Transversal Hypergraph problem asks to enumerate (list) all inclusion-minimal hitting sets of a hypergraph. It usually assumes that the input is completely known and does not change over the course of the enumeration. In many applications, the underlying hypergraph is too large or expensive to compute. This motivated the implicit hitting set framework [Chandrasekaran, Karp, Moreno-Centeno, and Vempala, SODA 2011] for the corresponding optimization problem of finding a smallest hitting set. Access to the input is given by an oracle that either confirms that a query set $S$ is a hitting set, or reveals a new hyperedge disjoint from $S$. We adapt this framework to enumeration. We show for a general class of algorithms that they are able to find all hitting sets when given access to such an oracle, even if the hypergraph is a priori unknown. We also prove that the current fastest Transversal Hypergraph algorithm, Minimal-to-Maximal Conversion Search by Murakami and Uno [DAM 2014], belongs to this class. We then engineer an implicit hitting set algorithm for the enumeration of minimal power dominating sets in graphs. A power dominating set is a selection of vertices that "observe" all vertices by exhaustively applying two rules: if a vertex is dominated by the selection, it becomes observed; and if an observed vertex has a unique unobserved neighbor, this neighbor becomes observed as well. An experimental evaluation on a collection of power grid instances from the literature shows that our approach achieves very high throughput rates.Authors: Sudipto Guha
The multi-armed bandit problem models the trade-off between exploration and exploitation. In this paper, we study the variant where exploration has a hard budget and precedes exploitation. Prior guarantees include a 1/3 approximation by Guha and Munagala using Lagrangian duality, and a 4/27 approximation by Ma against a primal linear programming relaxation for a more general model. We show that the analyses of both algorithms are tight, even when their relaxations are asymptotically exact. We provide a different efficient algorithm that achieves a 0.43 approximation. We then provide an efficient algorithm whose guarantee approaches 1-e^{-1} approx 0.63 for bounded exchangeable reward observations in a non-vanishing regime, which is asymptotically tight against natural linear programming relaxations. The technique also gives certificates for stopping sequential model evaluation.Authors: Michael Kapralov, Jakub Łącki, Silvio Lattanzi, Guy Weissenberg
Given a vertex $v$ in a large bipartite graph $G$, can one quickly find a small densely connected region near $v$? This is the algorithmic core of many fraud detection, community detection, and recommender systems. One would like a local algorithm, i.e., an algorithm that probes $G$ in only a small number of locations to find such a region. Our main contribution is the first constant-factor local approximation, independent of the maximum degree of the graph, for the classical notion of bipartite density: if the sides of a bipartite subgraph are $S$ and $T$, its density is $d(S,T):=e(S,T)/\sqrt{|S||T|}$, where $e(S,T)$ is the number of edges between $S$ and $T$. We consider cohesive dense subgraphs, since every dense subgraph contains a cohesive core of at least the same density. For such a cohesive dense subgraph $S\mathbin{\dot\cup}T$ with at most $k$ vertices per side, our algorithm, starting from any vertex in $S\mathbin{\dot\cup}T$, uses $O_ε(k^{4+ε})$ neighbor queries to find a subgraph $X\mathbin{\dot\cup}Y$ of density $Ω_ε(d(S,T))$ on $O_ε(k^{2+ε})$ vertices, for every fixed $ε>0$. Our result improves upon the result of Andersen (2010), whose approximation guarantee depends logarithmically on the maximum degree. We complement our positive result with information-theoretic and computational limitations showing that the quadratic dependence on $k$ in the output size is essentially unavoidable for constant-factor approximation. Our main technical innovation is an adaptation of the Lovász-Simonovits curve to the bipartite density problem, based on weak-$\ell_p$ norm bounds.Authors: Florian Hörsch, Marta Piecyk, Krisztina Szilágyi
Given a mixed graph $G$ and an ordered pair $(u,v)$ of vertices in $V(G)$, we say that an orientation $\vec{G}$ of $G$ satisfies $(u,v)$ if $v$ is reachable from $u$ in $\vec{G}$. We consider problems in which we seek orientations that satisfy a maximum number of pairs. We distinguish between two different problems. In the most general problem called Fixed Pairs Maximum Mixed Reachability Orientation (FPRO), a multiset $P$ of ordered pairs of vertices in $V(G)$ comes with the input. In the more restricted problem All Pairs Maximum Mixed Reachability Orientation (APRO), $P$ contains exactly one copy of every ordered pair of distinct vertices in $V(G)$. We compare the computational complexity of FPRO and APRO in two ways: First, we show that both FPRO and APRO behave similarly when it comes to approximation. Namely, they both admit an asymptotic approximation, but are unlikely to admit a constant factor approximation. Then, we consider the parameterization with respect to the treewidth of the underlying graph of the input mixed graph. We show that here the complexities of FPRO and APRO differ significantly. While it is well-known that FPRO is NP-hard even when this parameter is 1, we show that APRO is XP with respect to this parameter. On the other hand, we give a $W[1]$-hardness result for APRO.Authors: Kehang Zhou, Pinyan Lu
Chain-of-thought (CoT) enables constant-bit-size transformers to perform general-purpose computation through generated tokens (Li and Wang, 2025a), whereas looped transformers carry out the same computation by recurrence in hidden states (latent thought). We construct a family of constant-bit-size looped transformers that interpolates between CoT and latent thought. For a prescribed loop count $L=L(n)$ and a fixed integer $k\ge1$ satisfying $s(n)^{1/k}=Ω(L)$, our transformer simulates a time-$t(n)$, space-$s(n)$ Turing machine using a context window of $O(s(n)/L)$ and $O(t(n)s(n)^{1/k}/L)$ generated tokens, reducing both resources by a factor of $L$ relative to the corresponding unlooped queue-machine simulation. The construction also holds with softmax attention at constant bit-size, under the finite-precision kernel specified in this paper.Authors: Chenghua Liu, Boning Meng
We give a simplified, self-contained proof of OpenAI's FPRAS for counting perfect matchings in general graphs. As in the original proof, we use a restricted Poincaré inequality for two matchings to sample weighted perfect matchings and estimate their total weight. We simplify the proof of this inequality by isolating parts of alternating cycles directly on the original vertex set and controlling the resulting error terms. This avoids the auxiliary vertices and tree constructions used in the original proof. The argument preserves the required parameter bounds and yields the same FPRAS guarantee.Authors: Siyuan Chen
We prove that, for every \(\varepsilon>0\), a \((\frac{k}{2k-1}+\varepsilon)\)-approximation algorithm for maximizing monotone \(k\)-submodular functions requires exponentially many value-oracle queries. This improves the \(\frac{k+1}{2k}\) oracle bound of Iwata, Tanigawa, and Yoshida. Their \(\frac{k}{2k-1}\)-approximation algorithm therefore gives the exact threshold in the monotone setting. For \(k\ge5\), our bound also matches, up to an arbitrarily small loss, Aggarwal's recent approximation guarantee for non-monotone \(k\)-submodular maximization.Authors: Runtian Ren, Shengcai Liu
We study capacitated line aggregation with per-batch maximum delay. Requests arrive over time at locations on a rooted half-line and are served in instantaneous batches of at most $k$ requests. Each batch pays the distance to its farthest request plus the waiting time of its oldest request. The objective is to minimize the total cost. We give a deterministic online algorithm with competitive ratio $36+12\sqrt3$. The algorithm uses a Next Fit idea along paths of nested time intervals: it assigns a new group to an existing batch when a path-load test permits, and opens a new batch otherwise. The path load controls both capacity and the cost of opening new batches. Randomizing the common scale improves the expected competitive ratio to $(18+6\sqrt3)/\ln2$ against an oblivious adversary. Both guarantees extend to arbitrary indivisible request sizes. We also study capacitated LAD in the learning-augmented model. Advice revealed at its service times allows $(1+ε)$-consistency against every complete feasible advice schedule and $O(ε^{-2})$-robustness. The analysis charges repeated switches to successive decreases in the remaining advice cost.Authors: Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manmatha Roy
The arithmetic regularity lemma of Green is a fundamental tool in additive combinatorics, providing a decomposition of arbitrary subsets of finite Abelian groups into pseudorandom pieces with respect to Fourier analysis. Over the years, it has found numerous applications in combinatorics, property testing, and theoretical computer science. However, Green's proof is existential, and many algorithmic applications require an efficient procedure for constructing the underlying regular decomposition. De, Nadimpalli, and Servedio (SODA 2022) developed a query-efficient constructive regularity framework over $\mathbb{F}_2^n$ and explicitly raised the problem of extending their dimension-independent sumset-estimation algorithm to other finite Abelian groups. In this work, we resolve this question for finite Abelian groups of constant torsion. We develop the first constructive version of Green's {\em Arithmetic Regularity Lemma} in this general setting. Given oracle access to a subset of the group, our algorithm computes an implicit description of a regular decomposition together with an oracle representation of a structured subset satisfying the guarantees of Green's lemma. The algorithm runs in time and query complexity polynomial in the regularity parameters and the tower bound, while remaining independent of the size of the ambient group. As applications, we obtain efficient algorithms for removing linear configurations and approximately counting linear images, including weighted sumsets and suitable matrix systems of Cauchy--Schwarz complexity one, over finite Abelian groups of constant torsion. Our results provide a unified algorithmic framework extending dimension-independent constructive arithmetic regularity and its applications beyond $\mathbb{F}_2^n$.Authors: Tudor Cardas, Lucas Perotin, Bertrand Simon
Ski rental is one of the most fundamental online problems, where an agent repeatedly decides whether it should continue renting for a service, or buy it at a one-time fixed cost. In classic online analysis, an adversary may freely select any arbitrary time horizon $t$ after which the instance terminates, hence leading to strong competitive ratio lower bounds of 2 (deterministic) and $e/(e-1)$ (randomized). We consider a novel but natural model aiming at limiting the adversary's power without degrading its flexibility. A stochastic signal, containing no information apart from its arrival time, is transmitted to the algorithm at a time drawn from a known distribution scaled to $[0,t]$. This framework allows us to account for visible effects of the adversary's choice to the algorithm. Focusing as a first step on uniform distributions, we show that the best possible competitive ratios are approximately $1.478$ (deterministic) and $1.438$ (randomized). Surprisingly, simplistic deterministic strategies already achieve a performance of $1.489$.Authors: Yuval Gil, Magnús M. Halldórsson
We study fully dynamic $(Δ+1)$-coloring against an adaptive adversary. Behnezhad, Rajaraman, and Wasim (SODA 2025) gave the first algorithm with $\tilde O(n^{8/9})$ amortized update time, later improved to $\tilde O(n^{2/3})$ by Flin and Halldórsson (ICALP 2025). We give a fully dynamic $(Δ+1)$-coloring algorithm with $\tilde O(\sqrt n)$ \textbf{worst-case} update time. Unlike previous algorithms, it avoids sparse-dense decompositions and relies only on elementary data structures, resulting in a short self-contained algorithm and analysis. Moreover, it avoids global recoloring, resulting in a worst-case recourse of $3$.Authors: Daniel Dadush, Zhuan Khye Koh, Bento Natura, Neil Olver, László A. Végh
Recently, Allamigeon, Dadush, Loho, Natura, and Végh (ADLNV, SICOMP 2025) introduced an interior point method for linear programs whose number of iterations is bounded by the so-called straight line complexity (SLC) of the instance. This yields a strongly polynomial bound on the number of iterations of the corresponding interior point algorithm for broad classes of linear programs. In particular, in the companion paper we give a strongly polynomial straight line complexity bound for two-variable-per-inequality linear programs. However, in order to obtain a strongly polynomial algorithm for these classes, one also needs to address two important technical issues: initialization and bit-complexity bounds. Standard IPM initialization techniques either require numerical estimates that cannot be obtained in the strongly polynomial model, or involve modifying the instance in ways that do not preserve the geometry of the original LP, potentially affecting the SLC. In this work, we present an initialization framework for interior point methods for linear programming, along with a rounding procedure that ensures the continued feasibility of the IPM. We develop a multistage scheme in which each stage can be initialized in strongly polynomial time given the output of the previous stage. Additionally, we address the challenge of controlling the bit complexity of each iterate throughout the algorithm. To this end, we show that it is possible to represent iterates as low-complexity convex combinations of vertices and extreme rays. Our combinatorial rounding step is independent of the algorithm in ADLNV 2025, and can be applied more broadly in the context of path-following methods.from ECCC Papers
from Scott Aaronson
As I announced on this blog a couple weeks ago, I’m teaching a new course this semester at UT Austin, entitled AI Alignment Theory. To call such a course “timely” seems like an understatement; this is the first course I’ve ever taught for which multiple gargantuan developments relevant to the course have happened while I was teaching it.
Since AI alignment is still a field with no standard textbook (although that might be changing), no accepted body of mathematical theory, etc. etc., the way we’ve been running the course is like a humanities discussion seminar, albeit one that happens to be in a CS department and to include technical results from time to time. Basically, in each class session, a student “rapporteur” gives a talk on an AI alignment reading—which include “ancient” readings (from way back in 2016), “modern” readings (from, say, last week), and everything in between—and then we freely discuss and debate whatever was presented, with my own role mostly limited to that of gadfly (occasionally I’ll do a mini-lecture on some technical concept).
Anyway, two weeks ago, I promised a list of the papers and other writings that we’ve been discussing, as well as student “rapporteur reports” on those papers, which cover not only the papers themselves, but the students’ thoughts about the papers and (anonymized) summaries of points raised during our class discussion. People have been bugging me for that ever since.
Since I am to please, here you are, without further ado! I’ll continue to update the list as the semester progresses, so that this post can serve as a central public repository for the course.
(More readings TBD, until the semester ends!)
Thanks to my TA, Lin Lin Lee, for her help in getting all of this together.
Update: I welcome elevated discussion of these papers and rapporteur reports in the comment section; some of the students might chime in too! Because of the connection to an academic class, though, in this post I’ll be especially ruthless in keeping out nonconstructive or off-topic comments.
from ECCC Papers
By Ittai Abraham, Gilad Stern
Authors: Weikang Li
We prove that a quantum walker cannot search a two-dimensional lattice in Grover's $O(\sqrt N)$ time, resolving the long-standing open question posed by Aaronson and Ambainis in 2003. A walker that hops between neighbouring sites of an $L\times L$ lattice, $N=L^2$, needs $Ω(\sqrt{N\log N})$ local steps at least to find a marked vertex, even with unlimited memory and free queries. Hence, Tulsi's algorithm is asymptotically optimal. Our proof rests on a surprising correspondence with classical electrostatics. We treat the marked vertex as a point charge and weight the overlap between the walker's states with and without the mark by the potential drop, which vanishes where queries act. Only local steps change this weighted overlap, at a rate limited by the field energy, so the lower bound is set by the self-potential of the charge. In the plane this self-potential grows logarithmically with system size, like the Coulomb potential, leading to the extra root-logarithmic factor. Several marked vertices turn the charge into a conductor, and the lower bound depends on their arrangement through its capacitance.Authors: Eike Best, Raymond Devillers, Petr Jančar, Matěj Ošťádal
A ring Petri net (weighted circuit, cyclic weighted T-system) consists of a single directed circuit with arbitrary positive arc weights. We show that deciding liveness of ring Petri nets is coNP-complete, and that coNP-hardness holds in the strong sense already for token-conserving rings, in which every transition consumes and produces the same number of tokens. The proof is a short reduction from the covering problem for systems of residue classes (the complement of Simultaneous Incongruences). Together with a known reduction to circuits, it follows that liveness of weighted T-systems (weighted marked graphs, synchronous dataflow graphs) is coNP-complete, and coNP-hard in the strong sense. As a further consequence, the halting problem for chip-firing on simple directed graphs is NP-complete, which answers a question of Farrell and Levine. On 7 October 2026, the problem of liveness was posed to the AI model Claude Opus 5.5 (Anthropic), which found the reduction, also suggesting the application to the chip-firing problem, and wrote a first version of this paper; the human authors checked it and, together with the model, revised it iteratively into the present form.Authors: Manuel Aprile, Luca Ferrarini
The Strong Total Cover Problem (STCP) is a novel covering problem defined on a graph $G = (V, E)$, where the objective is to find a minimum-cardinality subset $T \subseteq V \cup E$ such that every element of $V \cup E$ is covered. In this setting, a vertex covers itself and all its incident edges, while an edge covers itself together with its two endpoints. The STCP resembles classical covering problems such as Vertex Cover and Edge Cover problems, and naturally arises as the dual of the total matching problem. In this paper, we investigate the STCP from algorithmic, complexity, and polyhedral perspectives. We first establish close connections between STCP, the Dominating Set Problem, and the Maximum Induced Matching Problem. These relationships provide structural insights, imply the NP-hardness of STCP, and identify graph classes for which the problem is polynomial-time solvable. We then investigate the weighted version of STCP, showing that it remains NP-hard even on complete graphs with binary weights. On the other hand, we present a 2-approximation algorithm, and a polynomial-time algorithm for complete bipartite graphs. On the polyhedral side, we introduce the Strong Total Cover Polytope and derive several families of valid inequalities, some of which are shown to define facets. Finally, we provide a complete linear description of the associated polytope for triangular cactus graphs, revealing an interesting contrast with the considerably more intricate facial structure of the dominating set polytope on cactus graphs.Authors: Igor C. Oliveira
We establish an unconditional super-polynomial separation between quantum and classical PAC learning of Boolean functions under the uniform distribution in the large error regime. For every advantage $λ(n) = n^{-ω(1)}$, we construct a concept class that a polynomial-time quantum learner learns to agreement $1/2+λ(n)$ with success probability at least $1-1/n^k$. The learner uses only quantum random examples and outputs a polynomial-size deterministic classical circuit. In contrast, no polynomial-time classical learner achieves agreement $1/2 + λ(n)/n^k$ with success probability greater than $1/n^k$, even with membership queries. To achieve this, we develop a nearly-optimal quantum learner that uses quantum random examples to produce a hypothesis achieving a prescribed correlation with an arbitrary Boolean function. The learner generalizes Fourier sampling from parity hypotheses to quadratic hypotheses. While standard Fourier sampling is insensitive to the sign of the correlation, we use interference to bias sampling toward positively correlated hypotheses. This is combined with a careful analysis of the resulting distribution to boost both the learner's success probability and its agreement with the target function. We believe that the resulting quantum learning algorithm might be of independent interest. Finally, although a robust quantum PAC learning advantage holds unconditionally in the large error regime, we note that an analogous separation between quantum and classical learning in the small error regime would imply that $\mathsf{NP} \nsubseteq \mathsf{BPP}$.Authors: Harumichi Nishimura
Private simultaneous quantum messages (PSQM) provide a minimal model of noninteractive secure multiparty quantum computation, yet their communication complexity for concrete functions remains poorly understood. We show that familiar total functions already exhibit both genuine quantum advantages and strong structural limitations. For three-party equality on $n$-bit inputs, which determines whether the players' $n$-bit strings are identical, we construct an entanglement-assisted protocol with asymptotic communication $(1.633\ldots)n$ qubits, whereas every perfectly correct protocol without prior entanglement requires at least $3n$ qubits. For three-bit majority, one shared GHZ state and one transmitted qubit per player suffice for perfect correctness and perfect privacy, reducing the communication from the optimal classical cost of six bits to three qubits. Three-bit AND behaves differently. No perfectly correct and perfectly private protocol exists when the players share an arbitrary three-qubit state, apply arbitrary local unitary encodings, and transmit one qubit each. However, increasing the local dimension overcomes this obstruction: one shared three-qutrit GHZ state and one transmitted qutrit per player yield a one-shot protocol with total communication $3\log_2 3$. Together with the six-bit classical lower bound, this gives a strict quantum communication advantage. More generally, for every $k\geq 3$, we construct a perfectly correct and perfectly private one-shot protocol for $k$-bit AND using one qudit of dimension at most $k$ per player, and hence at most $k\log_2 k$ qubits in total.Authors: Jake Anderson, Lars Magnus Hvattum, András Z. Salamon
We prove that deciding solvability of Puzznic, a falling-block puzzle game originally developed by Taito, is PSPACE-complete. To show hardness we construct a self-closing door gadget using Puzznic's game mechanics. For membership, we show that the configuration space is exponentially bounded and apply Savitch's theorem. We also improve an existing NP-completeness proof for a simpler version of the game known as Cubic, showing that this game is NP-complete even when restricted to only two kinds of blocks.Authors: James Davies, Paweł Rzążewski, Jack Spalding-Jamieson, Bartosz Walczak
String graphs are intersection graphs of continuous curves in the plane. In 2010, Fox and Pach proved that string graphs with $m$ edges admit balanced vertex separators of size $\mathcal{O}(m^{3/4}\sqrt{\log m})$ and conjectured that this bound can be improved to $\mathcal{O}(\sqrt{m})$, which would be optimal. After partial progress, Lee claimed in 2017 to prove this conjecture, and more generally to prove analogous separator theorems for region intersection graphs over minor-closed graph families. A key intermediate step in Lee's approach was a padded decomposition scheme for region intersection graphs. In 2024, Korhonen and Lokshtanov extended Lee's approach to the broader setting of graph classes excluding a fixed graph as an induced minor. These results have since found applications in a wide range of works. Later in 2024, a flaw was discovered in the construction of Lee's padded decomposition scheme, invalidating Lee's as well as Korhonen and Lokshtanov's separator results, and many works relying on them. In this work, we prove that string graphs with $m$ edges admit balanced separators of size $\mathcal{O}(\sqrt{m})$, and more generally obtain analogous $\mathcal{O}(\sqrt{m})$ bounds for region intersection graphs over fixed minor-closed graph families and for graphs excluding a fixed graph as an induced minor, thereby repairing the vast majority of the affected works. Furthermore, our balanced separators can be found in polynomial time. Our proof uses a different approach from Lee's and does not rely on padded decompositions. Since padded decompositions have also found applications independent of the separator theorems, particularly for string graphs, we also prove a padded decomposition result for region intersection graphs that is optimal for string graphs. We have formalized both the balanced separator and the padded decomposition results in Lean 4 with mathlib.Authors: Linda Kleist, Lena Scherzer
We study the geometric set cover problems of covering and partitioning a polygon into a minimum number of triangles. While the decision version of the covering problem is known to be APX-hard and $\exists\mathbb R$-complete (even for polygons without holes and vertices in general position), the computational complexity of partitioning a simple polygon into a minimum number of triangles is open. Our main result refutes a 40 year old conjecture by Asano, Asano, and Pinter stating that the triangle vertices of a minimum partition lie on intersection points of special lines, which are iteratively generated by the polygon vertices and the intersection points. In particular, we show that there exist polygons where all minimum triangle partitions need Steiner points with irrational coordinates. This indicates that the problem might be more complex than previously expected. Complementarily, we provide a simple constant factor approximation to compute a minimum triangle partition of a given polygon (possibly with holes). In the context of coverings, we devise the first constant factor approximation for computing a minimum triangle cover of a simple polygon. For general polygons, an $O(\log n)$-approximation follows by close inspection of previous work.Authors: Abigail Hickok, Valerio Galanti, Osama Al Dalahmah, Andrew J. Blumberg
We introduce two new methods for boundary detection in high-dimensional point cloud data, intended to work in situations with non-uniform density, high ambient dimension, and substantial noise. Our first method fits a separating hyperplane on local neighborhoods after doing local dimension reduction---this method works best when one can reliably estimate the intrinsic dimension of the data. Our second method measures the directional uniformity of local neighborhoods, and has the best overall performance on synthetic data. In addition to pointwise numerical boundary scores, our algorithms yield an estimated normal vector at each boundary point. We validate our methodology on synthetic data as well as two real examples: we analyze spatial transcriptomics data, where we show that we can detect the boundary of a tumor, and we also study LLM activation geometry.Authors: Carlos M. Nicolas
Given a set $S$ of $n$ points in general position in the plane, we define the $C$-set $C(p,q)$ of an oriented edge $(p,q)$ as the set of extreme points of the visibility set $V(p,q)$ facing $(p,q)$. Since every point of $V(p,q)$ that is not in $C(p,q)$ gives rise to an empty convex pentagon having $(p,q)$ as a boundary edge, it is natural to study the properties of $C$-sets in order to bound the number of empty convex pentagons of $S$. We prove tight bounds on the intersection size and union complexity of $C$-sets sharing an endpoint. We also consider the problem of bounding the number of empty pentagons and hexagons in terms of the number of interior and boundary points of $S$. While the hexagon bound is weak, it offers a potential step toward a superlinear lower bound. On the other hand, the two-parameter bound for pentagons, combined with the structural results on $C$-sets, yields a simple proof of an $Ω(n^{3/2})$ bound for the number of pentagons. While this is a significant improvement over previously published bounds, a recent preprint \cite{Astudillo2026} attains a better bound using completely different methods. Thus, the primary contribution of this paper lies in the structural results about $C$-sets and the two-parameter bounds for empty pentagons and hexagons.Authors: Yaqiao Li, Junyi Lin
Given a sequence of online points in general position in the plane, the geometric matching problem asks to match as many points as possible, subject to segment crossing constraints. We initiate the study of online geometric matching with limited crosses. In the $k$-crossing model each matched segment is allowed to have at most $k$ crosses, where $k=0$ corresponds to the online noncrossing matching model for which Bose et al. proved that Greedy is an optimal deterministic algorithm achieving a competitive ratio of $2/3$. In the triangle-free-crossing model no three matched segments are allowed to pairwise cross each other. Interestingly, we show in both cases the performance of Greedy does not improve by allowing crosses, and in fact, becomes worse in the $k$-crossing setting for $k\ge 1$. In the triangle-free-crossing model, we propose a simple two-layer-Greedy deterministic algorithm achieving a competitive ratio $4/5$. More interestingly, we propose and study the underlying segments blocking points extremal problem, and discuss its connection to vertex cover numbers and Ramsey numbers, with interesting open problems that might be of independent interest. We revisit the noncrossing model. We give a randomized algorithm which is an asymmetric version of Kamali et al., improving the competitive ratio from $0.66952$ to $0.67034$. We also show, via a conceptually simple construction, that no randomized algorithm can match more than $6/7$ fraction of points, improving the previous $16/17$ by Boyar et al.Authors: Hirotaka Yoneda, Masataka Yoneda
We study online graph coloring in the random-arrival model, where the vertices are presented in a uniformly random order. Assuming $n$ and $k$ are known in advance, we present a randomized exponential-time algorithm that colors any $k$-colorable graph on $n$ vertices with $O(k^3 \log^2 k \log^4 n)$ colors in expectation. This is the first online coloring algorithm that uses a polylogarithmic number of colors for all fixed $k \geq 3$, and is better than a known lower bound of $Ω(\log^{k-1} n)$ colors under adversarial arrivals for all fixed $k \geq 6$. In addition, assuming $n$ is known in advance, we obtain a competitive ratio of $\widetilde{O}(n^{2/3})$. For comparison, it is known to be NP-hard to approximate (offline) graph coloring within a factor of $n^{1-\varepsilon}$ for all fixed $\varepsilon > 0$. Therefore, our exponential-time online algorithm achieves a performance guarantee beyond the NP-hardness threshold for polynomial-time approximation algorithms.Authors: Vasyl Paliy, Youngtak Sohn
We study Glauber dynamics for Ising measures conditioned to have a sufficiently large majority of $+1$ spins. Under a sparse spectral width condition on the interaction matrix, we derive a Poincaré inequality for the conditioned measures from a magnetization drift condition, and a modified logarithmic Sobolev inequality from a stronger, entropy weighted condition. As applications, we obtain approximate posterior sampling in total variation distance for $\mathbb{Z}_2$ synchronization at high enough signal-to-noise ratio using $O(n\log n)$ Glauber updates from a spectral initialization. For ferromagnetic Ising models on random $d$-regular graphs, we prove rapid phase ordering down to inverse temperatures of order $1/d$, extending the temperature range of Gheissari, Sly, and Sohn (2025). Finally, we extend these inequalities to unconditioned Ising measures under an inward drift condition outside the conditioned region. This yields $O(n\log n)$ mixing of Glauber dynamics for the Sherrington-Kirkpatrick model at every fixed inverse temperature when the external field is sufficiently large.Authors: Anming Gu, Bobby Shi, Kevin Tian, Hubert Yang
We give faster algorithms for sampling from the uniform distribution over a polytope. Our main result is an algorithm that, when applied to a polytope with $m$ constraints in $n$ dimensions, uses $m \cdot \mathrm{poly}\log(\frac m δ)$ iterations, each running in time $O(mn^{ω- 1})$, to return a sample within total variation distance $δ$ to the uniform distribution. When $m =O(n)$ and $δ= \mathrm{poly}(\frac 1 n)$, our runtime improves upon all prior works by an $Ω(n^{2/3})$ factor. Our sampler is based on the recent \emph{functional stochastic localization} framework of [GST26], and achieves an iteration count nearly matching the Poincaré constant of the uniform distribution with respect to the logarithmic barrier.Authors: Aaron Bernstein, Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
We study the problem of load balancing in the dynamic setting. The input is a bipartite graph $G = (J \cup M, E)$ of jobs $J$ and machines $M$. Every job has a positive weight $w(j)$. The goal is to assign every job in $J$ to an adjacent machine in $M$ so as to minimize the maximum machine load, where the load of a machine is the sum of the weights of the jobs assigned to it. Although load balancing has been studied extensively in many models of computation, the only previous result in the dynamic model addresses the \emph{incremental} setting, where updates take the form of edge insertions and job deletions [BKS23b]. The authors show a $(1+ε)$-approximation for incremental \emph{fractional} load balancing with $\text{poly}(\log(n),1/ε)$ update time; they point out that their techniques do not extend to the decremental setting. Main Result: We obtain an algorithm which maintains a $(1+ε)$-approximate solution to the fractional load balancing problem under edge deletions and job insertions in $\tilde{O}(\log (n), 1/ε)$ update time. Our techniques are very different from those of the incremental algorithm of [BKS23b]. Instead, our algorithm is inspired by a load-balancing algorithm from the {\sc congest} model of computation [ALPZ21]. We develop a novel analytic framework for this algorithm, which allows us to show that it performs well in the dynamic setting. Rounding Scheme: We also present a black-box rounding scheme for dynamic load balancing. Plugging in our fractional algorithm, we obtain a decremental algorithm for $(2+ε)$-approximate \emph{integral} load balancing with $\text{poly}(\log(n),1/ε)$ update time. We also obtain the same bounds for incremental load balancing by plugging in the fractional algorithm of [BKS23b].Authors: Eliyahu Yablon
The girth of a weighted undirected graph is defined as the length of a shortest cycle in the graph. In this paper, we give a randomized $O\left(m^{1+2/(k-1)} n^{1/(k-1)}\right)$ algorithm to approximate the girth of a graph with $n$ vertices and $m$ edges to within a factor of $k$ for any real $k$. We assume that all edge weights are non-negative. For sufficiently high approximation factors, our algorithm outperforms the state of the art by polylogarithmic factors. Specifically, for approximation factors $k = c\frac{\log n}{\log \log n}$ where $c>5$, our algorithm gives a runtime of $O\left(m (\log n)^{5/c}\right)$, while instantiating the previous best $k$-approximation algorithms with $k = c\frac{\log n}{\log \log n}$ yields a running time of $O\left( \frac{cn (\log n)^{2 + 4/(3c)} }{\log \log n} + m\log n\right)$ (Kadria, Roditty, and Vassilevska Williams, arXiv:2607.00938). Furthermore, the algorithm presented here is conceptually simple, has relatively small constants, eschews single-source shortest path and sparse spanner algorithms, and employs a new technique, which we call ``random filtering.'' That being said, the basic algorithm returns only a numerical estimate for the girth, rather than a witness cycle.Authors: Yotam Kenneth-Mordoch
Finding a global minimum cut in an unweighted graph is a fundamental task in the cut-query model. While there exists a randomized algorithm for this task using $\tilde O(n)$ queries, known deterministic algorithms use $\tilde{O}(n^{5/3})$ queries. We improve upon this result and give a simple deterministic algorithm that finds a global minimum cut using $\tilde O(\min\left\{ nδ,n^2/δ\right\})$ cut queries, which equals $\tilde{O}(n^{3/2})$ in the worst case, where $δ$ is the minimum degree of the graph. The key ingredient in our approach is an efficient maximum $s,t$-flow algorithm, for the case when the minimum $s,t$-cut has value at most $δ$.Authors: Debarshi Chanda, Buddha Dev Das, Arijit Ghosh, Gopinath Mishra
Let $G=(V,E)$ be a $d$-uniform hypergraph with $|V|=n$ and $|E|=m$. Estimating $m$ from uniformly random hyperedge samples requires $Θ(\sqrt{m})$ samples by a birthday-paradox argument. We investigate the power of conditional sampling through a hierarchy of oracles: for an integer $1\le s\le d$, given pairwise disjoint subsets $X_1,\ldots,X_s\subseteq V$, the $s$-colorful oracle returns a hyperedge chosen uniformly at random from all hyperedges contained in $X_1\cup\cdots\cup X_s$ that intersect every $X_i$, provided one exists. For $s=1$, this samples a uniformly random hyperedge induced by $X_1$. For every $1\le s\le d$, we give a randomized algorithm that outputs $\widehat{m}\in[(1-\varepsilon)m,(1+\varepsilon)m]$ with probability at least $2/3$ using $O_{s,d}(\operatorname{poly}(1/\varepsilon,\log n))$ conditional samples, where the exponent of $\log n$ is an absolute constant independent of both $s$ and $d$. Conditional sampling thus yields an exponential separation over uniform hyperedge sampling. We also study the decision version, in which the oracle only reports whether a qualifying hyperedge exists. For every $1\le sAuthors: Han Dai, Shi Li
We revisit the capacitated $k$-median problem, focusing on constant-factor approximation algorithms with either $(1+ε)$-cardinality or capacity violations. Previous results [DemirciL16, Li16} achieve an $O_ε(1)$-approximation with $(1+ε)$-violations via complex extended configuration linear programming formulations with the round-or-cut framework. We propose a simpler, unified round-or-cut framework that handles both cardinality and capacity violation settings. Our main technical contribution is a mechanism that directly utilizes the costs of local instances to generate valid inequalities. Specifically, we partition the metric space into local pieces of size $O(1/ε)$ as in previous work, and construct instances of capacitated clustering with penalties, which allow client demands to be unserved at a penalty cost. Solving these local instances yields lower bounds on the original LP cost, yielding valid LP constraints. In contrast, previous approaches rely on complex extended configuration LPs over connection variables $x_{ij}$'s and opening variables $y_i$'s. As a secondary contribution, our approach achieves an improved running time of $\text{poly}(n, 1/ε)$, bypassing the exponential dependence on $1/ε$ required to solve the previous extended configuration LPs. Instead of solving the local instances optimally in time exponential in $1/ε$, we obtain $O(1/ε)$-approximate solutions in $\text{poly}(n, 1/ε)$ time. Finally, for the cardinality-violation setting, our algorithm opens a set of at most $(1+ε)k$ $\textit{distinct}$ facilities, and thus gives a bicriteria approximation in the $\textit{hard-capacitated}$ setting. In contrast, the algorithm of [Li16] may open the same facility multiple times.Authors: Ivan Fomin, Ivan Koryabkin, Boris Sheludko
Real-time inference on small devices needs low activation memory without extra latency, which makes operator order the most valuable memory lever: it is free in time. We show that the usual way of deploying a better order, handing it back to the compiler and regenerating code, is unreliable. In PyTorch Inductor the regenerated program misses its predicted peak in 22 of 54 CPU configurations. It is worse than the stock program in 9 of them and in 19 of 50 on a GPU, and on the GPU it also changes numerical results. We instead profile the generated program, model its memory exactly from its own statements and their read/write effects, and permute those statements. We prove that this realizes the modeled peak whenever allocation does not depend on history. It does so to the byte, with bitwise-identical results, in all our CPU runs. On the GPU we characterize why the caching allocator breaks the condition. To know when to stop, we give forward and reverse "trap" lower bounds, each computable with $O(n^2)$ minimum cuts. They certify the found order optimal for 94% of held-out wrapper graphs and all 16 microcontroller-class models we study, in under a second. So most inference graphs are already scheduled optimally. Branching networks are the exception, where reordering is free and pays, e.g. 10.0% on DeepLabV3. In compiled training we save up to 7.6%. Beyond the certified optimum we study selective recomputation with per-operator caps. It is strongly NP-hard for every fixed cap even at treewidth two, encodes knapsack exactly on series-parallel graphs, and is solvable exactly on bounded treewidth. It is useless on public tiny models whose peak is a single layer, but on architectures that hold a cheap value for a late reuse it pays: on the public ReDimNet speaker networks, whose order is already optimal, it lowers the peak by 5.2-6.1% at under 0.4% extra MACs, with bitwise-identical outputs.Authors: Kleitos Papadopoulos
We study deterministic single-item lot sizing with all-units quantity discounts, linear holding costs, and time-varying end-of-period inventory bounds. Unit prices may vary arbitrarily over time. For one common positive discount threshold, we give an exact algorithm requiring $O(n^3)$ arithmetic operations and $O(n^2)$ working space, including recovery of an optimal purchase plan. The method combines a critical-state theorem in cumulative-purchase coordinates with two prefix-minimum scans per dynamic-programming layer. The structural argument accommodates downward price discontinuities and distinguishes prescribed from free terminal inventory. With a fixed global set of $m$ positive threshold values, the bounds become $O_m(n^{m+2})$ time and $O_m(n^{m+1})$ space. Period-specific thresholds admit the same exact construction, but its state set can be exponential. For commensurate flow data, an inventory-lattice implementation takes $O(PW)$ time, where $P$ is the total number of price tiers and $W$ is the largest inventory-lattice width. We also derive a conditional optimality certificate from a monotone one-threshold relaxation; this certificate does not imply a near-linear worst-case algorithm for arbitrary prices. Exact-arithmetic implementations are checked against exhaustive inventory dynamic programs and tier-enumeration linear programs. An illustrative timing study identifies settings in which the lattice implementation is preferable.Authors: Kian Ghassemi, Masoud Seddighin, Saeed Seddighin
We study the metric distortion of the minimum spanning tree (MST) problem when numerical edge weights are unavailable and each vertex reports only a ranking of the other vertices induced by these weights. We first show, through a simple example, that without assumptions on the weights, no ordinal algorithm guarantees a finite approximation ratio. We therefore focus on general metrics and present a Borůvka-inspired algorithm using only ordinal comparisons that achieves distortion $O(\log n)$. We complement this result by showing that, for every $\varepsilon>0$, no deterministic ordinal algorithm guarantees distortion at most $3/2-\varepsilon$ on all finite metric instances. We then investigate more informative settings in pursuit of constant distortion, first considering two well-studied metric classes. For tree metrics realized on the given vertex set, a more careful variant of our initial algorithm achieves distortion~$1$, recovering an optimal MST from ordinal information alone. For the broad class of doubling metrics, a different algorithm based on \emph{endpoint cut stability} achieves distortion $2^{O(D)}$, where $D$ is the doubling dimension; this is constant for fixed $D$, independently of $n$. Finally, we study a query-based extension allowing comparisons between two edge lengths without revealing their numerical values. For general metrics with $n\geq2$, fewer than $n$ edge-comparison queries suffice to achieve distortion at most $2\log_2^* n-1$, which is near-constant even for very large inputs.Authors: Christian Coester, Yichen Huang, Michael Mitzenmacher
We study the problem of online clustering with movement cost, which generalizes the fundamental $k$-server problem. At each time step, the algorithm is given a set of points in a metric space and must choose $k$ cluster centers. The cost incurred is the sum of the clustering cost at each time step and the total distance that the centers move over time. Prior work established competitive algorithms for the case $k\in\{1,2\}$ on the line metric with the $k$-median clustering objective; under the $k$-median objective, this problem is also known as facility reallocation. We substantially generalize these results to arbitrary $k$, general metric spaces, and a broad class of clustering objectives. Specifically, we consider clustering costs defined as a norm of the distance vector from points to their nearest center, which subsumes the $k$-median, $k$-center, and (square root of) $k$-means objectives, and provide an asymptotically optimal $O(k)$-competitive randomized algorithm against adaptive online adversaries. The algorithm is based on a reduction to the $k$-server problem, establishing a tight connection between the problems. In this reduction, $k$-server requests are generated by Poisson processes, whose arrival rates evolve in continuous time and are driven by a dual representation of the clustering costs. Our method of using Poissonization in this context may also be of independent interest. We demonstrate another use of the idea by deriving similar reductions for batched set chasing problems. We also consider a different family of clustering objectives defined as a norm of the vector of cluster radii, which subsumes the sum-$k$-radii and the $k$-center objectives, and give a tight $O(k)$-competitive deterministic algorithm on the line.Authors: Tatsuya Terao
We present a simple deterministic semi-streaming algorithm that computes a $(1-\varepsilon)$-approximate maximum matching in general graphs in $O(1/\varepsilon^{2})$ passes. This matches the pass complexity of the auction algorithm of Assadi, Liu, and Tarjan~[SOSA'21] for bipartite graphs, and answers Open Question~2 of Assadi~[SOSA'24 \& TheoretiCS'25]. Our approach, which we call the \emph{budgeted price approach}, is very different from the previous $\mathrm{poly}(1/\varepsilon)$-pass semi-streaming algorithms for $(1-\varepsilon)$-approximation of matching in general graphs and improves their pass complexity. All previous approaches are augmenting-path-based and use $O(1/\varepsilon^{19})$ passes by Fischer, Mitrović, and Uitto~[STOC'22], $O(1/\varepsilon^{6})$ passes by Mitrović, Mukherjee, Sankowski, and Sheu~[ICALP'25], and $O(1/\varepsilon^{4})$ passes by Izumi, Kitamura, and Yamaguchi~['25].Authors: Yann Bourreau, Sebastian Brandt, Ananth Narayanan
We show that, on bipartite $n$-vertex graphs in the LOCAL model of distributed computation, $(Δ+ 1)$-edge coloring can be solved deterministically in $O(f(Δ) \log n)$ rounds for some function $f$. In particular this implies a deterministic $O(\log n)$-round upper bound for $(Δ+ 1)$-edge coloring on bipartite constant-degree graphs. Our results improve on the previous state-of-the-art bounds (which hold already on general graphs) whose $n$-dependencies are $\widetilde{O}(\log^5 n)$ rounds deterministically and $\widetilde{O}(\log^2 n)$ rounds randomized [Bernshteyn and Dhawan, J.\ Comb.\ Theory 2025]. In fact, we obtain the aforementioned results already for a more restrictive version of $(Δ+ 1)$-edge coloring that corresponds to a \emph{local-palette} strengthening of Vizing's theorem shown recently to hold [Christiansen, STOC 2023]. In this version, every edge $\{u, v\}$ has to be colored with a color from $\{1, \dots, \max(\operatorname{deg}(u), \operatorname{deg}(v))+ 1\}$. For all of our results, the vertices do not need to know on which side of the bipartition they lie---the structural promise of bipartiteness suffices.Authors: Jamie Fravel, Martin Koutecký, Pavlo Tsitsei
The conclusions of an experimental study of algorithms are only as good as the instances they are run on. Benchmark libraries for well-studied problems took decades to curate, while evaluations of new problems often fall back on random instances, which are known to be misleading: they may say more about the random generator than about the algorithmic question at hand. We treat instance generation as an optimization problem: parameterize the instance space, take the solver's running time as the objective, and let a black-box optimizer search for hard instances. We develop a widely applicable workflow built on the Nevergrad optimization platform and demonstrate it on four NP-hard problems: satisfiability, traveling salesperson, Hamiltonian cycle, and non-permutation flow-shop scheduling. The search needs only the solver, an instance encoder, and a compute budget. Our evolved instances beat the hardest instance of a budget-matched random draw in all four case studies, by an order of magnitude or more in three. They are often competitive with long-curated benchmark sets: our SAT champion is harder (for a three-solver portfolio) than 78% of the 498 SAT Competition formulas in its size class; our 20-city TSP champions take several times longer than the hardest measured classical TSPLIB instance (229 cities); and our flow-shop champion takes 238.6 seconds of CP Optimizer time to solve to proven optimality (versus 4.5 seconds for the hardest of 100,000 random draws) while denying CP-SAT an optimality proof. The optimizer even recovers known structure from running time alone: it locates a SAT clause/variable ratio near the phase transition and finds structurally different champions for the two scheduling engines.Authors: Thomas Dueholm Hansen, Uri Zwick
Acyclic Unique Sink Orientations (AUSOs) of the binary hypercube form an elegant abstraction of various optimization problems, ranging from linear programs whose feasibility region is a combinatorial hypercube, to 2-player turn-based stochastic games (2TBSGs) in which one of the players has two actions from each one of its states. The currently fastest known randomized algorithm for finding the sink of such AUSOs is the Random-Facet algorithm of Kalai (STOC 1992), and of Matoušek, Sharir and Welzl (SoCG 1992), adapted to the binary hypercube by Gärtner (RSA 2002). The expected number of vertex queries made by the algorithm is at most $e^{2\sqrt{n}}$, where $n$ is the dimension of the cube. We design an improved randomized sink-finding algorithm that performs an expected number of only $e^{\sqrt{(2+o(1))n}}$ queries. This is the first improved bound for the problem in over two decades. The improved algorithm is obtained by adapting improved versions of the Random-Facet algorithm for solving general linear programs, and LP-type problems, developed by Kalai (STOC 1992), Gärtner (FOCS 1992), and by Hansen and Zwick (STOC 2015). The improved bound is not implied by these much more general algorithms. A key feature of the improved algorithm and its analysis is its simplicity. The structure of binary AUSOs enables a simpler description and a much simpler analysis of the adapted algorithm. In particular, the recurrence relations bounding the complexity of the algorithm depend on only one variable, and not two, and they can be solved using fairly straightforward techniques.from ECCC Papers
So what to make of OpenAI and the future of Math? Here are some points I've either:
thought of myself or heard from a human or read from an AI.
Throughout this post I use the term AI to mean an AI system that produces mathematical results. I decline to say OpenAI or Anthropic as generic terms since about 20 years ago I used Intrade as a generic term for Betting Markets---then Intrade went out of business. I wish I had bet on that happening. Oh well.
1) Some of the proofs were Lean-formalized and some were not. If a proof is Lean-verified do we know the proof is valid? The issue is not bugs in Lean. The issue is that coding a theorem/proof into Lean may be done incorrectly. So Lean might be verifying a proof of a theorem different than what was intended.
Peter Woit, is a string-theory skeptic and a Lean-skeptic. See hereBy gasarch
So what to make of OpenAI and the future of Math? Here are some points I've either:
thought of myself or heard from a human or read from an AI.
Throughout this post I use the term AI to mean an AI system that produces mathematical results. I decline to say OpenAI or Anthropic as generic terms since about 20 years ago I used Intrade as a generic term for Betting Markets---then Intrade went out of business. I wish I had bet on that happening. Oh well.
1) Some of the proofs were Lean-formalized and some were not. If a proof is Lean-verified do we know the proof is valid? The issue is not bugs in Lean. The issue is that coding a theorem/proof into Lean may be done incorrectly. So Lean might be verifying a proof of a theorem different than what was intended.
from ECCC Papers
from ECCC Papers
By Ittai Abraham, Gilad Stern
By Ittai Abraham
from ECCC Papers
By Ittai Abraham, Gilad Stern
from Ben Recht
Hi there, argmin readers! Today’s post is a live blog of Class 12 of my graduate seminar “Forecasting: A Critical Retrospective.” The syllabus and list of past posts are here. It might also be a subtweet of yesterday’s AI discourse?
Twenty-five years ago, Leo Breiman wrote a prophetic warning to his statistical brethren:
“There are two cultures in the use of statistical modeling to reach conclusions from data. One assumes that the data are generated by a given stochastic data model. The other uses algorithmic models and treats the data mechanism as unknown. The statistical community has been committed to the almost exclusive use of data models. This commitment has led to irrelevant theory, questionable conclusions, and has kept statisticians from working on a large range of interesting current problems. Algorithmic modeling, both in theory and practice, has developed rapidly in fields outside statistics. It can be used both on large complex data sets and as a more accurate and informative alternative to data modeling on smaller data sets. If our goal as a field is to use data to solve problems, then we need to move away from exclusive dependence on data models and adopt a more diverse set of tools.”
Breiman saw that prediction was at the heart of most of his consulting projects. Rather than being asked to determine causation, he was asked to make forecasts. His list of examples is instructive:
Predicting next-day ozone levels.
Using mass spectra to identify halogen-containing compounds.
Predicting the class of a ship from high altitude radar returns.
Using sonar returns to predict the class of a submarine.
Identity of hand-sent Morse Code.
Toxicity of chemicals.
Online prediction of the cause of a freeway traffic breakdown.
Speech recognition.
The sources of delay in criminal trials in state court systems.
If you asked anyone today how they’d solve these tasks, they’d say “collect data and fit a neural net.” You had to be there at the time, but this was quite controversial in 2001. Indeed, even using a decision tree was controversial. Many people thought models built with expert knowledge, with meaningful parameters fit to data, would be far superior for prediction. Moreover, you’d be able to interpret your predictions because you had a mechanistic understanding of reality encoded your predictive stochastic data model.
Given what’s happened since, I don’t think anyone needs convincing that neural nets will work better. Indeed, the reaction in class yesterday confirmed that the zeitgeist has shifted 180 degrees. Of course you’d rather use a neural network than a complicated model. For all of those tasks, everyone would say “use a transformer or do in-context learning and forget about it.” Autoregression has won out by brute force.
Now, given my long history as a machine learning researcher, I don’t think you’ll be surprised to find that I agree with Breiman and struggle to justify stochastic models. However, I think I can capture the motivation of modelers: people want more from their models than predictions.
People like mathematical models because we think that understanding how something works from top to bottom lets us better predict how it will behave in the future. A mechanistic understanding not only lets us play out likely futures, but lets us imagine what might happen under a variety of different adversarial scenarios. These models assure us that we understand the present well, because we can point at all of the subcomponents and build a bottom-up description of macroscale behavior.
It’s so weird how our forecasting culture turns this around: IF we can make good predictions, THEN we understand. You present your Brier Score first. Only if it tops the prediction-market leaderboard are people impressed enough to go read your 25,000-word description of how you prognosticate. Accepting this logical inversion—that accurate predictions indicate understanding—is why our rational brethren venerate superforecasters. But it’s clear that even the most committed forecast bros don’t like this, because they also obsess about mechanistic interpretability.
But when we seek explanations, all we have is the data from which our predictions are made. Data-driven modeling is implicit, leaning on the tacit knowledge of what makes good data and what makes bad data. Almost everything you want to interpret lies in the data and your optimization objective. The compressed storage that are the parameters of your nonparametric model hold this information too, but reading the tea leaves of the weights is like trying to understand a book by looking at the bits in its zip file.
In a wholly data-driven world, better understanding can only come from getting new data. We can either wait for the future to roll in, or we can act to get that data now. That is, to rapidly understand the world you forecast, you have to be able to do things. You need to intervene and act to rule out explanations. This is experimentation.
Forecasts alone are not experimentation. Indeed, a recurring theme in this class is how passive forecasting is. Focusing so hard on prediction makes us forget we can take actions to change the future.
Some think that predictions can shape the world. By warning people of doom, perhaps someone out there will take action. And yet, my impression is that the most dedicated forecasters think their best available action is to place bets. Or write open letters. Abandoning their agency makes their prophecies self-fulfilling.
from CS Theory Events
By shacharlovett
from ECCC Papers
from ECCC Papers
Authors: Rahul Jain
We give a proof of the cubic parallel-repetition bound for finite two-player entangled games using quantum conditional relative entropy. For a game with entangled value $1-\varepsilon<1$ and answer alphabets $\mathcal A,\mathcal B$, its $n$-fold repeated value is at most \[ \exp[-Ω(\varepsilon^3n/L)],\qquad L:=\max\{1,\log(|\mathcal A||\mathcal B|)\}, \] for every $n\ge1$. This recovers Song's cubic rate. We also prove a threshold bound: the probability of winning a fraction at least $1-\varepsilon+δ$ is at most $\exp[-Ω(δ^5n/(\varepsilon^2L))]$ for $0<δ\le\varepsilon$. Our information charge is the decrease in relative entropy when a question reference is discarded. Our comparison states preserve the original conditional question law. A chain rule bounds the coordinate charges using the cost of conditioning on checked wins and retaining checked answers. Our main lemma converts small charges into nearby pure-state descriptions and local corrections, each depending only on one player's question. Together with Song's sampler, these enable approximate local preparation of the conditioned workspace.Authors: Sravanthi Chede, Vaibhav Krishan, Anil Shukla
In this work, we design knowledge compilation languages for quantified Boolean formulas (QBFs), with a particular focus on model counting. We introduce various languages in increasing order of their power of representation, starting from a simple tree-based structure, and extending it to DAGs for a more efficient representation. We study the power and limitations of each language. We also show that QBF queries such as model counting and MaxQBF are easy to handle in all these languages. These languages naturally lead to various static proof systems for the #QBF problem, the model-counting version of the QBF problem. We compare these systems with one another and with a recently introduced line-based #QBF-system called Q-MICE (Chede, Chew, Krishan and Shukla, SAT `26). We show that a minor extension of the Q-MICE system efficiently simulates all these static proof systems, and is in fact exponentially stronger than each of them. We also initiate the implementation of a solver based on these languages. The solver compiles a representation of an input QBF in the proposed tree-like language, which is subsequently used for model counting. This is the first knowledge compilation based solver for #QBF which can handle QBFs with doubly exponential model counts as well. Experimentally, we compare its performance with the state-of-the-art #QBF-solver d4-QBF which works well for QBFs with small model counts.Authors: Pachara Sawettamalya
Recent work of Sawettamalya and Yu (FOCS 2026) initiated the study of \emph{gap-majority} composition in randomized communication. They showed that if computing a $\{\pm 1\}$-valued function $f$ in $r$ rounds requires $I$ bits of information, then distinguishing $\sum_{i=1}^n f(X_i,Y_i)\geq 0.01\sqrt{n}$ from $\sum_{i=1}^n f(X_i,Y_i)\leq -0.01\sqrt{n}$ in $r$ rounds requires $n \cdot (I-O(\log n))$ bits of information. They also conjectured that the $O(\log n)$-additive ``loss'' can be further reduced to $O(1)$. In this note, we record that a minor adaptation to their approach combining with a finer analysis achieves the conjectured $O(1)$ loss, establishing a gap-majority lemma for bounded-round communication that is optimal up to constant factors.Authors: Bruno Loff, Mateusz Skomra
Our understanding of turn-based stochastic games is reminiscent of our understanding of linear programming in the 1970s. Instead of the simplex method, we have two families of algorithms - policy iteration and value iteration - which work well in practice but are known to run in exponential time on some input instances, and we still lack an algorithm that runs in polynomial time on all instances. A recent result by Loff and Skomra showed that, for deterministic discounted and mean-payoff games played on an ergodic graph, a variant of policy iteration runs in smoothed polynomial time. This offered an explanation of why policy iteration performs well in practice, analogous to Spielman and Teng's explanation for the simplex method. In this paper, we drop the ergodicity assumption: we show that their policy iteration algorithms run in smoothed polynomial time for any game graph. We do this by defining a condition number that naturally generalizes theirs, showing that sufficiently-perturbed games are well-conditioned with high probability, and showing that their algorithms are efficient on well-conditioned instances. Although the outline is similar, our proof requires a substantially new approach, based on log-Lipschitz distributions which recently appeared in work on the smoothed analysis of the simplex method. For our second contribution, we propose three new value iteration algorithms for solving deterministic mean-payoff games (also on any graph). All three are based on iterative methods for finding fixed points of non-expansive operators, which we show can be applied to the Shapley operator. The first two are simple applications of Krasnoselskii-Mann iteration and Halpern iteration. The third is quadratically faster but more complicated: it runs Zwick-Paterson and Halpern iterations in parallel. We prove that all three algorithms are correct and run in smoothed polynomial time.Authors: Lukas Pieper
We revisit the complexity classification of constraint satisfaction problems (CSPs) for first-order reducts of $(\mathbb{Z},<)$, established by Bodirsky, Martin, and Mottet in 2018. Following their approach, we give a self-contained proof of this classification, correcting several errors in the argument. We further show that, with the exception of cases arising from finite-domain CSPs, all tractable cases are solved by a well-known uniform algorithm, eliminating the need for the collection of ad-hoc algorithms used in the original paper. A central component of the proof allows the analysis to be restricted to first-order reducts of $(\mathbb{Z},<)$ that contain the successor relation. We substantially simplify this reduction and generalize the underlying construction. This generalization allows us to apply the same technique to first-order reducts of the triangular lattice graph and of infinite regular trees, yielding a complete complexity classification for these classes of structures, in particular a $\mathsf{P}$ versus $\mathsf{NP}$-complete dichotomy.Authors: Arnaud Vandaele
Nonnegative matrix factorization (NMF) approximates a nonnegative matrix by the product of two nonnegative matrices with a prescribed inner dimension~$r$. The existence of an exact NMF can be decided in polynomial time for every fixed~$r$, and a best rank-$1$ NMF in the Frobenius norm can be obtained from a truncated singular value decomposition. We prove that computing a best rank-$2$ NMF in the Frobenius norm is strongly NP-hard. Our proof uses a polynomial-time reduction from \textsc{Clique} that produces symmetric positive-definite, completely positive matrices with polynomially bounded integer entries. The same reduction also establishes strong NP-hardness of rank-$2$ symmetric NMF.Authors: Kristóf Zólomy
We study the deterministic query complexity of finding a fixed point of a monotone function $f:[n]^d\to[n]^d$, where querying $x$ returns $f(x)$. For fixed $d\ge2$, earlier work established a lower bound of $Ω((\log n)^2)$ and an upper bound of $O_d((\log n)^{\lceil(d+2)/3\rceil})$ for the query complexity. Very recently, several papers obtained improved lower bounds using AI-assisted proofs. In this paper, we further improve these lower bounds to $\text{Tarski}(n,d)=Ω_d((\log n)^{2+\lfloor\log_3(d/2)\rfloor})$. In particular, we obtain the optimal $Θ((\log n)^3)$ deterministic query complexity in six dimensions.Authors: Marshall Ball, Peter Crawford-Kahrl, Vladimir Podolskii, Morgan Prior
Multiparty Private Simultaneous Messages (PSM), also known as Decomposable Randomized Encoding (DRE) or information-theoretic garbling, is a model for non-interactive secure computation. Each party encodes its input using shared randomness and sends a message to an evaluator who does not know that randomness. The evaluator must recover the function output without learning anything else about the inputs. Perfect privacy requires identical transcript distributions on inputs with the same output. We also study the weaker notion of support privacy, which requires only that these distributions have the same support. We study the communication complexity of symmetric Boolean functions when each of the $n$ parties holds one input bit. Lower bounds. We prove a superlinear lower bound for support-private PSM protocols computing $OR_n$. Our technique gives $Ω(n\log n)$ lower bounds for $MAJ_n$ and $EMAJ_n$ (with even $n$), and an $Ω(n\log q)$ lower bound for $MOD_q$ when $q\leq(1-c)n$ for a fixed constant $c>0$. Upper bounds. We construct perfectly private PSM protocols of total communication $\widetilde{O}(n^{3/2})$ for every symmetric Boolean function, improving on the known quadratic bound. For $MAJ_n$, known branching-program constructions yield an upper bound of $O(n\log^3 n\log\log n)$. For $EMAJ_n$ and $MOD_q$ with prime $q$, the lower bounds are tight up to constant factors in the stated regimes. Under support privacy, we obtain $\widetilde{O}(n)$ communication for every symmetric Boolean function. Earlier lower-bound techniques of Ball et al. (ITCS 2020) yield only trivial linear bounds for symmetric Boolean functions. Concurrent and independent work by Holmgren and Wu proves a $ω(n)$ lower bound for $OR_n$ using the same combinatorial core. Both works used AI assistance.Authors: Bahman Kalantari
We study the problem of testing membership of the origin in the convex hull of $n$ unit vectors in $\mathbb{R}^m$, seeking a convex combination of norm at most $\varepsilon$ or a strict separating hyperplane. The Spherical Triangle Algorithm (STA) uses nearest-point updates on pivot segments. We first establish a conditional $O(1/\varepsilon)$ iteration bound from accumulated geometric progress, allowing deeper pivots to compensate for shallow ones. A three-point example shows that ordinary STA can require $Θ(\varepsilon^{-2})$ iterations. We show that the same conditional bound holds for STA with Wolfe minimum-norm correction (STA--WMC), provided the averaged geometric progress condition holds for the STA steps taken within this corrected method. We then combine STA, WMC, and the Nemirovski weighted-pivot method (NWP) in a hybrid with unconditional bounds of $O(\sqrt{\log n}/\varepsilon)$ matrix--vector products with the input matrix or its transpose and $O(mn\sqrt{\log n}/\varepsilon)$ arithmetic operations, including corrections. We also give a self-contained derivation of the $O(\sqrt{\log n}/\varepsilon)$ membership iteration bound for entropic Nesterov acceleration. Computationally, we compare five methods---ordinary STA, STA--WMC, the hybrid, standalone NWP, and entropic Nesterov acceleration---on convex-hull queries derived from 14 public benchmark datasets and on 204 controlled synthetic inputs. STA--WMC completes all cases in both comparisons, and the hybrid completes all public-data cases. STA performs well on favorable interior and separation instances; Nesterov acceleration is faster than the STA-based methods on the highest-dimensional random membership tests. The experiments show complementary strengths and distinguish practical performance from worst-case guarantees.Authors: Felix Windisch, Lukas Radl, Thomas Köhler, Shrisudhan Govindarajan, Marcel Pur, Andrea Tagliasacchi, Markus Steinberger
3D Voronoi diagrams provide a powerful mathematical framework for representing volumetric functions and geometry with applications to Materials Science, Biology, Simulation and Astrophysics. However, accurately resolving fine structures often requires millions of cells, imposing severe computational and memory constraints. Traditional mesh decimation or point cloud simplification techniques fail to account for the effects re-meshing has on neighbouring cells. In this work, we formalize the Voronoi reduction problem and propose a greedy edge-collapsing algorithm on the dual Delaunay tetrahedralisation that accounts for changes in the local geometry. Further, we demonstrate a novel volumetric error approximation technique that models convex cell intersections as truncated prismatoids, circumventing computationally prohibitive exact volume calculations and enabling massive GPU parallelization. Evaluations across Synthetic, Medicine and Material Science data demonstrate that VoroDuce decimates models with up to a million primitives, successfully compressing the representation while preserving the underlying data better than naive decimation approaches.Authors: Sujoy Bhore, Arnold Filter, Eunjin Oh, Hyeonjun Shin, Himanshi Singh
In this paper we study consistent hashing (a.k.a. sparse partitions) for doubling metrics in the Massively Parallel Computation (MPC) model. A $(Γ,Λ)$-hash with diameter bound $Δ$ partitions a metric space into clusters of diameter at most $Δ$ such that every ball of radius $Δ/Γ$ intersects at most $Λ$ clusters in expectation. Consistent hashing has emerged as a central tool in geometric MPC algorithms. However, so far it has been solely used in Euclidean spaces, where it can be pre-computed. On the other hand, in cases where the metric space is received as input and unknown in advance, no previous parallel construction was known. We present the first fully scalable MPC algorithm over machines with local space $n^σ$, that given an $n$-point metric space with doubling dimension $d\leq O(σ\log n)$, samples a randomized $(Γ,2^{O(d/Γ)})$-hash in $O(d/σ^3)$ rounds. There is a dichotomy: if the doubling dimension is $d=Ω(σ\cdot\log n)$, a polynomial number of rounds is required to compute such a hash. We conclude by showing that this MPC primitive yields $O(d/σ^3)$-round fully scalable MPC algorithms for a broad class of fundamental geometric problems in doubling metrics, including stochastic tree embeddings with $O(\log n)$ expected distortion, constant factor approximation for facility location, bicriteria $(O(ε^{-2}),1+ε)$-approximation for $k$-median and $k$-means.Authors: Felix Adena, Monika Henzinger, Christoph Kern, Daniel Rutschmann
We study the problem of maintaining the vertex connectivity $κ$ of a graph under edge insertions. For undirected graphs, our algorithm uses $O(κ^4 \log^2 n)$ amortized time per edge insertion. After each edge insertion, the algorithm outputs the current value of $κ$, plus a set of $κ$ vertices whose removal disconnects the graph. Our algorithm is Monte-Carlo randomized and works with a randomness-adaptive adversary. The algorithm also works on directed graphs against an oblivious adversary, which is equivalent to an output-adaptive adversary if we only have to output the current value of $κ$. Previously, algorithms for maintaining the vertex connectivity with $o(n)$ time per edge insertion were only known for $κ\le 2$, and need $\tilde{O}(\log^2 n)$ and $O(\sqrt{n})$ time per edge insertion for $κ= 1,2$, respectively. Moreover, for $κ> 4$, no algorithm faster than recomputation from scratch was known. We complement our algorithm with a conditional lower bound: Under the OMv conjecture, any insertions-only algorithm that outputs the current value of $κ$ after every insertion needs $Ω(n^{1-\varepsilon})$ amortized time per edge insertion for $κ= Θ(n)$. Previous conditional lower bounds for this problem only apply to worst case running time, or algorithms that support both edge insertions and edge deletions.Authors: Min Wu
In a self-sizing set-reconciliation protocol, a small first-round Invertible Bloom Lookup Table (IBLT) sketch attempts peeling decoding; after failure, the protocol estimates the difference count $d$ from the count energy and sizes the second round from a lower quantile of the measurement. This quantile must be computed conditionally on failure: the measurement and peeling success are determined by the same random mapping, so conditioning can shift the measurement law. In the ideal peeling model, inside the critical window where failure has nondegenerate probability, the standardized energy and a statistic of the unsigned mapping that governs the peeling outcome (the precritical score) have a joint Gaussian limit with correlation $η_kρ^2$, $ρ$ being the sign imbalance and $η_k$ a closed-form constant. The measurement conditional on failure is thus a bivariate normal truncated to a half-plane, which we call the Gaussian-selection law. Since $η_k$ changes sign between $k=4$ and $k=5$, under one-sided imbalance the unconditional threshold undercovers exactly when $k\ge5$ and is conservative for $k=3,4$. The key tool is a quenched CLT for a signed quadratic form on a random overlap graph; under asymptotically balanced signs, conditioning on any unsigned mapping event that is permutation-invariant and has probability bounded away from zero leaves the standard normal limit unchanged. After failure the protocol observes the total sign; inverting the selection law yields an upper confidence bound for $d$, asymptotically conservative in the critical window and, when $d/\sqrt M\to\infty$, along the whole load axis. The experiments use analytic constants, none fitted; the unconditional threshold carries a selection error that does not vanish with scale, while the corrected selection-law threshold matches per-configuration empirical quantiles.Authors: Diptaksho Palit, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
We revisit the classical problem of testing connectedness of graphs represented in the adjacency lists model and obtain optimal bounds. Specifically, we show that $\varepsilon$-testing connectedness of graphs with maximum degree at most $d$ requires $Ω(\frac{1}{\varepsilon} \log \frac{1}{\varepsilon d})$ queries (when $\varepsilon \le \frac{1}{4d^5}$). Our result implies that the connectedness tester of Levi, Pallavoor, Raskhodnikova, and Varma ({\em ACM Trans.\ Comput.\ Theory, 2022}) is optimal. We also study the problem of testing $k$-edge-connectedness of both directed and undirected graphs of average degree $\overline{d}$ in the adjacency lists model and design a tester with query complexity $O(\frac{k}{\varepsilon} \log \frac{1}{\varepsilon \overline{d}})$, improving upon the bounds by Forster, Nanongkai, Saranurak, Yang, and Yingchareonthawornchai (SODA 2020). Furthermore, we complement our upper bound by showing that every one-sided error $k$-edge-connectedness tester must make $Ω(k/\varepsilon)$ queries.Authors: Sara Ahmadian, Shuchi Chawla, Ravi Kumar, Manish Purohit, Shirley Zhang
We present a simple deterministic $O(\log n)$-competitive algorithm for the online minimum-cost perfect matching with delays (MPMD) problem on arbitrary, unknown metric spaces, where $n$ is the (unknown) number of requests. This improves upon the recent $O(\log^5 n)$-competitive algorithm of Dufay and Wattenhofer (SODA 2026) and nearly matches the $Ω(\log n / \log \log n)$ randomized lower bound of Ashlagi et al. (APPROX 2017). Our algorithmic framework rests on two ingredients: an online moat-growing process that grows active dual variables at a deliberately slowed constant rate $α< 1$ to control temporal asymmetry, and a delayed eligibility rule that matches requests in the same dual component only after their waiting time is proportional to their time-expanded distance. The framework extends naturally to arbitrary concave delay functions, maintaining an $O(\log n)$ competitive ratio, and to $k$-way matching with delays, yielding an $O(k \log n)$-competitive deterministic algorithm.Authors: Donglei Du
We obtain a $0.4584$-approximation for nonnegative, non-monotone, $L$-smooth DR-submodular maximization over compact convex down-closed subsets of the unit cube, improving the $4/9\approx0.4444$ ratio of Aggarwal's projection-based algorithm~\cite{aggarwal2026geometry}. A recovery map combining exponential and linear-fractional branches admits a cube-wide affine upper bound. The resulting continuous-time Frank--Wolfe-type algorithm with randomized output and its randomized discrete-time implementation both satisfy $\E F(\widehat x)\ge(0.4584-\varepsilon)\OPT-δLD^2$; the implementation uses polynomially many cube-wide value/full-gradient queries and ordinary linear maximization calls, where $D$ is the feasible diameter and $\varepsilon,δ>0$ are accuracy parameters. Our guarantee and Aggarwal's hardness bound~\cite{aggarwal2026geometry} place the optimal approximation ratio for cube-wide value/full-gradient queries and linear maximization, with additive error $δLD^2$, in $[0.4584,0.4705)$. Standard multilinear sampling and pipage rounding imply an expected $(0.4584-\varepsilon)$-approximation for nonnegative submodular set-function maximization under a matroid constraint \cite[Lemma B.3]{vondrak2013symmetry}.Authors: Mohammad Afzali, Hassan Ashtiani, Sivan Sabato
We propose a general framework for non-interactive locally differentially private (LDP) learning of structured univariate distributions that can be approximated by piece-wise polynomials. This gives the first sample-efficient LDP learners for several distribution classes, including mixtures of log-concave distributions, such as Gaussian mixture models (GMMs). These learners also provide agnostic guarantees and are computationally efficient. We also prove a lower bound for learning GMMs under LDP, improving on the standard pure-DP packing lower bounds of Bun et al. [BKSW19]. To obtain our general learning framework, we develop an efficient non-interactive LDP algorithm for synthetic data generation over large domains, which may be of independent interest. We then use it together with a deterministic adaptation of the non-private piecewise polynomial learner of Acharya et al. [ADLS17].Authors: Emile Anand, Peter Chen
We give a randomized algorithm that, for an $m\times n$ matrix whose columns have Euclidean norm at most one, finds a signing with discrepancy below $99$ in expected $\widetilde O(L_{\mathrm{in}}+n^ω)$ bit operations, where $L_{\mathrm{in}}$ is the input encoding length and $ω$ is the exponent of matrix multiplication. The previous fastest algorithm with a constant discrepancy bound, due to Li, is deterministic and uses $O(mn+n^{ω+2}\log^3 n)$ arithmetic operations. We build on the spectral signing framework of Guo, Fang, and Lu and of Li, which rounds a single fractional coloring while one spectral potential controls every row. Li's potential tracks a top eigenvalue, and the gap below that eigenvalue, which can be of order $1/n$, limits the length of every step. We replace it with a resolvent potential that is smooth without any gap condition, and we draw step signs at random, so that the potential only needs to be concave while progress is measured separately. Our key insight is to reuse a single subspace of directions throughout a batch of steps, thereby using only one spectral computation, so that the more expensive linear algebraic operations are paid for only polylogarithmically often at each scale. Within a batch, we sample directions from a Gaussian completion matrix whose inverse we maintain under rank-one row replacements. Finally, we use a finite-precision analysis to prove stability of the algorithm and attain the bit-complexity bound.Authors: Keisuke Korogi
We give a deterministic data structure for range weighted longest increasing subsequence (LIS) queries on $n$ values with positive weights. Preprocessing takes $O(n\log^2 n)$ time and space. Value queries take $O(\log n)$ time, and an optimal subsequence of $k$ elements can be reported in $O(k + \log n)$ time. This resolves an open question on truly subquadratic preprocessing with polylogarithmic query time. The key is a single-crossing property of envelopes for value-separated endpoint sets, enabling $O(\log n)$-time persistent merges. The bounds assume constant-time exact addition and comparison of weights.Authors: Reut Levi, Jonathan Meiri
In this paper we study the problem of tolerantly testing the property of being $H$-free (which also implies distance approximation from being $H$-free). In the general-graphs model, we show that tolerant $K_k$-freeness testing can be achieved with query complexity that is polynomial in the arboricity of the input graph $G$, $arb(G)$, and independent of the size of $G$ (for graphs in which the average degree is $Ω(1))$. Specifically for triangles, our algorithm distinguishes graphs which are $ε$-close to being triangle-free from graphs that are $3ε(1+η)$-far from being triangle-free with expected query complexity which is $\tilde{O}(arb^3(G))$ (for constant $η$ and $ε$). For general $k$-cliques our algorithm distinguishes graphs which are $ε$-close to being $K_k$-free from graphs which are ${k \choose 2}ε(1+η)$-far from being $K_k$-free with expected query complexity which is polynomial in $k$, $1/ε$, $1/η$ and $arb(G)$. We then generalize our result and provide a similar result for any motif $H$ which is $2$-connected and has radius $1$. This includes for example the wheel graph. Finally, we show that our tester can be applied to the bounded-degree model for tolerantly testing $H$-freeness for any motif $H$. The query complexity of the algorithm is polynomial in the degree bound, $d$, improving the previous state-of-the-art by Marko and Ron (TALG 2009) that obtained quasi-polynomial query complexity in $d$.Authors: Anand Babu, Ashwin Jacob, Hitendra Kumar, R. B. Sandeep
The Eccentricity Shortest Path problem asks, given a connected graph and a nonnegative integer $R$, whether some shortest path is within distance $R$ of every vertex. We study its structural parameterized complexity. We give fixed-parameter algorithms for vertex-deletion distance to cographs, vertex-deletion distance to interval graphs, and bandwidth. The interval-deletion result answers a question of Bhyravarapu et al. (IWOCA 2023). We obtain XP algorithms for vertex-deletion distance to chordal graphs, clique-width, and rank-width, without requiring expressions or decompositions for the latter two. Consequently, the problem is polynomial-time solvable for every fixed treewidth, answering a question of Chakraborty et al. (2026). We also derive fixed-parameter tractability for treedepth and XP membership for diameter from earlier algorithms. We prove $\mathsf{W}[3]$-hardness for cutwidth, and hence pathwidth and treewidth, even on graphs of maximum degree at most five; $\mathsf{W}[2]$-hardness for vertex clique-cover number; and NP-hardness on graphs of tree-independence number at most two. For maximum leaf number $\ell$, we obtain an $O(\ell^4)$-bit compression and a polynomial kernel. Finally, unless $\mathsf{NP}\subseteq\mathrm{coNP}/\mathrm{poly}$, we exclude polynomial kernels for bandwidth, feedback edge number, vertex-deletion distance to a clique, and vertex cover number. The last bound also excludes polynomial kernels for vertex-deletion distance to proper interval graphs.Authors: Ce Jin, Xiao Mao
We give a deterministic algorithm for finding a subset of the input integers $1\le a_1,\ldots,a_n \le Δ$ that sums to the target $t$ in $\mathcal{O}(n+Δ^{1+o(1)})$ time. This improves upon the previous $\widetilde{\mathcal{O}}(n + Δ^{1.5})$-time algorithm by Chen, Lian, Mao, and Zhang (SODA 2024), and achieves almost tight dependence on $Δ$ assuming SETH. We use an inverse theorem for subset sums due to Conlon, Fox, and Pham (2023), and develop a quotient variant of economic cap covering from the polytope approximation literature.Authors: Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud, Mathieu Mari, Prafullkumar Tale
We study the fixed-parameter tractability of the \textsc{Isometric Path Cover} problem where, given an integer $k$ and a simple, undirected, and unweighted graph $G$, the objective is to decide whether $G$ admits a set of $k$ isometric paths (i.e., shortest paths between their endpoints) whose union is the entire vertex set of $G$. We show that \textsc{Isometric Path Cover} is NP-hard on graphs of pathwidth (and thus treewidth) at most 287. This is an interesting contrast with the closely related problems \textsc{Isometric Path Partition} and \textsc{Path Cover}, which are both known to be XP for treewidth, see [Chakraborty et al., WG 2026] and [Foucaud et al., TCS 2026]. On the positive side, we show, by a suitable dynamic programming scheme, that \textsc{Isometric Path Cover} admits an XP algorithm w.r.t.~the parameter combination of treewidth and diameter, running in time $n^{\diam^{O(\tw)}}$ where $\diam$, $\tw$, and $n$ denote the diameter, the treewidth, and the number of vertices of the input graph, respectively. However, we also prove that \textsc{Isometric Path Cover} becomes W[1]-hard for pathwidth on graphs of diameter~7, showing that an XP algorithm is the best one can hope for w.r.t.~this parameterization, under standard complexity theory assumptions.Authors: L. Sunil Chandran, Rishikesh Gajjala, Suraj Kumar Sahoo, Aatman Supkar
We present compact SAT encodings and certifying exact solvers for boxicity and cubicity. The boxicity of a graph is the minimum dimension in which it is the intersection graph of axis-aligned boxes; cubicity is defined analogously using unit cubes. Grid-based formulations face a geometric discretization bottleneck, growing rapidly with the target dimension. We avoid this bottleneck by encoding the total order of interval endpoints in each coordinate. For an $n$-vertex graph and target dimension $d$, our boxicity encoding uses $O(n^2d)$ variables and $O(n^3d)$ clauses, both linear in $d$. Requiring the left- and right-endpoint orders to agree yields a cubicity encoding of the same asymptotic size. Satisfying models are decoded into independently checked geometric representations, while unsatisfiable instances used as lower-bound evidence carry mechanically verified DRAT certificates. In a controlled evaluation with 186 trials per encoding on standard and structured graph families, the order encoding solves 96.8% of trials, compared with 71.0% for the known grid formulation, and reduces mean PAR-2 time from 178.21 to 21.70 seconds. The pipeline also certifies exact values for several named graphs. We turn one such value into a reusable obstruction by proving that every Kneser graph $K(n,k)$ with $k\ge3$ and $n\ge2k+1$ contains an induced Desargues graph. The resulting lower bound, together with an explicit three-dimensional representation of $K(7,3)$, establishes $\operatorname{boxicity}(K(7,3))=3$. This disproves the conjecture of Caoduro and Sebo that $\operatorname{boxicity}(K(n,k))=n-k$ for all $k\ge3$ and $n\ge2k+1$.Authors: Linda Kleist, Ramin Kosfeld, Christian Rieck
The art gallery problem is a fundamental problem whose practical applications have inspired numerous variants. In this work, we investigate a setting in which full coverage of the gallery shall be ensured despite locational uncertainty of the guards. We study this problem for polyominoes under rectangular visibility, where a $k$-restless guard assigned to a cell may move to any cell within distance at most $k$. While all polyominoes are guardable for $k\in\{0, 1\}$, the same is not true for all $k\geq 2$. However, for a given polyomino $P$ and integer $k$, we present an algorithm that identifies a $k$-restless guard set of $P$ in polynomial time, or decides that no such set exists. For the cases $k\in\{0,1\}$, where $k$-restless guard sets always exist, we provide tight worst-case bounds on the number of $k$-restless guards that are always sufficient and sometimes necessary to guard a hole-free polyomino with $n$ vertices or $m$ cells. Moreover, we show that computing a minimum guard set is NP-hard. Complementing the hardness, we provide polynomial-time algorithms for solving the problem optimally for histograms, and leverage this to obtain a $20k$-approximation for polyominoes without holes.Authors: Chih-Hung Liu, Aaron Sidford, Ta-Wei Tu
In this paper we consider the problem of computing a positive diagonal scaling of a $d \times d$ symmetric $M$-matrix so that all row and column sums are $1$. We provide a poly-logarithmic iteration algorithm that solves this problem to high accuracy, where the cost of each iteration is dominated by the cost of solving a Laplacian system. This improves upon the recent $\tilde{O}(d^{1/3})$ iteration bound of [Vladu STOC 2025] and yields a randomized algorithm for the problem that runs in near-linear time and poly-logarithmic parallel depth.Authors: Sofya Raskhodnikova, Adam Smith, Connor Wagaman, Anatoly Zavyalov
We study the problem of approximately counting subgraphs under local node differential privacy (LNDP), a recently introduced model that enforces strong privacy guarantees in analyses of distributed social networks. We design a noninteractive $(\varepsilon,0)$-LNDP algorithm that, given any public $k$-node template graph $H$, counts occurrences of $H$ in a sensitive undirected $n$-node graph with additive error $O(n^{k-\frac{1}{2}}/\varepsilon^{k-1})$, for any constant $k$. We complement this algorithm with a lower bound showing that every noninteractive $(\varepsilon,δ)$-LNDP algorithm for counting copies of any $k$-node template graph with maximum degree greater than $1$ must have error $Ω(n^{k - \frac{1}{2}})$. Thus, our algorithm achieves optimal error for counting constant-size subgraphs, up to $\mathrm{poly}(1/\varepsilon)$ factors. Our results substantially expand the types of network statistics known to be approximable under LNDP: prior work considered only functions of the degree distribution. In addition, our lower bound yields the first known $\mathrm{poly}(n)$ gap between central and local node differential privacy when accuracy is required for all input graphs. Previous separations either only involved $\mathrm{poly}(1/\varepsilon)$ factors or only applied to promise problems.Authors: Bingbing Hu, Tomasz Kociumaka, Jakob Nogler, Barna Saha
Tree edit distance (TED), the analog of string edit distance (ED) for hierarchical data, is the minimum number of node insertions, deletions, and substitutions transforming one labeled rooted ordered tree into another. We narrow polynomial gaps between TED and ED in near-linear-time approximation, sublinear algorithms, and dynamic algorithms. We give an $n^{o(1)}$-approximation in $O(n)$ time and, for every $0<δ<1$, a $(\log n)^{O(1/δ)}$-approximation in $O(n^{1+δ})$ time. This improves the previous near-linear-time $O(\sqrt n)$-approximation [Boroujeni et al., STOC'19] and brings TED to parity with ED in this regime up to polylogarithmic factors. With query access to the balanced-parentheses (Euler-tour) representation of the input trees, we give the first sublinear-time TED algorithm: for every $τ\in[1,n]$, it computes a $τn^{o(1)}$-approximation of $1+\mathrm{ted}$ in $O(n/τ)$ time. For dynamic TED, we give an exact algorithm with amortized update time $\tilde{O}(k^7)$ and a $(1+\varepsilon)$-approximation with amortized update time $\tilde{O}_{\varepsilon}(k)$, where $k$ caps the distance that must be reported. The exact algorithm is the first to beat recomputation in a nontrivial parameter regime. The approximation improves prior dynamic guarantees [Das et al., FOCS'25] and cannot be significantly improved in any parameter regime without a breakthrough for static $(1+\varepsilon)$-approximation of ED. All results use dynamic programming on a new hierarchical tree decomposition, analogous to partitioning strings into blocks of geometrically decreasing sizes. It combines structural properties previously achieved only in isolation, providing a framework for transferring algorithmic ideas from ED to TED, with additional ingredients addressing the obstacles in each computational setting.Authors: Guido Lagos, Simón Ávila
We present an algorithm that computes the structural signature and the mean time-to-failure (MTTF) of a monotone binary system at every one of its states, rather than only at the state in which all components work. It makes no assumption on the structure function and evaluates it exactly once per state, as many times as needed for the signature of the complete system alone, so computing the MTTF everywhere costs only a factor polynomial in the number of components over computing it once. As a by-product, it identifies all minimal path sets. We assume exchangeable component failure times whose survivor count is a continuous-time Markov chain. This setting admits simultaneous failures, as in the Lévy-frailty Marshall-Olkin, binomial failure rate and lethal-shock models, where the simplifications available for single failures do not apply. We use the per-state MTTF to define threshold repair policies. We show that the per-state signature is a strictly finer decision criterion than the MTTF: signature dominance at a common failure count implies MTTF dominance, but not conversely. Under the Lévy-frailty Marshall-Olkin model the MTTF is monotone in the state, which yields the long-run cost rate of every threshold policy in a single pass. Experiments on 22 benchmark networks with up to 30 components and 31 failure models show that the best MTTF-threshold policy has a median excess cost of 0.36% over the optimal state-based policy, and that it is never worse than the best policy that repairs after a fixed number of failures.Authors: Jakob Nogler, Agnès Totschnig, Virginia Vassilevska Williams
In a seminal paper, Kratsch and Spinrad [SODA 2003 and SIAM Journal on Computing 2006] studied several important problems in structural graph theory that anticipated two trends in fine-grained complexity, both from the upper- and lower-bound side: * From the upper-bound side, for each of these problems the authors give an intermediate running time strictly between $n^ω$ and $n^3$, where $ω<2.371177$ is the matrix multiplication exponent. When optimized, this running time can be made $\tilde{\mathcal{O}}(n^{(3+ω)/2})$. By now, many more problems can be solved in this running time: directed unweighted or node-weighted APSP, a variety of matrix products such as max-min and dominance, RNA Folding and many more. For some of these, the community has also developed tools suggesting that this intermediate running time is necessary. * From the lower-bound side, the authors give lower bounds of $n^{ω-o(1)}$, conditioned on three natural hardness hypotheses on the complexity of quantified variants of triangle detection that account for different types of hardness of such problems. Despite this, it has remained open for over 20 years which of these two pieces of evidence reflects the truth for the problems that Kratsch and Spinrad study: whether the intermediate running time is indeed necessary and stronger lower bounds hold, or whether the hardness evidence of Kratsch and Spinrad is essentially tight. In this paper, we resolve this question and show that the latter is the case: all problems admit an $\tilde{\mathcal{O}}(n^ω)$ time algorithm. As an additional contribution, we make partial algorithmic progress on further problems in structural graph theory of intermediate complexity, improving over previous work [Chiu and Lu, STACS 2022 and Information and Computation 2024][Spinrad, Discrete Applied Math 2004].Authors: Nick Fischer, Jonas Schmidt
The Preprocessed 3SUM problem asks to preprocess a set $A$ of $n$ numbers so that we can quickly decide whether a query subset $A' \subseteq A$ contains a solution $a+b=c$. The best known query bounds differ substantially between integer and real inputs. For integers, a series of advances with near-quadratic preprocessing reduced the query time from $\tilde O(n^{13/7})$ [Chan, Lewenstein; STOC '15] to $\tilde O(n^{11/6})$ [Chan, Vassilevska W., Xu; STOC '23], and finally to $\tilde O(n^{3/2})$ [Kasliwal, Polak, Sharma; SOSA '25]. For reals, only the first of these bounds has been achieved, by adapting the corresponding integer algorithm [Fischer; SODA '25]. Is this gap inherent to the more limited tools available for real inputs? We give a randomized real-to-integer reduction with $\tilde O(n^2)$ preprocessing overhead and no asymptotic increase in query time. This yields $\tilde O(n^2)$ preprocessing and $\tilde O(n^{3/2})$ query time for real inputs, closing the gap. We show how to extend our result to the setting where one set is unknown at preprocessing time. Our reduction is conceptually simple, and relies on an interesting technical toolkit around old and new tools from sparse linear algebra. More broadly, it suggests a route to real-to-integer reductions for other additive problems.from David Eppstein
arXiv imposes a new limit of two submissions per submitter per month (\(\mathbb{M}\)).
Book of Shapes: A collection of minimal, generative and customizable SVG-patterns (\(\mathbb{M}\), via).
Sham scientific societies are misleading star researchers, according to Nature (\(\mathbb{M}\), via).
The \(13\times 13\) zebra graph is untraceable (\(\mathbb{M}\)). A zebra is a fairy chess piece that jumps like a longer knight, two steps in one direction and three in another. Almost a proof without words that the graph of its moves on a \(13\times 13\) chessboard has no Hamiltonian path.
The Harvard/Smithsonian Astrophysics Data System, a large bibliographic database for astronomy, astrophysics, and related fields, has been transitioning for the last year or so to become SciX with expanded areas of coverage “across space, Earth, and planetary sciences”, and is scheduled to complete the move in mid-November (\(\mathbb{M}\)). It’s difficult to find much about the move from adsabs to SciX that isn’t both heavy on promotion and light on content, but their press release is better than some, and there’s documentation on how to use SciX.
If you’ve ever wondered what those “bibcode” tags associated with some scientific references are, they’re pointers into this database. I imagine non-mathematicians have similar questions about what those “MR” and “Zbl” tags used for mathematical references are; the answer is the same, pointers to the MathSciNet and zbMATH databases respectively. And now I’m wondering why DBLP doesn’t have its own tags for computer science references.
Denny Vrandečić stumbled into a rabbit hole of unsourced Wikipedia claims about the production of a Spider Man movie, and AI hallucinations and circular reasoning when he tried to search for the missing sources and the edits that added the claims. The claims were eventually reinstated with proper sourcing, through the community of human editors of Wikipedia; Vrandečić concludes that, in contrast, “the AI in this case was actively harmful”.
If your \(\LaTeX\) input encodes an en-dash as a double-hyphen --, TeX will allow a line break after it. If it encodes it as a unicode en-dash character –, it will not allow a line break, both in pdflatex with \usepackage[utf8]{inputenc} and lualatex without (\(\mathbb{M}\)). Additionally, with the unicode en-dashes, pdflatex and lualatex will differ in how they break the words between the dashes: pdflatex will not break and hyphenate “Koebe–Andreev–Thurston” at all, but lualatex will break it as “Koebe–An- [line break] dreev–Thurston”. With double-hyphens, both are happy to produce the much better output “Koebe– [line break] Andreev–Thurston”. So let this be a lesson not to try to be fancy in how you type your dashes in \(\LaTeX\). Just use double hyphens (or triple hyphens for em-dashes) and let \(\LaTeX\) do the conversion to dashes.
On searching Wikipedia for article titles containing colons, like “ST:TNG”. It will think you are looking for an article titled “TNG” in the Sotho-language Wikipedia, regardless of how you try to escape the colon. But it turns out that, for Wikipedia, colons that are actually given in titles rather than used to demark other namespaces are equivalent to spaces. So the string you want to search for is “ST TNG”.
Numberphile video on Connor Hill’s classification of noble polyhedra (\(\mathbb{M}\)). A noble polyhedron has all faces and all vertices symmetric to each other, but not necessarily all edges. There are two infinite families and a lot of sporadic examples, especially if you allow self-intersections. Hill won the 2026 International Science and Engineering Fair, a high school student competition, for his determination of the complete list.
Show that two “ice cream cones” in a regular pentagon have the same angle (\(\mathbb{M}\)). A challenge problem on the mathematics StackExchange with a pretty diagram illustrating it.
Spanning surfaces of the same knot that cannot be deformed into each other, even in 4d (\(\mathbb{M}\)). Research from 2022 by Kyle Hayden, Seungwon Kim, Maggie Miller, JungHwan Park, and Isaac Sundberg, reported on at the time by Quanta, and helpful in understanding Maggie Miller’s new Joy of Why podcast episode “What Does the Fourth Dimension Actually Look Like?”.
What even is mathematical output? (\(\mathbb{M}\)). Among thoughts on AI in mathematics, David Roberts collects a farm of expert quotes on how horribly badly written and unintelligible the recent OpenAI preprint dump has been. Their Lean proofs aren’t any better: they contain large chunks of junk code that literally do nothing.
The septopert, a seven-sided polyhedron that cannot fit through a hole in itself.
Celebrating Loday’s associahedron (\(\mathbb{M}\)), 2023 survey by Pilaud, Santos, and Ziegler. See also two more recent articles on coloring the vertices of the associahedron: “A double-logarithmic upper bound on the chromatic number of the associahedron” (Oum and Wood), and “The chromatic number of the associahedron: simple and logarithmic” (Berendsohn, Cardinal, Iacono, and Kozma).
One of my cats, Smoke, looks through a window in the morning light (\(\mathbb{M}\)).

In the OpenAI Math Drop some papers have Lean proofs, others don't, including L = RL = BPL. Why is it hard to formalize results on complexity classes?
Let's consider an example, Lautemann's proof that BPP is in \(\Sigma^p_2\). It's a beautiful proof because it comes down to a single formula. I gave the full proof in a 2025 post, but to remind you, here is the setup.
Let \(B\) be in BPP, accepted by a probabilistic polynomial-time Turing machine \(M\) with error bounded by \(2^{-n}\). Let \(A(x,r)\) be true iff \(M(x)\) using random tape \(r\) accepts. \(A(x,r)\) is deterministically polynomial-time computable. We can assume \(|r|=|x|^k\) for some \(k\).
Here is the \(\Sigma^p_2\) expression for input \(x\) of length \(n\). All quantification is over binary strings of length \(n^k\). Let \(\oplus\) be bitwise parity (XOR) and \(\vee\) be logical OR.
\[\exists z_1,\ldots,z_{n^k}\ \forall y\ \ A(x,z_1\oplus y) \vee \cdots \vee A(x,z_{n^k}\oplus y)\]The hard part of the proof, besides coming up with this formula itself, is the probabilistic argument to show you always get the right answer.
So this seems simple enough to give a full Lean proof. And it is not too hard (for Claude) to get Lean to formalize the probabilistic argument, though even there Lean makes you deal with details we wave away on paper. When \(x\not\in B\) the argument needs \(n^k2^{-n}<1\), which fails for small \(n\), so short inputs need separate handling. But you also need to show the following:
Let \(A(x,r)\) be polynomial-time computable. Then given \(x\), \(y\) and the \(z_i\) as inputs, you can compute \(A(x,z_1\oplus y) \vee \cdots \vee A(x,z_{n^k}\oplus y)\) in polynomial time, where \(u\oplus v\) is bitwise parity.
There is nothing challenging about this statement. It is so painfully obviously true that I didn't even bring up this point in the 2025 post. But proving you can do this in polynomial time on a Turing machine, even though the only operations are bitwise parity, ORs and composition, is just very complicated to formalize in Lean.
Some suggest that using Cobham's characterization might be easier. But see below for what you need to do for bitwise parity alone. Imagine how complicated it would all get for something like Toda's theorem.
Update: Since I first drafted this post, OpenAI dropped a claimed Lean proof of L = RL = BPL, so maybe ignore this whole post?
Cobham defined his class as the smallest set of functions on the natural numbers (viewed as binary strings, with \(|x|\) the length of \(x\) and \(|0|=0\)) that contains the constant zero, the projections, the two successor functions \(s_0(x)=2x\) and \(s_1(x)=2x+1\), and the smash function \(x\#y=2^{|x|\cdot|y|}\), and that is closed under composition and bounded recursion on notation. The second operation defines a new function \(f\) from functions \(g\), \(h_0\), \(h_1\) in the class by \[\begin{aligned} f(0,\vec{y})&=g(\vec{y})\\ f(s_i(x),\vec{y})&=h_i(x,\vec{y},f(x,\vec{y})) \end{aligned}\] for \(i\in\{0,1\}\) and \(s_i(x)\neq 0\), provided that \(f(x,\vec{y})\leq k(x,\vec{y})\) for some \(k\) already in the class. The recursion runs over the bits of \(x\), so it takes only \(|x|\) steps. The smash function gives the outputs polynomial growth in their lengths, and the bound \(k\) keeps that growth from compounding over the recursion. Cobham's theorem says that this class is exactly the set of functions computable in polynomial time.
As an example, consider bitwise XOR, \(f(x,y)=x\oplus y\). The difficulty is that bounded recursion on notation peels bits off only one argument, while XOR has to move through \(x\) and \(y\) together. The fix is to recurse on a long enough counter \(T\) and extract the bits of \(x\) and \(y\) by shifting. We first need four helper functions, each defined by a single bounded recursion on notation: \[\begin{aligned} \mathrm{par}(0)=\mathrm{par}(s_0(x))&=0, & \mathrm{par}(s_1(x))&=1\\ \mathrm{half}(0)&=0, & \mathrm{half}(s_i(x))&=x\\ \mathrm{msp}(0,x)&=x, & \mathrm{msp}(s_i(w),x)&=\mathrm{half}(\mathrm{msp}(w,x))\\ C(0,u,v)=C(s_0(a),u,v)&=u, & C(s_1(a),u,v)&=v \end{aligned}\] with bounds \(1\), \(x\), \(x\) and \(s_1(u)\#s_1(v)\) respectively. Here \(\mathrm{msp}(w,x)=\lfloor x/2^{|w|}\rfloor\), so bit \(j\) of \(x\) is \(\mathrm{par}(\mathrm{msp}(w,x))\) for any \(w\) with \(|w|=j\). \(C\) is a conditional on the low bit of \(a\). Composition then gives the XOR of the low bits of \(a\) and \(c\), \(\beta(a,c)=C(a,\mathrm{par}(c),C(c,1,0))\), and appending the low bit of \(b\) to \(z\), \(\mathrm{app}(b,z)=C(b,s_0(z),s_1(z))\).
Now we recurse on \(w\) with \(T\), \(x\) and \(y\) as parameters, building the answer from the top bit down. Let \(m_i=\mathrm{msp}(s_i(w),T)\), which has length \(|T|-|w|-1\), the position of the next bit to append, and let \(b_i=\beta(\mathrm{msp}(m_i,x),\mathrm{msp}(m_i,y))\) be that bit of \(x\oplus y\). Then \[\begin{aligned} G(0,T,x,y)&=0\\ G(s_i(w),T,x,y)&=\mathrm{app}(b_i,G(w,T,x,y)) \end{aligned}\] By induction, \(G(w,T,x,y)\) is \(x\oplus y\) shifted right by \(|T|-|w|\) bits, so it is bounded by \(s_1(x)\#s_1(y)\). Finally we set \[f(x,y)=G(T,T,x,y)\quad\text{where } T=s_1(x)\#s_1(y).\] The smash gives \(|T|=(|x|+1)(|y|+1)+1\geq\max(|x|,|y|)\), so the recursion starts above the high bits of both arguments, where every bit is zero. \(T\) is much longer than it needs to be, but that costs only polynomially many extra steps.
By Lance Fortnow
In the OpenAI Math Drop some papers have Lean proofs, others don't, including L = RL = BPL. Why is it hard to formalize results on complexity classes?
Let's consider an example, Lautemann's proof that BPP is in \(\Sigma^p_2\). It's a beautiful proof because it comes down to a single formula. I gave the full proof in a 2025 post, but to remind you, here is the setup.
Let \(B\) be in BPP, accepted by a probabilistic polynomial-time Turing machine \(M\) with error bounded by \(2^{-n}\). Let \(A(x,r)\) be true iff \(M(x)\) using random tape \(r\) accepts. \(A(x,r)\) is deterministically polynomial-time computable. We can assume \(|r|=|x|^k\) for some \(k\).
Here is the \(\Sigma^p_2\) expression for input \(x\) of length \(n\). All quantification is over binary strings of length \(n^k\). Let \(\oplus\) be bitwise parity (XOR) and \(\vee\) be logical OR.
\[\exists z_1,\ldots,z_{n^k}\ \forall y\ \ A(x,z_1\oplus y) \vee \cdots \vee A(x,z_{n^k}\oplus y)\]The hard part of the proof, besides coming up with this formula itself, is the probabilistic argument to show you always get the right answer.
So this seems simple enough to give a full Lean proof. And it is not too hard (for Claude) to get Lean to formalize the probabilistic argument, though even there Lean makes you deal with details we wave away on paper. When \(x\not\in B\) the argument needs \(n^k2^{-n}<1\), which fails for small \(n\), so short inputs need separate handling. But you also need to show the following:
Let \(A(x,r)\) be polynomial-time computable. Then given \(x\), \(y\) and the \(z_i\) as inputs, you can compute \(A(x,z_1\oplus y) \vee \cdots \vee A(x,z_{n^k}\oplus y)\) in polynomial time, where \(u\oplus v\) is bitwise parity.
There is nothing challenging about this statement. It is so painfully obviously true that I didn't even bring up this point in the 2025 post. But proving you can do this in polynomial time on a Turing machine, even though the only operations are bitwise parity, ORs and composition, is just very complicated to formalize in Lean.
Some suggest that using Cobham's characterization might be easier. But see below for what you need to do for bitwise parity alone. Imagine how complicated it would all get for something like Toda's theorem.
Update: Since I first drafted this post, OpenAI dropped a claimed Lean proof of L = RL = BPL, so maybe ignore this whole post?
Cobham defined his class as the smallest set of functions on the natural numbers (viewed as binary strings, with \(|x|\) the length of \(x\) and \(|0|=0\)) that contains the constant zero, the projections, the two successor functions \(s_0(x)=2x\) and \(s_1(x)=2x+1\), and the smash function \(x\#y=2^{|x|\cdot|y|}\), and that is closed under composition and bounded recursion on notation. The second operation defines a new function \(f\) from functions \(g\), \(h_0\), \(h_1\) in the class by \[\begin{aligned} f(0,\vec{y})&=g(\vec{y})\\ f(s_i(x),\vec{y})&=h_i(x,\vec{y},f(x,\vec{y})) \end{aligned}\] for \(i\in\{0,1\}\) and \(s_i(x)\neq 0\), provided that \(f(x,\vec{y})\leq k(x,\vec{y})\) for some \(k\) already in the class. The recursion runs over the bits of \(x\), so it takes only \(|x|\) steps. The smash function gives the outputs polynomial growth in their lengths, and the bound \(k\) keeps that growth from compounding over the recursion. Cobham's theorem says that this class is exactly the set of functions computable in polynomial time.
As an example, consider bitwise XOR, \(f(x,y)=x\oplus y\). The difficulty is that bounded recursion on notation peels bits off only one argument, while XOR has to move through \(x\) and \(y\) together. The fix is to recurse on a long enough counter \(T\) and extract the bits of \(x\) and \(y\) by shifting. We first need four helper functions, each defined by a single bounded recursion on notation: \[\begin{aligned} \mathrm{par}(0)=\mathrm{par}(s_0(x))&=0, & \mathrm{par}(s_1(x))&=1\\ \mathrm{half}(0)&=0, & \mathrm{half}(s_i(x))&=x\\ \mathrm{msp}(0,x)&=x, & \mathrm{msp}(s_i(w),x)&=\mathrm{half}(\mathrm{msp}(w,x))\\ C(0,u,v)=C(s_0(a),u,v)&=u, & C(s_1(a),u,v)&=v \end{aligned}\] with bounds \(1\), \(x\), \(x\) and \(s_1(u)\#s_1(v)\) respectively. Here \(\mathrm{msp}(w,x)=\lfloor x/2^{|w|}\rfloor\), so bit \(j\) of \(x\) is \(\mathrm{par}(\mathrm{msp}(w,x))\) for any \(w\) with \(|w|=j\). \(C\) is a conditional on the low bit of \(a\). Composition then gives the XOR of the low bits of \(a\) and \(c\), \(\beta(a,c)=C(a,\mathrm{par}(c),C(c,1,0))\), and appending the low bit of \(b\) to \(z\), \(\mathrm{app}(b,z)=C(b,s_0(z),s_1(z))\).
Now we recurse on \(w\) with \(T\), \(x\) and \(y\) as parameters, building the answer from the top bit down. Let \(m_i=\mathrm{msp}(s_i(w),T)\), which has length \(|T|-|w|-1\), the position of the next bit to append, and let \(b_i=\beta(\mathrm{msp}(m_i,x),\mathrm{msp}(m_i,y))\) be that bit of \(x\oplus y\). Then \[\begin{aligned} G(0,T,x,y)&=0\\ G(s_i(w),T,x,y)&=\mathrm{app}(b_i,G(w,T,x,y)) \end{aligned}\] By induction, \(G(w,T,x,y)\) is \(x\oplus y\) shifted right by \(|T|-|w|\) bits, so it is bounded by \(s_1(x)\#s_1(y)\). Finally we set \[f(x,y)=G(T,T,x,y)\quad\text{where } T=s_1(x)\#s_1(y).\] The smash gives \(|T|=(|x|+1)(|y|+1)+1\geq\max(|x|,|y|)\), so the recursion starts above the high bits of both arguments, where every bit is zero. \(T\) is much longer than it needs to be, but that costs only polynomially many extra steps.
from ECCC Papers
Authors: Tomoyuki Yamakami
Greibach and Ginsburg (1969) studied abstract families of languages or AFLs. A full AFL is a class of languages closed under the following operations: homomorphism, inverse homomorphism, intersection with regular languages, union, concatenation, and Kleene star. Greibach (1970) used a restricted substitution, called nested iterated substitution, to introduce the notion of super AFLs, which are full AFLs that are further closed under nested iterated substitution. The smallest super AFL was shown to be the class of all context-free languages. From this fact, we focus on Greibach's limited, univariable application of nested iterated substitution and further generalize it into k-variate. This introduces the notion of nested iterated $k$-variate substitution whose definition does not rely on "machines". Recently, a "two-tape" version of Hibbard's (1967) rewriting systems, which were later reformulated by Pighizzini and Pisoni (2014) as k-limited automata with "single" input/work tapes, has been studied under the name of depth-k storage automata. This work unearths a few characteristics of the languages recognized by those automata under a restriction known as frozen blank sensitivity in terms of full AFLs and nested iterated k-variate substitution. This will promote a further abstract treatment of those languages.Authors: Tomoyuki Yamakami
Parikh's famous theorem relates to the semi-linearity of context-free languages. We seek for expanding the scope of the semi-linear property from context-free languages to languages beyond them. Of those languages, this work focuses on the languages that are particularly recognized by one-way nondeterministic depth-k storage automata under a natural restriction of frozen blank sensitivity. Those languages (which are called $k$-storable languages) have been already proven to satisfy a natural generalization of the well-known pumping lemmas for regular and context-free languages. The semi-linearity of k-storable languages generalizes Parikh's theorem on the semi-linearity of context-free languages. As for bounded languages, Ginsburg and Spanier's well-known theorem characterizes context-free languages in terms of stratified semi-linearity. This notion is further generalized and is used to characterize the k-storable languages as well. Such a generalization is interesting in its own right. This helps us take an abstract treatment of k-storable languages without relying on "machines". Our results strengthen the belief that those languages are "natural" generalizations of context-free languages.Authors: Kengo Hashimoto
Poset games form a fundamental class of combinatorial games that includes classical games such as Nim and Chomp. Determining the outcome of a poset game is known to be PSPACE-complete even for posets of height at most three. However, the exact computational complexity of Two-Level Poset Game, played on posets of height at most two, has remained an open problem for over a decade. We resolve this problem by proving that Two-Level Poset Game is PSPACE-complete via a polynomial-time reduction from Avoid True on positive CNF formulas.Authors: Aaron Sterling
Liu introduced generalized Fibonacci gates on domains of size 3 and 4, proved that Holant problems built from them are tractable by a cut-and-merge algorithm, and conjectured that Fibonacci gates with matching polynomial-time algorithms exist on all higher domains. We extend the definition uniformly to every domain size $k$ and show that a family of domain-$k$ generalized Fibonacci gates is the same thing as a $k$-dimensional commutative Frobenius (equivalently, Artinian Gorenstein) algebra $A$ equipped with an orthonormal basis containing $1$. Under this dictionary Liu's parameter constraints are exactly associativity of $A$, a gate is an element $w\in A$, merging two gates is multiplication in $A$, and the Holant value of a connected graph $G$ is $τ\bigl(h^{\,|E|-|V|+1}\prod_v w_v\bigr)$ for a fixed ``handle'' element $h\in A$. This proves Liu's conjecture for every $k$, with an algorithm whose cost is polynomial in $k$ as well as in the graph. We also give a closure criterion for linear recurrences of any depth (a balance condition implies closure, and is necessary when the unit is a combination of the colours), and we map the landscape: semisimple algebras are exactly Liu's orthogonal frames, smoothable algebras with nilpotents are collided frames, and families whose algebra is not smoothable (``frameless'' families) exist exactly when $k\ge 14$. Finally we show that every non-semisimple part of a family is invisible to the Holant on connected graphs with two or more independent cycles. This note states the results and sketches the proofs; the proofs of the main theorems are short and are given essentially in full.Authors: Daniel Dadush, Anita Dürr, Thekla Hamm, Jonas Schmidt, Karol Węgrzycki
We consider the problem of counting solutions to integer linear programming problems of the form $\{x \in \mathbb{Z}^n_{\geq 0} : Ax = b\}$ where $A \in \{-Δ,\ldots,Δ\}^{m \times n}$ and $b \in \mathbb{Z}^m$. We present an algorithm that counts solutions with $(nΔ)^{m + o(1)}\! \cdot \log\lVert b\rVert$ arithmetic operations. This simplifies the algorithm of Gribanov and Malyshev, who considered the problem for the more general setting in which $A$ is $Δ$-modular.Authors: Saint Wesonga
Bhrushundi et al. (2019) introduced torus polynomial approximation as an approach to separating Majority from $ACC^0$. In this model, approximation is measured modulo integers. Krishan and Vishwanathan (2026) developed a duality framework for lower bounds and posed five open problems. We resolve two of these, concerning integer lifts and explicit polynomial approximations. An integer lift records the integer shifts that turn a torus approximation into an ordinary real approximation. We show that a degree-d torus polynomial approximating Majority with error at most 1/8 and lift contained in an interval of width $B$ must satisfy $d(B + 1) = Ω(n)$. This rules out low-degree approximating polynomials with lifts in {-1, 0, 1}, answering their Open Problem 2. We also answer Open Problem 5 by giving, for every Boolean function on $n \geq 1$ variables, an explicit torus polynomial approximation of degree at most $n - 1$. Its error is optimal: zero when the accepting set has even cardinality and $2^{-n-1}$ otherwise. The results presented were discovered and formalized in Lean using GPT-6 Astra.Authors: Halley Goldberg, Jinqiao Hu, Zhenjian Lu, Jingyi Lyu, Igor C. Oliveira
Understanding the average-case complexity of $\mathsf{NP}$ is a central goal in complexity theory and cryptography. A necessary milestone is to understand the corresponding average-case versus worst-case question for the polynomial hierarchy ($\mathsf{PH}$). In a celebrated result, Hirahara [Hir21] proved that if every distributional problem in $\mathsf{PH}$ is easy on average, then every language in $\mathsf{PH}$ admits worst-case algorithms running in time $2^{O(n/\log n)}$. Remarkably, although the statement of Hirahara's theorem makes no reference to meta-complexity, all known proofs appear to use time-bounded Kolmogorov complexity and its associated meta-computational problems in an essential way. We show that the reliance on techniques and perspectives from meta-complexity is not simply a coincidence. Building on previous work of Hirahara [Hir20] and on a recent result of Hu, Lu, and Oliveira [HLO25], we prove that relating the average-case and worst-case complexities of $\mathsf{PH}$ is in fact equivalent to a purely meta-computational implication: efficient algorithms for a standard gap version of $\mathsf{MINpKT}$ with $\mathsf{PH}$ oracle access imply efficient algorithms for a mild gap version. Crucially, in these promise problems the standard gap separates a YES instance with time bound $t$ from a NO instance with time bound $\mathsf{poly}(t)$, whereas the mild gap keeps the YES threshold $t$ and moves the NO threshold to $t+\mathsf{poly}(n)$. Together with prior work, this equivalence points to the study of gap reductions as a potentially promising route toward understanding the relation between average-case and worst-case complexity. We make progress by proving that the gap in running time can be eliminated in the average-case setting. Finally, we prove that in the worst-case setting any efficient reduction between the two problems must use nonrelativizing techniques.Authors: Huanjian Zhou, Taiji Suzuki
We study the number of exact matrix-vector queries needed to sample a centered $d$-dimensional Gaussian with condition number at most $κ$ to total variation error $\varepsilon$. The best known algorithm uses $O(\min\{d,\sqrtκ\log(\frac{d}{\varepsilon})\})$ queries, while the known lower bounds do not grow as $\varepsilon\to0$ and match this bound only for $κ\le d^{1/5-δ}$ at constant accuracy. We introduce a construction based on a hidden determinant sign and prove a lower bound of $Ω\!\left(\min\left\{d,\sqrtκ\log\left(1+\frac{d}{\sqrtκ\,\varepsilon}\right)\right\}\right)$ uniformly for all $d\ge1$, $κ\ge4$, and $0<\varepsilon\le\tfrac{1}{16}$. This bound matches the known upper bound up to constant factors whenever $κ\le d^{2-δ}$ for fixed $δ\in(0,2)$, or $\varepsilon\le d^{-c}$ for fixed $c>0$. We also extend a recent fixed-spectrum construction with a hidden eigenbasis from $κ=2$ to $2\leκ\le d^{1-δ}$, for any fixed $δ\in(0,1)$. This gives an $Ω_δ(\sqrtκ\log d)$ lower bound at constant accuracy that holds even when the spectrum of the precision matrix is known to the algorithm.Authors: Laurie Boveroux, Margarida Carvalho, Andrea Lodi, Quentin Louveaux
While sensitivity analysis for linear programs with parametric right- hand side vectors is well established, cases involving parametric constraint matrices remain less explored. To address this gap, we investigate linear programs where the constraint matrix depends linearly on a scalar parameter. Our goal is to compute the minimum and maximum optimal values of these parametric linear programs within a fixed parameter range. This corresponds to solving two bilevel programs. We show that both decision versions of these optimization problems are NP-complete by proving both NP-hardness and membership in NP. We additionally identify three sufficient conditions on the parametric matrix under which the bilevel programs are no longer NP-hard. We introduce a reformulation for both problems, together with a Farkas-based certificate for the lower-level feasibility condition, and compare the execution time for solving them on standard benchmark instances. The experiments highlight a practical dichotomy. Although both bilevel optimizations are NP-hard, computing the parameter value corresponding to the minimum of the linear program is fast, whereas computing the value corresponding to the maximum is not. We relate this asymmetry to the parametric equality constraints, whose free dual variables leave the relaxation of the maximum reformulation unbounded.Authors: Halley Goldberg, Jinqiao Hu, Zhenjian Lu, Jingyi Lyu, Igor C. Oliveira
Symmetry of Information (SoI) [ZL70] is a fundamental theorem of classical Kolmogorov complexity whose status for time-bounded computation is closely related to central open problems in complexity theory and cryptography. In a recent development, [HMO26] showed that SoI fails for $rKt$ complexity, namely in the setting of randomized computation. By contrast, many basic properties of Kolmogorov complexity are known to remain valid in the presence of nondeterminism [HLO26], suggesting that SoI may provide a fruitful structural principle for exploring the relative power of randomness and nondeterminism in computation. Our results reveal that the validity of SoI for nondeterministic computation, namely for $nKt$ complexity, is a subtle question connected to several frontiers. We show that symmetry of information holds on average for randomized extensions of $nKt$, while its worst case validity would imply breakthrough complexity separations. Although the standard cryptographic argument for asymmetry does not extend to the nondeterministic setting, we provide evidence that information remains asymmetric in nondeterministic computations. Among other results, we show that SoI would imply a collapse of exponential time classes to low levels of the polynomial hierarchy. Then, building on the work of [Hir22b, GK22, KK26, HMO26], we develop a general framework connecting symmetry of information, meta-complexity, and explicit constructions in the nondeterministic setting. More precisely, we prove that suitable formulations of these three notions are quantitatively equivalent. We apply different aspects of this correspondence to make progress on complexity lower bounds and on the failure of SoI for nondeterministic computation. These consequences are unconditional and provide some of the strongest known lower bounds in meta-complexity.Authors: Ditbul Ban, Younghun Roh, Julian Shun, Vihan Lakshman
Quantifying the diversity of a set of objects is a fundamental problem in machine learning and statistics. Mironov and Prokhorenkova (2025) recently showed that three axioms-monotonicity, uniqueness, and continuity-are crucial for a reliable diversity measure and that none of the standard metrics in the literature satisfy all three. They also constructed two measures that do satisfy the axioms, but both are NP-hard to compute, leaving open the question of whether efficient axiomatic diversity measures can exist. We study a Euclidean-restricted version of this question. We introduce Geometric Kernel Diversity (GKD), which associates a radial kernel solid with each point and measures the volume of their union. We show that canonical GKD satisfies all three Mironov-Prokhorenkova axioms on Euclidean-realizable inputs. For canonical GKD, we give exact polynomial-time algorithms in dimensions $d \le 3$. In arbitrary dimensions, we give a randomized algorithm that returns a $(1 \pm \varepsilon)$-approximation with probability at least $1-δ$ in time $O \left(\frac{nd}{\varepsilon^2}\log\frac{2}δ\right)$ for $n$ points. The axiomatic guarantee applies to exact canonical GKD; the randomized algorithm approximates this deterministic quantity. We further show that the two diversity measures of Mironov and Prokhorenkova (2025) remain NP-hard on Euclidean-realizable inputs and, unless $\mathrm{NP} = \mathrm{RP}$, admit no FPRAS even on this restricted domain.Authors: Malik Barrett
In the classical art gallery problem, a guard sees a target when the segment joining them lies entirely within the polygon. We explore what changes when sight may bend along regular arcs on absolutely irreducible curves, but only those defined by primitive integer polynomials of total degree at most \(d\) and coefficient height at most \(H\). We call such curves admissible sight carriers. Arcs can dramatically improve sight. In a one-sided comb, no straight-line guard sees selected targets in two different teeth, yet a single central guard sees a chosen target in every tooth along parabolic carriers. Sight can also fail in two different ways. Geometrically, the polygon may block every sight arc of the allowed degree between two points. For instance, in an alternating comb, the number of guards needed for a row of targets spanning the comb grows linearly with the number of sides at each fixed degree, even for carriers with arbitrary real coefficients. Arithmetically, no admissible carrier may pass through the points at all. Even in the unit square, at fixed \(d\) and \(H\), the proportion of rational targets that must guard themselves tends to one as the height bound grows. An algebraic target may lie on no rational curve of degree at most \(d\), however large \(H\) is. Both failures can be overcome for finite target sets by allowing the degree and coefficient height to grow. We show that every finite set of algebraic targets in a rational polygon becomes visible from any rational interior guard, with explicit bounds. We also construct, for every \(d\), arbitrarily large Galois orbits in the unit square, all of projective height \(4^{d+1}\), whose points must each guard themselves at degree \(d\) for every \(H\). Yet at degree \(d+1\) and coefficient height one, a single guard sees the whole orbit along \(Z(Y-X^{d+1})\).Authors: Emanuel A. Lazar, Chris H. Rycroft
Widely used methods for identifying crystal structure in atomistic simulations are limited in practice to a handful of simple structures, leaving many important crystalline systems without automated classification techniques. Voronoi topology analysis offers a route to classifying arbitrary crystalline and defect environments, but realizing this potential first requires enumerating the Voronoi cell topologies that can arise under thermal perturbation of a structure of interest. We present an algorithm that deterministically enumerates all Voronoi cell topologies arising from generic infinitesimal perturbations of an arbitrary crystal structure, producing structural classifiers that extend automated identification to general crystalline systems. We demonstrate the approach on several structures of general interest.Authors: Deepak Ajwani, Paula Carroll, Rishikesh Gajjala, Ananta Manoranjan, Ryan O'Connor, Rajiv Raman, Saurabh Ray, Aimen Taha
Extremal constructions play a central role in the design and analysis of algorithms. Integrality-gap instances expose the limitations of relaxations, while hard configurations reveal structural sources of computational difficulty. Such constructions, however, are still typically discovered through a slow, manual process. This paper investigates how machine learning can accelerate their discovery to support algorithm design and analysis. We build on PatternBoost, a framework alternating local search with generation from a trained transformer, using its Axplorer implementation to investigate three problems: integrality gaps for maximum independent set of rectangles, integrality gaps for stabbing unit squares with axis-parallel lines, and hard instances for recursive guillotine cutting. By exploring candidate representations, local search operations, and surrogate models used to rank candidates before exact verification, we carefully adapt the framework to these combinatorial geometry problems.While naive representations and search strategies fail to find non-trivial instances, our tailored adaptation discovers numerous non-trivial constructions. For stabbing unit squares, the method reaches a gap of $20/13\approx 1.54$, improving on the literature's best known lower bound of $3/2$. Purely automated search converges rapidly and then plateaus, prompting the question of what is required to push the bound higher still. We find that initial instance diversity plays an important role: with modest expert input via a structured staircase construction, the system reaches an improved integrality gap of $14/9\approx 1.555$. These results demonstrate that machine learning and domain expertise can be combined to discover new extremal constructions that advance algorithmic lower bounds.Authors: Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui
We study proportional cake cutting under an equal-length constraint, where each of $n$ agents must receive a bundle of length exactly $1/n$ that is worth at least $1/n$ to that agent. Our main result determines the exact worst-case number of cuts needed to guarantee such an allocation, namely $2n-2$ for every $n$. This improves on the previously known quadratic upper bound. The proof combines the constrained necklace-splitting theorem with a recursive assignment argument based on Hall's theorem. The same bound extends to the stronger requirement of envy-freeness when $n$ is a prime power, and an $O(n^{1.525})$ upper bound holds for arbitrary $n$. We then ask whether such allocations can be computed. We first show that no deterministic protocol in the Robertson--Webb model terminates after finitely many queries on every instance and always returns an exact equal-length proportional allocation, even for two agents with identical valuations. For every $\varepsilon>0$, however, $O(n^2/\varepsilon)$ queries suffice to produce an allocation in which every agent receives a bundle of length exactly $1/n$ and value at least $1/n-\varepsilon$, again using at most $2n-2$ cuts. Finally, we augment the Robertson--Webb model with two-knife queries. We show that recursive balanced halving attains the optimal bound of $2n-2$ cuts when $n$ is a power of two. For arbitrary $n$, we give a procedure using $O(n\log n)$ cuts.Authors: Yann Bourreau, Filippo Casagrande, Tim Göttlicher, Ananth Narayanan Karunattillam
We give a dynamic graph algorithm which maintains a 3-coloring in bipartite graphs under edge insertions such that the coloring only changes within a radius of $O(\log n)$ around an inserted edge. In the context of locality theory in distributed graph algorithms, this gives an upper bound on the locality under the dynamic-LOCAL model. Our bound on the locality is tight, as the problem admits a matching $Ω(\log n)$ lower bound in the stronger online-LOCAL model, by a result of Chang et al. [PODC 2024]. Thus, our result closes the gap between dynamic and online locality of this problem.Authors: Mirza Galib Anwarul Husain Baig, Aman Kumar, Pawan Kumar Saw, Vikash Tripathi
We study non-adaptive bit-probe schemes for static set membership. Each query reads a fixed number of bits and answers by strict majority. We revisit the random bipartite-graph construction of Garg and Radhakrishnan [STACS, 2017]. The main observation is that a slightly stronger expansion property already bounds the number of exceptional elements. This makes a separate probabilistic estimate for exceptional elements unnecessary. A detailed union-bound calculation then gives, for every fixed $t\ge5$, a logarithm-free existence bound of $O_t(m^{1/c}n^{1-1/c})$, where $c=\lfloor(t-1)/2\rfloor$. For odd $t$, this removes the logarithmic factor from the general upper bound of Garg and Radhakrishnan [STACS, 2017].Authors: Quanlong Niu, Riheng Jia
The Emergency Vertex Cover problem (Em-VC) assigns budgets to stations at graph vertices to cover every edge while minimizing the total budget. The cost of covering an edge from a station is the shortest-path distance from the station to the nearer endpoint plus the edge length. We study how restricting the number of stations affects the cost of ordinary and fault-tolerant coverage. In ordinary Em-VC, we prove that the optimal solution using at most two stations costs at most $5/4$ times the unrestricted optimum, improving the known $4/3$ guarantee for a single station. A recurrence extends this bound to larger station limits, giving approximation factors that converge to $\sqrt{5}-1$. Budget-threshold enumeration computes the restricted optimum in polynomial time for every fixed station limit. Under $k$-fold coverage, every edge must be covered by at least $k$ distinct stations, ensuring coverage after any $k-1$ station failures. We prove that selecting the $k$ vertices with the smallest full-coverage costs yields a $2$-approximation relative to the unrestricted optimum for $k$-fold coverage. When $k=2$, we combine upper bounds derived from the structure of the covering balls to improve the approximation guarantee to $5/3$.Authors: Yinhao Dong, Pan Peng, Ali Vakilian, Santhoshini Velusamy, Xiaoyang Xu
We study learning-augmented streaming algorithms for estimating the value of Boolean Maximum Constraint Satisfaction Problems (Max-CSPs). Specifically, we consider streaming algorithms equipped with an $\varepsilon$-accurate oracle: for each variable, the oracle outputs a label in $\{-1,1\}$ that agrees with a fixed optimal assignment with probability $1/2+\varepsilon$, and disagrees otherwise. Prior work by Dong, Peng, and Vakilian [ITCS 2025] showed that, for the special case of Max-Cut, such an oracle enables a $(1/2+Ω(\varepsilon^2))$-approximation using $\operatorname{poly}(1/\varepsilon)$ words of space in insertion-only streams, and $\operatorname{poly}(1/\varepsilon,\log n)$ words of space in dynamic streams. We substantially generalize and strengthen their result, provided that a highly accurate estimate of $\varepsilon$ is available. For any Boolean Max-$2$CSP and any $η>0$ independent of $\varepsilon$, we obtain, with high constant probability, a single-pass $(1-η)$-approximation using $\operatorname{poly}(1/\varepsilon,1/η)$ words of space in insertion-only streams, and $\operatorname{poly}(1/\varepsilon,1/η,\log n)$ words of space in dynamic streams, where $n$ is the number of variables. We further extend our techniques to general Boolean Max-$k$CSPs for $k\ge 3$, with slightly worse space complexity.Authors: William Kuszmaul
In this note we explore the following simple question: How does the classic \emph{gambler's ruin} phenomenon change if we allow the gambler \emph{financial leverage}? We show that, with a moderate amount of leverage, it is possible for an (idealized) gambler to sustain seemingly improbable profits over a remarkably long time horizon without ever going bankrupt, \emph{even} if the gambler makes only fair bets. With a leverage ratio of $L = 10$ (less than what Lehman Brothers Holdings had from 1995--2008), the probability of multiplying one's money by $1000\times$ without going bankrupt is roughly $50\%$. More generally, given $L$-fold leverage, and given the goal of multiplying one's money by a factor of $r > 1$, the optimal gambling strategy has probability roughly $r^{-1/L}$ of success. The results in this note are designed as part of the course development for the CMU randomized algorithms course.Authors: Mina Dalirrooyfard, Christopher Ye
Tokenization is an essential preprocessing step in almost all large language models (LLMs). One of the most popular frameworks is BPE tokenization, which consists of special token segmentation, pretokenization, and byte-pair encoding (BPE). However, existing algorithms are sequential, with each stage only processing complete output from the previous stage. In order to reduce latency and memory footprints, recent works (Jiang and Gong, ICML 2026) (Li, Yang and Mamouras, ASPLOS 2026) (Mamouras, Li and Yang, PLDI 2026) have initiated the study of online algorithms for subroutines such as pretokenization and BPE with a goal of streaming input to output as the input arrives online. However, the search for efficient online tokenization remains open. In this work, we formalize and resolve online tokenization. We introduce the notion of delay for online tokenization which characterizes the extent to which the algorithm output lags behind the (possibly computationally intractable) optimum. We give a near-linear time algorithm with optimal delay (up to constant factors). We complement this algorithm with a conditional lower bound: unless $\mathbf{P} = \mathbf{NP}$, there is no polynomial time algorithm that beats the delay of our algorithm by more than a constant factor. We implement a practical variant for tokenizers from OpenAI's tiktoken and HuggingFace's tokenizers. We obtain a $7.9\times$-$34.8\times$ latency advantage (measured as time to first token) over tiktoken (as well as the recent gigatoken tokenizer) and our implementation maintains approximately constant memory usage independent of input size. Our implementation also achieves a $2.4\times$-$7.0\times$ improvement in throughput over tiktoken and $15.8\times$-$38.1\times$ over tokenizers.Authors: Maria Chudnovsky, Ilya Maier
A $u\hbox{-}v$ separator in $G$ is a set $S\subseteq V(G)\setminus\{u,v\}$ such that there is no $u\hbox{-}v$ path in $G\setminus S$. A minimal separator in $G$ is a set $S$ such that for some $u,v\in V(G)\setminus S$, $S$ is a $u\hbox{-}v$ separator in $G$ but no proper subset of $S$ is. A set $S$ is bisimplicial if it is the union of at most two cliques. Recognizing graphs in which every minimal separator is the union of at most $k$ cliques is polynomial-time solvable for $k=1$ and NP-hard for every fixed $k\geq 3$. We settle the remaining case $k=2$ by giving a polynomial-time algorithm to decide whether every minimal separator in a graph is bisimplicial. A set $S$ is triad-free if its independence number $α(S)$ is at most two. Given a graph $G$ and two vertices $u,v$, the problem of finding a $u\hbox{-}v$ separator $S$ with $α(S)\leq k$ had the same complexity gap: it was known to be polynomial-time solvable for $k=1$ and NP-hard for every fixed $k\geq 3$. We resolve the remaining case $k=2$ by giving a polynomial-time algorithm that finds a triad-free $u\hbox{-}v$ separator or determines that none exists.Authors: Sayan Bandyapadhyay, William Lochet, Saket Saurabh, Jie Xue
We study multi-robot motion planning in a polygonal environment with polygonal robots. The setting of the problem consists of a polygonal domain $\mathcal{W}$ with $n$ vertices and $k$ robots $R_1,\dots,R_k$ translating in $\mathcal{W}$ each of which is represented by a polygon of constant complexity. Given a source configuration $\mathbf{s}$ and a target configuration $\mathbf{t}$ of the robots in $\mathcal{W}$, the goal of the problem is to find a collision-free motion plan from $\mathbf{s}$ to $\mathbf{t}$ that is shortest with respect to some cost function. We present the first fully polynomial-time approximation schemes (FPTAS) for motion planning with any fixed number $k$ of robots, under the min-sum objective, the min-max objective, and the min-makespan objective. Here, the min-sum variant aims to minimize the total traveling distance of all robots, the min-max variant aims to minimize the maximum traveling distance of a single robot, and the min-makespan variant aims to minimize the total time cost under the assumption that all robots move with a maximum speed $1$. The algorithm directly generalizes to the problem in any fixed dimension $d$, with a polytope environment and polytope robots. Our result settles an open question of Agarwal, Halperin, Sharir, Steiger [SODA'24] and Agarwal, Holmgren, Steiger [SODA'26], who gave an FPTAS for $k=2$ unit-square robots and a bicriteria-approximation algorithm for a fixed number $k$ of unit-square or unit-disk robots, respectively. Compared to the previous results, our algorithm is substantially simpler.Authors: Rajat Adak
Edge deletion problems ask for the fewest edges whose deletion gives a graph with a specified property. We study two such problems on block graphs. First making the graph claw-free, and second making it a line graph. Since every line graph is claw-free, the second problem is at least as difficult as the first. We show that on block graphs the two optimum values are always equal, and both are attained by the line graph of a forest. The main step is a completion argument, in which starting from any claw-free solution, we put back edges to get some nice structure inside each block still maintaining the claw-free property. This reduces both edge-deletion problems to the same problem of selecting vertices within the blocks of the input graph. We solve it by dynamic programming in $O(n+m)$ time, which also produces an optimal deletion set and a forest whose line graph is what remains after the completion argument. We also extend the method to $K_{1,r+1}$-free edge deletion for every fixed $r$.Authors: Adrian Miclăuş, Alexandru Popa, Andrei Popa
We study \textsc{Bounded-Density Vertex Deletion} (BDVD), where one asks whether at most \(k\) vertices can be deleted so that every remaining subgraph has density at most a rational input threshold \(τ_ρ\). We address the twin-cover and distance-to-cluster cases left open by Raupach, Breitkopf, Herrmann, and Nichterlein (MFCS 2026). We prove fixed-parameter tractability parameterized solely by the twin-cover number, for unrestricted input density. For distance to cluster, we establish fixed-parameter tractability parameterized by \(\operatorname{dc}(G)+\lfloor2τ_ρ+1\rfloor\), and complement this with \(\mathsf{W[1]}\)-hardness parameterized by \(\operatorname{dc}(G)\) alone when the target density is part of the input, even for integral targets. Thus distance to cluster alone is fixed-parameter tractable throughout \(τ_ρ<1\), while it is insufficient for unrestricted input density. Finally, we settle the combined parameter treewidth plus solution size, an open problem posed by Bazgan, Nichterlein, and Vazquez Alferez (JCSS 2025). We prove that BDVD is \(\mathsf{W[1]}\)-hard parameterized by \(\operatorname{td}(G)+k\), and hence also by \(\operatorname{tw}(G)+k\), already for targets strictly between \(1\) and \(2\).Authors: Barna Saha, Christopher Ye
In this note, we provide a deterministic algorithm that computes the $(\min, +)$-Matrix Product $C = A * B$ of two $N \times N$ matrices $A$ and $B$ with polynomially bounded integer entries in $\tilde{O}(N^{2.9964})$ time, improving upon the exponent of $O(N^{2.9995})$ time obtained in the recent breakthrough by Anthropic (Alman and Vassilevska Williams, 2026). Our algorithm uses a phased approach first proposed by Bringmann, Grandoni, Saha, and Vassilevska Williams in 2016. The phased approach produces an approximation $\tilde{C}$ of $C$ in truly subcubic time such that the number of remaining triples $(i,k,j): A_{i,k}+B_{k,j} < \tilde{C}(i,j)$ is truly subcubic. This provided strong evidence that a truly subcubic $(\min, +)$-Matrix Product and therefore, a truly subcubic algorithm for All Pairs Shortest Paths (APSP) may exist. However, to find the remaining triples in subcubic time, a sparse certificate is needed whose construction was not known. We use the thin matrix product theorem of the recent breakthrough to provide such a certificate. This gives a simple modular subcubic algorithm for APSP.Authors: Rudranarayan Kar, Diya Roy, Abhishek Sahu
Clustering is a basic tool for grouping data into meaningful classes, but in many applications the resulting clusters must also respect the fairness conditions among different groups. We study this direction for the group-fair Euclidean $k$-center problem in fixed dimension, where the input points are partitioned into disjoint color classes, and every cluster must satisfy given lower and upper bounds on the fraction of each color. We give a separator-based recursive approximation algorithm for the continuous-center setting. The main idea is to first reduce the continuous search space to a finite candidate center set and then use the geometric sphere separators to break the instance into smaller subproblems. Our algorithm gives a bicriteria approximation: the clustering radius is within a factor of $(1+ε)$ of the optimum exactly fair solution, while the fairness bounds are relaxed only by a multiplicative factor. For fixed dimension, number of colors, and approximation parameters, the running time is polynomial in input size and subexponential in $k$. A recent IJCAI-ECAI2026 result gives a $(1+ε)$-approximation for group-fair $k$-center in bounded doubling metrics with running time $(k/ε)^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$. In the fixed-dimensional Euclidean setting considered here, we improve the dependence on $k$ to subexponential, while allowing continuous centers. The fairness guarantees of the two results are different: the previous work allows an additive fairness violation, whereas our algorithm uses a controlled multiplicative relaxation.Authors: Zizong Wang, Yibo Wang
We give a randomized polynomial-time $0.48$-approximation for maximizing a nonnegative non-monotone $k$-submodular function under a matroid constraint, for every $k\ge2$. The algorithm combines a top-two label rule with a nested-chain potential and maximum-weight matroid bases. Its analysis reduces the approximation guarantee to a one-dimensional time allocation: a uniform local lower bound leads to a linear differential equation, concavity closes the remaining interval, and two elementary budgets complete the proof. A strict saving in the time budget absorbs sampling and discretization errors, yielding the exact $0.48$ guarantee in the value-oracle model.Authors: Paul Duetting, Michal Feldman, Mathieu Molina
We resolve the problem of unweighted online stochastic matching with a known arrival law by establishing its optimal competitive ratio. For Poisson arrivals, we achieve $1-e/e^e\approx0.8206$, matching the upper bound of Chierichetti, Giacchini, Panconesi, and Vattani [ICALP 2025]. For exactly $n$ i.i.d.~arrivals, we obtain the same guarantee up to an additive $O(n^{-1/2})$ loss. Our key technical contribution is an exact correspondence between Poisson matching and exponential scheduling, preserving both online performance and the expected offline optimum. To prove the latter, we show that the distribution of the maximum of a random supermodular set function is determined by its joint distributions along chains of nested sets, a result of independent interest. This reduces the analysis to chains, where classical Poisson--exponential duality applies. The offline equivalence extends to arbitrary nonnegative edge weights. We then design a posterior allocation policy for exponential scheduling and use the correspondence to transfer its optimal competitive guarantee to online matching. Additionally, we show that the optimal competitive ratio under an unknown arrival law is strictly lower than $1-e/e^e$, establishing a strict separation between the known and unknown arrival models.from TCS+ Seminar Series
The next TCS+ talk will take place this coming Wednesday, October 21st at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Rachel Zhang from UC Berkeley will speak about “Linear Time Encodable Quantum Error-Correcting Codes” (abstract below).
You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.
Abstract: In this talk, I will describe a construction of quantum CSS codes with rate-distance tradeoff approaching the CSS GV bound, which can be encoded by a quantum circuit of logarithmic depth and a linear number of gates. Our construction is heavily inspired by a work of Brehm and Resch and can be viewed as a quantum analogue of classical multiple accumulate codes. The encoder has a particularly simple structure, consisting of a single constant depth outer quantum circuit followed by several classical accumulation and inverse-accumulation layers.
from CCI: jobs
The Institute for Advanced Study is holding a special year in Expansion and Computation in 2027/2028. We are seeking PhD holders with interest in theoretical aspects of computer science and extensive background in relevant areas in mathematics.
Website: https://www.ias.edu/math/events/special-year-expansion-and-computation
Email: dinuri@gmail.com, dminzer@mit.edu
from ECCC Papers
from ECCC Papers
from ECCC Papers
Authors: Khazaliya Liana, Kuske Clemens
Non-clashing teaching minimizes teaching complexity among models satisfying the Goldman--Mathias collusion-avoidance criterion. While the Vapnik--Chervonenkis dimension (VCdim) measures the complexity of learning from samples, non-clashing teaching dimension (NCTD) measures the number of examples required when a teacher can select them. Whether NCTD is always bounded above by VCdim remains a fundamental open question in learning theory. In this paper, we investigate this question for the concept classes of closed neighborhoods in planar graphs. We prove a tight upper bound of two on their NCTD, thereby establishing the conjectured inequality for this family. For the positive variant NCTD+, in which teaching sets contain only positive examples, we obtain a tight upper bound of four. Finally, we show that deciding whether either NCTD+ or NCTD is at most one is NP-complete, even for concept classes of closed neighborhoods in planar graphs. In particular, despite the upper bound of two on NCTD for such classes, distinguishing between NCTD values of one and two remains NP-hard.Authors: Alkis Kalavasis, Panagiotis Patsilinakos, Stratis Skoulakis, Manolis Zampetakis
We study the complexity of computing approximate first-order Nash equilibria in min-max optimization problems with one dimensional min and max players and product constraints. For black-box access to the objective, we prove that any algorithm requires $Ω(1/\sqrtε)$ queries to find an $ε$-first-order Nash point. In the white-box setting, we establish CLS-hardness by reducing from End-of-Potential-Line. These results show that even the simplest min-max setting with one dimensional min and max players is at least as hard as CLS and therefore does not admit polynomial-time algorithms unless $\mathsf{CLS}\subseteq \mathsf{P}$.Authors: Diyi Liu, Shuchen Zhu, Wibe Albert de Jong, Di Fang, David Williams-Young, Chao Yang
We construct Clifford+$T$ circuits implementing arbitrary $n$-qubit unitaries with worst-case $T$-count $\widetilde{O}(N^{8/7})$ at constant operator-norm error, where $N=2^n$, improving the previous exponent $5/4$. The construction uses $\widetilde{O}(N^{6/7})$ clean ancillas. The main idea is to reduce the data addressed by each query to the block-encoding circuit for a sparse piece while controlling the additional simulation work needed to combine the pieces. We simulate a Hermitian logarithm of the target by flattening its traceless part with a two-layer random similarity transformation, randomly partitioning the transformed generator into block-sparse Hermitian pieces, and combining their evolutions using qDRIFT. For a target operator-norm error $ε\in(0,1/2)$, let $L=\log_2(N/ε)$, the qubit count plus the requested bits of accuracy. By successively correcting the approximation error, we obtain a circuit using $\widetilde{O}(N^{8/7}L^{3/7}+NL)$ $T$ gates and $\widetilde{O}(N)$ clean ancillas whenever $L\le N$. We also prove that, at constant precision, the exponent $8/7$ is optimal within a sequential block-SELECT model.Authors: Walid Ben-Ameur, Alessandro Maddaloni
In the Hunters and Rabbit game, hunters shoot at a set of vertices at each round, while an invisible rabbit must move along an edge. We prove that deciding whether a given number of hunters can guarantee capture is PSPACE-complete, even on simple bipartite graphs. The reduction uses intersection nonemptiness for inverse finite automata: one common word must put all automata in accepting states simultaneously. A clique acting as a safe haven and two families of guards force every winning strategy to simulate common transitions. Existing transformations remove the restriction on the rabbit's initial positions and yield PSPACE-completeness for the directed game with one hunter, even on oriented graphs with positive minimum outdegree. Adjusting the guard sizes also proves PSPACE-completeness of the firefighting game, in which the rabbit may remain at its current vertex.Authors: Antoine Amarilli, Mikaël Monet, Harshul Sagar
We consider the problem of computing the probability of existence of a source-to-target path or walk satisfying a given length constraint in an input probabilistic graph. The length constraints we consider can require the length to be at least $\ell$, at most $\ell$, or exactly $\ell$, for $\ell$ a target length given as input. The probabilistic graphs that we consider are directed graphs where each edge is annotated with an independent probability of existence. As this task is generally intractable (#P-hard), we aim for algorithms applying to input graphs that are assumed to be of bounded treewidth. We classify the complexity landscape of these problems: - We give an XP algorithm parameterised by treewidth to compute the probability that an input probabilistic graph contains a source-to-target path/walk of length $\geq \ell$, and do the same for a path/walk of length $\leq \ell$. - We show that the four problems mentioned in the last item are W[1]-hard parameterised by pathwidth (hence not FPT under the standard assumption that FPT$\neq$W[1]). This is in contrast to the case of non-probabilistic graphs, where the corresponding problems were known to be FPT parameterised by treewidth; and to the connectivity problem (and more generally MSO evaluation) on probabilistic graphs, where the same was known. - Surprisingly, we show that it is #P-hard to compute the probability that an input graph contains a source-to-target path/walk of length exactly $\ell$, even on graphs of pathwidth $2$. By contrast, all our problems are tractable on graphs of treewidth $1$. - Last, we investigate the complexity of our problems when the edges can carry weights. This causes all our problems to become #P-hard already on pathwidth-2 graphs, and causes specifically the ``exactly $\ell$'' walk problem to be #P-hard even on pathwidth-1 graphs.Authors: Jacek Karwowski, Frank Nielsen, Sam Staton
We study the compositional, intensional information geometry of probabilistic programs. For a first-order probabilistic programming language with finite random variables, we construct a contravariant lax monoidal functor that, for a program of type $X \to Y$, pulls back a (degenerate) Riemannian metric on $Y$ to $X$. It specialises to the Fisher metric in the case of standard statistical models and to ordinary pullback in the case of deterministic programs. We further justify this construction in two ways. First, we show that this functor arises as a pullback of geometry from a universal space of programs over a type $Y$ with a fixed trace space. Second, we show that it is a special case of a more general pullback construction over weighted measures. Our compositional geometry depends on the presentation of the program, and we study how it relates to the (non-compositional) geometry of the realised measures by establishing a three-level inequality relating our score-velocity metric for the program, the program's corresponding output-conditioned metric, and the standard Wasserstein-Fisher-Rao metric of the realised family. Finally, we show how the theory can be extended to accommodate continuous random variables using diffeological quasi-Borel spaces. We also discuss several concrete directions for future work.Authors: Chih-Hung Liu
Given a set $P$ of $n$ point sites in the plane, the $k$ nearest neighbors problem is to build a data structure that, for a query point $v$ and a query integer $k$, reports the $k$ nearest point sites of $v$ in $P$ efficiently. For the Euclidean metric, after four decades of efforts, an optimal data structure has been developed with $O(n)$ space, $O(\log n+k)$ query time and $O(n\log n)$ preprocessing time [Mat92b, Cha00, AC09, CT16]. In contrast, for a family of distance functions, the state-of-the-art data structure [AES99, KMR+20, Liu22] attains $O(n\log\log n)$ space, $O(\log n+k)$ query time and expected $O(n\log n)$ preprocessing time. An open question is the existence of an optimal data structure with $O(n)$ space and $O(\log n + k)$ query time for distance functions more general than the Euclidean metric. Such an optimal data structure also remains unknown for non-point sites in the Euclidean metric, even for disk sites or, more generally, additively weighted Euclidean distances. We develop an optimal $k$-nearest-neighbors data structure for additively weighted Euclidean distances with $O(n)$ space, $O(\log n + k)$ query time and expected $O(n\log n)$ preprocessing time. Since this data structure can be adjusted to disk sites, it serves as an initial result toward optimality for non-point sites. We also adapt our data structure to point sites under a family of convex metrics, including commonly used $L_p$ metrics and uniform orientation metrics. The data structure can be further extended to distance functions that satisfy certain axioms. Thus, we demonstrate the existence of optimal $k$-nearest-neighbors data structures for distance functions more general than point sites in the Euclidean metric. Our main technical advance is to generalize Matoušek's shallow partition theorem for hyperplanes [Mat92b] to these settings, while achieving a logarithmic crossing number.Authors: Shravan Mehra, Sagnik Mukhopadhyay, Vihan Shah
We study the randomised and deterministic demand-query complexity of approximate bipartite matching with few query rounds. The demand-query model, introduced in [Blumrosen and Nisan SICOMP 2009; Nisan SODA 2021], is inspired by combinatorial auctions and welfare maximisation, where an oracle returns the first neighbouring vertex (item) of a vertex u (agent) according to a given permutation pi (preference ordering of the agent over the items). For randomised algorithms, our main result gives a trade-off between the number of rounds k, the per-round query budget q=n^{1+δ}, and the achievable approximation ratio. Let 1 <= k <= log n, and -1 <= delta <= 1/k. Every k-round randomised algorithm using O(q) demand queries per round has a worst-case expected-size approximation factor of Omega(n^{1/2k-delta/2}/k). Conversely, we give a randomised algorithm achieving approximation factor O(n^{(1-k*delta)/(k+1)}/k) in expectation. For deterministic algorithms, for k*q >= n, we show that the optimal deterministic approximation factor is ~Theta(n^2/(q*k^2)), thereby improving the previous lower bound of [Nisan SODA 2021] by a polynomial factor over a wide range of parameters. In particular, for q=Theta(n), we improve the deterministic round-complexity lower bound for constant-factor approximation from ~Omega(n^{1/3}) to ~Omega(sqrt n). Our algorithms produce matching and vertex-cover certificates; the deterministic trade-off also extends to minimum vertex cover and maximum fractional matching. We extend the randomised upper bounds to the weaker Demand-OR model [Nisan 2021]. We prove a non-adaptive simulation of uniform random-neighbour queries using known techniques, avoiding the O(log n)-round penalty of the trivial binary-search simulation. Consequently, our upper bounds yield the same k-round approximation guarantees using O(q * log^2 n) Demand-OR queries per round.Authors: Ahmed Ghazy, Jakob Greilhuber, Tim A. Hartmann
For Vertex Cover, a minimal blocking set of a graph $G$ is an inclusion-wise minimal vertex set contained in no minimum vertex cover of $G$. Bougeret et al. [SIDMA 2022] showed that, for all minor-closed graph classes $\mathcal{G}$, Vertex Cover has a polynomial kernel parameterized by the distance to $\mathcal{G}$ if and only if $\mathcal{G}$ has bounded minimal blocking sets. In this work, we explore how far this connection between minimal blocking sets and kernelization extends to $\mathcal{F}$-Minor Deletion parameterized by the deletion distance to $\mathcal{G}$. A minimal $\mathcal{F}$-blocking set of $G$ is a minimal vertex set not contained in any optimal $\mathcal{F}$-Minor Deletion solution of $G$. For connected families $\mathcal{F}$, we show that if some graph class $\mathcal{G}$ closed under disjoint union has unbounded minimal $\mathcal{F}$-blocking sets, then $\mathcal{F}$-Minor Deletion parameterized by the deletion distance to $\mathcal{G}$ has no polynomial kernel. This generalizes a result of Hols et al. [SIDMA 2022] for Vertex Cover. We then show that this criterion does not capture all kernelization lower bounds for $\mathcal{F}$-Minor Deletion, even for minor-closed graph classes. Motivated by the work of Dekker and Jansen [Discrete Appl. Math. 2024], we study the more general notion of extended $\mathcal{F}$-blocking sets and the kernelization lower bounds they yield. For every fixed integer $η\geq 1$, Pw-$η$ Deletion is the problem of deleting at most $k$ vertices to reduce the pathwidth to at most $η$. We show that it has no polynomial kernel parameterized by the distance to graphs with pathwidth at most $η+1$. Moreover, for connected families $\mathcal{F}$, we show that $\mathcal{F}$-Minor Deletion parameterized by the distance to graphs with pathwidth at most $\max_{F\in\mathcal{F}} pw(F)+1$ has no polynomial kernel.Authors: Jan Dreier, Robert Ganian, Marlene Gründel, Roohani Sharma, Simon Wietheger
The Boolean Satisfiability (SAT) problem is a remarkably expressive computational problem, serving both as a cornerstone of complexity theory and as a unifying language for a wide range of search and reasoning tasks. While $\mathrm{NP}$-complete in general, SAT is well known to be linear-time solvable on instances with bounded treewidth. This motivates the search for "hidden" tree-like structures in formulas---for instance by detecting so-called weak $t$-treewidth backdoors. Such backdoors are sets of $k$ variables that can be assigned in such a way that the remaining instance has treewidth at most $t$ and is satisfiable whenever the original instance is. Ever since Gaspers and Szeider [ICALP 2012] showed that finding a weak $t$-treewidth backdoor for a SAT formula is $\mathrm{W}[2]$-hard with respect to $k$, tractability results have been restricted to structurally sparse formulas---most notably, a linear-time algorithm for $d$-SAT (bounded clause-length SAT) by Fomin, Lokshtanov, Misra, Ramanujan, and Saurabh [SODA 2015] and a non-uniform polynomial-time algorithm when the incidence graph of the input formula belongs to a nowhere-dense graph class (or more generally is $K_{d,d}$-free) by Lokshtanov, Panolan, and Ramanujan [ICALP 2022]. In this paper, we push the tractability boundaries of finding weak $t$-treewidth backdoors beyond sparsity and into the regime of "well-behaved" dense formulas. Aiming towards relaxing structural input restrictions from nowhere-dense to edge-stable graph classes, as featured in the theory of beyond sparsity for FO model checking, or to bounded VC-dimension set systems, we identify signed semi-ladder-freeness as the correct dense structural restriction that establishes the boundary between tractability and intractability along this line.Authors: Jongseo Lee, Roohani Sharma, Sebastian Wiederrecht
For a fixed finite collection of graphs $\mathcal{F}$, the $\mathcal{F}$-Minor-Free Deletion problem asks, given a graph $G$ and an integer $k$, whether there is a set $S\subseteq V(G)$ with $|S|\leq k$ such that $G-S$ contains no graph of $\mathcal{F}$ as a minor. This generalizes Vertex Cover, Feedback Vertex Set, and Vertex Planarization, among many others. Baste, Sau, and Thilikos [JCSS 2020, SICOMP 2023] showed that, assuming the Exponential Time Hypothesis (ETH), there are collections $\mathcal{F}$ for which the problem cannot be solved in time $2^{o(\mathrm{tw}\log\mathrm{tw})}n^{O(1)}$ on $n$-vertex graphs of treewidth $\mathrm{tw}$, and gave a matching algorithm. We ask whether this super-exponential dependence persists under more restrictive structural parameters. First, we strengthen their lower bound. Assuming ETH, for every fixed $h\geq 6$, $\{P_h\}$-Minor-Free Deletion, where $P_h$ is the path on $h$ vertices, cannot be solved in time $2^{o(t\log t)}n^{O(1)}$, where $t=\mathrm{fvs}+\mathrm{td}$ is the sum of the feedback vertex set number and treedepth of the input graph. These two parameters are incomparable, but both individually upper bound the treewidth. Together with the $2^{O(\mathrm{tw}\log\mathrm{tw})}n^{O(1)}$-time algorithm of Baste, Sau, and Thilikos [SICOMP 2023], our lower bound is tight. In contrast, we show that asymptotically faster algorithms are possible when parameterized by the vertex cover number $\mathrm{vc}$. Specifically, for any finite family $\mathcal{F}$, $\mathcal{F}$-Minor-Free Deletion can be solved in time $2^{O(\mathrm{vc})}n^{O(1)}$. Taken together, our results show that the boundary between single-exponential and super-exponential complexity for this problem lies between the vertex cover number and the feedback vertex set number (plus treedepth).Authors: Zekun Ye
We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most $k$ nonzero Fourier coefficients. We give a learner with near-optimal $\widetilde{O}(k)$ sample complexity independent of the input length $n$. The learner uses only separate measurements of individual examples. This improves the previous $O(k^{3/2}\log^2 k)$ upper bound (Arunachalam, Chakraborty, Lee, Paraashar, and de Wolf, 2021). The main ingredient is a candidate set formed by symmetric differences of subsets from independent groups of Fourier samples. A multilinear majority polynomial combines unbiased random approximations into an accurate witness whose Fourier support lies in this set. Granularity then forces the set to contain the entire Fourier support, including subsets never directly sampled. For comparison, we derive the tight classical sample complexity $Θ(nk)$ by combining known sparse-recovery and lower-bound results.Authors: Sinan G. Aksoy, Eli Friedman, Nate Veldt, Stephen J. Young
Rubinstein et al. introduce the study of connectivity and minimum cut problems in the cut query model, where an algorithm can only access the edges of a graph through CUT queries. In this work, we examine the query complexity of densest subgraph problems. Our first contribution is to generalize the uniform sparsification approach for Densest Subgraph and other heavy subgraph problems to weighted graphs, achieving the following results. >A $(1+\varepsilon)$-approximation for weighted Densest Subgraph in $O(n\log^2 n/\varepsilon^2)$ queries, roughly matching the $Ω(n/\log n)$ lower bound we prove for randomized algorithms. >A $(1+\varepsilon)$-approximation for weighted Max Cut in $O(n\log^2 n/\varepsilon^2)$ queries. This improves upon the bound of $O(n\log^3 n(\log n+1/\varepsilon^2))$ queries achieved by Plevrakis et al., making significant progress towards their lower bound of $Ω(n/\log n)$ queries. In contrast, we rule out approximation schemes with truly subquadratic query complexity for Densest $k$-Subgraph and settle its exact query complexity in both the unweighted and deterministic settings. For hypergraphs, we show CUT queries alone cannot achieve $o(\sqrt{n})$-approximation for Densest Subhypergraph or $o(n)$-approximation for Densest $k$-Subhypergraph, regardless of the number of queries. Augmenting CUT queries with the EDGE oracle of Chen et al., we overcome this barrier for Densest Subhypergraph and obtain a $(1+\varepsilon)$-approximation on rank-$r$ hypergraphs using $O(nr\log n/\varepsilon^2)$ queries. We also extend our Densest $k$-Subgraph hardness results to hypergraphs and prove exponential query lower bounds for exact Densest $k$-Subhypergraph. Lastly, confirming a conjecture of Chakrabarty and Liao, we show that simulating an ADD query using CUT and IS-EDGE$^?$ queries requires exponentially-many queries.Authors: Thomas Depian, Giuseppe Liotta, Fabrizio Montecchiani, Martin Nöllenburg
Stack and queue layouts are two extensively studied and complementary linear representations of graphs. A stack (queue) layout $\langle \prec, σ\rangle$ of a graph $G$ consists of a total ordering $\prec$ of its vertices and of a partitioning $σ$ of its edges into pages, such that no two independent edges on the same page cross (nest). We propose a generalized model with colored edges (one color per edge) and capacitated pages. Namely, the input graph is equipped with colored edges and a prescribed budget for each page-color pair $(p,c)$ - this budget determines the maximum number of edges of color $c$ that page $p$ can accept. This model is motivated by fair allocation scenarios where budgets can be used to control the share of monochromatic edges on each page. Unfortunately, it is known that deciding whether a stack (queue) layout exists is NP-hard already with two (one) pages. Thus, we focus on the fixed-order setting - where the linear order $\prec$ is part of the input - for which an ordinary 2-page stack or $\ell$-page queue layout can be computed in polynomial time. Despite the restrictive setting, we show that both capacitated problems are NP-complete already for two pages. Furthermore, we study the complexity of the problems when parameterized by the number of pages, colors, and/or the structure of the edge conflict graph with respect to the fixed linear order $\prec$. Our analysis paints a detailed complexity landscape and uncovers a surprisingly intricate interplay between the considered parameters.Authors: Adam N. Elmachtoub, Bento Natura, Meike Neuwohner
In submodular facility location (SFL), introduced by Svitkina and Tardos (SODA 2006), clients $\cal C$ in a metric space are assigned to facilities $\cal F$. A facility serving a set $S \subseteq \cal C$ of clients incurs cost $g(S)$, where $g$ is a monotone submodular function common to all facilities. The best known approximation factor for SFL is $O(\log\log|\cal C|)$, due to Abbasi, Adamczyk, Bosch-Calvo, Byrka, Grandoni, Sornat, and Tinguely (ICALP 2024), improving on the $O(\log|\cal C|)$-approximation of Svitkina and Tardos. We show that this is best possible up to a constant factor in the value-oracle model by showing that there exists no algorithm with only polynomially many queries to $g$ with approximation ratio $o(\log\log|\cal C|)$. This bound holds for algorithms with unlimited computation time, and when $g$ is restricted to matroid rank functions. We also show that the natural linear programming relaxation has an integrality gap of $Θ(\log\log|\cal C|)$. Our lower bound follows by constructing an extension of Vondrák's symmetry-gap approach (FOCS 2009) for matroid rank functions.Authors: Darya Melnyk, Linda Thelen, Yuyi Wang
In this paper, we study online paging with delay or deadlines. In online paging with delay, an online algorithm manages a cache of size $k$ and needs to serve incoming requests by adding the requested pages to the cache. In addition, it has the option to delay serving incoming requests at a cost that depends on the delay. We propose a new online algorithm, which combines a threshold rule with first-in, first-out (FIFO) replacement, and show that it is $(2k+2)$-competitive for cache size $k$. This result corrects a previously published claim that the competitive ratio is exactly $2k+1$ regardless of the number of holes (pages outside the cache). However, in the case of one hole, we show that the FIFO rule with a different threshold is indeed $(2k+1)$-competitive, giving a tight result. In the case of deadlines, the same analysis gives a deadline-triggered algorithm that is $(k+1)$-competitive in general and $k$-competitive if there is only one hole. Moreover, we show that the second hole makes paging with deadlines strictly harder than classical paging, where the competitive ratio is independent of the number of holes. For paging with deadlines, we prove a deterministic lower bound of $k+\tfrac12$, already for two holes. We show that, as a consequence, no threshold-triggered algorithm can achieve a competitive ratio less than $2k+\frac32$ in general.Authors: Jonathan Cremer
Let $V_i(n)$ denote the minimum worst-case number of comparisons needed to find the $i$-th smallest of $n$ distinct elements. We construct algorithms showing $V_7(16)\le28$ and $V_8(16)\le29$, improving the previously reported upper bounds of 30 and 31. Together with known lower bounds, these results establish $V_7(16)=28$ and leave $V_8(16)\in\{28,29\}$. For 17 elements, we establish $V_5(17)=27$ and improve the upper bounds for ranks 6 through 9 to 29, 30, 31, and 31, respectively. Every new upper bound has an explicit decision-graph certificate verified by a static checker developed independently of the search. We also derive a lower bound for selection from a partially ordered state by combining the Fussenegger-Gabow weight with its order-reversed counterpart. All new upper bounds and this lower bound are formally verified in Lean 4. For $V_8(16)$, we show that a lower bound based solely on the total number of decision-tree leaves cannot establish $V_8(16)\ge29$. The algorithms were found using fixed-budget search, information-guided comparison ordering, and proof-number search. Proof-number search was decisive in finding the 28-comparison algorithm; in our experiments, refuting a comparison budget remained substantially more expensive than finding an algorithm within it.Authors: Qisheng Wang
We present an optimal tester for support size that determines whether an unknown probability distribution is supported on $n$ elements or $\varepsilon$-far away (in total variation distance) with sample complexity $Θ(\frac{n}{\varepsilon\log(n)})$, improving the prior best $O(\frac{n}{\varepsilon\log(n)} \log(\min\{\frac{1}{\varepsilon}, n\}))$ due to Ferreira Pinto Jr. and Harms (STOC 2025). As a generalization, we provide a pretty good lower bound on support size.Authors: Sharareh Alipour
The Held--Karp bound is a linear-programming lower bound for the metric traveling salesperson problem (TSP). We approximate this bound in the multi-pass insertion-only streaming model for metrics induced by connected positive-weight graphs. For an $n$-vertex, $m$-edge graph and $0<\eps\le1/2$, the algorithm returns a $(1+\eps)$ upper approximation with high probability, using $\wtO(\eps^{-4})$ passes, $\wtO(n\eps^{-2})$ words, and $\wtO(m\eps^{-4})$ arithmetic operations per pass. We replace the changing edge-weight vector by a short history of multiplicative-weights (MWU) updates. After initialization, updates repeat until a column is removed. We store each repeated update once, with its repetition count. The record length depends on the number of columns, not updates; the argument applies to any fixed nonnegative matrix. For Held--Karp, tree-path queries recover edge weights from these records. Separate search and update thresholds allow fresh sparsifiers at successive search stages. Controlled rounding gives a bounded-precision implementation. The estimate yields a $(3/2+\eps)$ graph-metric TSP value estimate and a $(7/5+\eps)$ estimate when the input graph is unweighted. Conversely, in weighted graph streams, every one-pass $(1+η)$ upper approximation to Held--Karp, for fixed $0\leη<1$, requires quadratic space. The algorithms estimate values; they do not construct tours within these bounds.Authors: Sharareh Alipour, Ali Nowzari
We give improved sublinear-time and semi-streaming approximation algorithms for maximum path cover, $(1,2)$-TSP, and Max-TSP. For each fixed $\eps>0$, our distance-query algorithm estimates the optimum cost of an $n$-vertex $(1,2)$-TSP instance from above within factor $2-\cstar+\eps=1.413184\ldots+\eps$, with high probability, in $n^{2-Ω_\eps(1)}$ time, where $\cstar=2(\sec1-\tan1)$. This improves the $3/2+\eps$ factor of direct matching estimation in this subquadratic regime~\cite{BhattacharyaKissSaranurak2023} and of the faster near-linear estimator~\cite{BehnezhadEtAl2024}. A single random vertex order defines an implicit bipartite graph whose matchings project to path covers. An alternating-permutation analysis shows that its expected maximum matching size is at least $\cstar$ times the optimum path-cover size. On long paths, even the best of polynomially many uniform orders retains only a $\cstar+o(1)$ fraction with high probability. In semi-streaming, we construct deterministic $(5/7-\eps)$-approximate unweighted path covers and $(9/7+\eps+5/(7n))$-approximate $(1,2)$-TSP tours, improving the respective $2/3-\eps$ and $4/3+\eps+1/n$ guarantees in~\cite{AlipourFarokhnejadMoemke2025}. For nonnegative weights, we obtain $2/3-\eps$ for path cover and Max-TSP, improving the earlier asymptotic $7/12-\eps$ Max-TSP bound. These algorithms use $\poly(1/\eps)$ passes independent of $n$ and $O(n\log(n/\eps)\poly(1/\eps))$ words. We compute two approximate matchings separated by edge deletion. A cycle-compensation lemma accounts for the weight removed when breaking their cycles. For unweighted graphs, a third approximate matching on a simple auxiliary graph with at most $2n$ vertices chooses component connections; a Tutte--Berge count proves the stronger bound.Authors: Zhongyang Li
We construct an approximate sampler for finite doubly free-boundary Macdonald rail-yard processes with Macdonald, boundary, and edge parameters in $(0,1)$. The construction allows arbitrary finite sequences of additions and removals of horizontal or vertical strips and all four boundary types. It reverses a finite commutation--reflection history from a partition sequence whose entries are equal, with the common partition weighted by both boundaries. We derive local reconstruction kernels from the skew Cauchy, Littlewood, and branching identities. Bulk and boundary updates combine integer increments with conditional shape sampling at a prescribed size; same-sign swaps use finite conditional resampling. For $K$ reflection periods and an initial partition-size cutoff $M$, the algorithm terminates almost surely and samples the resulting approximating law exactly. We prove total variation convergence to the target process as $K,M\to\infty$ and give explicit bounds for both truncation errors, decaying geometrically in the cutoffs for fixed input parameters. Under fixed parameter bounds, we also bound the expected operation count of direct enumeration in a unit-cost model. We further construct an exact rejection sampler for the initial partition law without a size cutoff or evaluation of its normalizing constant. Using this sampler removes the size-truncation error, leaving only the error from the finite reflection history.Authors: Heng Guo, Daniel A. Spielman, Xinyuan Zhang
We show that the guaranties of the Gram-Schmidt Walk Algorithm of Bansal, Dadush, Garg, and Lovett can be achieved by an Ising model. Given vectors $v_1, \ldots, v_n$ of norm less than 1, we give a closed form for a centrally symmetric distribution on a vector $σ\in \{\pm 1 \}^n$ so that the signed sum $\sum_j σ(j) v_j$ is $1$-subgaussian. We show that the Glauber dynamics for this model mix rapidly provided that the norms of the input vectors are bounded below 1 by an inverse-polynomial. The proofs employ the theory of Lorentzian polynomials, and we use these techniques to show fast mixing bounds for other spin systems.Authors: Tomáš Domes, Pavel Veselý
Quantile summaries provide a scalable way to estimate the distribution of individual attributes in large datasets that are often distributed across multiple machines or generated by sensor networks. The state-of-the-art summaries with \emph{relative error guarantees} of $\pm \varepsilon\cdot \mathrm{rank}$, offering increasingly higher accuracy towards the distribution's tails, are ReqSketch (Cormode et al., JACM 2023) and the recent streaming algorithm by Gribelyuk et al. (SODA 2025). For inputs of size $N$ and probability $δ$ of exceeding the error bound, ReqSketch achieves space of $O(\varepsilon^{-1}\cdot \log^{1.5}(\varepsilon N)\cdot \sqrt{\log δ^{-1}})$ memory words, and offers \emph{full mergeability}, allowing distributed or parallel processing of datasets. In contrast, the latter algorithm exceeds the lower bound of $Ω(\varepsilon^{-1}\cdot \log(\varepsilon N)\cdot \log\logδ^{-1})$ from (Cormode \& Veselý, PODS 2020) only by a factor of $O(\log\varepsilon^{-1}\cdot (\log \varepsilon^{-1} + \log\log N)\cdot\log^2\logδ^{-1})$, but it lacks the mergeability property, is substantially more involved than ReqSketch, and has unclear practical performance. Both of these data structures consist of relative compactors from ReqSketch that subsample the stream in a structured way and work well in the streaming setting but are difficult to analyze under mergeability. We design a new relative-error quantile summary that achieves full mergeability and also improves the state-of-the-art streaming space bound to $$O(\varepsilon^{-1}\cdot \log(\varepsilon N) \cdot\log \log δ^{-1} \cdot (\log \varepsilon^{-1} + \log \log(\varepsilon N) + \log \log δ^{-1})),$$ which is substantially closer to the lower bound. At the same time, our data structure is simpler than the algorithm from (Gribelyuk et al., SODA 2025) and therefore more suitable for implementation.Authors: Vikrant Ashvinkumar
In the restricted shortest paths problem, we are given an $n$-vertex $m$-edge directed graph $G$ whose edges are assigned two non-negative weights (or resources) called lengths and costs, a source vertex $s$, and a cost threshold $C$. The goal is to find, for each target vertex $t$, the length of the shortest $(s,t)$-path whose total cost is at most $C$. Ashvinkumar, Bernstein, and Karczmarz (SODA 2025) gave the first randomized bicriteria $(1+\varepsilon,1+\varepsilon)$-approximate algorithm on directed graphs running in sub-$mn$ time, answering a problem posed by Bernstein (SODA 2012). We substantially improve this on two fronts, supplying a deterministic bicriteria $(1+\varepsilon,1+\varepsilon)$-approximate algorithm running in near-linear time. Our approach straightforwardly generalizes to more than two resources. For $k$ resources, a deterministic $(1+\varepsilon_1,\ldots,1+\varepsilon_k)$-approximate algorithm running in near-linear time is possible, with $\varepsilon_1=\ldots=\varepsilon_k=\varepsilon$.Authors: Emil Schätzle, Simon Meierhans, Rasmus Kyng, Maximilian Probst Gutenberg
In a recent breakthrough, Chen, Kyng, Liu, Peng, Probst Gutenberg, and Sachdeva (arXiv:2203.00671) designed the first almost-linear-time algorithm for minimum-cost flow. Their approach uses an Interior Point Method (IPM) to achieve complexity $m^{1+o(1)}\log U \log C$. However, the $m^{1+o(1)}$ factor hides intricate recursive data structures, large constants and multiple log factors. In this paper, we give an implementation following the core ideas of their IPM with practical data structures and empirically obtained decision rules. We compare our solver with the cost scaling and network simplex solvers of LEMON on the instance families of the DIMACS Flow Challenge 2.0 core benchmark. Our implementation scales competitively on five of twelve families and better on two. On grid_wide we observe close to linear scaling: $m^{1.04}$ against $m^{1.48}$ for LEMON. We read these results as first evidence that the almost-linear-time framework can be relevant in practice, discuss our insights gained during the implementation process, and motivate where future work should focus to bridge the theory-practice gap.Authors: Seri Khoury, Aaron Schild
We prove that $o(\frac{\log n}{\log\log n})$-round randomized LOCAL algorithms find a maximal independent set (MIS) with subconstant probability on some input. This shows that the 40-year-old $O(\log n)$-round randomized CONGEST algorithm of Luby and Alon, Babai, and Itai is nearly optimal. Our lower bound improves upon the $Ω(\sqrt{\log n})$-round lower bound of Khoury and Schild and nearly closes the 20+ year-old gap between the $O(\log n)$-round algorithm and the $Ω(\sqrt{\frac{\log n}{\log\log n}})$-round lower bound of Kuhn, Moscibroda, and Wattenhofer. To close this gap, one must show a lower bound for a graph that is not locally treelike. We do this by starting with a $D$-regular, $Θ(\log_D n)$-girth graph, with $D = Θ(\log n)$. Crucially, this is not our final graph. We obtain our hard instance by \emph{replacing} each vertex of this treelike graph with a clique on $n^c$ vertices for some constant $c \in (0,1)$. We then replace each edge with a bipartite Erdős--Rényi graph between the corresponding cliques, with each edge present independently with probability $1/2$. We analyze arbitrary LOCAL algorithms on our non-treelike hard instance with a novel round elimination approach. We describe algorithms that output a set of vertices in this graph using two metrics: their \emph{occupancy probability} and their \emph{conflict probability}. Our round elimination framework takes an $r$-round algorithm and produces an $(r-1)$-round algorithm where occupancy and conflict probabilities collectively slightly degrade, but individually can significantly improve or degrade. This round elimination result is obtained by exploiting the lack of large biclique complements in dense bipartite Erdős--Rényi graphs, which in turn allows us to bound the entropy of the output distribution for any independent set algorithm.Authors: Rares-Darius Buhai, Vincent Cohen-Addad, Henry Fleischmann, Anupam Gupta, Antoni Jubés Monforte, Madhusudhan Reddy Pittu, Miltiadis Stouras, Ola Svensson, Lukas Vogl
The Greedy algorithm of Jain, Mahdian, Markakis, Saberi, and Vazirani was the best Lagrangian-multiplier-preserving (LMP) approximation algorithm for facility location, and thus the engine behind the best $k$-median guarantees, for over two decades. Its $2$-LMP guarantee was only recently broken by a small amount ($(2-η)$-LMP where $η\approx 2.25 \cdot 10^{-7}$) through local-search post-processing. That analysis relies on the structure of worst-case instances, and it appears difficult to obtain substantial further improvements along those lines. We take a different approach and change the algorithm itself: we introduce general bidding functions, replacing the classical linear bid with a richer family of rules and prove a polynomial-time $1.95$-LMP approximation, a large improvement over the long-standing factor of~$2$. We further show that these generalized bidding rules can be made smooth (log-adaptive), building on the recent framework developed for the classical Greedy algorithm by Cohen-Addad, Grandoni, Lee, Schwiegelshohn, and Svensson. This yields a polynomial-time $1.95$-approximation that opens $k+O_\varepsilon(\log n)$ centers. Combined with a $(1.89+\varepsilon)$-approximation algorithm for stable instances in our companion work \cite{stableinstances}, we achieve a better-than-2 approximation for the $k$-median problem in polynomial-time.Authors: Ilie Sarpe, Theofanis Georgakopoulos, Aristides Gionis
Plurality-voting ensembles aggregate the predictions of multiple base classifiers and output the most voted class, with ties typically broken at random. Despite the simple aggregation rule, attributing the impact of each base classifier to the ensemble's predictions is far from straightforward. That is, a single base classifier's impact depends on how it interacts with the votes of all other classifiers in the ensemble, for example, in resolving ties, and not only on its own predictions. We address the attribution problem using established tools from cooperative game theory, studying the Banzhaf and Shapley power indices for new games modeling plurality voting and random tie-breaking, for binary and multiclass classification settings. Computing power indices is, in general, intractable. Surprisingly, our methods, collectively named ENPOWER, enable the exact computation of Banzhaf and Shapley values in linear time for the binary classification setting and in low-degree polynomial time for the multiclass setting. The algorithms in ENPOWER rely on new combinatorial formulations of the Banzhaf and Shapley indices, yielding closed-form solutions for the binary case and ordinary generating function representations for the multiclass case. We validate empirically the methods in ENPOWER demonstrating their high applicability, providing attribution values not captured by existing methods. We apply the attribution of ENPOWER to: ensemble pruning and prompt-based ensembling of vision-language models.Authors: Lucas P. Oliveira, Ben Bals, Aalt D. J. van Dijk, Solon P. Pissis
A protein-protein interaction (PPI) network is a graph whose nodes are protein sequences and whose edges represent physical interactions between proteins. Correlated Motif Mining (CMM) seeks pairs of sequence motifs whose co-occurrence in interacting proteins reveals binding sites and interaction mechanisms. Formally, in the $(\ell,d)$-CMM problem, we are given a graph $G=(V,E)$, with $V\subseteqΣ^*$ for an alphabet $Σ$, and integers $0\leq d<\ell$, and we seek a pair $\{X,Y\}$ of motifs, each of length $\ell$ and containing $d$ wildcards, that maximizes a support measure $f(G,\{X,Y\})$; e.g., the count $f_E$ of edges $\{u,v\}\in E$ such that $X$ matches a substring of $u$ and $Y$ matches a substring of $v$, or vice versa. Although existing approaches have produced biologically meaningful results, they are either inefficient or heuristic-based, as the underlying optimization problem is NP-hard. Here, we revisit $(\ell,d)$-CMM. For $d=0$, we give an exact $\mathcal{O}(N^2)$-time and $\mathcal{O}(N)$-space algorithm, where $N$ is the total length of the node strings, and prove that this time is conditionally optimal under the Strong Exponential-Time Hypothesis. For any $d>0$, we give an exact $\mathcal{O}\!\left(\binom{\ell}{d}^2N^2\right)$-time and $\mathcal{O}(N)$-space algorithm, and observe that the problem is W[1]-hard parameterized by $d$. The latter algorithm improves the state of the art by exponentially large factors in both time and space. We further demonstrate experimentally that our algorithms are practical on real-world PPI networks and find significantly higher-scoring motif pairs than the state of the art. Moreover, we show that our algorithms find many top-scoring motif pairs that the state of the art misses entirely. Taken together, our results suggest that exact CMM with wildcards is more tractable in practice than previously assumed.