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: Vahan Mkrtchyan
If $G$ and $H$ are two cubic graphs, then an $H$-coloring of $G$ is a mapping $f: E(G)\rightarrow E(H)$, such that for every $v\in V(G)$ there is a vertex $x\in V(H)$, such that $f(\partial_G(v))=\partial_H(x)$. If $G$ admits an $H$-coloring then it is common to write $H\prec G$. In this paper, for a fixed connected cubic graph $H$, we consider a decision problem, which we call $H$-coloring. In this problem, on the input one is given a connected cubic graph $G$. The goal is to decide whether $H\prec G$. A conjecture by Hakobyan and the author states that $H$-coloring is polynomial time solvable, if $H$ does not admit a $P_{12}$-coloring. Here $P_{12}$ is the unique cubic graph obtained from the Petersen graph by expanding one of its vertices into a triangle. In this paper, we disprove this conjecture under $P\neq NP$, by showing that $S_6$-coloring is NP-complete. Here $S_6$ is the unique cubic graph on six vertices having exactly one bridge. Our second result is an algorithm that solves $H$-coloring problem in time $O^*(c^n)$, where $H$ is a simple connected cubic graph, $n$ is the number of vertices of the input cubic graph $G$ and $c=\sqrt{8}\approx 2.8284$.Authors: Reijo Jaakkola
The Minimum Equivalent Expression problem (MEE) asks, given a propositional formula $φ$ and an integer $k$, whether $φ$ is equivalent to a formula with at most $k$ occurrences of propositional variables. While the problem is clearly in $Σ_2^p$, its completeness under polynomial-time many-one reductions has remained open since at least 1979. Buchfuhrer and Umans showed in 2008 that it is $Σ_2^p$-complete under polynomial-time Turing reductions. In this note, we present a proof discovered by GPT-Sol-6.1 which establishes that MEE is $Σ_2^p$-complete also under polynomial-time many-one reductions.Authors: Huanyi Zhou
Graph tensors extend the matrix multiplication tensor by placing a two-party identity tensor on every edge of a graph and keeping one tensor leg at every vertex. We study the asymptotic rank of the tensor associated with the complete graph. For every integer $n\geq 2$, over the complex numbers, we prove \[ \left\lfloor\frac{n^2}{4}\right\rfloor \leq \log_2\widetilde R\bigl(\mathsf{GT}_2(K_n)\bigr) \leq \frac{n^2}{4}. \] The upper bound matches the maximum-cut lower bound for every even $n$ and differs from it by only $1/4$ for every odd $n$. In particular, the exponent per edge is below $2/3$ for every $n\geq5$, answering a question of Christandl, Vrana, and Zuiddam. Our proof extends the polynomial multiplication approach underlying OpenAI's bound $ω\leq9/4$. The main step separates any fixed number of shared tensor legs simultaneously, using only linearly many direct-sum copies in the number of blocks. This yields an entropy inequality for higher-order tensors. We apply it to the tensor for multiplying $n-1$ polynomials, whose rank is linear in the input length. Discrete concavity and a shifted tripling inequality then force a lower bound on a symmetrized spectral profile. Comparing this growth with polynomial interpolation gives the stated upper bound while preserving all $n$ tensor legs. We also prove an operational barrier for these higher-order polynomial constructions. For $n\geq3$, the specified formal reduction rules cannot certify an exponent below $n^2/4$ for $\mathsf{GT}_2(K_n)$, even after taking tensor powers and allowing subexponential overhead and common auxiliary factors. This extends the symmetric three-leg barrier of Amanov, van den Berg, and Zuiddam and explains the remaining gap for odd complete graphs within this method.Authors: Michal Garlik, Svyatoslav Gryaznov, Jiaqi Lu, Rahul Santhanam, Iddo Tzameret
We initiate the study of the meta-mathematics of algebraic circuit lower bounds, aiming both to gain insight into the methods sufficient and necessary to prove algebraic circuit lower bounds, and to contribute to the study of bounded arithmetic as a logical foundation for complexity lower bounds. We demonstrate that while algebraic circuit lower bounds are hard for somewhat weak proof systems such as Polynomial Calculus Resolution ($\mathsf{PCR}$), contemporary lower bounds are efficiently provable in proof systems and bounded arithmetic theories corresponding to $\mathsf{NC}^2$, such as $\mathsf{VNC}^2$ and the corresponding class of propositional Frege proofs of quasipolynomial-size. Moreover, going below $\mathsf{VNC}^2$ into algebraic constant-depth reasoning is likely insufficient to efficiently prove already constant-depth algebraic circuit lower bounds. Under an algebraic analogue of the Krajicek--Razborov conjecture, our results suggest that proving superpolynomial lower bounds for general algebraic circuits will require stronger reasoning than that used in the rank-based proofs studied here. Specifically, we show the following.Authors: Mario Ullrich
We prove a Borsuk-Ulam theorem for adaptive measurements: if $2^n\le m$, then any $n$ adaptively chosen continuous functionals take identical values at two antipodal points of any sphere in $\mathbb{R}^m$. Consequently, at least $\lceil\log_2(m+1)\rceil$ adaptive continuous measurements are needed to learn the vectors of a ball in $\mathbb{R}^m$ with an error smaller than its radius, which matches the recently obtained upper bound up to one measurement. The bound extends to Bernstein widths in Banach spaces. The main idea of the proof was found by Claude Fable 5, an AI model developed by Anthropic, and we document the development in a last section.Authors: Chengu Wang
Alice and Bob hold complementary halves of the columns of an $n\times n$ matrix of $k$-bit integers and decide whether it is singular over $\mathbb Q$. Up to constant-factor dimension growth, this partitioned problem is equivalent to additive singularity, where Alice and Bob hold $n\times n$ matrices $A,B$ of $k$-bit integers and test the singularity of $A+B$ over $\mathbb Q$. We prove a bounded-error quantum lower bound $Ω(\min\{n^{3/2}\sqrt{k\log n},n^2\log(nk)\})$ and a randomized upper bound $O(n^2\min\{k,\log(k+\log n)\})$. The bounds match at $Θ(n^2\log(nk))$ for $k\ge n\log n$. The lower bound holds even under the promise of rank $n-1$ versus $n$. Its proof combines an integer witness with a local digit encoding, while the upper-bound protocol lifts modular kernel relations using short messages. Bitwise sharing changes how the communication complexity depends on the entry bit length $k$. If Alice and Bob instead hold $n\times n$ matrices $A,B$ of $k$-bit integers and test whether their entrywise bitwise XOR $A\oplus B$ is singular over $\mathbb Q$, we prove a quantum lower bound $Ω(n^2k)$, matching the trivial upper bound. This lower bound holds even under the promise of rank $n-1$ versus $n$. Our proof uses a dense weighted equation and a signed Fourier witness whose exceptional dyadic frequencies can be removed at small variation cost.Authors: Swastik Kopparty, Rishabh Kothary, Ashutosh Shankar
We revisit a classical result of Coppersmith and Shparlinski showing bounds on how well polynomials can approximate the discrete log function. They showed that for any univariate polynomial $f(X) \in \mathbb{F}_p[X]$ with $deg(f) \leq D$, we have: $$ |\{ x \in \mathbb{F}_p^\times \mid f(x) = dlog(x) \}| \leq \sqrt{2 D p}.$$ We show two improvements: (1) For all $D$, we improve the upper bound above to $(1+o(1)) \cdot \sqrt{Dp}$. In particular, we give nontrivial upper bounds on the approximation even for $D > p/2$. This new upper bound is the Johnson bound from the theory of list-decoding of error-correcting codes, and in fact our proof uses a connection to that problem, as well as other combinatorial ideas. (2) For $D = 1$, where both the above bounds are $O(\sqrt{p})$, we give an asymptotically improved upper bound of $O(p^{2/5})$. This is based on the sum-product phenomenon of additive combinatorics. We also improve the [CS00] bounds on the number of points of the form $(x, dlog(x)) \in \mathbb{F}_p^2$ that any bivariate polynomial $Q(X,Y) \in \mathbb{F}_p[X,Y]$ with $deg(Q) \leq D$ can vanish on, with our new bounds approaching the analogue of the Johnson bound for this problem.Authors: Anne Condon, David Doty, Niels Kornerup, David Soloveichik, David Wolpert
When any physical system executes a logically irreversible (non-injective) step of a computation, the excess heat released over the Landauer limit is an energetic cost that cannot be recovered. In modern computers this cost vastly dwarfs the Landauer cost. Modern stochastic thermodynamics refers to this cost as the ``entropy production'' and has derived fundamental lower bounds on its value. Here we introduce a thermodynamic model of circuits using heat functions and investigate its entropy production, deriving new results on the thermodynamic complexity of circuits. We first show that computing the optimal heat functions for gates in a given circuit (minimizing the entropy production) is PP-complete and multiplicative approximation of those heat functions is NP-hard, but additive approximation admits a polynomial-time randomized algorithm. We give tight bounds for entropy production for certain specific families of circuits (on uniformly distributed inputs): an $n$-ary AND tree of depth $O(\log n)$ requires $Ω(n)$ entropy production, while a serial chain achieves $O(1)$ in an idealized model, showing an energy-depth tradeoff. The Batcher odd-even mergesort network on $n$ bits has $Θ(n)$ entropy production, asymptotically less than its $Θ(n \log^2 n)$ gate count. On random permutations of distinct integers its entropy production is $Θ(n \log^2 n)$, asymptotically exceeding the Landauer cost of sorting; but preceding it with Leighton and Plaxton's almost-sorting network reduces the total heat released to $O(n \log n)$. Finally, we show how to sort $n$ values with zero circuit entropy production over any exchangeable input distribution. Our framework also yields streamlined proofs of known results in stochastic thermodynamics on mismatch cost and modularity cost.Authors: Beizhen Zhao, Nanjie Yao, Boyi Fu, Qingsong Yan, Haofan Ren, Kaiyong Zhao, Hao Wang
Sparse-view 4D reconstruction is highly under-constrained when only a few cameras are available. Generative priors can recover missing appearances, but video models are computationally impractical for iterative reconstruction, whereas single-view models produce temporally inconsistent pseudo-observations. Moreover, directly absorbing uncertain generative outputs into Gaussian optimization often creates redundant primitives and floating artifacts. To address these challenges, we propose DUET4D, a self-corrective coupled guidance framework for sparse-view 4D Gaussian splatting. The core of our approach is a self-corrective framework where the 4D representation guides generative prior for spatio-temporal consistent supervisions. We first construct sequential alignments from current Gaussian evidence to steer the latent restoration. Then we use Sequential Fidelity Resampling to lift generative supervisions into Gaussian space to selectively distinguish repeatedly supported primitives. The corrected representation then provides more reliable Gaussian evidence for the next restoration cycle. Extensive experiments demonstrate that DUET4D significantly improves rendering quality and rendering efficiency.Authors: Miguel Esteban Pérez Ibarra
The Pythagoras tree of A. E. Bosman (1942) is drawn with squares in the plane and, in the three-dimensional versions we know of, with cubes. This article documents a tree built instead from regular dodecahedra: each dodecahedron carries five smaller copies, one on each edge of a single pentagonal "crown" face, scaled by $g \approx 0.4346$ and twisted by $45^\circ$ about the edge. The construction first existed only as a pair of rendered images and two undocumented C++ programs. We recover its exact parameters from the original Blender scene, reformulate it as an iterated function system with condensation, and prove with a short computer-assisted argument that it never collides with itself: two of its dodecahedra overlap only when one is the parent of the other. A Pythagorean identity for the six face axes of the dodecahedron singles out the scale $1/\sqrt{5}$ and the twist $\arccos(1/\sqrt{5})$. With these values each child rests flat against a face of its parent, the five children together have exactly the parent's surface area, and the crown of the tree is a fractal of Hausdorff dimension exactly 2. Finally we ask whether the tree can grow on all twelve faces at once. A parity argument shows that at the artwork's proportions it cannot, but smaller scale factors admit certified clash-free all-faces trees.Authors: Liangchen Liu, Yen-Hsi Richard Tsai
We propose a parametrization-free framework for estimating the second fundamental form and the principal curvatures of a submanifold of $\mathbb{R}^d$. The method uses the closest point projections of a few short random rays and recovers the curvature from the curves that these projections induce on the submanifold, without coordinate charts or local fitting. We analyze the geometry of the induced curves and characterize when they are geodesics. For hypersurfaces, these results give two algorithms with error bounds: a least squares reconstruction of the second fundamental form from the curvatures of the induced curves, and a direct estimate of all principal curvatures from the eigenvalues of a $d\times d$ matrix built from $d$ rays, which needs no normal information and costs $\mathcal{O}(d^3)$ besides the projections. In higher codimension, we can also recover the second fundamental form one normal direction at a time. On point clouds, where the projection becomes a nearest neighbor query, we bound the additional error. Experiments confirm the predicted rates for hypersurfaces in up to $128$ dimensions, for surfaces of codimension up to $98$, and on point clouds, demonstrating the effectiveness of the proposed framework in practice.Authors: Zhao Song
We give a deterministic quasi-polynomial-time algorithm for the maximum independent set problem. If an $N$-vertex graph contains an independent set of size $2^{-t}N$, where $t$ is an integer with $1\le t\le\sqrt{\log N}/12$, then our algorithm finds an independent set of size $2^t$ in time $N^{O(t)}$. This gives an approximation ratio of $N/2^{Ω(\sqrt{\log N})}$ in time $N^{O(\sqrt{\log N})}$, improving on the approximation ratio $N/2^{Ω((\log N)^{1/3})}$ obtained by Lovett [Lov26]. A limitation of this form of analysis follows from the integrality gaps of Tulsiani [Tul09]. These gaps imply that a universal guarantee of the form $\operatorname{Las}_{R(t)}(G)\ge2^{-t}N\Longrightarrowα(G)\ge2^t$, at $2^{o(\sqrt{\log N\log\log N})}$ levels, cannot hold over a range extending beyond $t=O(\sqrt{\log N\log\log N})$. Thus, the exponent $1/2$ is the limit of this form of analysis, up to a factor of $\sqrt{\log\log N}$.Authors: Vinayak M. Kumar
The Poisson approximation theorem states that when $m$ balls are tossed uniformly and randomly into $n$ bins, the distribution of the bin loads can sometimes be approximated by $n$ independent Poisson random variables of mean $m/n$. We show that when the balls are tossed via a random $\mathbb{F}_2$-linear map, the load distribution is still governed by this Poisson distribution, albeit in a (necessarily) weaker manner. This allows us to show that a random linear map behaves like a fully random map in the following ways: 1. $\textbf{Expected loads.}$ We show that the expected value of the $r$th largest bin is governed by the $r$th largest value among $n$ independent Poisson random variables of mean $m/n$. Specializing to the canonical setting of $m=n$ and $r=1$, our bounds show that the expected maximum load when $n$ balls are hashed into $n$ bins by a random $\mathbb{F}_2$-linear map is no more than the corresponding expectation for a fully random map $\textit{plus}$ $\frac{3}2 + o(1)$. Specializing to $m\gg n\log n$, we show that the expected max load is $(1+o(1))m/n$ in this regime. 2. $\textbf{Concentration.}$ When $m\gg n\log (1/ρ)$ balls are tossed into $n$ bins randomly, we expect with $0.99$ probability that $\textit{every}$ density-$ρ$ subset of bins will contain a $(1\pm o(1) )ρ$-fraction of the balls. We show that this remains the case if the $m$ balls are tossed using a random linear map, and our bound matches the $o(1)$-factor produced by the fully random case. This gives a stronger version of the Leftover Hash Lemma for linear maps. An implication of this is that all bins have load $m/n \pm O(\sqrt{(m/n)\log n})$ with probability $0.99$. We obtain these results by showing that the average of a log-potential on the bin loads is upper bounded by the cumulant generating function of a Poisson random variable of mean $m/n$.Authors: Christopher Harbourne, Nathan Fisher, Kecheng Yang, Pontus Ekberg, Sanjoy Baruah, Zhishan Guo
Value-based Task Selection (VTS) asks whether a real-time system can select tasks whose total value reaches a required target while preserving every deadline. We study its threshold decision form for finite collections of independent sporadic tasks scheduled preemptively on one processor. We prove that this problem is $Σ_2^P$-complete for both constrained and arbitrary deadlines, even when all numerical parameters are encoded in unary. The existential choice is the selected task set, while the universal condition requires every processor-demand window to remain feasible. Our hardness reduction already uses constrained-deadline tasks. It represents universal assignments by Chinese Remainder Theorem timestamps and uses polynomial-weight local selector locks to enforce a valid existential assignment. The reduction produces polynomially many tasks, and every generated execution time, deadline, period, task value, and target is polynomially bounded in the source-instance size.Authors: Khaled Elbassioni
We prove unconditional lower bounds on the number of recursive calls made by the two algorithms of Fredman and Khachiyan (1996) for monotone Boolean duality testing, as a function of the explicit input size $N$. For Algorithm A we show a lower bound of $N^{Ω(\log N)}$ on the dual pairs $(\HH_k,\LL_k)$ obtained from the read-once family of Gurvich and Khachiyan. The proof lower-bounds the number of leaves of every binary decision tree computing the function by the modulus of its multilinear polynomial evaluated at a complex point of the unit circle. It therefore applies to every choice of branching variables and, more generally, to the class of two-child variable-restriction procedures whose terminal calls have polynomially bounded decision-tree complexity. On this family the number of calls is exactly $N^{Θ(\log N)}$. For Algorithm B, a symmetric specialization of the polynomial padding construction of Kobayashi, Kurita, and Wasa, with full polynomial blocks, yields at least $q^{(t-1)k-t(t-1)/2}$ calls, where $k=4t^2$ and $q=Θ(t^2)$; as a function of $N$ this is $N^{Ω(\sqrt{\log N/\log\log N})}$ along an infinite family. In an appendix we show that applying the padding construction directly to Algorithm A gives $Ω(2^n)$ calls on a dual pair obtained from an unsatisfiable $n$-variable formula, which is only $N^{Ω(\sqrt{\log N/\log\log N})}$ in terms of the input size. No complexity-theoretic assumption is used. The proofs allow every branching-variable choice permitted by the respective algorithm. They concern the original recursive procedures, counting every invocation separately, without sharing calls or adding positive stopping tests.Authors: Hadley Black, Arya Mazumdar, Barna Saha, Geelon So
This work establishes the query complexity of learning high-dimensional boxes in the exact query learning setting. Let $X \subset \mathbb{R}^d$ be a set of $n$ points, labeled by a collection of $k$ boxes: the label of each point in $X$ is determined by the unique box containing it. A learner aims to exactly recover the labels for every point in $X$ given access to a label oracle. We consider three increasingly-structured settings. In the most general setting, there are no conditions on the boxes, and they may overlap. We show that CAL (Cohn-Atlas-Ladner 1994), a classical active learning algorithm, is minimax-optimal with query complexity $Θ(kd \log (n/kd))$. When the boxes are disjoint, we examine two regimes. In the large-$k$ regime, CAL remains minimax-optimal. For the constant-$k$ regime, an optimized variant of the Halving algorithm (Hegedüs 1995) can beat CAL by a $\log(d)$ factor. Finally, in the most-structured settings, the boxes correspond to the leaves of a constant-sized decision tree. We prove a tight query complexity of $Θ(d + \log n)$ that is additive in $d$ and $\log n$, generalizing a recent result (Black-Larsen-Mazumdar-Saha-So 2026) that establishes the query complexity of learning decision stumps.Authors: Junqiu Hu, Lingxiao Huang, Jian Li, Baoduo Xu
We study the optimal coreset size for Euclidean $(k,z)$-clustering, where $z\ge1$ is fixed. Huang, Li, and Wu (STOC 2024) proved a lower bound of $Ω_z(k\varepsilon^{-z-2})$ for $\varepsilon\gtrsim_z k^{-1/(z+2)}$, matching the known upper bound up to polylogarithmic factors. For $0<\varepsilonAuthors: Kaisei Deguchi, Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
We present a polynomial-time randomized algorithm that colors every $n$-vertex $3$-colorable graph with $O(n^{0.1537})$ colors. This improves upon the previous bound of $O(n^{0.1954})$ colors by Bansal, Huang, and Lee (SODA '27). To achieve this result, we introduce a new algorithmic framework for finding a large independent set from a solution to the vector coloring SDP. Combined with the (combinatorial) dense-progress algorithm of Kawarabayashi, Thorup, and Yoneda (STOC '24), this framework yields an $n^{1/6 + o(1)}$-coloring algorithm. Furthermore, we strengthen the SDP-based algorithm specifically for 3-colorable graphs to achieve $O(n^{0.1537})$ colors.Authors: Sharma V. Thankachan
Suffix array and inverse suffix array queries on a text of length $n$ can be answered in $\widetilde{O}(τ^3)$ time using an auxiliary data structure occupying $O(n/τ)$ words, for any $τ\in [1,n]$.Authors: Gonzalo Navarro
Large sparse matrices---adjacency matrices of web and social graphs, feature matrices of machine-learning pipelines, the relations of graph databases---are routinely compressed to save space. Classical compressors, however, force the matrix to be decompressed before it can be used, so the space savings often yield a computational overhead. A recent line of work studies \emph{computation-friendly} compression: formats that are not only small, but let us carry out matrix--vector products, and in some cases matrix--matrix products, sums and closures, directly on the compressed representation {\em in time proportional to that compressed size}. This survey organizes that literature around the kind of redundancy each format exploits: spatial clustering of the nonzeros ($k^2$-trees and their variants), similarity between rows (Boldi--Vigna-style referencing and set-difference compression), repeated substrings (grammar compression), and dense bipartite substructures (bicliques). For each family we describe the representation, the algorithms, the theoretical guarantees and the empirical performance. Further, we show that the last three families are instances of a single general scheme, which we call a {\em sparse straight-line factorization} of the matrix, whose forward and backward substitutions evaluate right and left products in time proportional to the size of the representation, and that the product of two such factorizations is again one, which gives matrix--matrix products with a compressed output. An appendix reviews formats that must be decompressed (at least partially) before operating, for completeness. We close with a cross-family comparison and a list of open problems.Authors: Kiarash Banihashem, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh
We study the problem of submodular maximization under a matroid constraint. In this problem, there is a monotone submodular function $f: 2^{N} \rightarrow \mathbb{R}^+$ and a matroid $M(N, I)$, accessible via value and independence oracles and the goal is to find the independent set $S \in I$ maximizing the objective function, i.e., $f(S) = \max_{I \in I} f(I)$. In the fully dynamic setting, the active ground set $N \subseteq N$ evolves through element insertions and deletions. The goal is to maintain a solution $S \subseteq N$ with $S \in I$ and $f(S) = \max_{I \subseteq N,, I \in I} f(I)$ after each update. Two approximation algorithms have been proposed to solve this problem: Dütting et al. developed a $(4+ε)$-approximation algorithm with an expected amortized update time of $O\!\bigl(\frac{k^2}ε \log k \log n \log^3 \frac{k}ε\bigr)$, and Banihashem et al. achieved a similar approximation with a better update time $O\!\bigl(k \log k \log^3 \frac{k}ε\bigr)$. However, these methods both become inefficient when the rank $k$ of the matroid is large (e.g., when $k = n^{o(1)}$). The central open question in this line of work is whether a fully dynamic algorithm with polylogarithmic update time exists. We resolve this question by presenting the first fully dynamic algorithm for submodular maximization over matroids with polylogarithmic update time. Our algorithm maintains a $(4+ε)$-approximate solution with expected amortized update time $poly(\log n, ε^{-1})$, where $n = |N|$. In particular, the update time is independent of the matroid rank $k$, thereby eliminating the dependence on $k$ and settling the open problem.Authors: Justin Y. Chen, Ying Feng, Piotr Indyk, Michael Kapralov, Ekaterina Kochetkova, Boris Prokhorov
A growing body of work on KV-cache compression aims to reduce the memory requirements of autoregressive generation. These methods compress the stored context while approximately preserving attention computation, enabling generation with reduced memory consumption. Almost tight theoretical results on the worst case space complexity of attention have recently been obtained, but they are achieved by instances where queries can be perfectly aligned with keys. This directly contradicts the observed anisotropy of the key/query geometry in real transformers. In particular, it has been shown empirically that key/query cosine similarities are small even for most correlated pairs, i.e., near-perfect alignment of queries with keys does not happen in practice. In this paper, we study the space complexity of attention approximation under the assumption that key/query cosine similarities belong to a small interval around zero, i.e., a query cannot align too much with any key. We give a nearly space optimal algorithm and a corresponding space lower bound. Surprisingly, the distribution of key/query cosine similarities in our lower bound exhibits the anisotropy property empirically established and studied in the literature. Additionally, we show that the simple uniform sampling algorithm is nearly optimal for a typical range of parameters, supporting its surprising effectiveness on real datasets.Authors: Bo Peng, Zhihao Gavin Tang
We study the order-selection prophet inequality. A gambler knows the distributions of independent nonnegative random values, chooses the order in which to inspect them, and may irrevocably accept at most one value, at the time it is revealed. Since the order is irrelevant when the values are i.i.d., no algorithm can guarantee more than the optimal i.i.d.\ ratio $Γ_\star\approx0.74544$ of the expected maximum. We give an algorithm with competitive ratio $0.74500001$, less than $4.5\times10^{-4}$ below this bound. The algorithm samples independent arrival times and uses item-dependent thresholds. It is designed so that, conditional on its value, every item is selected with probability equal to a fixed fraction of its probability of being the maximum. We show that the constructions of this form that apply one local rule to every item are exactly those given by an allocation kernel, that is, by a coupling of two uniform random variables. Requiring every rarely winning item to follow the optimal i.i.d.\ threshold path singles out a baseline kernel, for which we prove analytically a ratio $Γ_0\approx0.7389$, defined through a one-dimensional control problem. Our final kernel perturbs this baseline, and its guarantee combines analytic estimates with a rigorous computer-assisted certificate.Authors: Armando Rodado Amaris
The greedy algorithm for minimum 3-cut splits a global minimum-weight cut and then the cheaper of its two sides; it is a tight $4/3$-approximation. We show that it is exact, from every global minimum-weight cut, whenever some optimal 3-partition has two parts joined by total weight at least the weighted edge connectivity $λ$. This extends both theorems of Hochbaum and Shmoys from unweighted planar graphs to all weighted graphs, recovers the $4/3$ bound, and generalizes to minimum $k$-cut with a one-paragraph proof. The remaining hard instances have all pair weights below $λ$; for them we prove a merge lemma for Gomory-Hu sides. Finally, we give a 7-vertex graph with a unique Gomory-Hu tree whose unique optimal 3-partition contains no side of that tree, so the first stage of Kapoor's algorithm does not suffice on its own. The main theorem, the 4/3 bound, the merge lemmas and the counterexample are verified in the Lean 4 proof assistant.Authors: Weitian Tong, Yao Xu
We study unweighted nonpreemptive throughput maximization: given jobs with processing times, release times, and deadlines, schedule a maximum-cardinality subset on identical machines. For every fixed $\varepsilon>0$, we give randomized algorithms with expected approximation ratios $17/13+\varepsilon$ in polynomial time and $21/17+\varepsilon$ in pseudopolynomial time. These improve the respective $4/3+\varepsilon$ and $5/4+\varepsilon$ guarantees of Armbruster, Grandoni, Tinguely, and Wiese [STOC'26]. Both results hold for an arbitrary number of identical machines. Our algorithms build on their configuration-LP and matching framework, which partitions time into blocks. For a job whose window meets multiple blocks, its boundary blocks are the first and last such blocks. Crossing boundary pairs, whose endpoints strictly interleave, permit additional assignments to sampled execution slots, while a noncrossing family can be coordinated using consistent joint distributions on at most three blocks. The exchange analysis accounts for fractional job assignments that must be erased before inserting an additional job. For the pseudopolynomial implementation, we project configurations onto selected job identities and use separate configuration distributions with common placement marginals. This retains efficient pricing while enforcing the correlations needed for coordination.Authors: Nicola Wengiel
We study online vector balancing for independent sparse random vectors: each arrival is supported on a uniformly random set of $s$ of the $n$ coordinates, with nonzero entries equal to one (binary model) or independent random signs (signed model), and an online algorithm must sign each vector upon arrival. The prefix discrepancy is the largest $\ell_\infty$-norm of the signed sums up to the horizon $T$, the terminal discrepancy that of the sum at time $T$. For binary inputs with $2\le s\le n/2$ and $T=Θ(n)$, Altschuler and Tikhomirov showed that both are of order $\sqrt{s}+\log\log n$; they asked how the prefix discrepancy depends on the horizon and whether a matching terminal bound holds at every prescribed time. Over long horizons, the two differ. For every fixed $s\ge2$ and $c>0$, every online algorithm, even a randomized one that knows the horizon, incurs with high probability prefix discrepancy $Ω(\log\log n+(\log T/\log n)^{α_s})$ for $n\le T\le e^{cn}$, where $α_s=(2^{s-1}-1)/(2^s-1)$. For $s=2$, quadratic Greedy matches this bound; for fixed $s\ge3$, we give an online algorithm with prefix discrepancy $O(\log\log n+(\log T/\log n)^{1/2})$. In contrast, a deterministic algorithm that knows neither the horizon nor the failure probability keeps the terminal discrepancy $O_k(\sqrt{s}+\log\log n)$ at each prescribed time, with failure probability $n^{-k}$ for every fixed $k$, for $2\le s\le n/2$ (binary model) and $2\le s\le n$ (signed model); for $s=2$, quadratic Greedy itself does so. This answers their terminal question, and the same order is optimal for prefixes at all polynomial horizons $T\ge n$. The lower bound uses a finite safety game realized within the input law; the upper bounds use moments of elementary symmetric polynomials and, at terminal times, a $\cosh$ potential or a translated gauge with a Foster inequality at every state.Authors: Hongyi Chen, Tianyi Zhang
We study approximation algorithms for constructing sparse navigable graphs in general metrics. Given an $n$-point metric $(P,d)$ and a parameter $α\ge 1$, an $α$-navigable graph is a directed graph $G=(P,E)$ such that for every ordered pair of distinct points $s,t\in P$, the vertex $s$ has an outgoing edge $(s,p)$ with $d(p,t)Authors: Yang P. Liu, Hoai-An Nguyen, Vihan Shah, David P. Woodruff
We give an $\tilde{O}(n/\varepsilon)$-space algorithm for the minimum cut problem in dynamic streams, resolving the space complexity of streaming min-cut up to polylogarithmic factors. Ding, Garces, Li, Lin, Nelson, Shah, and Woodruff (ITCS 2025) obtained the same $\tilde{O}(n/\varepsilon)$ space bound for insertion-only streams, while prior to our work the best known bound even for unweighted dynamic streams was $\tilde{O}(n/\varepsilon^2)$, due to Ahn, Guha, and McGregor (PODS 2012). Our main technical contribution is an $\tilde{O}(n/\varepsilon)$-space for-each cut sketch in dynamic streams, which may be of independent interest. The construction applies to weighted graphs under general $\pmΔ$ updates, a stronger model than the standard dynamic-stream setting in which weighted edges are inserted and deleted in their entirety. Despite this stronger guarantee, our algorithm is surprisingly simple and relies on very little machinery. We also obtain applications to minimum $\ell_p$-norm $k$-partitioning for every fixed $k$, weighted correlation-clustering evaluation for two clusters, and for-each cut sketching in balanced directed graphs.Authors: Merav Parter, Elizaveta Popova, Elad Tzalik
We present new constructions of vertex fault-tolerant (VFT) $(α,β)$-spanners with substantially improved size bounds. Given a bound $f$ on the number of vertex faults, an $f$-VFT $(α,β)$-spanner is a subgraph of $G$ that preserves an $(α,β)$-spanner of $G- F$ for every fault set $F \subseteq V$ with $|F| \le f$. Most existing constructions of VFT $(α,β)$-spanners rely on a black-box sampling technique that incurs an exponential blow-up compared to their non-fault-tolerant counterparts. We develop two independent techniques for constructing $f$-VFT $(α,β)$-spanners that improve the dependence on $f$, reducing it to polynomial overhead. For every unweighted graph $G=(V,E)$ on $n$ vertices, stretch parameter $k$, and fault parameter $f$, we show: (i) $f$-VFT $(O_ε(k^ε), O_ε(k))$-spanners with $\tilde{O}(f^{exp(1/ε)}\cdot n^{1+1/k})$ edges for any $ε\in (0,1)$. For any fixed constant $ε$, this introduces a $poly(f)$ overhead compared to the non-faulty constructions of [Ben-Levy and Parter, SODA 2020] and [Chechik and Lifshitz, SODA 2026]. (ii) For any $δ\in (0,1)$, an $f$-VFT $\left(O_δ(\sqrt{k}),O_δ(k) \right)$-spanner of size $\tilde{O}(f^{1+δ} \cdot n^{1+\frac{1}{k}})$. Hence, it incurs a size overhead of only $f^{1+δ}$ compared to the above-mentioned non-faulty analogs. (iii) $f$-VFT $(k,k-1)$ spanner of size $O(k^3 \cdot f \cdot n^{1+\frac{1}{k}})$, nearly matching the lower bound $Ω(f^{1-\frac{1}{k}}n^{1+\frac{1}{k}})$ known for $f$-VFT $(2k-1,0)$ spanners by [Bodwin et al., SODA 2018]. The first result is obtained via a new adaptation of the Baswana--Sen framework to the VFT $(α,β)$ setting. The other two bounds follow from a highly involved analysis of a natural extension of the fault-tolerant greedy spanner.Authors: Karthekeyan Chandrasekaran, Chandra Chekuri, Weihao Zhu
We study a simple random deletion algorithm to find short circuits in regular matroids. Given a regular matroid $M$ with $m$ elements, the algorithm randomly deletes each element independently with probability $1-1/m^{Θ(1/g)}$ where $g$ is the size of a minimum circuit, and returns the remaining set $R$ of elements. We establish the following results: 1. With high probability, $R$ contains no circuit and is therefore independent. 2. For every $α$-approximate minimum circuit $C$ where $α\geq 1$, with probability at least $m^{-O(α)}$, the entire circuit $C$ survives in $R$ and moreover, the minimum number of elements that need to be removed to make $R$ independent is $O(α\log(α+2))$. This yields an algorithmic proof that the number of $α$-approximate minimum circuits is $m^{O(α)}$, improving the previous known bound of $m^{O(α^2)}$ by Gurjar and Vishnoi, and resolving a recent conjecture of Khanna, Putterman, and Song. Our results yield two immediate applications. First, we obtain very simple RNC algorithms for computing the shortest circuit, and for enumerating all $α$-approximate circuits, of a regular matroid without computing the Seymour decomposition. Second, we obtain a randomized parallel algorithm to find a basis of a regular matroid under independence-oracle access. It uses polynomially many independence-oracle queries in $O(\log m)$ adaptive rounds and succeeds with high probability. This follows from the framework of Khanna, Putterman, and Song and the improved counting bound, and extends their result from graphic matroids to regular matroids.Authors: Florian Kurpicz, Maximilian Paris
The Burrows-Wheeler transform (BWT) is the core of many compressed full-text indexes and most read aligners. The fastest BWT constructions on GPUs need about $20$ bytes of device memory per character, which severely limits the texts that can be processed there. For example, on our GPU with 24 GB device memory, this is only about 1200 MiB. Prefix-free parsing (PFP) can be used to reduce the memory requirements of BWT construction algorithms in main memory. But, it uses hash tables and inverted lists which are not suited for GPUs. We show that PFP-based BWT construction can work with only sorting, scanning, and simple data-parallel procedures. This results in our GPU construction gpupfpbwt that on an NVIDIA RTX 3090, reduces the peak memory on an English text 11.9 bytes per character. There, it can processes 2108 MiB input files, which is 1.8 times larger than what the current state of the art libcubwt can handle. It is faster than or on par with libcubwt on eight of nine repetitive texts but 2.0 to 3.2 times slower on five of six non-repetitive ones, i.e., it provides a trade-off between required device memory and throughput.Authors: Qiuyu Chen, Baao Xie
Position auctions require assigning advertisers to positions and determining their display order. Under cascade behavior, earlier clicks prevent users from reaching later placements, coupling the click probabilities of selected advertisements. Existing methods achieve constant-factor welfare approximation and monotone logarithmic-factor approximation separately, leaving open whether both guarantees can be attained simultaneously. The difficulty is that welfare-preserving rounding need not maintain the monotonicity of individual click-through rates required for truthful bidding. We resolve this problem by developing a polynomial-time randomized mechanism that achieves a factor-6 welfare approximation and truthfulness in expectation for arbitrary public advertiser-position click probabilities. The mechanism optimizes a reach-weighted linear relaxation and converts its solution into feasible ordered allocations through matching decomposition, probability-bounded grouping, and calibrated attenuation. This construction compensates for cascade dependence and ensures that each advertiser's expected click-through rate equals exactly one sixth of its fractional click coordinate. The resulting identity transfers the monotonicity of the fractional allocation to the implemented mechanism, enabling exact incentive-compatible payments while preserving the welfare guarantee. The allocation lottery and payments are computable in polynomial bit time, with exact sampling in expected polynomial time.Authors: Wei Li
We study non-preemptive scheduling on identical parallel machines in which assigning job $j$ to machine $M_i$ incurs the cost $c_{ij}=a_iw_j+b_j$. The processing times $p_j$ and the cost weights $w_j$ are independent, and the number of machines is part of the input. For every fixed $\varepsilon\in(0,1]$ and every deadline $T$ for which a schedule with makespan at most $T$ exists, we give a polynomial-time algorithm that computes a schedule with makespan at most $(1+\varepsilon)T$ whose total assignment cost does not exceed the minimum under the deadline $T$. Using this algorithm as a subroutine, we obtain a polynomial-time approximation scheme for minimizing the makespan under a total cost budget whose schedules always satisfy the budget; this answers an open question for costs $c_{ij}=l_ic_j$ with $c_j$ independent of $p_j$. For the lexicographic problem, in which the total assignment cost is minimized among all schedules of minimum makespan, we obtain in polynomial time a schedule with makespan at most $1+\varepsilon$ times the minimum and total assignment cost at most that of a lexicographically optimal schedule; this improves the makespan guarantees of earlier algorithms for additive and multiplicative costs. For costs $c_{ij}=s_i+a_iw_j$, where $s_i$ is charged for each job processed on $M_i$, the same guarantees are obtained in quasi-polynomial time.Authors: Bryant Gipson
The subgraph isomorphism problem (SGI) asks a deceptively simple question: is a graph B found inside a parent graph A? Famously NP-complete and the subject of volumes of study, attempts to practically solve subgraph problems typically require specialized software or the focused application of problem-specific theoretical knowledge. Here we present a straightforward linear framework that neatly joins SGI to lattice theory and constrained satisfiability and, importantly, yields an easily implemented algorithm that naturally leverages consumer-grade hardware and off-the-shelf libraries to compete with state-of-the-art specialized solvers. We additionally show practical realizations in approachable settings, along with some benchmarks that reduce 6+ hour computations to seconds. Aimed at readability, we develop a series of computable algebraic invariants and demonstrate their application to familiar problems such as the Knight's Tour, with a focus on providing an accessible entry point for researchers in graph theory, abstract algebra, and students in general.Authors: Andrew Krapivin, William Kuszmaul
In this paper, we introduce braided cuckoo hashing, an open-addressed hash table that supports load factor up to $1 - \varepsilon$ (for some parameter $\varepsilon \in (0, 1)$), while supporting queries, insertions, and deletions in worst-case time $O(\log \varepsilon^{-1})$, with high probability. This result represents an exponential improvement on insertion/deletion time over previous constructions, and disproves a conjecture of Bender, Kuszmaul, and Zhou that the product of worst-case query time and expected insertion/deletion time must be $Ω(\varepsilon^{-1})$.from Scott Aaronson
The title Curt put next to my head could’ve been in reference to many, many things! But sorry, he just mean AI. He and I start with the Mathacre, of course, but then we get onto the firewall paradox and then Curt starts asking about computational complexity and the Second Law, and then about Integrated Information Theory.
OK, despite the title of this post, short break from “The Topic.” Here’s an absolute masterpiece of mathematical exposition, from the “Polylog” YouTube channel, which tells the story of the determination of Busy Beaver values through spectacular animations. I play cameo roles in the video, although I embarrass myself (as the video silently points out) by transposing two digits in the value of BB(5)…!
And, coming soon (not on YouTube quite yet): a conversation about the Mathacre with celebrated physics popularizer (and character on The Big Bang Theory) Brian Greene, recorded in-person in NYC during my recent trip to speak in the math department at Columbia University!
And to preempt the inevitable comments about it: yes, my students just came to my office to tell me that an OpenAI model has now refuted the Exponential Time Hypothesis, by giving an algorithm to solve 3SAT in an amount of time that scales roughly like exp(n/√log(n)). Even as we struggle to digest the previous courses, the endless buffet continues!
from ECCC Papers
from Ben Recht
Over the past few weeks, I’ve been giving a talk, “The World Is Something We Make,” about truly open language models. I’ve written everything I say in that talk on this blog at one point or another, but I’ve never put all of those thoughts in one post. Given that Anthropic S-1 was just released, with them beckoning us to submit to their unstoppable momentum, it felt worth reminding myself and you, my readers, that there is clearly another way forward and that no future is inevitable.
In 2024, David Donoho wrote a compelling essay, “Data Science at the Singularity,” arguing that the superpowers behind advances in AI were the engineering and research practice. The community encouraged what Donoho dubbed “frictionless reproducibility,” a culture of shared tasks, code, and benchmarks. People worked on a shared suite of datasets. They engaged in (mostly friendly) open competition to show who could be best. But most importantly, they made their processes, procedures, and code open.
This open process not only improved performance on the shared benchmarks. It also bred remarkable innovations, including code optimization and acceleration, generalization to new problem domains, opening the field to more engineers and stakeholders, and transparent processes that allowed reasonable auditing of the technology.
You can trace this pattern linking openness and innovation all the way back to digit recognition at Bell Labs in the 1960s.1 Indeed, you might argue that the AI Winters happen precisely when people stop sharing benchmarks and tasks. Over the past twenty years, frictionless reproducibility has reshaped how we build recommendation systems, classify images, and think about language. It even led to a Nobel Prize in chemistry, with protein structure prediction effectively being solved through the pathway of frictionless reproducibility.
Unfortunately, with the rise of large language models, the machine learning community took a hard 180 into a world of consolidated, closed development. The original sin of the language model was using training data acquired illegally. Even though the companies maintain this is all fair use, they clearly don’t believe it because they refused to tell everyone else what data they used for training. This quickly became an excuse to close off research, justified by specious arguments about capitalist competition and fantastical stories about sci-fi safety.
The end state we’re in today is reprehensible. On the one hand, machine learning technology is more amazing than I ever imagined it could be. On the other hand, it’s a technology making everyone miserable. Knowledge workers drive themselves insane in a flow state with their stochastic productivity software. Data centers are less popular than coal plants. And the broader community outside of the umbrella of creatively financed venture spending can’t take back control because small innovations on small models have no relevance or impact.
So what is our path back to openness? Open weight models are a nice first step. At least they introduce low-cost competition to the market. If you haven’t found a way to run an open model in an open harness and see that it’s probably good enough for 99% of your work, you are very much missing out! But they aren’t really open, are they? As the open software community will attest, if someone gave you an exe file to run, you wouldn’t consider that open. Moreover, the competitive open-weight models are all Chinese, which raises many trust issues for many developers. No, open must mean everything open. That means open weights, code, data, and process. To the best of my knowledge, only two initiatives, Marin and AI2, are committed to this kind of truly open development. They are heroic, but vastly under-resourced.
My question to everyone reading this is simple: how do we collectively commit to building this sort of open infrastructure? Open from top to bottom.
My Berkeley colleague Ion Stoica pithily laid out the three necessary components of any large AI project: people, data, and compute. In talking to people over the last few months, I know there is no shortage of people who want to help build truly open language models. Open efforts like Marin, AI2, and, to some extent, NVIDIA, have compelling stories about how we can build training datasets without theft and copyright violations. Sure, there are still unknowns about post-training data, but I’m sure we can make progress on that out in the open too. The hard one, as far as I can tell, is compute. We need a massive collaboration to donate, harvest, and share idle compute. That will require more creativity, but this is creativity about collaboration, not technology. We have the technology to do it. We just need to figure out the right architecture of participation to grow a system bigger than the sum of its parts.
The history of machine learning shows that once we have an open prototype, the floodgates open. Imagine we had a truly open model as good as Opus 4.5. In months, the open software and machine learning communities will have figured out how to train this 1000x more efficiently. They will have figured out ways to fine-tune it to specific tasks and domains. And they will have audited its guts to understand how to deploy it safely and securely. But this is all predicated on having the open prototype so we can collaborate.
I don’t think it’s absurd to imagine such a prototype existing. We just need a bit of organization to put this effort together. The title of this post is a quote from David Graeber, who wrote, “The ultimate hidden truth of the world is that it is something that we make, and could just as easily make differently.” No future is inevitable. Cheers to that.
I write about this history extensively in Chapter 5 of The Irrational Decision.
Authors: Remi Pallen
The Medvedev lattice is a tool used to classify the complexity of effective closed sets. In this article, we are interested in the complexity of using this tool. In particular, we study the complexity of deciding whether two effective closed sets have the same degree, when one is fixed and the other is given as input. This problem is naturally~$Σ^0_3$, and among other results, we show that for all degrees except the maximal one, the problem reaches its maximal complexity. It turns out that the argument is not uniform and depends on the self-similarity of the fixed degree, a notion that we introduce in this article. The complexity of having maximal degree is particularly difficult to establish, but we obtain a lower bound that almost matches the upper bound. We also show that deciding whether an effective closed set has a degree incomparable with a fixed degree $d$ is $Π^0_3$-complete whenever $\mathbf{0}_s <_s d <_s \mathbf{1}_s$.Authors: Pierre-Jean Spaenlehauer
Finding the roots of a polynomial over a finite field $\mathbb F_q$ in deterministic polynomial time is a long-standing open problem. Classical deterministic methods work in the multiplicative group $\mathbb F_q^\times$ and are efficient only when $q-1$ is smooth, which is rarely the case. We propose a method that replaces $\mathbb F_q^\times$ by the groups of rational points of an elliptic curve $E$ and of its quadratic twist $\widetilde E$. The computation splits into an offline phase, which depends only on $\mathbb F_q$ and outputs a short \emph{elliptic preprocessing datum} $\mathcal D$, and an online phase, which processes the input polynomial. Writing $Ξ(\mathcal D)$ for the largest prime factor of $\lvert E(\mathbb F_q)\rvert\cdot\lvert\widetilde E(\mathbb F_q)\rvert$, the online phase is deterministic and finds the roots of any $f\in\mathbb F_q[X]$ of degree $n$ within $\widetilde O(Ξ(\mathcal D)^2\,n\log^2 q+n^ω\log q+n\log^3 q)$ operations in $\mathbb F_q$. A precursor of our method is an algorithm by Rónyai, which recovers the roots through Galois computations over number fields, relies on GRH, and comes with a polynomial bound of unspecified degree; in contrast, our online phase works entirely over $\mathbb F_q$ and is unconditional. Moreover, $\mathcal D$ can be certified deterministically and unconditionally in time polynomial in $\log q$ and $Ξ(\mathcal D)$. We conjecture that every $\mathbb F_q$ of large enough characteristic admits a datum with $Ξ(\mathcal D)\leq(\log q)^{O(1)}$, and support this with a heuristic and with experiments. Constructing such a datum in polynomial time remains open.Authors: Sarah Houdaigoui, Nacim Oijid, Matthieu Petiteau, Alexandre Vigny
In a directed graph, a stable (or acyclic) set is a set which does not induce a directed cycle. Given a directed graph and two acyclic sets of the same size, the Acyclic-Set-Reconfiguration with Directed Token Sliding (ASR) problem asks whether one can, by iteratively replacing a vertex by an adjacent one, transform the first set into the second one, while maintaining acyclicity during the transformation. In this work, we present a study of the complexity of ASR and provide an FPT algorithm for semi-complete digraphs, when parametrized by the size of the sets being reconfigured, the directed pathwidth (or equivalently, the directed treewidth) of the instance, and a newly introduced parameter called the iteration of the reconfiguration sequence. To the best of our knowledge, the reconfiguration of stable sets has only been studied on undirected graphs, or (more recently) on sparse directed graphs.Authors: Zhijun Zhang
Determining the communication complexity of graph connectivity has been one of the longest standing open problems in communication complexity since the seminal work of Babai, Frankl, and Simon [FOCS'86]. A simple protocol transmits a spanning forest using $O(N\log N)$ communication on $N$-vertex graphs. While this was shown optimal for deterministic protocols by Hajnal, Maass, and Turán [STOC'88], the optimal nondeterministic and randomized complexities have remained unresolved for decades. We settle the nondeterministic communication complexity of graph connectivity by proving an optimal $Ω(N\log N)$ lower bound. The best prior bound was $Ω(N\log\log N)$ due to Raz and Spieker [Combinatorica'95]. Our bound is shown by upper bounding the maximum size of $1$-monochromatic rectangles. Generalizing our techniques to weighted, almost $1$-monochromatic rectangles yields an $Ω(N \cdot \log(\min(1/\varepsilon,N)))$ lower bound for randomized protocols with error probability $\varepsilon$. In particular, this bound is optimal for any polynomially small $\varepsilon$. For constant error probability, we also prove that any $r$-round protocol requires $Ω(N/r \cdot \log N)$ communication, which is optimal for every constant $r$. Previously, optimal $Ω(N\log N)$ lower bounds for graph connectivity were known only for $1$-round [Sun, Woodruff; APPROX/RANDOM'15] and $2$-round protocols [Radhakrishnan, Reddy, Venkat; ITCS'26]. Our proof introduces a new communication problem which can be viewed as a composition of inner product and pointer chasing problems. Our lower bounds can be extended to other fundamental graph properties, and also imply optimality of known query and streaming algorithms for related problems.Authors: Steven Heilman
We simplify and improve OpenAI's proof of the propeller conjecture of Khot and Naor from 2008: the sum of the squared lengths of the Gaussian moments of any partition of Euclidean space is at most $9/(8π)$. We show equality only occurs for three 120 degree sectors in the plane (up to symmetries, measure zero changes, and taking orthogonal cross products with Euclidean space). We also remove computer assistance from the three-dimensional case of the conjecture, which previously used an epsilon net traversal.Authors: Abhranil Chatterjee, Sumanta Ghosh, Zeyu Guo, Rohit Gurjar, Roshan Raj
We give a deterministic quasipolynomial-time construction of Reed-Solomon codes that are list-decodable beyond the Johnson radius. Specifically, for every $ε\in(0,1]$ and all sufficiently large $n$, we construct an $[n,k]$ Reed-Solomon code of rate $R=Ω(ε/(1+\log(1/ε)))$ over a field of size $(nk)^{quasi-poly(nk)}$ that is $(1-ε,O(1/ε))$ list-decodable. The construction runs in quasi-poly(nk) time. We also give a deterministic construction of $[n,k]$-MDS$(3)$ Reed-Solomon codes for all integers $1\leq kAuthors: Rahul Moorthy, Volkan Isler
Methods for learning continuous representations, such as latent manifolds, are fundamental and ubiquitous in modern machine learning. Yet many geometric objects combine continuous shape information with discrete combinatorial structure. This combination presents a fundamental challenge for representation learning because small geometric perturbations can induce abrupt changes in the underlying discrete representation. As a result, the smoothness assumptions that make continuous representations effective no longer hold. Polygons provide a canonical example. Their vertex locations vary continuously, but infinitesimal changes in geometry can dramatically alter the associated visibility graph. Existing methods address the inverse mapping from visibility graphs to polygon geometry using vertex-, triangulation-, or signed-distance-function (SDF)-based representations. Vertex- and triangulation-based approaches construct polygons through explicit geometric operations. However, they are less effective at modeling the relationship between geometry and visibility. SDF-based approaches capture this relationship more naturally. Their intermediate states, however, do not correspond to explicit stages of polygon construction. We present VisFlow, a novel, interpretable flow formulation that combines continuous SDF representations with explicit polygon evolution. We evaluate VisFlow on Visibility Reconstruction and Visibility Characterization. Visibility Reconstruction generates one polygon consistent with a visibility graph (G), while Visibility Characterization characterizes all such polygons. VisFlow maintains 20% more visibility relations on Visibility Reconstruction and improves coverage by 30% on Visibility Characterization compared to state-of-the-art methods.Authors: Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
We give a combinatorial algorithm that computes an exact minimum-cost flow in $n^{2+o(1)}$ time. This is the first combinatorial improvement since Goldberg-Tarjan [GT87], and is almost optimal in dense graphs. All previous faster algorithms, including the almost-linear-time algorithm of Chen et al. [CKL+22], rely on interior-point methods. Our main conceptual contribution is a black-box reduction from exact minimum-cost flow on general graphs to its approximation on DAGs, with only an $n^{o(1)}$ loss on the running time. This reduction allows future work on combinatorial minimum-cost flow to focus on DAGs, typically much easier to handle than general graphs. Our $n^{2+o(1)}$-time algorithm follows by combining this reduction with a simple augmenting-path-based approximation algorithm on DAGs. The reduction is based on a new structural result, called a flow-cost-preserving DAG projection. Given an arbitrary directed graph, this construction produces a DAG that approximately preserves both the congestion of flows and their cost up to a small loss.Authors: Ziyad Benomar, Vianney Perchet
We study preemptive single-machine scheduling with predictions, where a prediction of the order of the jobs (or of their sizes) is available, and the objective is to minimize the total completion time. An algorithm is $c$-consistent if it is $c$-competitive when the prediction is correct, and $R$-robust if it is $R$-competitive whatever the prediction. Since the introduction of this problem as one of the first examples of learning-augmented algorithms, the best possible trade-off between consistency and robustness has remained open. We determine it exactly for deterministic algorithms. For every $R>2$, we give an $R$-robust algorithm whose consistency is \[ c(R)=R\Big(1-\Big(1-\frac{R+2}{R^2}\Big)^{\frac R{R+2}}\Big), \] and we prove that no deterministic $R$-robust algorithm, with either predicted order or predicted job sizes, has better consistency. In particular, consistency $1+\eps$ is achievable with robustness $\eps^{-1/2}+\frac16+O(\sqrt\eps)$, whereas all previous algorithms required robustness $Θ(1/\eps)$. Our algorithm is greedy: it follows the predicted order as fast as possible, subject to the invariant that the cost paid so far is at most $R$ times the optimum of the instance in which every unfinished job would end immediately. The matching lower bound rests on the observation that every robust deterministic algorithm must satisfy the same invariant along its run on correct predictions.Authors: Karyamsetty Martin
The asymptotic competitive ratio of online bin packing has been bracketed since 2018 by the lower bound 1.54278 of Balogh, Bekesi, Dosa, Epstein and Levin and the upper bound 1.57829 of their Advanced Harmonic algorithm. We revisit both sides with exact rational computation and prove what the computations say. On the upper bound, we rebuild the certification of Advanced Harmonic as an exact optimization over its dual parameters; with the published parameters this already certifies a ratio strictly below the published one, and re-tuning the algorithm's proportion parameters gives a certified ratio of 1.5782147437 (an exact rational), independently re-verified on all 402 scenarios. To our knowledge this is the first movement of the upper bound since 2018. On the lower bound, we prove that the 2018 adversary construction is rigid: extending it by any finite number of new batches of ordinary size (outside the window of sizes s with 2s > 1 and rational part at most 0.64819), placed anywhere, with counts depending on the observed statistics, adaptive or not, never improves the bound at any truncation level. The load-bearing fact is that the construction is volume-tight at every stop. A single window-sized batch added to the truncation-3 tree is shown by machine-verified certificates to leave its value below the published limit. A computational map covers the remaining natural extensions: unions of structural variants, two-statistic multi-batch adversaries, and three families of adaptive conditions that the paper's separation theorem allows but never uses; none improves the bound. On the algorithm side we show that the marking, bonus-item and red-sand mechanisms of Extreme Harmonic bind nowhere in Advanced Harmonic, whose bottleneck is a two-medium-item bin that no known mechanism targets. We record two corrections to commonly cited numbers.Authors: Xiangle Chen
The Smallest Grammar Problem (SGP) asks for a smallest straight-line grammar generating a given string, where size is the total length of the right-hand sides. Rules may be nested, so locally optimal choices of repeated fragments need not combine into an optimal grammar. We show that in an optimal grammar one can choose an occurrence of the expansion of each auxiliary nonterminal such that these intervals are pairwise disjoint. Hence the dictionary can be read off from a partition of the input, decoupling the choice of the dictionary from the parsing of rules. Using this property together with a bound on references to rules of length two, we obtain an exact algorithm running in $O^*(1.8723^n)$ time and $O(n)$ words of space, improving the $O^*(3^n)$ bound of Casel et al. for general grammars. For alphabet size $σ$ and $R=\log_σn$, we give a $2^{O((n/R)\log(R+1))}$-time algorithm, which is subexponential for fixed alphabets. Conversely, using an anchor-based projection from encoded grammars back to source grammars, we prove that SGP is NP-complete over a binary alphabet, answering a question of Casel et al., and construct instance families of tunable alphabet size on which no $2^{o(n/R)}n^{O(1)}$-time algorithm exists under ETH. Finally, for every $c>1$ we give a constant-degree integer polynomial formulation of SGP with $O(c^n)$ variables. By the barrier theorem of Belova, Golovnev, Kulikov, Mihajlin, and Sharipov, a proof that SGP is $λ^n$-SETH-hard under their deterministic fine-grained reductions would imply new lower bounds for Boolean series-parallel circuits or for arithmetic circuits.Authors: Ohad Ayalon, Ilan Reuven Cohen
Smith's rule orders jobs by their weight-to-processing-time ratios. We study the robustness of its list schedule on identical parallel machines when job $j$ is ordered using a nominal processing time $μ_j$ and its true processing time satisfies $μ_j\leq p_j\leqαμ_j$, where $α\geq1$. We determine the exact worst-case approximation ratio against the clairvoyant optimum, taking the supremum over machine counts. The ratio is an explicit continuous piecewise-algebraic function of $α$. It equals the Kawaguchi--Kyan constant $(1+\sqrt{2})/2$ at $α=1$ and is exactly $\sqrtα$ for $α\geq4$. On one machine the exact ratio is $\sqrtα$. For every fixed machine count, no deterministic nonpreemptive algorithm can improve on this guarantee, even with knowledge of $α$. The proof reduces to a common nominal Smith ratio and endpoint errors. Cutting the list schedule at its minimum final machine load yields a prefix--suffix certificate; two packings of matching lower-bound instances explain the branches below $α=4$. We also prove a nominal-to-robust transfer: any fixed schedule ordered by nominal Smith ratios on each machine, with nominal approximation ratio $1+δ$, has realized ratio at most $\sqrtα+αδ$. A nominal approximation scheme then gives, for every fixed $\varepsilon>0$, a deterministic polynomial-time algorithm independent of $α$ with ratio $(1+\varepsilon)\sqrtα$ simultaneously for $1\leqα\leq4$.Authors: Nick Fischer
Since the early days of fine-grained complexity, many geometric problems have been shown to require quadratic time under the 3SUM Hypothesis. But as the 3SUM Hypothesis was recently refuted, these lower bounds have lost their foundation. In this note we point out that many of them can be recovered under an alternative hardness assumption, the $k$-AP Hypothesis. The required changes to the proofs are trivial, so the lower bounds remain just as easy to teach.Authors: Haoming Wang, Ming Yuan
We study the structure and exact certification of nonnegative tensor decompositions supplied through rational factor matrices. Every failure of minimality or essential uniqueness contains an irreducible positive exchange between $p$ supplied terms and $q$ competing terms. A dimension count based on the Lovitz--Petrov splitting theorem bounds the effective order of such an exchange, the sum over the modes of the joint factor-span dimension minus one, by $p+q-2$, and this bound is attained at every supplied length $R\ge2$. After eliminating ambient-row variables by the Farkas lemma, the resulting semialgebraic systems have fewer than $2R^2$ real variables. For input bit length $L$, this gives a deterministic $G(R)L^{O(R^2)}$-time algorithm that computes the nonnegative rank and an exact minimum-length decomposition, decides minimality and essential uniqueness, and returns exact witnesses when either property fails. The exponent is independent of the tensor order and the mode dimensions. For Lebesgue moment tensors, positive quadrature determines the nonnegative rank and the uniqueness behavior, and some rational length-$R$ inputs force a common field of degree at least $\lfloor R/2\rfloor!$ for any exact minimum-length output. As an illustration, an implementation resolves all 114 instances left inconclusive by earlier positive-scattering criteria, of which 95 are minimal and essentially unique and 19 are minimal but nonunique.Authors: Mónika Csikós, Nabil H Mustafa
Given a set system (X, S), we consider the problems of constructing perfect matchings and spanning paths (also known as Welzl orders) of X with low crossing numbers with respect to S. Matchings with low crossing numbers were originally introduced in the late 1980s in the seminal works of Welzl [29, 30] and Chazelle-Welzl [7], who showed that any set system (X, S) with bounded dual VC-dimension d has a matching with crossing number O |X| 1-1/d , which is optimal. Low-crossing matchings and spanning paths have found several applications outside of their initial realm of computational geometry, including algorithmic graph theory, model checking, and game theory. In many of these applications, |S| is near-linear in |X|, which motivated the search for an improved construction for this regime. However, the proposed new algorithms provided only average-case bounds or sub-optimal crossing number guarantees for d $\ge$ 2 [5, 12]. We propose a new quasi-uniform sampling based framework. This allows us to obtain a simple algorithm with expected running time of __ |X| 2 + |S| $\bullet$ |X| , which improves upon the previous-best Our result has several immediate consequences, including new faster algorithms for constructing low-crossing spanning paths for set systems induced by balls, as well as for neighborhood set systems of graphs. Moreover, we get the first quadratic-time algorithm for combinatorial discrepancy, with nearly optimal discrepancy (up to a log factor), for bounded dual VC-dimension set systems. Beyond these applications, we believe that our idea could be applied to other algorithms that use the multiplicative weight update method.Authors: Nicolas Christianson
We establish an $Ω(d)$ lower bound on the competitive ratio of convex body chasing in $\mathbb{R}^d$ with $\ell_p$ movement costs for any $p \in [1, \infty)$. Previously, the best known lower bound for general $p$ was $Ω(\max\{\sqrt{d}, d^{1-1/p}\})$, established by Bubeck et al. (2019); a linear lower bound was known only for $p = \infty$, realized by the standard construction of chasing faces of a hypercube. Our lower bound strictly improves on the prior bound for every fixed $p \in [1, \infty)$ and shows that the functional Steiner point algorithm of Sellke (2023) - which has competitive ratio $O(d)$ - is asymptotically optimal for every $\ell_p$ norm. Our lower bound is based on the recursive construction of Bubeck, Coester, and Rabani (2023) for metrical service systems, which gives a lower bound of $Ω(r^2)$ for requests of size $O(r)$ in that setting. We show that requests in their construction, each comprising a set of discrete points in a graph metric, can be mapped to the vertices of convex requests in a $(2r+1)$-dimensional vector space while approximately preserving movement costs up to a factor of $O(r)$, which establishes the lower bound.Authors: Jørgen Bang-Jensen, Stéphane Bessy, Amadeus Reinald
A path or cycle in a $2$-edge-coloured graph is alternating if consecutive edges have different colours. These objects are natural analogues of paths and cycles in graphs, and even more so in digraphs. A well-studied class is that of acyclic $2$-edge-coloured graphs, that is, those forbidding alternating cycles. In particular, (acyclic) $2$-edge-coloured graphs generalize directed (acyclic) graphs (DAGs), but the complexity of problems on DAGs is much better understood than that of the corresponding problems on acyclic $2$-edge-coloured graphs. We investigate the complexity of two such problems, whose directed counterparts are well-known. Our first result is an $n^{O(k)}$-time algorithm for the alternating $k$-linkage problem on acyclic $2$-edge-coloured graphs. This problem asks for $k$ vertex-disjoint alternating paths joining $k$ prescribed pairs of vertices. This generalizes the directed $k$-linkage algorithm for DAGs. For every fixed $k$, this also yields a polynomial-time algorithm for finding $k$ internally vertex-disjoint alternating $(s,t)$-paths, solving an open problem by Abouelaoualim et al. from 2008. We then consider the alternating chromatic number of $2$-edge-coloured graphs, defined as the minimum number of parts in a vertex partition such that each part induces an acyclic subgraph. This notion is analogous to the dichromatic number of digraphs, where it is known that deciding dichromatic number $2$ is NP-complete even on tournaments. Our second result is that deciding alternating chromatic number $2$ is NP-complete on complete $2$-edge-coloured graphs. Equivalently, deciding whether a graph can be partitioned into two induced threshold graphs is NP-complete.Authors: Ilias Diakonikolas, Jelena Diakonikolas, Puqian Wang, Nikos Zarifis
We study the fundamental problem of PAC learning positive linear combinations of $k$ arbitrary ReLU activations on $\mathbb{R}^d$ with respect to the Gaussian distribution, in $L_2$ loss. We give the first fully-polynomial time algorithm for this learning task. Specifically, our algorithm draws $\mathrm{poly}(d, k, 1/ε)$ samples, runs in $\mathrm{poly}(d, k, 1/ε)$ time, and outputs a hypothesis that is $ε$-close to the target concept with high probability. All prior algorithms for this problem require super-polynomial time in $k$ or $1/ε$, or leverage strong well-conditioned assumptions on the weight matrix. On a technical level, our approach develops a novel boosting procedure of a ``weak'' learner that recovers the hidden weight vectors to constant error, in a list-decodable manner. To develop this ``weak'' learning procedure, we leverage implicit tensor computation techniques to construct a low-degree filtering procedure based on Hermite tensors of the target function. This procedure amplifies separation among (clusters of) weight vectors to learn each of them to constant error. We then argue that the same procedure can be used for improving the estimation of hidden weight vectors, using gradient descent-like updates on the Euclidean sphere. A crucial ingredient of our algorithm is a pruning approach that ensures only relevant vectors that approximate the hidden weight vectors at target accuracy are maintained by the algorithm.Authors: Nicolás Araya, José Zagal, Cecilia Hernández, Gonzalo Navarro
Boolean matrix multiplication is a fundamental operation in many graph-based applications, including web and social network analysis, information retrieval, and graph query evaluation. However, conventional sparse representations such as CSR}/CSC still incur significant space and time costs on large graphs. In this work, we introduce a method for multiplying Boolean matrices based on a biclique-based compressed representation that decomposes them into dense bipartite subgraphs, thereby capturing large sets of implicit edges. We first improve the iterative biclique extraction algorithm of Hernández and Navarro by introducing percentile-based parameter adaptation that dynamically adjusts its parameters according to the degree distribution, enhancing both extraction efficiency and compression ratio. We then extend the Schoor multiplication algorithm to operate directly on biclique-encoded matrices, thereby enabling a compositional form of multiplication where the output can also be represented as a collection of bicliques. Our experimental results on large real-world web and social graphs show that our approach achieves substantial reductions in space and computation time with respect to CSR/CSC-based representations. For example, using biclique extraction just as a tool to speed up multiplication (but retaining the CSR/CSC format) yields up to 34-fold speedups. Further, using the biclique-based representation for input and output yields up to a 10-fold reduction in space and up to a 290-fold speedup for matrix multiplication. These results demonstrate that our representation based on bicliques is both space- and time-effective to support an algebra of Boolean matrices.Authors: Philip Bille, Inge Li Gørtz, Rikke Jessen, Jingxun Li, Simon Rumle Tarnow, Renfei Zhou
We show that there is a logarithmic separation between LZ77 and LZ-End, and between LZ77 and grammar compression.Authors: Siyue Liu, Taihei Oki, Chao Xu
Let $M$ be a matroid, let $\ell:E(M)\to G$ be a labeling of its elements by an abelian group, and let $F\subseteq G$ be finite. A base is $F$-avoiding if the label sum of its elements is not in $F$. We prove that, for arbitrary costs, a min-cost $F$-avoiding base can be obtained from any min-cost base using at most $|F|$ exchanges. This resolves the weighted proximity conjecture by Hörsch, Imolay, Mizutani, Oki, and Schwarcz. Our main technical tool is to replace the assumption of Schrijver--Seymour Conjecture in Liu and Xu's earlier work with Kemperman--Scherk Theorem. The proximity theorem combined with approaches in earlier work gives an FPT algorithm that finds a min-cost $F$-avoiding base parameterized by $|G|$. We additionally give an FPT algorithm parameterized by $|F|$, answering a question of Hörsch et al.Authors: Benjamin Aram Berendsohn
The selection problem asks to find the $k$-th smallest element in a given set $X$. Its complexity is well-known to be $Θ(|X|)$ for every fixed $k$. We consider the poset selection problem where a partial order $P$ on $X$ is given, and the underlying order of $X$ is guaranteed to be a linear extension of $P$. This generalizes several variants of the selection problem studied before. Our main result is an algorithm that performs $O( k + \operatorname{OPT}(P,k) )$ comparisons, where $\operatorname{OPT}(P,k)$ is the minimum number of comparisons required for the input $(P,k)$. If $P$ is a rooted tree, we obtain an $O( \operatorname{OPT} \log (k / \operatorname{OPT}) )$ algorithm, which can be further improved to $O( \operatorname{OPT} \log \log (k/\operatorname{OPT}) )$ or $O( \operatorname{OPT} \log \operatorname{OPT})$ under mild assumptions about $P$. Our algorithms are based on the work of Kaplan, Kozma, Zamir, and Zwick [SOSA 2019], who used Chazelle's soft heaps [J. ACM 2000] to simplify several older results. We introduce a new soft heap variant, the weighted soft heap, which allows greater control over which elements get corrupted.Authors: Niels Inselmann Christiansen, Eva Rotenberg
We consider the problem of maintaining the triconnectivity in some biconnected graph G in the incremental dynamic setting. We consider updates in the form of edge insertions and edge subdivisions, and triconnectivity queries, i.e. queries of the form "are there at least three vertex disjoint paths between a and b?". All algorithms presented in this paper are deterministic. All queries and updates are answered in worst-case $O(\log n)$ time. By combining this result for biconnected graphs with a result of Holm and Rotenberg [SODA'20] we get an algorithm for general graphs with a worst-case running time of $O(\log^2 n)$ per operation. These algorithms represent an improvement of the state-of-the-art by a factor of $O(\log n)$.from Sophie Huiberts
Many colleagues are struggling with The Hiring Question.
For junior folks, The Hiring Question is "what should I do to get a job in the LLM-era." They worry whether they should get in on the roboticized proofs gold rush, and how this interacts with the fear of getting scooped. There is much uncertainty about how journals or hiring committees would value their work, if the committee knew that the applicant didn't come up with their own proofs.
For senior folks, The Hiring Question is the opposite side of this coin. They are unsure how to define research excellence for their institution, leading to uncertainty about how to evaluate candidates. Advisors are also unsure how to help their students.
I am here to tell you, that Europe has solved all these problems. The next meta[1] has already been invented, and once American institutions catch up to this strategy then the career game theory will work itself out to a comfortable place for everyone.
== Three Papers Every respectable institution knows that bibliometrics are cringe. Research assesment cannot be based on counting somebody's number of papers, nor can it be based on seeing which journal or conference those papers appeared in. This is a broadly supported norm, even if some people still struggle. When I have been on hiring committees, there was always some laggard still counting papers and looking at CORE rankings. But when you remind them of the institution's commitment to DORA, these people are quickly embarrassed into silence.
What do we do instead? Every job applicant is asked to attach 3 papers to their application. Often these will be their 3 most prominent papers, though they can also select a subset that best conveys their breadth of work. In any case, these will be 3 papers that the applicant is proud of. These 3 papers are in addition to a CV (including publication list) and research statement.
The committee will look at the attached papers to evaluate the quality of the candidate's past work, and look at the research statement to estimate the quality of their future work. The role of the full publication list is merely to support the case that the candidate has the required experience to credibly execute on their promised future plans.
== The Meta for Institutions
This phenomenon, of a limited number of papers considered for evaluation, is widespread but not universal. In the UK this principle is part of the national evaluation of universities. Both the German granting agency DFG and the Dutch NWO evaluate a candidate's track record based on the few publications they may attach (Europe's ERC counts all the way up to 10). Every hiring committee I have been on has followed the same 3 paper format, but only 1 or 2 jobs that I have applied to did.
We see that the '3 papers only' principle is nowhere near universal. But it is common enough that it shapes your career strategy as an early career researcher. If, as an applicant, you want to have a shot at getting these jobs or grants, then all you care about is your top 3 papers. That is because papers 4 up through infinity do not count.
For institutions, following this evaluation meta allows you to hire responsible researchers at the top of their field. Those backwards institutions who still count papers and venues become less attractive places to work, because nobody wants to live under the leadership of bean counters. Such institutions get a bad reputation and are left to hire the salami-slicers among the talent pool.
== The Meta for Applicants
If you have only 3 papers to show off your skills as a researcher, it would be bad strategy to use 1 of those slots on your ChatGPT weekend project. A paper like that neither demonstrates your capabilities, nor does it illustrate what you spend your time on.
A good paper, one which increases your chances of getting hired, is one that represents a large fraction of your research time, reflects your standard of work, and conveys which subjects you consider interesting enough to spend effort on. In your research statement, you describe what type of work you have done, what you value, and what you plan to do. Your three papers you choose to best support your story.
It is up to the hiring committee to then look at everyone's stories, including the implicit or explicit messages about LLM use, and select applicants based on the committee's priorities. That is where pluralism reigns: there are no priorities that all scientists or all committees would agree. As Feyerabend would say, 'anything goes.' Focus on presenting yourself in a way that you are proud of, and by applying to jobs you will eventually find employment and colleagues that mesh with how you approach mathematical work.
== Why is This Good?
In the age of robots, the European meta is more desireable than ever before. The game theory for junior researchers is clear: any time you spend effort on a new paper, it should at least beat your 3rd best ever paper in quality. This encourages slow science and careful work, discouraging minimum-publishable-units and other degrading practices.
Under the three-paper meta there is no incentive to post flag-staking AI slop, even when you fear you may get scooped if you wait. You cannot attach slop to your application, because the hiring committee will actually look at your attached papers.
The three-paper meta has been favored for years already at all respectable institutions. In today's mathematically uncertain times these hiring strategies are more desireable than ever before.
== Conclusion
The three-paper meta already exists, it is prevalent enough that young researchers can build their careers on this. I personally did so. I publish ~1 paper per year and have never worried about pressure to publish more. That strategy has let me build a body of work that I am proud of, and has also led to stable employment. The same has worked for many of my friends and colleagues.
If we wish to reduce the phenomenon of AI slop flag planting, the main thing we need is for the alternative strategy (publishing lots of low-effort papers) to further lose out for young people. Hence, it is high time for bean-counters to step back and let their deparments enter the 21st century.
| [1] | In video game culture, the meta refers to the current dominant strategy for playing. Partly the meta is the current Nash equilibirium, partly it is the current state-of-the-art knowledge of optimal play. A game's meta can evolve based on outside circumstances (rules changes, new content being released) or inside circumstances (new strategies are found and disseminated, new counterplay is found). |
from Scott Aaronson
Someone writing an article for the Israeli press about “people abroad who love Israel but might be worried” emailed me the following questions:
“1. What is something about Israel that you admire/appreciate over the years?
2. What are you worried the most about Israel these days?”
So I replied as follows:
“It’s hard to know where to start with either of your questions! But briefly:
Tiny Israel standing up for itself, against an often hostile and unjust world, is a huge part of what’s given me the self-confidence to stand up for myself in my own life. That was true even before I had visited Israel or spent significant time there, gazed across the desert at the still-clear ruins of the Roman siege of Masada, staggered overwhelmed out of Yad Vashem into the sunlight of Jerusalem, tasted the hummus or pomegranate juice or ice cream with blended fruit, befriended or had academic collaborations with dozens of Israelis, or married an Israeli woman.
My fear is merely the ‘obvious’ one — that, in response to the staggering hostility directed against the ‘Jew among the nations,’ Israel will become more and more belligerent, isolated, and right-wing. It will get demographically overwhelmed by those who don’t want to work or serve in the army, while hundreds of thousands of secular educated Israelis leave. It will be internally divided almost to the point of civil war. It will repudiate the liberal-democratic vision of Herzl and Ben-Gurion, of world-class universities and making the deserts bloom, for the swaggering, theocratic vision of Smotrich and Ben-Gvir, of chasing Palestinians from their olive groves. It will become more and more like the hateful caricature of itself that the anti-Israel people in the West always imagined. And then, having been internally weakened in all of these ways, it will finally be destroyed by its external enemies, who will never have rested the whole time, who never once wavered in their dream of a second Holocaust.
I hope and pray that in the upcoming election, the Israeli voters make optimistic choices that repudiate these fears.”
As I’ll do more and more with political posts, I’m leaving the comments off. Why? Because my remaining life is too short to spend it battling an endless parade of trolls and griefers, leftists and rightists and just nihilists, who might or might not be AI.
(Lance and Bill did a vidcast about the OpenAI Document Drop. See here. My spellcheck thinks that vidcast and OpenAI are not words.)
The Metric TSP problem is TSP where, for all vertices \(x,y,z\),
\(w(x,z) \le w(x,y) + w(y,z) \).
In 1976 Christofides and Serdyukov (independently of each other) showed that there is a poly time algorithm for a 1.5-approx to Metric TSP.
Some people thought the 1.5 could be improved.
Some people thought that 1.5 is optimal.
1.5 is a natural number. Hmm, that's not quite right. 1.5 is a pretty number. It would not be a surprise if someone had proven
If there is a poly time (\(1.5-\epsilon\)) approx then P=NP.
Indeed, people tried to prove that.
In 2020 Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan proved
there is a poly time (\(1.5-\frac{1}{10^{36}}\)) approximation algorithm.
Darling thinks this result is hilarious. I tried to tell her that the result is important since
a) We now know that 1.5 is NOT optimal.
b) One of the authors, Nathan Klein, had been in my REU program in 2015.
c) The arxiv version has one author using their middle initial, one author doing nothing for their middle name, and one author spelling out their entire middle name. I think that's unusual.
She was not impressed.
Nobody believes that \(1.5-\frac{1}{10^{36}}\) is optimal.
Is there a current conjecture? Klein told me he thinks 4/3. A pretty number.
The recent results on Matrix Mult and Int Mult give a contrast involving pretty runtime and ugly runtimes.
MATRIX MULT
Let \(\omega\) be the least \(a\) such that two \(n\times n\) matrices can be multiplied together with \(O(n^a)\) operations. This definition is not quite right for two reasons:
(i) It is possible (though I think unlikely) that there is no least \(a\), For example, if there is a sequence of algorithms with runtime \(O(n^{2.1})\), \(O(n^{2.01})\), \(O(n^{2.001})\), \(\ldots\), then there is no least \(a\),
(ii) It is possible (though I thought unlikely before Oct 6, 2026), that the runtime may be different over different fields.
We keep the incorrect definition to prove that ChatGPT is not the boss of me.
Here are some known results. I may have missed some:
The traditional algorithm: \(\omega\le 3\).
Strassen's Algorithm (1969): \(\omega\le \log_2 7 = 2.807\ldots \).
Coppersmith-Winograd (1990): \(\omega \le 2.376\ldots \).
Stothers (2010): \(\omega \le 2.3736\ldots\).
V.V. Williams (2012): \(\omega \le 2.3728642\ldots \). (Stothers and V.V. Williams were independent.)By gasarch
(Lance and Bill did a vidcast about the OpenAI Document Drop. See here. My spellcheck thinks that vidcast and OpenAI are not words.)
The Metric TSP problem is TSP where, for all vertices \(x,y,z\),
\(w(x,z) \le w(x,y) + w(y,z) \).
In 1976 Christofides and Serdyukov (independently of each other) showed that there is a poly time algorithm for a 1.5-approx to Metric TSP.
Some people thought the 1.5 could be improved.
Some people thought that 1.5 is optimal.
1.5 is a natural number. Hmm, that's not quite right. 1.5 is a pretty number. It would not be a surprise if someone had proven
If there is a poly time (\(1.5-\epsilon\)) approx then P=NP.
Indeed, people tried to prove that.
In 2020 Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan proved
there is a poly time (\(1.5-\frac{1}{10^{36}}\)) approximation algorithm.
Darling thinks this result is hilarious. I tried to tell her that the result is important since
a) We now know that 1.5 is NOT optimal.
b) One of the authors, Nathan Klein, had been in my REU program in 2015.
c) The arxiv version has one author using their middle initial, one author doing nothing for their middle name, and one author spelling out their entire middle name. I think that's unusual.
She was not impressed.
Nobody believes that \(1.5-\frac{1}{10^{36}}\) is optimal.
Is there a current conjecture? Klein told me he thinks 4/3. A pretty number.
The recent results on Matrix Mult and Int Mult give a contrast involving pretty runtime and ugly runtimes.
MATRIX MULT
Let \(\omega\) be the least \(a\) such that two \(n\times n\) matrices can be multiplied together with \(O(n^a)\) operations. This definition is not quite right for two reasons:
(i) It is possible (though I think unlikely) that there is no least \(a\), For example, if there is a sequence of algorithms with runtime \(O(n^{2.1})\), \(O(n^{2.01})\), \(O(n^{2.001})\), \(\ldots\), then there is no least \(a\),
(ii) It is possible (though I thought unlikely before Oct 6, 2026), that the runtime may be different over different fields.
We keep the incorrect definition to prove that ChatGPT is not the boss of me.
Here are some known results. I may have missed some:
The traditional algorithm: \(\omega\le 3\).
Strassen's Algorithm (1969): \(\omega\le \log_2 7 = 2.807\ldots \).
Coppersmith-Winograd (1990): \(\omega \le 2.376\ldots \).
Stothers (2010): \(\omega \le 2.3736\ldots\).
from ECCC Papers
from ECCC Papers
from ECCC Papers
from ECCC Papers
from CCI: jobs
The George R. Brown School of Engineering and Computing at Rice University in Houston, Texas, invites applications for one open-rank faculty position in foundational artificial intelligence. We seek candidates who advance the statistical, mathematical, computational, or algorithmic foundations of artificial intelligence (AI) and scientific machine learning.
Website: https://apply.interfolio.com/195687
Email: maryama@rice.edu
from ECCC Papers
from Gil Kalai
Michael O. Rabin 1931-2026
There is a lot of academic activity in the week of October 25-29, 2026, and on Tuesday, October 27, 2026 we have the Israeli general elections. Let me encourage all my Israeli friends and readers to vote!
Here is a partial list of activities. (Please add more in comments, or private emails.)
Mathematicsfrom CCI: jobs
I invite applications for a postdoc position in complexity theory at Princeton University
Website: https://apply.interfolio.com/191810
Email: ran.raz.mail@gmail.com
from ECCC Papers
from ECCC Papers
from ECCC Papers
from CS Theory Events
By shacharlovett
Please join us for a one-day workshop, “Recent advances in Regularity Lemmas (with and without calibration)”, taking place on Tuesday, November 17 at Stanford University.
There has been a lot of exciting recent work connecting regularity lemmas to multiaccuracy and multicalibration, with applications across complexity theory, cryptography, learning theory, and communication complexity, among other areas. The workshop will feature talks on some of these advances and provide an opportunity to discuss new results and open questions.
You can attend either in person or online. To register and see the program, please visit: https://regularitylemmas.github.io/.
We hope to see you there!
Best,
Sílvia Casacuberta, Parikshit Gopalan, Nika Haghtalab, Omer Reingold, and Salil Vadhan
By Yuval Efron, Jovan Komatovic, Ling Ren
Authors: Alexander Meiburg
Does computing a composition of total Boolean functions require the product of the randomized query complexities of its factors? We give a negative answer. There are families of total functions $f,g$ such that $R(f\circ g) =Θ\!\left(\frac1{\log R(g)}\right)R(f)R(g)$ This result requires first separating linearized query complexity $\LR$, as well as noisy randomized query complexity $noisyR$, from standard randomized query complexity $R$. Both constructions essentially come from totalizing existing partial function separations, albeit via different techniques. By adapting these techniques, we also construct total functions separating every adjacent pair in the chain from sabotage $RS$, max-conflict $\barχ$, and linearised query complexity $LR$. We show that AND-of-ORs separates conflict $χ$ from max-conflict $\barχ$ complexity and makes conflict and sabotage incomparable. Finally, randomized complexity can be smaller than its composition limit $R^*$ by the maximal factor $Θ(\log R)$. The total--total composition separation is also formalized in Lean.Authors: Mark Braverman, Dor Minzer
In a $k$-XOR game $Ψ$ over $\mathbb{F}_p$, a verifier samples challenges $(x_1,\ldots,x_k)\simμ$ where $μ$ is a distribution over $Σ_1\times\ldots\times Σ_k$, sends $x_i$ to player $i$ and receives an answer $f_i(x_i)\in\mathbb{F}_p$, and accepts if and only if $f_1(x_1)+\ldots+f_k(x_k)=t(x_1,\ldots,x_k)$, where $t\colon Σ_1\times\ldots\times Σ_k\to\mathbb{F}_p$ is a fixed map. We show that if $Ψ$ has value strictly less than $1$, then the value of the $n$-fold repeated game $Ψ^{\otimes n}$ is at most $2^{-cn}$ where $c = c(Ψ)>0$ is a fixed constant. This extends a previous result of [Bhangale-Braverman-Khot-Liu-Minzer] showing exponential decay for some $3$-XOR games. Our proof uses a relaxation of the value of games studied in the quantum setting, called the commuting value of a game. We show a transformation that maps a $k$-player game $Ψ$ with value strictly less than $1$ to a $2k$-player game $Ψ'$ with commuting value less than $1$, such that $\mathsf{val}(Ψ^{\otimes n})\leq \mathsf{val}((Ψ')^{\otimes n})$. We prove that $\mathsf{val}(Ψ')<1$ has a direct proof using nothing more than the Cauchy-Schwarz inequality, which we are able to tensorize to get that $\mathsf{val}((Ψ')^{\otimes n})$ vanishes exponentially fast in $n$.Authors: Matthew Blake, Firas A. Khasawneh
Fundamental to the field of topological signal processing (TSP) is the \textit{persistence diagram} (PD), or barcode, of a signal, which gives noise-resistant measures of topologically significant features as distinct from noise. Existing literature proves that the total persistence computed from these diagrams is equal to the total variation, for certain continuous signals on compact domains. We provide a closed formula for this shared quantity, and generalize to all continuous and discrete functions on bounded domains, and to certain functions on non-compact 1D manifolds. Extending the identification of continuous and discrete persistence, we investigate the similarities of functions with the same PDs, and prove that, for any $n$, the persistence diagram can be calculated as a function of the sequence of critical values; we compute these formulas for $n \leq 6$. Finally, we examine which function transformations cause predictable changes in the PD of the transformed function, characterizing affine and linear transformations.Authors: Raghuwansh Raj, George Panagopoulos, Jun Pang
Topological deep learning (TDL) architectures are typically evaluated on synthetic complex pairs that differ in a target invariant. Yet, whether a model recovers that invariant or an artifact of the chosen discretization is seldom audited. To examine this, we design and test pairs of complexes that look identical to standard homological and local message-passing tests, have the same Hasse graphs, yet differ in the target invariant. We study two beyond-homology regimes: nonAbelian fundamental-group structure and homotopy-matched orientability. For the former, we construct genus-2 pairs that match homology, cell statistics, local incidence profiles, and rank-colored Hasse 1-WL behavior while differing in their fundamental groups. For the latter, we evaluate punctured torus-Klein bottle pairs and show that distance, boundary, cycle, and spectral signals can confound apparent orientability detection, motivating stronger matched controls. Under the tested settings, subcomplex-lifted architectures separate some pairs beyond the matched homological, local-incidence, and Hasse 1-WL controls, while a depth sweep reveals an empirical depth-dependent trend without establishing a general barrier or direct computation of the target invariants. These results show that claims of topological expressivity must be stated relative to the model representation, explicitly controlled information channels, and the precise scope of the benchmark.Authors: Robin Belton, Patrick Schnider
The Mapper algorithm is a popular graphical tool for data visualization and exploration in topological data analysis (TDA). It takes as input a data set $X$ and returns a graph that aims to capture the underlying topological features of these data. The Mapper algorithm has several parameters that need to be specified by the user: a $\textit{filter function}$ $f:X\to Y$ where $X$ is often a point cloud data set in $\mathbb{R}^n$ and $Y$ is the $\textit{reference space}$ that is often a lower dimensional Euclidean space, a $\textit{cover}$ of $f(X)$, and a $\textit{clustering algorithm}$ that is applied to the pre-image of each element in the cover. In this paper, we consider the following question: What graphs can occur as the output of the Mapper algorithm? It is known that when $Y=\mathbb{R}^3$, any graph can be a Mapper graph. In this work, we focus on a more practical case where the filter function is $f:\mathbb{R}^2\to\mathbb{R}$. We consider two different scenarios. In the first scenario, we fix the parameters of the Mapper algorithm, but vary the data. This way we characterize exactly the graphs that can occur for several choices of parameters. In the second scenario, we fix the data set but vary the parameters. This can be seen as a way to understand how much the output can differ depending on the choices of parameters.In both settings, we find close connections to classical topics in graph drawing.Authors: Chandra Kanta Mohapatra
Let $\F$ be a finite field. Given $N$ distinct points $\bmα_1,\ldots,\bmα_N \in \F^m$ and associated values $β_1,\ldots,β_N \in \F$, we study the problem of computing an $m$-variate polynomial $f(\vy) \in \F[\vy]$ of individual degree less than $d$, with $d^m \ge N$, that satisfies $f(\bmα_i)=β_i$ for all $i\in[N]$, whenever such an $f$ exists. This is known as the\textit{ multivariate polynomial interpolation} problem. In this work, given $N=d^m$, we present a deterministic algorithm for multivariate polynomial interpolation over an arbitrary finite field $\F$ that runs in near-quadratic time $N^{2+o(1)}\poly(m,d,\log|\F|)$, assuming $d$ is $ω(1)$. This bound holds whenever the associated \emph{multivariate Vandermonde} matrix is nonsingular, has constant co-rank, or admits some special structure. In the general case, we give a randomized Las Vegas algorithm attaining the same near-quadratic running time, provided the finite field is sufficiently large and $d$ grows similar to the previous case. Unlike other multivariate interpolation strategies, we do not assume black-box access to the polynomial. In particular, we are not permitted to query arbitrary input points to obtain their evaluations. Our interpolation result follows by combining Wiedemann's classical approach~\cite{w86} for solving sparse linear systems with known bounds for fast \emph{multivariate multipoint evaluation} over finite fields~\cite{umans08, KU11, BGKM23, BGGKU24}. Specifically, our deterministic interpolation strategy relies on a deterministic variant of Wiedemann's approach, which is more commonly used in the randomized setting.Authors: Amir Carmel, Robert Krauthgamer
Data summarization techniques, such as coresets, are essential for scaling clustering algorithms to massive datasets. We study uniform sampling, which is an extremely simple and ultra-efficient method to construct coresets, in the context of weak, stable, and strong coresets for the $k$-means problem in Hilbert space. We begin with the fundamental case $k=1$, and establish matching upper and lower bounds on the sample complexity of stable and weak coresets, finding that the two notions require different sample complexities. As a consequence, we obtain tight bounds for stable $1$-median coresets in $\ell_1$ and $\ell_2$ (and thus also Kendall--tau and Jaccard metrics), removing the dimension dependence of Carmel and Krauthgamer (ICLR 2026). Our analysis is substantially simpler than prior work and reduces to bounding the deviation of the sample mean. For the general $k$-means problem on $ρ$-separated instances, a well-studied structural assumption on the input, we show that uniform sampling yields a stable coreset for all $O(1)$-approximate solutions, and a strong coreset if the instance additionally has bounded kurtosis. In all these results, the sample complexity is independent of the dimension and the instance size.Authors: Gautam Kamath, Mahbod Majid, Ankur Moitra, Argyris Mouzakis, Jonathan Ullman
We study learning a discrete distribution under person-level differential privacy in the batched setting. Given $n$ users, each contributing $m$ i.i.d. samples from an unknown distribution $μ$ over $[k]$, we seek an estimate of $μ$ with total-variation error $α$. We give polynomial-time algorithms under both pure and approximate differential privacy. Under pure $(\varepsilon,0)$-DP, we achieve $n = \widetilde O(k/(α^2 m)+k/(α\sqrt{m}\varepsilon)+k/\varepsilon)$, the first polynomial-time pure-DP guarantee matching the information-theoretic optimum up to logarithmic factors. Under approximate $(\varepsilon,δ)$-DP, we achieve $n = \widetilde O(k/(α^2 m)+k/(α\sqrt{m}\varepsilon)+k+\log(1/δ)/\varepsilon)$. At $δ=2^{-Θ(k)}$, this is $\widetilde O(k)$ for fixed $α,\varepsilon,m$ and failure probability. Our algorithms use a new degree-6 sum-of-squares estimator for learning from untrusted batches. Its key ingredient is a trace-bounded diagonal majorizer for the difference between the empirical covariance of the repaired batch averages and the multinomial covariance predicted by their mean. We prove that clean data admit this certificate through semidefinite-programming duality and a new application of the stronger symmetric form of Grothendieck's inequality due to Friedland and Lim. The certificate preserves the mean-dependent variance of multinomial batch averages, yielding the near-optimal robust rate $O(η\sqrt{\log(1/η)/m})$ and providing the score required by the privacy reduction. We also prove a statistical query lower bound ruling out a uniformly smaller order of error under fixed polynomial SQ resource bounds.Authors: Sophia Heimann, Hung P. Hoang, Stefan Hougardy
We prove the all-exp property for the Traveling Salesman Problem with the $2$-opt neighborhood, and for $(3,2,2)$- and $(2,3,2)$-Maximum Constraint Assignment with the flip neighborhood. The all-exp property states that infinitely many instances have an initial solution from which every sequence of improving moves to a local optimum, and hence every run of local search, has exponential length. For the Traveling Salesman Problem, the all-exp property was previously known for every $k$-opt neighborhood with $k \ge 3$, so our result for $2$-opt completes the picture for all $k$-kopt neighborhoods. In $(p,q,r)$-Maximum Constraint Assignment, each constraint involves at most $p$ variables, each variable occurs in at most $q$ constraints, and each domain has size $r$. Decreasing any of the parameters of $(3,2,2)$ or $(2,3,2)$ yields a problem in which every sequence of improving flips has polynomial length, so both Maximum Constraint Assignment results are tight. All three results settle long-standing open problems. Our proofs build on a common construction idea, which reveals a close connection between the local-search dynamics of the three problems.Authors: Jackson Bibbens, Adam Lechowicz, Nicolas Christianson, Bo Sun, Mohammad Hajiesmaili
We introduce peak-aware one-way trading ($\texttt{PA-OWT}$), an online problem in which a player must purchase a fixed quantity of an asset by a deadline, minimizing its total cost plus a charge proportional to the largest single purchase at any time. The model is motivated by electricity procurement, where the cost of energy rewards buying at low prices, but peak demand charges discourage concentrating purchases in short periods. Balancing these incentives is challenging when future prices are unknown: a large purchase can establish a peak that later decisions cannot undo. We develop a peak-aware online algorithm that balances price and peak control with deadline feasibility and achieves the order-optimal competitive ratio. We further extend our results to a learning-augmented algorithm that uses predictions of optimal purchasing decisions to achieve an order-optimal consistency-robustness tradeoff, exploiting accurate advice while retaining worst-case guarantees in the face of arbitrary prediction errors. Finally, we evaluate our algorithms in a case study on electricity procurement using historical electricity price traces to understand the benefits of peak-aware purchasing.Authors: Gabriel Marques Domingues, Claire Mathieu, Boaz Patt-Shamir
We study the aggregation task (convergecast) in networks in the case that the values to be aggregated do not fit in a single message. We assume that every node starts with an input value, and there is an aggregation operator that is commutative, associative, and length-preserving, i.e., the result of aggregating two values has the same length as each of the input values. Since values do not fit in a message, they are transferred in a ``train'' of pipelined messages, which must be terminated whenever we want to aggregate values. The goal is to minimize the makespan time of aggregating all values. We present general lower bounds on the problem and optimal algorithms for several prevalent parallel computing architectures, including the hypercube and complete bipartite graphs, under both the splittable and unsplittable flows models. We also present an $O(\log n)$ approximation for general graphs in the unsplittable flows model.Authors: Yuhao Guo, Seth Pettie, Chengzhang Wan
We consider the class of open addressing hash tables that uses a fixed offset sequence $r_0,r_1,\ldots,r_{n-1}$ to find an open slot in the table. As special cases this subsumes linear probing ($r_i=i$) and quadratic probing ($r_i=i^2$). We give a simple analysis that the expected insertion time when the load factor is $1-ε$ is $O(ε^{-2})$. This bound is tight for linear probing (but not for quadratic probing), so the analysis cannot be improved at this level of generality.Authors: Philip Bille, Inge Li Gørtz, Christoffer Krogh, Christian Møller Mikkelstrup
The delayed deterministic finite automaton ($\text{D}^2\text{FA}$) is a powerful tool for compressing the prohibitively large deterministic finite automata (DFAs) used in modern signature-based deep packet inspection systems. A $\text{D}^2\text{FA}$ augments a DFA with unlabeled default transitions to remove transitions that are similar. This technique works well in practice and has inspired numerous subsequent studies. However, existing approaches do not guarantee a $\text{D}^2\text{FA}$ of optimal size as they restrict the default transitions to form a forest. In this paper, we consider the problem of finding an optimal $\text{D}^2\text{FA}$. We make the key observation that cycles of default transitions can be valid and produce a smaller $\text{D}^2\text{FA}$, provided that for every character in the alphabet, at least one state in the cycle has an outgoing transition labeled by that character. This observation raises fundamental questions concerning the computational complexity of finding an optimal $\text{D}^2\text{FA}$ and the approximation guarantee of the standard (forest-restricted) approach. We answer both questions by showing that it is NP-hard to find an optimal $\text{D}^2\text{FA}$ and by proving that the standard approach provides a $3/2$-approximation to the optimum. To establish NP-hardness, we construct a reduction from set cover using a DFA with gadgets where valid default transition choices correspond to selecting sets. To prove our approximation ratio, we compare the cycles in an optimal solution to a variant where the default transitions form a forest. Finally, we demonstrate that this $3/2$ ratio is tight via a constructed family of DFAs.Authors: Duc A. Hoang
A \emph{proper vertex coloring} assigns colors to vertices so that adjacent vertices have distinct colors. A \emph{Kempe change} in a proper vertex coloring exchanges two colors on one component of the subgraph induced by the vertices of those colors. For a fixed palette of $k$ colors, \textsc{Kempe Reachability} asks whether two given proper vertex colorings of the same graph are connected by a sequence of Kempe changes. This problem is known to be $\mathsf{PSPACE}$-complete for every fixed $k\geq 3$. A graph is \emph{claw-free} if no vertex has three pairwise nonadjacent neighbors. The \emph{line graph} of a graph has one vertex for each edge, with two vertices adjacent exactly when the corresponding edges share an end. Line graphs are claw-free, and their Kempe changes correspond to \emph{edge-Kempe changes} in the original graph, which exchange two colors on one component of the subgraph formed by the edges of those colors. A claw-free graph with a proper $k$-coloring has maximum degree at most $2k-2$, whereas for $k\geq 4$ all proper $k$-colorings of a graph of maximum degree at most $k$ are connected by Kempe changes. We show that, for every fixed $k\geq 3$, \textsc{Kempe Reachability} with $k$ colors is $\mathsf{PSPACE}$-complete even on line graphs of connected simple $k$-regular graphs, and hence even on connected $(2k-2)$-regular claw-free graphs. Equivalently, deciding whether two proper $k$-edge-colorings are connected by edge-Kempe changes is $\mathsf{PSPACE}$-complete even on connected simple $k$-regular graphs. ChatGPT 6 Pro and Claude Fable 5.1 were used to assist with developing and reviewing mathematical arguments and drafting and revising the paper. The author takes full responsibility for the correctness and content of the paper.Authors: Duc A. Hoang
A $k$-path vertex cover ($k$-PVC) of a graph is a set of vertices meeting every path on $k$ vertices. In Token Sliding, one token occupies each vertex of a cover; a move slides one token along an edge to an unoccupied vertex, preserving the cover property. We study whether two covers of a tree are joined by such moves. The case $k=2$ admits a linear-time decision algorithm. For every integer $k\geq2$, we give an $O(kn^2)$-time decision algorithm on trees of order $n$, with $k$ part of the input. Two covers are reachable precisely when their rigid tokens, which never move, occupy the same set and every component remaining after their deletion has the same token count. The proof transforms configurations of equal size without rigid tokens into a canonical configuration built on properly rooted subtrees, whose paths on $k$ vertices pass through their roots. A rooted-subtree recurrence identifies movable candidate tokens. We also give a direct recursive construction between the supplied endpoints, returning at most $8n^2\,3^{\lceil n/2\rceil}$ slides in $O(n^{10}3^{n/2})$ time. ChatGPT 6 Pro and Claude Fable 5.1 were used to assist with developing and reviewing mathematical arguments and drafting and revising the paper. The author takes full responsibility for the correctness and content of the paper.Authors: Jarosław Byrka, Yuhao Guo, Yang Hu, Shi Li, Yongho Shin, Phanu Vajanopath, Chengzhang Wan, Zaixuan Wang
We study the classic $k$-median problem and refine the iterative rounding framework recently introduced by Byrka, Guo, Hu, Li, Wan, and Wang [FOCS'26], which yields a $(2+\varepsilon)$-approximation. Our algorithm opens $k+O(1)$ facilities and achieves an expected connection cost of at most $1.9999$ times the value of the standard LP relaxation. Although the numerical improvement over $2$ is small, it establishes a conceptual result: the integrality gap of the standard relaxation is strictly below $2$ when a constant number of extra facilities is allowed. This partially answers an open question of Li and Svensson [STOC'13]. Combined with their reduction, our result yields a $1.9999$-approximation algorithm for $k$-median. Our approach builds on several technical ingredients. First, we develop a preprocessing routine that makes the LP solution $\mathrm{poly}(\varepsilon)$-integral, at the cost of a $(1+\varepsilon)$ factor in the connection cost and $O(1)$ extra facilities. Unlike the preprocessing of Byrka et al. [FOCS'26], our conversion is unconditional: it requires no special treatment of clients whose fractional facilities are concentrated. Next, we show that the main rounding algorithm can open facilities one at a time, eliminating the batch processing used by Byrka et al. [FOCS'26]. Finally, the improvement over 2 comes from a tighter analysis for clients whose distances from to its facilities are not all equal, and a complementary algorithm for the case in which these distances are nearly uniform.Authors: Timothé Picavet
We study distributed approximation of Minimum Dominating Set in a very general class of sparse graphs, extending near-optimal approximation results from the minor-free setting to bounded expansion. In more detail, for fixed $d$ and $\varepsilon>0$, we give a new deterministic constant-round LOCAL algorithm for Minimum Dominating Set on graphs of maximum average degree at most $d$ and bounded depth-one shallow-minor density. Its approximation ratio is $d+1+\varepsilon$, which is optimal up to $\varepsilon$ for every even integer $d\geq 2$. This improves on the recent results of Amiri and Siebertz by extending beyond proper minor-closed classes. From this algorithm, we derive almost-tight constant-round approximations for a number of graph classes. We get $(7+\varepsilon)$-approximations for planar graphs and graphs of bounded Euler genus, and $(5+\varepsilon)$-approximations for their triangle-free subclasses. This answers the $7+\varepsilon$ question of Wawrzyniak positively, and matches the recent results of Amiri and Siebertz. We also apply our algorithm to classes of bounded queue-number or stack-number, obtaining bounds that are tight up to $\varepsilon$. Additionally, we answer questions of Amiri and Siebertz about improving the dependence of the round complexity on $1/\varepsilon$ and obtaining polynomial local computation for fixed parameters, when comparing the output to the usual domination number.Authors: Deepak Bhati, Pranjal Dutta, Antoine Joux, Mahesh Sreekumar Rajasree, Karol Wegrzycki
The Equal Subset Sum problem asks, given n positive integers bounded by M, to find two distinct non-empty subsets with the same sum. We study this problem in the regime $M = 2^{o(n)}$, where the pigeonhole principle guarantees that a solution exists, and the main challenge is to find one efficiently. A straightforward dynamic-programming algorithm runs in time poly(n).$M$. After a sequence of improvements, the current best algorithm, due to Jin, Williams, and Zhang (ESA 2025), achieves running time poly(n).$M^{1/3}$. In this work, we give the first poly(n).$M^{o(1)}$-time algorithm for Equal Subset Sum in the regime $M = 2^{o(n)}$. We complement this algorithmic result with a tight conditional lower bound showing that any substantial improvement would require a major breakthrough in approximation algorithms for lattice problems, building on recent techniques of Vafa and Vaikuntanathan (STOC 2025). Finally, we show that our techniques yield an asymptotically faster algorithm for the regime when $M = Θ(2^{n})$: a poly(n)$\cdot 2^{n/4}$-time algorithm in the average case.Authors: Junhua Liu, Zhicheng Liang, Zejun Zhang, Langzhou He, Feng Qian
Generative AI assistants are becoming an advertising medium, embedding sponsored content in their answers. This setting departs from classical position auctions in two ways: an ad's click-through rate depends on the passage that hosts it, and because users stop at their first click, earlier ads take clicks from later ones. This competition for clicks makes truthfulness delicate: a higher bid can reshape the allocation and put a competitor ahead of the bidder, reducing the bidder's clicks. Existing mechanisms either attain a constant fraction of the optimal welfare (advertisers' total click value) but are not known to be truthful, or are truthful but their welfare guarantee degrades as the number of passages grows. We achieve both even when the answer and its editorial order are fixed before bidding. Assuming each ad's click-through rate when reached is known and unaffected by omitting other ads, we give a computationally efficient mechanism that is truthful in expectation and attains at least half the optimal welfare under free reordering. Our key idea, click thinning, omits ads at random, showing earlier ads less often so that each ad's overall click probability no longer depends on the order of the ads. Welfare maximization then reduces to a tractable matching problem, and solving it exactly with VCG-style payments makes truthful bidding optimal in expectation. Characterizing the click probabilities that omission can achieve sharpens the approximation factor from $2$ to $2-(1-δ)^{K-1}$ when at most $K$ ads are shown and each click-through rate is at most $δ$. This factor is the best possible for any order-preserving rule, even one that ignores incentives and computation, so truthfulness and computational efficiency incur no additional worst-case loss.Authors: Haoran wang
We study the mixing time of two local Markov chains for uniformly sampling proper edge colorings of trees. For a tree with $n$ vertices and maximum degree $Δ$, we establish optimal mixing-time bounds for the single-edge Glauber dynamics when $q\geΔ+2$ and for the neighboring-edge heat-bath dynamics when $q\geΔ+1$. Both chains mix in $O_Δ(n(\log n+\log(1/\varepsilon)))$ steps, uniformly over the number of colors $q$. These bounds are tight in their dependence on $n$ for fixed $Δ$. Our proof establishes log-Sobolev inequalities through local color release, reusable recoloring buffers, and component entropy mixing. The two dynamics require different local constructions: a two-spare-color buffer for single-edge updates and a second-layer controller for neighboring-edge updates. The resulting entropy analysis applies to general bounded-degree trees, including regimes where worst-case spatial mixing fails.Authors: Hiroyasu Usami
An online tracker retains one state and may reset only to the current observation, although its complete observed history is available. Offline knows the future and obeys the same reset rule. Under a hard discrepancy radius, for every horizon $T\ge5$ and every feasible randomized causal policy, a fixed path on a known five-point metric requires at least $(T+1)/2$ expected refreshes, against exactly two offline refreshes with a strict radius margin. Missing the useful prefix center forces a refresh at every suffix observation. The path visits four values, with resolution fixed as $T$ grows. Write $J_λ$ for cumulative discrepancy plus a charge $λ>0$ per refresh, and $V_T$ for the sum of successive observation distances. A candidate prefix adapts Bienkowski and Schmid's randomized lower bound to this objective under current resets, even with a known horizon and $V_T<3λ$. This construction needs finer grids; a fixed finite metric with positive minimum separation instead admits a competitive policy for penalized tracking. An anytime policy satisfies $J_λ\leλ+4\sqrt{λTV_T}$ without knowing the horizon or final variation. Clipping for a known horizon gives $J_λ\leλT$ and a factor-three comparison with the minimum of three analytical bounds, without knowing final variation. Current-value diameter and readout sensitivity give same-input output bounds for mixtures, including squared-distance softmax.Authors: Li-Hsuan Chen, Florent Foucaud, Ling-Ju Hung, Ralf Klasing, Lucas Lorieau, Peter Rossmanith
We study how covering a graph by a small number of shortest or approximately shortest paths/walks constrains its treewidth and pathwidth. A path or walk is $(α,β)$-quasi-shortest for $α\geq1$ and $β\geq 0$ if each contiguous segment has length at most $α$ times the distance between its endpoints plus $β$. For graphs vertex-covered by $k$ shortest paths, we establish the first known polynomial pathwidth bound of $O(k^3)$. For edge-coverage, we improve the previously known $O(k^4)$ upper bound to $O(k^2\log k)$. As a main ingredient of the proofs, we first show that if the vertices of a graph can be covered by $k$ $(α,β)$-quasi-shortest paths or walks, then its treewidth is $O_{α,β}(k^2)$; this is a consequence of the fact that such graphs have linear metric growth and the technique developed in [Campbell et al., E-JC 2023]. To obtain the above pathwidth upper bounds, we combine this result with techniques from the literature in a nontrivial way. On the other hand, we show that there exist connected bipartite cubic graph whose edges can be covered by $k$ shortest paths and whose pathwidth is $Ω(k\log k)$, providing the first superlinear lower bound. For graphs covered by $k=2$ $(α,0)$-quasi-shortest paths with $α>1$, we show that, unlike treewidth and unlike the case $α=1$ and $β=0$ of exact shortest paths, the pathwidth may be unbounded. Finally, for every fixed rationals $α\geq1$ and $β\geq 0$, we give XP algorithms with a running time of $n^{f(k,α,β)}$ for some function~$f$ that decide whether the vertices of a graph can be covered by at most $k$ $(α,β)$-quasi-shortest paths or walks. The algorithms combine our treewidth upper bounds with an algorithmic meta-theorem from [Dreier et al., LICS 2025]. [abstract shortened to meet the arXiv requirements]Authors: Joseph Seffi Naor, Tomer Tsachor
We study the paging with time windows problem, a natural generalization of classical paging, in which each request must be served within a specified time interval. This model allows the algorithm to delay service and batch service requests over time, but also introduces significant challenges due to overlapping requests. While the problem is well understood in the unweighted setting, where optimal $O(\log k)$-competitive algorithms are known, the weighted case remains more elusive. The best previously known algorithm, due to Gupta, Kumar, and Panigrahi, achieves an $O(\log k \log n)$-competitive ratio, leaving a gap between weighted and unweighted settings. We obtain an $O(\log k)$-competitive algorithm for weighted paging with time windows, matching the optimal competitive ratio. The core of our approach is a structural decomposition that separates the evolution of the cache from the scheduling of page loads. We show that, given a sequence of cache configurations, computing a near-optimal sequence of page loads reduces to a variant of the Joint Replenishment Problem with deadlines (JRP-D) with time-dependent opening costs. We design a constant-competitive online algorithm for this variant and prove that the reduction is tight. Combining this with an existing online construction of cache configurations yields the desired bound.Authors: Haotian Tang
Phylogenetic distance deconvolution represents mixture-to-reference distances by weighted sources placed on a reference tree. We study the minimum number of strictly interior sources that explains a distance profile, and what incomplete references cost. On a positive-rational reduced tree we give an exact algorithm with 2^O(K) poly(B) bit complexity for a free positive mean pendant and any nonempty set of observed leaves. With arbitrary missing references and a prescribed pendant the problem is W[1]-hard in the source budget K, even on positive binary trees supplied with a strict explanation using at most K+1 sources. We then use the algorithm as an instrument. Removing references can only lower the minimum source count, never raise it. The direction is a theorem at every error tolerance and held without exception in 23,545 draws, so which references are missing matters more than how many. Two adversarially chosen references suffice, at the median, to destroy uniqueness of the minimum explanation, and that number does not grow with panel size (Spearman 0.203, p = 0.15, over 20 to 353 references) where random loss scales linearly. Discarding 7,931 of 10,575 references from a real 16S panel at random costs 1.8% of the tolerance at which one source suffices. Discarding comparably many as whole clades costs 90%. That tolerance needs neither ground truth nor an error model, which makes the model measurable on real data. Published distance estimates exceed it in 296 of 296 cases. The mixture inferred by the published heuristic reproduces real observations better than the configuration that generated them in 282 of 296. The phenomenon is not unobservable in practice. It is unobservable through a point estimate of the count. Methods for this problem should report the tolerance at which an explanation of a given size exists.from Emanuele Viola
It will be better and faster than anything else out there, and will be trained and maintained by each of us. All the prompts will be public, and access will be shared equally among the community. It will be a most ambitious research project, like mapping the genome, particle colliders, or space telescopes. We will use it to solve the greatest mysteries in math, like the P vs NP problem. It should be funded at the government level and work on it should start immediately. The project will attract the brightest scientists from all over the world, and make us a beacon for progress.
Otherwise, it is not going to be fun to do astronomy if someone else has a better telescope.
from Ben Recht
Hi there, argmin readers! Today’s post is a live blog of Class 14 of my graduate seminar “Forecasting: A Critical Retrospective,” turning to the less controversial subject of public opinion polling. The syllabus and list of past posts are here.
Our next two units on forecasting focus on forecasting societal behavior, and to do that we first need to talk about how we measure properties of society. One of those main measurements is surveys. Today, I want to describe some techniques survey designers use to avoid ever having to interact with actual people.
Let’s start with the basics.1 Let’s say you want to measure some property of a population, like what percentage of dentists recommend chewing sugarless gum. You can’t ask all of the dentists, so you gather a random sample and then extrapolate the fraction in the sample to represent the fraction in the broader population of dentists.
The main idea of why this is reasonable is simple. If you gathered a true random subset of a population of people and asked them a yes-or-no question, then the average of the answers in the sample would most of the time be very close to the average in the population. You can even quantify how close. The expected gap between the sample average and the population average is nearly independent of the population size and mostly a function of the sample size. This gap is inversely proportional to the square root of the sample size, so if you want to estimate the fraction of a population that answers yes to some question, you can get a “margin of error” of a few percentage points with a few hundred people.
This is a colloquial description of the weak law of large numbers. It often feels miraculous. You can get a good estimate of an average with 600 samples no matter how large the population is. But that margin of error is only true if you have a truly random sample. Unfortunately, when you’re harassing people to answer your annoying surveys, you never get a truly random sample! Not everyone will talk to a pollster, and not everyone is reachable in the first place.
So the data that surveyors gather is a mix of randomness, convenience, and population predilections. You can’t just average the responses and hope for the best. Without a truly random sample, that average will be biased. Fortunately or unfortunately, statisticians have spent decades finding clever ways to use math to patch up social scientific deficiencies. They don’t let people’s actual behavior get in the way of a good time!
One idea is to use post-stratification to recalibrate your survey. The idea behind post-stratification is that once you have a fine enough demographic coarse-graining of people, there are no systematic biases in reporting. There are many justifications for this assumption, but more or less it assumes that within each demographic unit, respondents vote like nonrespondents.2 If this is true, you can weight the respondents in your sample by their demographic proportion in the population and combine them into a new estimate that is unbiased, assuming your model relating demography and human behavior is correct. My friends Avi, Eli, and Erin wrote a clear introduction to how this is done in practice and what assumptions have to hold for this reweighting to be unbiased.
Now those demographic weights themselves are also hard to come by. First, you need an accurate census to guess the fraction of the population that belongs to each demographic cell. This creates a problem of turtles all the way down, because it requires doing censuses that have similar response and bias issues. Second, you need to be sure that you actually sample someone from every demographic stratum in your survey. That is almost never true.
So what you do instead is fit the weights in your sample using a statistical prediction model. There are many dark-art techniques to do this, each with its own ornate justifications. Fitting the weights gives modelers a lot of degrees of freedom. Pollsters are now using their own internal models to weight their numbers. Different models can cause swings in estimates far outside the “margin of error” reported with the poll.
This is only one way statistical prediction blurs into statistical sampling. Indeed, you can lower the variance of your survey with a good prediction. In classical survey calibration, you combine your model’s guess of the outcome with the estimated deviation from that model in your survey sample. In this paradigm, if you really believe in your prediction model, you can throw the survey correction out altogether.
If you want to boost your confidence, you can even combine these two prediction techniques. Statisticians hilariously call this “doubly robust.” If the model that predicts poll answers from demographics is correct, the term that depends on the sample data will be small and not mess up your prediction. If the model that predicts who will be in the sample based on demographics is correct, this will cancel out the effect of the answer-predicting function. Unfortunately, some guy told me that all models were wrong. In that case, there are no guarantees.
Regardless, my point here is to show how statistical modeling can replace statistical sampling. As more and more people refuse to answer polls, these statistical models end up replacing talking to people. In practice, surveys become more about what experts believe about society than what society actually is. Many of these experts seem to believe that they can forecast human behavior without ever observing humans.
I debated putting all the equations here, but I try to keep this blog as equation-free as possible. I will do it if enough of you bug me in the comments.
Statisticians, don’t @ me for oversimplifying your weird assumptions about how people behave.
from ECCC Papers
Authors: Inhyuk Park, Chenglin Fan
We show that for all polynomials $T$ and $b$, every relation in NTIME($T$) has a binary PCP with $O(1)$ non-adaptive queries, perfect completeness, soundness error 1/2 and length $(T+b)\cdot(\log(T+b))^{O(1)}$, which is perfect zero knowledge against every adaptive, possibly malicious verifier making at most $b$ queries. This improves the length $\tilde O(T+b^2)$ of Zeilberger, O'Connor, Gur and Spooner (2026), who observed that Dinur's gap amplification preserves zero knowledge. The simulator runs in expected polynomial time (or in strict polynomial time, with a failure symbol or with negligible statistical error). For $b\le T$ the length is $T\cdot\mathrm{polylog}\,T$, the form of the shortest known constant-query PCPs without zero knowledge. Unless NP $\subseteq$ BPP, the dependence on $b$ is optimal up to the polylogarithmic factor for polynomial-time simulators: zero knowledge is free up to linear query bounds. Zero-knowledge interactive oracle proofs achieved length $\tilde O(T+b)$ in 2016-17; we obtain it for PCPs. Gur, O'Connor and Spooner (STOC 2025) asked whether NP has such PCPs of quasilinear length (their Open Problem 1). This paper answers it for every polynomial query bound, with the simulators above in place of a strict polynomial-time perfect simulator. The proofs were developed with extensive AI assistance and have been checked by the authors. We mask the Reed-Solomon proof of proximity of Ben-Sasson and Sudan at every node of its recursion. By a locator lemma, at every node, whatever $k$ of its proof symbols reveal about its input is determined by $O(k)$ input values. We prove it with the coprime-order argument of Bafna and Vyas (2026); our treatment of domain points is new. Dinur's gap amplification gives constant query complexity. The query count and the polylogarithmic exponent are absolute but very large.Authors: Arman Adibi, Piotr Krysta
We characterize the minimax sample complexity of estimating Rényi entropy from independent samples on an alphabet of size at most $k$, when the known order $α>1$ may vary with $k$. For every fixed additive accuracy $\varepsilon\in(0,1/2)$ and success probability $2/3$, we prove matching bounds with constants independent of $k$ and $α$. For $1<α<\log k$, the rate is $Θ_\varepsilon(αk^{1-1/α}X_α(k,\varepsilon))$, where a monotone scalar inequality defines $X_α$ at noninteger orders. The bounds remain uniform as the order approaches one or an integer, or grows with the alphabet. Integer orders below $\log k$ have rate $Θ_\varepsilon(αk^{1-1/α})$; orders at least $\log k$ and min-entropy have rate $Θ_\varepsilon(k\log k)$. We extend the analysis to logarithms of positive additive functionals. For every fixed continuous $f$ satisfying $f(0)=0$, $f(x)>0$ for $x>0$, and $f(x)\sim ax^r$ at zero, with $a>0$ and $r>1$, estimating $-β^{-1}\log\sum_i f(p_i)$ at fixed accuracy, for fixed $β>0$, has sample complexity $Θ(k^{1-1/r})$ for integer $r$ and $Θ(k/\log k)$ otherwise. A replication reduction preserves the sampling experiment and transfers the rates for powers. Smooth flat functions show that regularity alone does not determine the complexity. The upper bound combines polynomial approximation, Gamma count statistics, and an independent pilot, with a global affine correction near order one. The lower bound uses interpolation to construct positive mean-one priors and controls their distinguishability and entropy separation after normalization. Exact count-variance identities and weighted approximation duality connect the two arguments.Authors: Ashkan Soleymani, Gabriele Farina
We give an algorithm for computing an $\eps$-approximate fixed point of any $d$-dimensional nonexpansion with respect to the $\ell_\infty$ norm in time $\log(1/\eps)^{O(\log^2 d)}$. At its core, our method uses a boosting argument to geometrically shrink a search region. Among other consequences, our algorithm implies that simple stochastic games can be solved in quasipolynomial time.Authors: Alimzhan Amanov, Maxim van den Berg, Jeroen Zuiddam
We give an exposition of OpenAI's recent proof that the exponent $ω_\mathbb{C}$ of matrix multiplication over the complex numbers satisfies $ω_\mathbb{C}\leq9/4$. Our version of the proof gives $ω_\mathbb{F}\leq9/4$ over every field $\mathbb{F}$. We also treat the rectangular matrix multiplication exponent $ω_\mathbb{F}(a,b,c)$. Here we have $ω_\mathbb{F}(1,k,1)=2$ for $0\leq k\leq1/2$ and $ω_\mathbb{F}(1,k,1)\leq1+k+1/(4k)$ for $k\geq1/2$, and, for real numbers $a\geq b\geq c\geq0$, $ω_\mathbb{F}(a,b,c)=a+b$ if $c(a+b)\leq ab$ and $ω_\mathbb{F}(a,b,c)\leq(a+b+c)/2+(ab/c+ac/b+bc/a)/4$ otherwise. Our exposition is in the language of degeneration inequalities among polynomial multiplication tensors and Strassen's asymptotic spectrum duality. We moreover prove an operational barrier (which can be thought of as coming from an operational asymptotic spectrum) showing that the current analysis of all these upper bounds on $ω_\mathbb{F}$ and $ω_\mathbb{F}(a,b,c)$ is optimal and that in fact the current degeneration ingredients cannot improve the bounds.Authors: Chengu Wang
We prove that the randomized communication complexity of Vector-in-Subspace in $\mathbb R^n$ with error at most $1/3$ is $Θ(\sqrt n)$. Alice holds a unit vector $u$ and Bob holds an $n/2$-dimensional subspace $H$; they must distinguish $u\in H$ from $u\in H^\perp$. An exact one-way quantum protocol uses $O(\log n)$ qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's $O(\sqrt n)$ upper bound, improves the $Ω(n^{1/3})$ lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's $Ω(\sqrt n)$ result. The proof establishes a Gaussian moment bound over complete rectangle partitions. A complex Gaussian representation yields a vanishing even moment whose cancellation is preserved when averaging over the partition. We control the signed conditional moments around a real center by decomposing conditional Gaussian measures into fixed coordinates and sub-Gaussian components. Combining this estimate with spherical harmonic analysis gives the communication lower bound.Authors: Priyanshu Pant, Ranveer Singh
A graph is called Pfaffian if it admits a Pfaffian orientation. The Pfaffian recognition problem asks whether a given graph is Pfaffian. In 1989, Vazirani and Yannakakis showed that this problem is polynomial time equivalent to testing whether a prescribed orientation is Pfaffian, and that the problem belongs to $\mathsf{coNP}$. The complexity of the problem for general graphs has remained open since then. For bipartite graphs, polynomial time recognition algorithms were obtained by Robertson, Seymour, and Thomas in 1999, and independently by McCuaig in 2004. We show that testing whether a given orientation is Pfaffian can be reduced to polynomial identity testing. This gives a randomized polynomial time algorithm for Pfaffian recognition on general graphs, placing the problem in $\mathsf{coRP}$.Authors: James Fox, Mirela Damian
We study lattice-based collective construction of a target polyomino on the integer grid, where robots place unit square blocks subject to two physical constraints: the partial structure must remain connected at all times, and no placement may create an unfillable one-cell gap. We present a wavefront sweep algorithm that computes a dependency structure satisfying the local conditions required for safe assembly. Given a list of n cells sorted lexicographically by coordinates, the orientation can be computed in O(n) time using O(n) auxiliary space.Authors: Leonid Barenboim, Arnold Filtser, Omrit Filtser, Orr Fischer
The Fréchet distance (also known as the dog-leash distance) is a well-studied and prevalent distance measure for polygonal curves. In this paper we present parallel algorithms for computing the discrete \frechet\ distance between two curves, in both the PRAM and MPC models. For two polygonal curves of length $n$, we show that the distance between them can be computed in the PRAM model in $O(\log n/ σ)$ rounds and $\tilde{O}(n^{2+σ})$ total work for any $0<σ<1$. In the sublinear MPC model with $n^ρ$ space per machine, it can be computed in $O(\log n / ρ^2)$ rounds and $\tilde{O}(n^{2+ρ})$ total space. For $c$-packed curves, we match our bounds to the sequential algorithms, showing that a $(1+\eps)$-approximation of the distance can be computed in the PRAM model in $O(\log{n}+1/σ^3)$ rounds and $\tilde{O}(n^{1+σ})$ total work, and in the sublinear MPC model in $O(1 /ρ^3)$ rounds and $\tilde{O}(n^{1+ρ})$ total space, for any constant $\eps>0$. As part of our algorithms for $c$-packed curves, we also present parallel algorithms for computing curve simplifications, which may be of independent interest.Authors: Ssu-Yuan Lo, Ching-Kai Wang, Kuan-Lun Chen, Hao-Tsung Yang
We address the Diverse Traveling Salesman Problem (D-TSP) that seeks a set of $k$ distinct TSP tours. Each selected tour must not exceed a prescribed multiple of the optimal tour length, while the maximum pairwise Jaccard similarity within the selected set is minimized. This formulation is important for applications requiring both solution quality and fault tolerance, such as logistics planning, robotics, and strategic patrolling. We propose a novel hybrid framework that decomposes D-TSP into a sampling stage and a selection stage. The selection stage is a max-min dispersion problem, for which any approximation better than a factor of two is NP-hard; we therefore focus on the sampling stage. Our contributions are both theoretical and empirical. Theoretically, we give two end-to-end guarantees for the optimal sampling distribution, from two perspectives: including an optimal set in the sampled pool, or having at least $k$ mutually distant tours in the pool. The second reduces the number of samples from exponential to linear in $k$, at the cost of weakening the benchmark from the best $k$ tours to the best $βk$ for some $β> 1$. For practical use, we prove that a pipeline that samples spanning trees and then converts to tours does not hurt the quality of the pool in principle. Empirically, both objectives are learnable, and our experiments not only validate the analysis but also outperform the baselines on both in-distribution and out-of-distribution instances, by a single trained model with no fine-tuning.Authors: John Iacono, Akash Pareek
In STOC 1972, J{ü}rg Nievergelt and Edward M.~Reingold introduced the $BB[α]$-tree, also known as a \emph{weight-balanced} tree, which for any $α\in (0,\frac{1}{2}]$ is a binary search tree where every node with induced subtree size $s$ has children with induced subtree sizes at least $α(s+1)-1$. A new rotation-based binary search tree, the \emph{PopTree}, is introduced. The PopTree stores $n$ elements and is a $BB[\tfrac1{20}]$-tree after the execution of each search and a $BB[\tfrac1{729}]$-tree at all times, notably while rebalancing. For any constant $α$, its performance on search sequences of length $Ω(n \log n)$ is proved to be within a constant factor (which can depend on $α$) of the optimal offline rotation-based binary search tree that maintains the $BB[α]$ balance invariant.Authors: Deepak Bhati, Anubhav Dhar, Pranjal Dutta, Mahesh Sreekumar Rajasree, Karol Węgrzycki
We study Largest Cardinality Subset Sum (LCSS): given $n$ nonnegative integers and a target $t$, compute a subset summing to $t$ with maximum cardinality. We also consider its all-targets version (ATLCSS), which asks for this maximum for every sum $s\in\{1,\ldots,t\}$. The LCSS problem sits squarely between the subset sum and the knapsack problem. A straightforward dynamic-programming algorithm runs in time $O(nt)$ and solves ATLCSS, and using Jin and Bringmann (both in STOC 2024, independent work) $0$-$1$ knapsack results we achieve a $\widetilde{O}(n + a_{\max}^2)$-time deterministic algorithm for LCSS. Our main result is a randomized $\widetilde{O}(n+\sqrt{n}\,t)$-time algorithm for LCSS. Then, we complement this result with a randomized $\widetilde{O}(n+t^{3/2})$-time algorithm for ATLCSS. Together, our two algorithms give a $\widetilde{O}(n+t\min\{\sqrt{n},\sqrt{t}\})$-time algorithm for LCSS. As an application of ATLCSS, we solve the search version of Projection Subset Sum, introduced by Dutta and Rajasree (SYNSAC 2023), in $\widetilde{O}(n+t^{3/2})$ time for every fixed $\ell_p$ norm with $p\geq 1$. For $\ell_1$, we obtain $\widetilde{O}(n+t)$ time, removing the unique-representation assumption required by their algorithm. Both algorithms output an optimal modified vector and a witnessing subset.Authors: Sankardeep Chakraborty, Seungbum Jo
We study labeling schemes for $p \times q$ $Γ$-free binary matrices, which do not contain a submatrix of the form $Γ= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$. We give a labeling scheme that uses $O(\log^2 N)$-bit labels for rows and columns, where $N=p+q$, such that any matrix entry can be determined from the corresponding two labels in constant time in the word RAM model. The worst-case label size matches the counting lower bound up to constant factors. We also show that the entrywise least $Γ$-free supermatrix of an arbitrary $p\times q$ binary matrix, together with its labels, can be constructed in $O(pq)$ time. Our construction represents a $Γ$-free matrix by a sequence of rooted forests, where each column corresponds to a node and the $1$-entries of each row form a root path in its corresponding forest. For $n$-vertex strongly chordal and chordal bipartite graphs, our result gives asymptotically optimal $O(\log^2 n)$-bit adjacency labeling schemes with constant-time queries. These results answer both representation questions posed by Spinrad in 1995.Authors: Sizhe Li, Nicolas Christianson, Tongxin Li
We study the problem of characterizing the optimal consistency--robustness tradeoff for single-machine non-clairvoyant scheduling with predicted processing times. For a fixed number of jobs $n$, Wei and Zhang (2020) established a lower bound on the achievable consistency--robustness tradeoff which is known to be tight only in a few restrictive cases, leaving the optimal tradeoff for general $n$ unresolved. A different worst-case-$n$ regime was introduced by Benomar et al. (2025), who applied the former work's construction to show that for $λ\in (0, 1)$, any $(1+λ)$-consistent algorithm must be $1 + Ω(\sqrt{1/λ})$-robust. On the other hand, the best known upper bound gives $(1+λ)$-consistency and $1+O(1/λ)$-robustness, leaving a polynomial gap. In this work, we develop a new lower bound using a multi-stage adversarial construction and a new algorithm that together give a near-optimal characterization of the consistency--robustness tradeoff: for every $n$, our upper bound is within a multiplicative factor $3/2$ of our lower bound, and thus our algorithm is within a multiplicative factor $3/2$ of the online optimal. In particular, our lower bound shows that any $(1+λ)$-consistent algorithm must have robustness at least $1/\sqrtλ$ as $n \to \infty$, while our algorithm achieves robustness at most $\frac{1}{2}+\sqrt{\frac{5}{4}+1/λ}$ for any $n$, matching the lower bound in the leading term as $λ\downarrow 0$; our upper bound also closes the polynomial gap in the worst-case-$n$ regime. We additionally show how our algorithm can be made error-tolerant, preserving the near-optimal consistency-robustness tradeoff while incurring only slightly degraded performance under bounded prediction errors.Authors: Therese Biedl, Günter Rote
In interval graphs and many generalizations thereof, problems such as Matching, Independent Set, and Dominating Set can be solved with simple greedy algorithms in linear (i.e., $O(m+n)$) time. However, it is sometimes possible to improve on this runtime if a suitable representation as intersection graph is given; for example it is possible to find a minimum dominating set in an interval graph in $O(n)$ time. We study RDV graphs, a generalization of interval graphs, namely, the intersection graphs of directed paths in a rooted tree. It was known that the above three problems can be solved in $O(n\log n)$ time if a suitably small representation is given. In this paper, we reduce the runtime to $O(n)$. Furthermore, while the previous results used non-trivial operations such as range-minimum queries and ray-shooting queries, we need nothing more complicated than lists and (for Matching) a Union-Find data structure.Authors: Frank Kammer, Sandra Kiefer, Johannes Meintrup
Temporal graphs are graphs whose edge relation changes in discrete time steps. The Temporal Exploration Problem (TEXP) asks for a temporal walk that visits all vertices. We show that every connected temporal graph with $n$ vertices can be explored in $O(qn\log^3(n))$ time steps, where $q$ is the number of vertex color classes induced by the 2-dimensional Weisfeiler-Leman (2-WL) coloring. For small $q$, our bound substantially improves on the known worst-case bound of $Θ(n^2)$ in general connected temporal graphs. A corresponding walk can be constructed in deterministic polynomial time. The upper bound is complemented by lower bounds of $Ω(n\log(n))$ when $q$ is constant and $Ω(qn)$ when $1 \leq q \leq n$. We also apply our techniques to the Temporal Rendezvous Problem (TRP), in which two agents that do not communicate have to meet on a vertex of the temporal graph. Our exploration algorithm yields that, with only polynomial-time computational power, the agents can meet in $O(n\log^3(n))$ time steps, leaving a gap of only $\log^2(n)$ to the known lower bound. Dogeas, Erlebach, Kammer, Meintrup, and Moses Jr. [ICALP'24] have shown an $O(rn^{1+ε})$ bound for TEXP, for every fixed $ε> 0$, where $r$ is the number of orbits, and an $O(n^{1+ε})$ bound for TRP. Both results require superpolynomial computation time. Our contribution improves upon these results in several ways. First, the dependence on $n$ in the upper bounds on the number of time steps is decreased from $n^{1+ε}$ to $n\log^3(n)$ for both TEXP and TRP. Second, for TEXP, we bound the number of time steps linearly by the parameter q, which is efficiently computable and upper bounded by $r$. Third, we provide novel deterministic polynomial-time algorithms for both TEXP and TRP.Authors: Jingyang Zhao, Mingyu Xiao
The non-preemptive dial-a-ride problem (DaRP) asks for a minimum-cost route of a capacitated vehicle that serves a collection of pickup-and-delivery requests, without allowing objects to be transferred or temporarily unloaded. We study this problem and the closely related minimum-ratio Steiner $k$-Forest (S$k$F) in general symmetric metrics on $n$ locations. We develop a randomized polynomial-time algorithm with expected approximation ratio $\mathcal{O}(n^{1/4}\log^{11}n)$ for the minimum-ratio S$k$F. Our algorithm combines a deterministic approximation on hierarchically well-separated trees with randomized metric embeddings. Using this algorithm, we obtain expected $\mathcal{O}(n^{1/4}\log^{12}n)$-approximations for both the non-preemptive DaRP and the S$k$F. These guarantees improve on the previous $n^{0.3+\varepsilon}$-approximation ratios for the S$k$F and the non-preemptive DaRP, where $\varepsilon>0$ is any fixed constant. Complementing these algorithmic results, we establish the first superconstant inapproximability bounds for the non-preemptive DaRP. Under the Exponential Time Hypothesis (ETH), no deterministic polynomial-time algorithm achieves an $x^{1/(\log\log x)^c}$-approximation for some constant $c>0$, where $x$ denotes either the number of locations $n$ or the vehicle capacity $k$. Under the quantitative Gap-ETH, we rule out every deterministic polynomial-time $x^{o(1)}$-approximation. These bounds hold even on unit-edge stars with $n=(2+o(1))k$.Authors: Cecilia Chen, Rajni Dabas, Samir Khuller, Emilie Rivkin
Power grids use a constantly changing mix of fossil fuels and clean renewables like solar and wind. Because of this, the {\em carbon footprint} fluctuates drastically based on time and geographic location. Time-varying carbon intensity creates opportunities to reduce carbon emissions by shifting workloads to cleaner periods, but deadlines, task dependencies, and limited edge capacity constrain this flexibility. We study carbon-aware scheduling of jobs with release times, deadlines, and arbitrary precedence constraints under piecewise-constant carbon costs. Jobs execute preemptively on a single edge server or are outsourced at job-dependent costs to an unlimited-capacity cloud, modeled as providing instantaneous execution. The objective is to minimize the sum of edge carbon costs and cloud outsourcing costs while satisfying all timing and precedence constraints. For edge-only execution, we give an exact polynomial-time algorithm. Allowing cloud outsourcing makes the problem NP-hard, but we obtain a fully polynomial-time approximation scheme through a reduction to preemptive scheduling with rejection penalties (weighted tardiness). In contrast, even two edge servers without job migration admit no polynomially bounded approximation when carbon-cost variation is unrestricted, unless \(P=NP\). We complement these theoretical results with experiments on controlled synthetic workloads and production-derived Alibaba traces. On synthetic instances, our incremental max-flow implementation is $4.96\times$ faster on average than a direct min-cost flow, while experiements on production-derived workloads evaluate its performance under realistic job structures.Authors: Shihao Shao, Dacheng Tao
Haussler's covering lemma (JCTA 1995) gives the sharp $(C/δ)^d$ metric-entropy bound for binary VC classes under normalized $\ell_1$ distance. We prove a sharp global dynamic analogue for bounded real-valued classes in normalized $\ell_p$, for every $1\le p<\infty$. Writing $d=\operatorname{sfat}_{\varepsilon/32}(\mathcal F)$, we obtain a global dynamic cover of size at most $(C/\varepsilon^p)^d$ for every horizon and $0<\varepsilon<1/2$. Here a single family of deterministic causal experts, fixed independently of the instance sequence, covers every target on every sequence. For $0<\varepsilon<1/4$, a matching worst-case lower bound $(c/\varepsilon)^{pd}$ holds already for binary classes on one fixed sequence, even with real-valued experts. The constants are universal, independent of $p$. For $p=2$, this resolves the horizon-independent sequential $\ell_2$ covering problem of Rakhlin, Sridharan, and Tewari (PTRF 2015) in a stronger global form. For $p=1$, it gives the sharp $(C/δ)^{\operatorname{Ldim}(\mathcal H)}$ global dynamic covering bound for binary classes, resolving questions of Alon, Ben-Eliezer, Dagan, Moran, Naor, and Yogev (STOC 2021) and Malliaris and Moran (Trans. AMS 2024). Our proof combines rank-decreasing correction schedules and accurate sampled prefixes with exact continuations after target identification. Shared-parent routing distributes these continuations among eligible prefixes, eliminating the logarithmic overhead.Authors: Gunjan Kumar, Yash Pote, Jonathan Scarlett
In likelihood-free hypothesis testing (LFHT), given samples from two unknown distributions $P,Q$ on $[n]$ with $\mathrm{d_{TV}}(P,Q)\geq\varepsilon$, and from a third distribution $D\in\{P,Q\}$, the goal is to identify whether $D=P$ or $D=Q$. We study asymmetric likelihood-free hypothesis testing, where the sample budgets $s_P$ and $s_Q$ for $P$ and $Q$ may differ, and characterize the feasible triples $(s_P,s_Q,s_D)$ up to logarithmic factors. We establish that unequal reference budgets can give a polynomial saving. For instance, for constant separation, $n$ samples from $P$ and $n^{3/4}$ from $Q$ allow testing with $\widetilde O(n^{1/4})$ samples from $D$, whereas both existing baselines---symmetric LFHT and unequal-sample closeness testing---require $Ω(\sqrt n)$ samples from $D$. We further apply our results to non-adaptive distribution 2-clustering, where the sample allocation among $k$ distributions must be fixed before observing any data. We obtain matching upper and lower bounds for this problem up to logarithmic factors in terms of the domain size, number of distributions, smaller cluster size, and separation, both with one cluster distribution known and with both unknown. Comparing with known bounds for adaptive sample allocation gives a worst-case adaptivity gap of $\widetildeΘ(k^{1/4})$.Authors: Sebastian Forster, Martin Grösbacher
The $k$-center problem is one of the most fundamental clustering problems and has applications in a wide range of areas, including facility location, network design, data mining, and machine learning. Given a set of objects together with a distance measure, the goal is to select $k$ centers such that the maximum distance from any object to its closest center is minimized. The $k$-center problem has been studied extensively from a theoretical perspective, both in metric spaces and on graphs. While there have been experimental studies for $k$-center clustering in metric spaces, a comprehensive experimental comparison of graph-based $k$-center algorithms on large-scale graphs is still lacking. In this paper, we bridge this gap by evaluating a set of algorithms ranging from classical approaches such as Gonzalez's greedy algorithm [TCS 1985], an algorithm based on the framework established by Hochbaum and Shmoys [Math. Oper. Res. 1985], to more recent methods, including algorithms by Thorup [SICOMP 2001] and Abboud et al. [SOSA 2023]. Our study considers both running time, solution quality and the effects of parallelism on a variety of synthetic and real-world datasets. Our goal is to provide a comprehensive comparison of state-of-the-art $k$-center algorithms on graphs and identify the strengths and weaknesses of different approaches in practice.Authors: Kathrin Hanauer, Sophia Heck, Monika Henzinger, Leonhard Sidl
Counting small patterns is a core primitive in large-scale graph analytics, with numerous applications in data management and network analysis. As modern graphs are massive and continuously evolving, maintaining such counts efficiently under updates is essential. Although specialized dynamic algorithms for patterns with up to four vertices exist, they remain largely theoretical; practitioners instead rely on general-purpose or approximate methods. We present an in-depth study of two dynamic approaches by Eppstein et al. and Hanauer et al. for maintaining counts of triangles and all connected four-vertex subgraph patterns, both based on variants of heavy-light vertex partitioning. We introduce theoretical and practical optimizations and develop hybrid variants that combine complementary strengths of both approaches. Experiments on 56 large real-world and synthetic dynamic graphs show that our optimized algorithms outperform the original methods and strong static and dynamic baselines on nearly all instances, both in total running time and worst-case update time, with speedups of up to several orders of magnitude. We further provide practical guidelines for algorithm selection and tuning. To the best of our knowledge, this is the first comprehensive empirical study of heavy-light partitioning for dynamic subgraph counting, and our findings may inform other algorithms based on this technique.Authors: Avi Kadria, Liam Roditty
An approximate distance oracle (ADO) is a compact data structure that answers distance queries within a multiplicative \emph{stretch} $k$. The classical oracle of Thorup and Zwick~[STOC'01, JACM'05] has stretch $k=2\ell-1$ and uses $O(\ell n^{1+1/\ell})$ space, for every integer $\ell\ge1$, and this trade-off is optimal for dense graphs under the Erdős girth conjecture. However, for sparse graphs ($m=O(n)$), their lower bound yields nothing beyond $Ω(m)$ space. A pivot-based $1$-hop ADO gives every vertex $\tilde{O}(1)$ pivots and returns as an estimate the length of a walk of the form $u\to p_u \to p_v \to v$, where $p_u$ is a pivot of $u$, $p_v$ is a pivot of $v$, and $p_u\to p_v$ is a stored distance. We observe that all the state-of-the-art ADOs with $\tilde{O}(1)$ query time are in fact pivot-based $1$-hop ADOs. Our main result is that, under the Erdős girth conjecture for graphs with constant degree, there are sparse graphs on which every \emph{pivot-based} $1$-hop ADO with stretch $k$ requires $\widetildeΩ(m^{1+2/(k+1)})$ space, for every \emph{real} $k\ge1$. This matches the best known upper bounds with $\tilde{O}(1)$ query time, up to polylogarithmic factors, at every stretch where they are known. We also extend our lower bound to pivot-based ADOs with any constant number $β$ of hops, showing that they require $\widetildeΩ(m^{1+2/(β(k+1))})$ space. In addition, we obtain a tight lower bound for two-hop hopsets. Under the Erdős girth conjecture, for every integer $\ell\ge3$, $(2\ell-3,2)$-hopsets on sparse graphs require size $Ω(m^{1+1/\ell})$, which matches a construction based on the oracles of [Kadria and Roditty, ISAAC'25]. Using the recent explicit high-girth graphs of Double Agent~[doubleAI'26], we also obtain unconditional versions of our ADO lower bounds, with the exponent above $1$ multiplied by $4/5$.In fall of 1985 when I started graduate school, my advisor Michael Sipser asked me to read an early handwritten manuscript by Johan Håstad of his switching lemma. I spent many hours decoding the notation and working through the messy conditional probabilities until I felt I had checked every step of the proof. When I started presenting this to Sipser, he stopped me and said he didn't want the details but instead the intuition of the proof. I had nothing.
I'm reminded of this story as I hear the complaints of how badly OpenAI wrote the 712 papers released on October 6th, as though humans wrote crystal-clear proofs beforehand, definitely not the case in general, especially in the early versions.
Noam Nisan once told me that reading a badly written proof leads to better understanding since you really need to figure out the details instead of having them neatly spelled out. Perhaps, but do not use this as an excuse for not taking the time to write the details properly.
I approach reading the proof of a new result by assuming the proof is wrong until I'm convinced otherwise. Working my way through early versions of Immerman-Szelepcsényi and Toda's theorem definitely forced me to understand these proofs well so I could explain them to others.
I just gave up on fully understanding some results like the original PCP theorem and Ran Raz's Parallel Repetition Theorem, despite seeing the authors give talks on the papers. Sometimes you have to trust the authors and others who hopefully have read the paper. Don't even get me started on László Babai's Graph Isomorphism in quasipolynomial time. And some papers, like Primes in P, require mathematical results in other subfields that I just have to accept.
Sometimes you'll just get better versions of proofs, most famously Irit Dinur's combinatorial proof of the PCP theorem. I only really understood the switching lemma years later when Sophie Laplante and I wrote a Kolmogorov complexity-based proof building on a then-new proof of Alexander Razborov.
When I get stuck in a proof, I sometimes ask the authors, but usually as a last resort unless I can talk to them in person. That's an advantage we have now: you can ask AI to get you over a hurdle in a proof. Claude, while maybe not as good at proving theorems as the unreleased OpenAI model, does a better job writing them up. And one hopes that we'll see simplified and possibly strengthened versions of some of these important results, written by humans or human-AI collaborations. Maybe we'll even get the intuition Sipser told me to seek all those years ago.
By Lance Fortnow
In fall of 1985 when I started graduate school, my advisor Michael Sipser asked me to read an early handwritten manuscript by Johan Håstad of his switching lemma. I spent many hours decoding the notation and working through the messy conditional probabilities until I felt I had checked every step of the proof. When I started presenting this to Sipser, he stopped me and said he didn't want the details but instead the intuition of the proof. I had nothing.
I'm reminded of this story as I hear the complaints of how badly OpenAI wrote the 712 papers released on October 6th, as though humans wrote crystal-clear proofs beforehand, definitely not the case in general, especially in the early versions.
Noam Nisan once told me that reading a badly written proof leads to better understanding since you really need to figure out the details instead of having them neatly spelled out. Perhaps, but do not use this as an excuse for not taking the time to write the details properly.
I approach reading the proof of a new result by assuming the proof is wrong until I'm convinced otherwise. Working my way through early versions of Immerman-Szelepcsényi and Toda's theorem definitely forced me to understand these proofs well so I could explain them to others.
I just gave up on fully understanding some results like the original PCP theorem and Ran Raz's Parallel Repetition Theorem, despite seeing the authors give talks on the papers. Sometimes you have to trust the authors and others who hopefully have read the paper. Don't even get me started on László Babai's Graph Isomorphism in quasipolynomial time. And some papers, like Primes in P, require mathematical results in other subfields that I just have to accept.
Sometimes you'll just get better versions of proofs, most famously Irit Dinur's combinatorial proof of the PCP theorem. I only really understood the switching lemma years later when Sophie Laplante and I wrote a Kolmogorov complexity-based proof building on a then-new proof of Alexander Razborov.
When I get stuck in a proof, I sometimes ask the authors, but usually as a last resort unless I can talk to them in person. That's an advantage we have now: you can ask AI to get you over a hurdle in a proof. Claude, while maybe not as good at proving theorems as the unreleased OpenAI model, does a better job writing them up. And one hopes that we'll see simplified and possibly strengthened versions of some of these important results, written by humans or human-AI collaborations. Maybe we'll even get the intuition Sipser told me to seek all those years ago.
from Ben Recht
Hi there, argmin readers! Today’s post is a live blog of Class 13 of my graduate seminar “Forecasting: A Critical Retrospective,” in which we touched the third rail of forecasting discourse: pandemic modeling. The syllabus and list of past posts are here.
No forecast had a greater impact on our lives than “Report 9: Impact of non-pharmaceutical interventions (NPIs) to reduce COVID-19 mortality and healthcare demand.” Written by epidemiologist Neil Ferguson and colleagues, the report presented prefactual scenarios of what would happen in the UK and the US under various pandemic mitigation strategies. Report 9 was released on March 16, 2020, and many nations and states soon heeded its advice, closing schools and businesses and mandating that citizens lock themselves in their houses.
The report estimated the death tolls—without error bars—for three potential policy scenarios. Doing nothing would lead to 510,000 deaths in the UK. Enacting a “mitigation” policy, where symptomatic people isolated at home and people at risk practiced “social distancing,” would lead to 250,000 deaths. Most optimistically, following the lead of China and enacting a policy of “suppression”—an aggressive, authoritarian shutdown of society—would “flatten the curve” and lead to only 20,000 deaths.
These numbers came from a complex computer simulation with over 900 parameters, almost all of which were unknown. Despite this tremendous uncertainty, the report concluded that “epidemic suppression is the only viable strategy at the current time.”
Even at the time, it was clear that Report 9 was more an advocacy document than a scientific report. Report 9 provided a scenario under which a better future, under a completely untried and untested policy, was possible. Unfortunately, that better future didn’t manifest itself, and faith in public health agencies and other decision-making institutions has never recovered. The team leaned on its institutionally approved scientific expertise to sway public opinion. This was a major risk, and, in retrospect, I wonder if the broader public health community thinks it was worth it.
I don’t want to litigate pandemic policies today, but we can’t talk about what forecasting does without talking about Report 9. It has all the hallmarks of a bad forecast. Its authors used a complex model to produce concrete numbers with no qualification of the tremendous uncertainty in their numbers. They didn’t share their baroque model with the public for over a month. Once it was released, others showed the model itself only shakily supported its own findings. Indeed, Edeling et al. showed that under a mild sensitivity analysis, the 20,000-deaths forecast was at the lower boundary of the 68% confidence interval, well below the mean forecast. It’s as if the team chose parameters to make their policy look as good as possible.
Moreover, the team refused to estimate any of the impacts of their policies beyond burden on the health system and deaths. Report 9 wrote, “while experience in China and now South Korea show that suppression is possible in the short term, it remains to be seen whether it is possible long-term, and whether the social and economic costs of the interventions adopted thus far can be reduced.” They had only a single sentence estimating these costs: “The social and economic effects of the measures which are needed to achieve this policy goal will be profound.” They claimed estimating these social impacts, whether on educational outcomes or economic output, was outside their expertise. Many interpreted this as the team asserting these outcomes were not ethically significant enough to even attempt to model.
As the pandemic progressed, it became apparent that the epidemiology community was bad at short-term forecasting. Human pandemics had basic rise-and-fall shapes predicted by elementary compartment models (known as SIR models), but when they would rise and peak was much harder to guess than Report 9 suggested. Indeed, recent work by White and Leon suggests that overconfidence in forecasts comes from trends that are easy to spot: seasonal trends, statistical smoothing, and exponential growth make pandemics easy to predict. Without these features, disease impact is impossible to predict. Scoring rules paper over the fact that we mostly have no idea how to forecast these things. We all learned in real time that epidemiological tools have very little predictive power. They are, at best, descriptive. And yet we were told in March 2020 to trust their long-term forecasting.
The actual death toll in the UK was later estimated to be around 230,000. Whatever the actual number is, the consensus is that it is much, much larger than 20,000. As is always the case when a forecast doesn’t pan out, the forecasters can argue there is no true Scotsman. They might say the policy was poorly implemented and the disease would have gone away if we had acted better. Such arguments carry no water in medicine, and they shouldn’t carry water here. A medical intervention is only effective if a patient population is willing to take it. A real population isn’t what you wish it would be. None of the proposed non-pharmaceutical interventions stopped the eventual wave of disease anywhere on earth, even in China.
Whether the suppression strategy worked is unknowable. We know that more than twenty thousand people died. We don’t know how many would have died under a different policy. We can’t know what the economic and educational outcomes would have been under a different policy either.
What exactly can we conclude then? A while back, I wrote about the Y2K bug and the preparedness paradox and latched onto John Quiggin’s argument that there were multiple true interpretations of the decision making. The COVID pandemic brought a similar pattern of simultaneous truths. It’s true that many people suffered and died, and some were saved by avoiding contact with others. It’s true that we overreacted and harmed children’s education and socialization. It’s true that “the other side” promoted plenty of craziness (Ivermectin? Hydroxychloroquine? Injected bleach?). I could make a long list of truths that would logically contradict each other.
But it’s also true that no one was able to predict the future. It’s obvious in retrospect, but questions of what should be normalized are questions of values, not data science. And in most political decisions, values have to trump science and its messy uncertainty. COVID forced us to make massively consequential decisions in the face of massive uncertainty. We used numerical reports and forecasts to dodge the moral consequences of our actions.
from Gil Kalai
Let f(d) be the smallest integer so that every set of diameter one in can be covered by f(d) sets of smaller diameter.
Let g(d) be the smallest integer so that every finite set of diameter one in can be covered by g(d) sets of smaller diameter.
Clearly g(d) ≤ f(d)
Test your intuition: Is g(d)=f(d) ?
TYI (60): my intuitionThe answer is not known, but my own intuition is that g(d)<f(d) for every large d. In my lecture around the Borsuk Conjecture at Jeff Kahn’s fest I raised the conjecture that this is indeed the case. I also mentioned an interesting psychological fact: Over the years, both before and after I wrote my 2015 survey article on problems around Borsuk’s conjecture, I have encountered several incorrect proofs that g(d) = f(d). Often these proofs involve the De Bruijn–Erdős theorem, which asserts that an infinite graph with finite chromatic number has a finite subgraph with the same chromatic number. (This result is also an easy consequence of compactness in mathematical logic.) Some proofs also involve the claim that there is a constant c < 1 such that every set of diameter one in can be covered by g(d) sets of diameter at most c.
In my lecture at Jeff Kahn’s conference I mentioned that I am usually convinced by such proofs for a while, until the prover (and sometimes I) finds the mistake. This gave me extra motivation to firmly conjecture that for some dimensions (or even for almost all dimensions) g(d)<f(d). Sure enough, this happened again after my talk, once again I was convinced for a short while by proofs presented to me that g(d)=f(d).
Open AI’s proof that f(9)>10One of the 700 or so papers released by Open AI on October 6, 2026 asserts that f(9)>10. This is a major progress on the Borsuk’s problem. (Of course, the proof needs to be carefully checked. The main theorem has also been formalized in Lean.)
The construction itself is one of the constructions Jeff and I studied—the set of matrices of the form where
is a unit vector in
. For
, these are symmetric matrices of trace one, and therefore they lie in a nine-dimensional affine space. The distance between two such matrices is maximal precisely when the corresponding vectors are orthogonal.
What is new is the proof that this set cannot be covered by ten sets of smaller diameter. The proof is topological. You can regard it as related to the topological proof of the Borsuk–Ulam theorem, which implies that when you cover the unit sphere in with
closed sets, one of these sets must contain a pair of antipodal points. The topology here looks more complicated and the proof looks very beautiful!
One of the reasons for my (shaky) intuition regarding g(d) < f(d) is that I do not see, for example, why the Borsuk–Ulam theorem or its proof implies (the easy fact) that there is a finite set of diameter one that cannot be covered by d+1 sets of smaller diameter.
A figure from the AI paper
Can transversality save Borsuk’s conjecture? And Gábor Damásdi’s characterization of spatial diameter graphsIn my lecture at Jeff Kahn’s conference, I mentioned several new developments around Borsuk’s conjecture. I will mention here one development from Gábor Damásdi’s October 2026 paper, which characterizes finite diameter graphs in three-dimensional space.
This work fits in a nice way with my attempt to save Borsuk’s conjecture using transversality. My conjecture applies to both finite and infinite sets, but for finite sets it has a simple formulation: If the diameter graph of a finite set in $\mathbb R^d$ is stress-free, then it is (d+1)-colorable. Here stress-free means that there is no nonzero assignment of equilibrium stresses to the edges of the diameter graph.
Gábor Damásdi proved that extremal diameter frameworks in three-dimensional space are stress-free. He also achieved a complete characterization of finite diameter graphs in three-dimensional space: they are precisely the subgraphs of non-bipartite quadrangulations of the projective plane (with at least one edge). Earlier, Yaakov Kupitz, Horst Martini, and Micha Perles showed that the graphs associated with extremal configurations in three dimensions (with (2n-2) diameter pairs) have a remarkable strong self-duality property, and they conjectured a converse that Damásdi has now proved and strengthened.
Pictures from the last two lectures in Jeff Kahn’s fest.I first met Fan Fei at the conference.
I first met Paul Seymour, path-width, tree-width, and tree-decompositions in 1983.
from CS Theory Events
By shacharlovett
from Scott Aaronson
Today, I take a break from your regularly-scheduled AI mathocalypse programming to urge my American readers to vote in the Congressional midterms, early if possible, if you haven’t already. Especially if your state faces one or more major contests, as does my adopted home state of Texas.
Me, I voted straight-ticket Democrat today, as I’ve done in every election since I became eligible over a quarter-century ago (except for when I vote-swapped with someone from another state).
So yes, I voted for the guy who studied theology a short walk from my house, and who seems to have really internalized the whole Jesus thing about kindness to everyone—
—over his sneering, thuggish, cartoonishly mafia-like opponent. Fingers crossed that Talarico pulls off a historic upset for our state (he’s currently a 2-to-1 favorite in the prediction markets).
The Texas Republicans did everything they possibly could to make this choice easy for me, by being corrupt, conspiratorial, racist, and Taliban-like even by the jaw-droppingly debased standards of MAGA in 2026. As I draw breath, I could never vote for a slate one of whose candidates attacked UT students for the crime of being visibly Southeast Asian while cheering their school’s football victory from the stands—and whose other candidates could barely bring themselves to condemn this knuckle-dragging racist, for fear of angering their base. (It’s like, didn’t you want immigrants to assimilate to American culture? What more could these kids possibly do, short of skin bleach?)
All the same, this was also the first US election in my lifetime where I felt like my vote was genuinely in play—especially when I listened to Talarico’s condemnations of Israel, for having the temerity to fight the same kind of war any random other nation would’ve fought had it been attacked as Israel was on October 7. When Hasan Piker came to speak to a cheering crowd here at UT Austin, I actually wrote to someone I know in the Talarico campaign, to ask whether Talarico would show enough balls to condemn Piker’s many antisemitic and anti-American statements, and renounce his support. My contact was nice enough to reply to me, saying: don’t worry, James is taking care to be far away from Austin during Piker’s visit, so he won’t need to engage at all!
So then, this is my candidate: the guy who’s strategically silent on the wildly-popular streamer who’d gladly see my Israeli family members raped and beheaded, rather than campaigning with that streamer like Abdul El-Sayed did in Michigan. I unironically believe that, for Talarico, it took genuine moral courage to resist the whole momentum of his party’s youth even to this extent.
To earn my vote in the near future under these circumstances, all a Texas Republican would need to do is be somewhat sane or reasonable. He or she might affirm, for example, that racism is bad, that abortion is a woman’s choice, that Christianity is not the state religion of the US, that Covid vaccines work, that human emissions are worryingly changing the earth’s climate, and/or that Joe Biden won in 2020, while still being arbitrarily right-wing on taxes and other stuff. He or she could then simply wait for the Democrats to descend fully into the worldview of the masked hooligans who are currently setting France’s beautiful cities aflame, terrorizing its shopkeepers, and looting as many Louis Vuitton handbags as they can carry … all for Palestine, of course, and for the death of global capitalism, and for the violent overthrow of the scheming, money-grubbing, hook-nosed, international Talmudic … err, I mean “Zionists.”
What I’m trying to say is, it was a genuine achievement on the part of the Texas Republicans to fail to earn a single vote from me this cycle.
from ECCC Papers
from ECCC Papers
Authors: Krishnamoorthy Dinesh, Chandana Sasidharan
One of the central questions in space complexity is whether nondeterministic logspace computations ($\textsf{NL}$) can be simulated in unambiguous logspace ($\textsf{UL}$). A stronger notion, \emph{reach unambiguity} ($\textsf{RUL} \subseteq \textsf{UL} \cap \textsf{co}\textsf{UL}$), requires every configuration reachable from the start to have exactly one computation path (Buntrock et.al. 91). While directed graph reachability is $\textsf{NL}$-complete, planar graph reachability is in $\textsf{UL}$ and undirected graph reachability is in deterministic logspace ($\textsf{L}$). In this work, we study the space complexity of reachability problem for restricted directed graph families and show the following. - For reach unambiguous graphs (graphs with at most one path from start vertex to every vertex), Lange (Lange 97) showed that reachability is in $\textsf{RUL}$. As our main result, we show that for simple path graphs (introduced in Kannan et.al. 08), which contains reach unambiguous graphs), where each vertex has at most one simple path from the start, we show that the reachability problem lies in $\textsf{UL} \cap \textsf{co}\textsf{UL}$. - Our first result can also be equivalently stated as: the recognition problem for simple path is in $\textsf{UL} \cap \textsf{co}\textsf{UL}$ if and only if the reachability problem restricted to simple path graphs is also in $\textsf{UL} \cap \textsf{co}\textsf{UL}$. Inspired by this, we investigate the complexity of graph recognition versus graph reachability for graph classes. Observe that for any graph class, solving reachability (for the class) also solves the recognition problem for that class. We show that for reach unambiguous graphs, solving recognition is as hard as solving reachability (making both of them $\textsf{RUL}$-complete). (Abstract shortened to meet arXiv limits)Authors: Sanyou Mei
We study turn-based deterministic zero-sum games with discounted and long-run average costs. For discounted costs, we establish exponential and superpolynomial iteration lower bounds for the simple strategy-iteration method with Dantzig's rule under unrestricted costs and unit weights, respectively. To the best of our knowledge, this shows for the first time that the method is not strongly polynomial even when all action costs belong to $\{-1,0,1\}$. For long-run average costs, we establish an exponential iteration lower bound for termination of a Dantzig counterpart with unrestricted costs and prove that it admits a strongly polynomial implementation with unit weights.Authors: William Cruz-Santos
LABS are a fundamental combinatorial optimization problem arising in sequence design and statistical physics, yet the formal complexity of the standard fixed-geometry problem remains unresolved. We study how zero-energy complexity changes when support geometry is included as part of the input and then progressively restricted. For unary standard LABS, we establish membership in $\NP$ and a sparsity/Mahaney consequence: Karp NP-hardness would imply $\Ptime=\NP$. For Pair-Set-LABS and Masked-LABS, zero-energy feasibility is polynomial-time decidable when every pair group or masked row has at most three terms and is NP-complete when four terms are allowed. NP-completeness persists when active supports are restricted to contiguous intervals.Authors: Qi Cheng
We prove a polylogarithmic exceptional-set estimate for symmetric five-term sums of roots of unity of arbitrary order. More precisely, at most $O((\log(2N))^{11})$ points of the $N$-grid satisfy $|1+2\cos(2πx)+2\cos(2πy)|<\exp(-C(\log(2N))^{13})$. This implies the corresponding bound for small conjugates at the reduced conductor: outside polylogarithmically many real embeddings, every such sum is at least quasipolynomially large. The proof is unconditional and combines a polynomial-vector-field multiplicity estimate, arithmetic jet determinants, analytic propagation, and interpolation determinants for nearby grid points. As a companion result, assuming a uniform number-field $abc$ conjecture, we prove that every sum of a fixed number of distinct prime-order roots of unity has modulus at least $\exp(-\varepsilon p)$ for every $\varepsilon>0$ and all sufficiently large primes $p$, uniformly in the exponents. That proof uses simultaneous compression of the exponents, discriminant estimates, and cyclic resultants.Authors: Xin Li, Yan Zhong
We give a short-description decomposition of bounded-width CNFs. For every fixed $\varepsilon>0$, every width-$b$ CNF on $m$ variables is an exact disjoint union of at most $2^{\varepsilon m}$ width-$b$ CNFs, each determined by $2^{O_\varepsilon(b)}\log(m+1)$ satisfying assignments. For every fixed $d\ge3$, we prove a worst-case size lower bound of $2^{Ω_d((n\log n)^{1/(d-1)})}$ against depth-at-most-$d$ unbounded-fan-in AND/OR circuits with input negations for three polynomial-time Boolean families: inverse trace over binary fields, the Goldreich--Tal trilinear function, and OpenAI's polynomial evaluator with its original parameters. All parameter bits count as inputs. For inverse trace, every such circuit of size at most $S$, where $n\le S\le2^{c_dn^{1/(d-1)}}$, has uniform sign correlation at most $2^{-η_dn\log\log S/(\log S)^{d-1}}$. Here $c_d,η_d>0$ depend only on $d$. This improves on the classical parity correlation bound. The lower bounds combine the decomposition with restriction arguments; the correlation bound additionally uses common partial decision trees. We also construct exact nonuniform AND/OR circuits for inverse trace of size $2^{O(n^{2/3})}$ at depth eight and $2^{O(\sqrt n\log n)}$ at depth nine. For every fixed integer $h\ge2$, the construction gives depth-$(4h+1)$ circuits of size $2^{O_h(n^{1/h}\log n)}$. The upper bounds implement finite-field evaluation and interpolation using circuits that enumerate intermediate states.Authors: Russ Woodroofe
We show that the problem of deciding whether a simplicial complex is partitionable is NP-complete in dimensions two and higher, answering a 1995 question of Kleinschmidt and Onn.Authors: Rafael Pass
We give a self-contained constructive proof that the matrix multiplication exponent satisfies $ω\le9/4$. This bound was recently claimed by OpenAI~\cite{original} through non-constructive arguments in Strassen's asymptotic spectral framework, counting exact scalar arithmetic operations over the complex numbers. We explicitly construct a Strassen-style matrix multiplication identity and obtain the bound by ordinary block recursion. For every $γ>0$, the resulting algorithm multiplies two $n\times n$ integer matrices using $O(n^{9/4+γ})$ integer arithmetic operations.Authors: Simon Mackenzie, Mashbat Suzuki
Envy-free cake cutting asks how to divide a resource so that no agent prefers another agent's share. Finding such a division with few queries about preferences has been a longstanding challenge. Aziz and Mackenzie gave the first query bound depending only on the number $n$ of agents: a tower of six $n$'s. Subsequent improvements culminated in Ye and Bai's single-exponential bound of $n^{O(1)}2^n$. A large gap remains between this deterministic upper bound and Procaccia's general lower bound of $Ω(n^2)$. Whether polynomially many queries suffice is a central open question in fair division. We show that a polynomial expected query bound is possible. Our randomised protocol uses only independent, uniformly sampled points from the cake as its source of randomness. For every profile of $n$ agents with nonnegative, additive, nonatomic valuations, the protocol has the following guarantees: (1) It terminates with probability one. (2) Every allocation it returns is complete and exactly envy-free. (3) Its expected number of Robertson-Webb queries is $\widetilde{O}(n^{30})$. The expectation is taken solely over the protocol's random choices, with no distributional assumptions on preferences.Authors: Holger Boche, Volker Pohl, H. Vincent Poor, Frank H. P. Fitzek
If a regular linear differential-algebraic equation has a unique solution, this solution is known to be Turing computable. In contrast, this paper shows that singular linear differential-algebraic equations exhibit fundamentally different computability properties. More precisely, we show that for every linear differential-algebraic equation (LDAE) with constant computable coefficients, there exists a computable input function with strong regularity properties such that the LDAE admits a unique solution, yet this solution is not Turing computable. In fact, the solution is non-computable at certain computable times.Authors: Arnaud Mary
We present lower bounds for the maximum minimal hitting set problem and for the problem of enumeration of minimal transversals in bounded-dimension hypergraphs. Our starting point is the recent reduction of Kobayashi, Kurita, and Wasa (2026), developed to establish ETH-based hardness of hypergraph dualization. Adapting their construction, we show that, under ETH, deciding whether a hypergraph $\mathcal{G}$ with $n$ vertices and $m$ hyperedges has a minimal transversal of size at least $k$ cannot be done in time $n^{f(k)}m^{o(k)}$, for an arbitrary computable $f$. We transfer this bound to the following decision problem: given a dimension-at-most-$r$ hypergraph and a family of $s$ of its minimal transversals, decide whether another exists. Under ETH, this problem admits no uniform algorithm with running time $n^{f(r)}(s+1)^{o(r)}$. Under SETH, for every fixed $t \geq 2$, it admits no algorithm with running time $\poly(|\mathcal{G}|)(s+1)^c$ for dimension at most $2t$ and any $cAuthors: Florestan Brunck, Christoph Hertrich, Kilian Ruess, Jack Stade, Amir Yehudayoff
We prove that every $\operatorname{ReLU}$ network can be exactly simulated by a $\operatorname{ReLU}$ network with two hidden layers. We present two proofs: one that is based on fillings in homological algebra and a direct combinatorial proof.Authors: Francesco Maria Guadagnuolo, Alessio Borgi, Dorina Thanou, Pietro Liò
We extend the Bochner-Weitzenböck decomposition to cellular sheaf Laplacians, splitting it into a positive semidefinite term, the Bochner sheaf Laplacian, and a block diagonal term, the Forman curvature. We show that the Bochner Laplacians form a class of cellular sheaves that extends both connection and matrix-weighted Laplacians, and generalizes signed graphs to $d$ dimensions. We give a holonomy characterization of their kernel, prove the related Cheeger inequalities, and attach to them a random walk that generalizes the Gremban expansion. For the Forman term, we prove a discrete Bochner theorem, which bounds the first cohomology of a cellular sheaf with nonnegative curvature, and we read the whole decomposition as an opinion-dynamics model. We then apply this machinery to Sheaf Neural Networks, whose learnt Laplacian is otherwise unobserved. The Bochner interpretation yields a node-level conviction score that acts as an operational importance measure under frozen-model interventions, while the Forman profile provides a local descriptor of the learnt operator.Authors: Philémon Beghin, Jean-Philippe Échard, Anthony Peeters, Arnaud Schenkel, Anne-Emmanuelle Ceulemans, François Glineur
This study compares ten digital 3D acquisition techniques applied to violin family instrument plates, assessing their accuracy and relevance for scientific and cultural heritage applications. Evaluated methods include two photogrammetric workflows, medical and industrial computed tomography, terrestrial laser scanning, two structured-light configurations (blue light and infrared), and three consumer-grade iPad Pro approaches: TrueDepth scanning and LiDAR using two different applications. The methods were applied to five historical instruments from the "Musical Instruments Museum" (Brussels) and the "Musée de la Musique" (Paris). Since no geometric ground truth is available, accuracy is assessed through systematic pairwise point-to-plane comparisons of the resulting point clouds. These comparisons are jointly analysed to estimate the intrinsic error of each technique (i.e. the expected discrepancy between the model and the true but unknown geometry) without designating any technique as reference. Results are discussed with respect to intended uses, offering recommendations for techniques depending on the dedicated objectives.Authors: Greg Sidebottom
We give a scheme that multiplies two $3\times3$ matrices with 23 multiplications and 55 additions over any ring, one addition below the previous record of 56 (Sun, 2026) and the first below 56 for exact non-commutative $3\times3$ multiplication without a change of basis. The scheme forms 13 signed combinations of the entries of A and 14 of B, takes 23 products, and recombines them with 28 further additions; its correctness is machine-checked in Lean 4. The previous records, from 60 down to 56, were obtained by greedy common-subexpression elimination, which only bounds each side of a scheme from above. We minimize both input sides exactly by chain covering, and the output side exactly through the transposition principle: the 9-by-23 output map costs its transpose plus 14, and the transpose is a 9-input map that the input-side minimizer solves exactly. Applied to Perminov's cn122 scheme (class i19w225c4efh, published at 58 additions) this gives 55 = 13 + 14 + 28, where greedy elimination reaches only 29 on the output side. The same method shows that Sun's representative is output-optimal at 56, and an exact orbit-wide computation over the Heule-Kauers-Seidl database shows that the record class is the only database class attaining 55.Authors: Markus Bläser, Pranjal Dutta, Sagnik Dutta, Gorav Jindal
We study the shift equivalence testing problem for high-degree sparse multivariate polynomials. Given explicit spar se representations of two polynomials $f,g\in\mathbb{Q}[x_1,\ldots,x_n]$, with exponents encoded in binary, sparsities $s$ and $t$, and total degree at most $d$, the task is to decide whether there is a vector $\mathbf{a}\in\mathbb{Q}^n$ such that $f(\mathbf{x}+\mathbf{a})\equiv g(\mathbf{x})$. Furthermore, one needs to output such a vector if it exists. Dvir, Oliveira, and Shpilka (ICALP 2014) studied shift equivalence for low-degree arithmetic circuits. Their framew ork does not apply directly to sparse polynomials, which are not closed under shifts, and they left open whether shift equivalence of sparse polynomials admits an efficient deterministic algorithm. We answer this question positively over $\mathbb{Q}$. If the input coefficients have bit-size at most $τ$, we sh ow that a rational shift of polynomial bit-size exists whenever the polynomials are shift equivalent. Moreover, our alg orithm outputs such a shift and has a running time of $\operatorname{poly}(n,s,t,τ,\log d)$ in the bit model. The ar ithmetic and structural parts of our result also hold over any field of characteristic zero or characteristic larger th an $d$.Authors: Kiril Bangachev
This mostly expository note studies the sample-noise regimes in which the testing problem for noisy $k$-XOR in dimension $n$ can be efficiently solved. Concretely, we ask what pairs $(β, δ)$ admit algorithms running in time $n^{O(k)}$ where $m = n^β, β\in [0,k]$ is the number of samples and $\mathsf{Bern}(n^{-δ}),δ\in (0,+\infty)$ is the noise distribution. The current state-of-the-art algorithms are: I. A folklore algorithm when $β> 1, δ>1$ based on Gaussian elimination; II. A folklore algorithm when $β\ge k/2$ based on the birthday paradox; III. A recent algorithm in the regime $β> δ+ k(1-δ), δ\in (0,1)$ based on a reduction to the first algorithm [DJ24,CSZ24]. IV. Extending [AF09], we strictly improve the last regime to $β> δ+ (k-1)(1-δ), δ\in (0,1).$ These algorithms correspond to efficiently finding short cycles in uniform hypergraphs and can be equivalently phrased as algorithmic Moore bounds.Authors: Davide Bilò, Giordano Colli, Stefano Leucci
We study the \emph{Monitoring Edge-Geodetic Set} problem (MEG-Set), which asks for a minimum-cardinality set $M$ of vertices of an undirected graph $G$ of $n$ vertices such that every edge of $G$ belongs to all shortest paths between some pair of vertices in $M$. We present new approximation and hardness results for MEG-Set. On the positive side, we design a deterministic polynomial-time $O(n^{1/3}\log^{2/3}n)$-approximation algorithm, improving upon the previously best-known $O(\sqrt{n\log n})$ approximation ratio. On the negative side, for every constant $\varepsilon \in (0,1)$, we prove that the problem admits no polynomial-time $\big(2^{\log^{1-\varepsilon} n}\big)$-approximation algorithm, unless $\mathsf{NP}\subseteq \mathsf{DTIME}(n^{\operatorname{polylog} n})$. This substantially improves upon the previously known logarithmic inapproximability bound. We also prove that \megset is $\mathsf{NP}$-hard on planar $2$-degenerate graphs, whereas $\mathsf{NP}$-hardness was previously known for $1$-apex $2$-degenerate graphs. We conclude by observing a connection between monitoring edge-geodetic sets and subsetwise distance preservers, i.e., subgraphs that preserve distances between all pairs of vertices in $S\subseteq V(G)$. Specifically, we show that any upper bound on the size of the latter yields a lower bound on the size of the former.Authors: Quanlong Niu, Wei Liang, Riheng Jia, Zhao Zhang
The Minimum Shared-Power Edge Cut (MSPEC) problem seeks to disconnect two designated terminals with minimum total power by assigning powers to graph vertices and deleting every edge for which the sum of the powers at its endpoints reaches its edge weight. Previous work gave a fully polynomial-time approximation scheme for this problem, while its exact computational complexity remained open. We prove that general MSPEC with nonnegative edge weights can be solved exactly in polynomial time. Specifically, we first use linear programming duality for each fixed cut to reformulate MSPEC as minimizing the maximum terminal-relaxed matching weight over all $s$-$t$ cuts. Then, we construct a terminal-copy extended graph that transforms the maximum-weight matching model with unconstrained terminal capacities for a fixed cut into an equivalent ordinary maximum-weight matching model. Next, we extend the submodularity of the unweighted maximum-matching cut function to nonnegative edge weights and prove that the restriction obtained by fixing the terminal copies on prescribed sides remains submodular. Consequently, MSPEC reduces to exact submodular function minimization. Once an optimal cut is obtained, a corresponding optimal power assignment can be recovered. This result resolves the open question concerning the exact computational complexity of general MSPEC.Authors: Quanlong Niu, Riheng Jia
The residual maximum matching problem asks for a maximum matching whose deletion leaves a graph with the largest possible matching number. For unweighted graphs, previous work provides a $1/2$-approximation guarantee in general graphs and a $2/3$ guarantee in graphs with a perfect matching. We present a $2/3$-approximation algorithm running in $O(n^5)$ time, extending the latter guarantee to general graphs. The algorithm improves the residual matching number through single-edge exchanges involving free vertices. We prove that, for any maximum matching that admits no further improvement by such exchanges, the residual matching number is at least $2/3$ of the optimum, and we give an example showing that this bound is tight.Authors: Zhangsong Li, Allan Sly
We study Glauber dynamics for the Ising model on random $d$-regular graphs with $n$ vertices at low temperature, in the regime $β\geq C/d$ where $C,d$ are sufficiently large constants. In this regime, the full mixing time is exponential in $n$, because of the bottleneck between the two dominant phases: configurations with a majority of plus spins and configurations with a majority of minus spins. We show that, for sufficiently large $d$, if the dynamics is initialized with an excess of at least $ε_{C,d} n$ plus spins over minus spins, then it quasi-equilibrates in time $O(\log n)$ to the Gibbs measure conditioned on positive magnetization. In addition, the required bias $ε_{C,d}$ can be chosen so that $ε_{C,d}\to 0$ as $d,C\to\infty$. Previous bound of \cite{GSS25+} in the Ising and large-$d$ setting required $β\gtrsim (\log d)/d$. A key difficulty is that, even from the all-plus initialization, one must control the propagation of negative information in spacetime in a low-temperature model with strong local correlations. We address this by developing a new bootstrap approach to proving subcriticality of disagreement clusters under the grand coupling.Authors: Shahin Kamali, Seyed-Mohammad Seyed-Javadi
In the telephone model a message starts at a source vertex, and in every round each informed vertex may call one neighbour. Telephone multicast asks for a schedule that informs a given set of $k$ terminals in the fewest rounds. On directed graphs, the best known ratio for this problem was $\tilde O(\sqrt k)$, due to Elkin and Kortsarz and to Hathcock, Kortsarz and Ravi. For every integer $\ell\ge2$, we give a deterministic combinatorial algorithm with running time $n^{O(\ell)}$ that computes a schedule of length $O(\ell^3\log k)\cdot(\mathrm{OPT}+k^{1/\ell})$, where $n$ is the number of vertices and $\mathrm{OPT}$ the optimum. Since $\mathrm{OPT}\ge\log_2(k+1)$, this gives ratio $O(k^ε)$ in time $n^{O(1/ε)}$ for every fixed $ε>0$, and ratio $O(\log^4k)$ in quasi-polynomial time. The method rests on jump trees with additive vertex loads, a height reduction that bounds the load of every vertex, and a recursive greedy algorithm with an exponential potential. We also show that directed multicast is a special case of the degree-bounded directed Steiner tree problem on a time-expanded digraph. With known algorithms for that problem this gives randomized ratios $O(\log^2n)$ in time $n^{O(\log n)}$ and $O(n^ε)$ in time $n^{O(1/ε)}$, which, unlike ours, grow with $n$. On the hardness side, directed multicast stays $(1-ε)\ln k$-hard even when $\mathrm{OPT}=O(\log k)$, the regime in which the previous algorithms were weakest.Authors: Lunjia Hu, Anish Jayant, Peter Li, Princewill Okoroafor, Abhishek Shetty
Motivated by the notion of features from machine learning, we study the complexity of representing data that allows for evaluation with a given family of functions. Concretely, we consider a deterministic encoder that observes $X\sim D$ and produces a finite encoding before a task $f\in\mathcal{F}\subseteq\{0,1\}^{\mathcal{X}}$ is specified. For each task, a decoder must predict $f(X)$ with error at most $\varepsilon$ under $D$. We construct an encoder that outputs a representation with $O(d^{*}\log(1/\varepsilon))$ bits, where $d^{*}$ is the dual VC dimension of $\mathcal{F}$. Our encoder greedily selects $O((d^{*}/\varepsilon)\log(1/\varepsilon))$ functions from the class and uses their joint label pattern to produce the encoding. The key idea in our upper bound is a novel potential function argument, where we compare the entropy gained from each greedy selection with the number of patterns allowed by the dual VC dimension. We present lower bounds showing that the representation length achieved by our encoder is worst-case optimal for every $d^* \ge 1$ and $\varepsilon < 1/4$ up to a universal constant factor, and instance-wise optimal for every family $\mathcal{F}$ up to an $O(\log(1/\varepsilon))$ factor. We give two ways to learn the representation from unlabeled samples, with different guarantees on the representation size and sample complexity. Experimentally, we verify the greedy construction's accuracy-size tradeoff and explore its connection to neural sparse autoencoders.Authors: Vincent Froese, Leon Kellerhals, Frank Sommer, Manuel Sorge, Ondřej Suchý
In Cluster Editing, we are given a graph $G$ and an integer $k$ and ask whether at most $k$ edge insertions and deletions turn $G$ into a disjoint union of cliques. Komusiewicz and Niedermeier asked in 2012 at MFCS whether Cluster Editing is fixed-parameter tractable with respect to the number $\ell$ of edge deletions, a parameter based on the solution rather than on the structure of the input graph. We answer this question negatively: Cluster Editing with at most $k$ edits, at most $\ell$ of which are deletions, is W[1]-hard with respect to $\ell$, even when combined with the pathwidth and the feedback edge set number of the input graph. The hardness extends to editing towards $H$-free graphs for every graph $H$ that is a clique minus one edge on at least four vertices. On the positive side, we show that the problem becomes fixed-parameter tractable when $\ell$ is combined with the excess $μ$ of $k$ over the lower bound given by a packing of modification-disjoint induced paths on three vertices, a lower bound that state-of-the-art solvers use. Each of the two parameters alone leads to intractability, but together they admit an $O(4^{μ+\ell}\cdot(n+m+μ))$-time algorithm and a problem kernel with $O((\ell+μ)^2)$ vertices. Both results extend to packings of stars and the algorithm extends to $H$-free editing.Authors: Argyrios Deligkas, Eduard Eiben, Robert Ganian, Tiger-Lily Goldsmith, Marlene Gründel, Simon Wietheger
We study the parameterized complexity of finding an EF1 allocation of indivisible items in the group-sharing setting, which has received increasing attention in recent years. There, items are not allocated to individual agents but rather to one of two (or possibly more) groups, and agents within that group all share the assigned items. We consider both the "fixed" (EF1-Fix) and "variable" (EF1-Var) group cases, where in the former the assignments of agents to groups are prescribed. While both are NP-hard in the classical sense, we show that their algorithmic behavior differs significantly from the parameterized perspective. As our main results, we: (1) prove that both cases are NP-hard even when the number of agents is a small constant; (2) circumvent this hardness by establishing fixed-parameter tractability for EF1-Var w.r.t. the number of "subjective" items, that is, items which are viewed as chores or goods by different agents---but rule out an analogous result for EF1-Fix; and (3) establish fixed-parameter tractability for EF1-Fix w.r.t. the number of item types, but link the existence of an analogous fixed-parameter algorithm for EF1-Var to a fundamental open question in the setting of Integer Linear Programming.Authors: Rishi Advani, Abolfazl Asudeh
In the classical necklace splitting problem, beads of different colors lie on a line, and the goal is to divide them among $k$ agents using as few cuts as possible so that every agent receives the same number of beads of each color. We study the planar analog in which a cut is a full straight line and the objective is minimizing the number of lines: $m$ points colored red and blue must be separated by straight-line cuts into regions that can be allocated to $k$ agents so that each agent receives the same number of points of each color. Projection to a line gives $2(k-1)$ cuts, and $k-1$ are sometimes necessary; we give algorithms, static and dynamic, that provably close part of this gap. We develop several approaches that capitalize on the extra degree of freedom: a ``star'' search that produces solutions with as few as $\lceil \frac{k}{2} \rceil$ cuts and never more than $k$ whenever a fair contiguous circular partition exists, with further guarantees for evenly spaced input, and a general algorithm that produces at most $k + \log_2(k+1) - 2$ cuts in $Θ(m \log k)$ time, built on a one-dimensional necklace splitting subroutine that requires no presorting. We then adapt the general algorithm to a dynamic setting, maintaining exact fairness and the cut bound under arbitrary relocation of points, with expected update time that scales with the total distance moved.Authors: Maciej Skórski
Collisions are a basic probe of unknown distributions, used for testing and for counting substructures in graphs, and they underlie Rényi entropy, a fundamental measure of uncertainty with applications in cryptography, machine learning, physics, and biology. Motivated by this, we study the natural birthday estimator. We prove Bernstein-type concentration for it and show that it is minimax optimal, uniformly and jointly in alphabet size, order, accuracy, and confidence, with no sample splitting, clipping, or median aggregation. This, in particular, settles the sample complexity of integer-order Rényi entropy estimation up to absolute constants in all regimes, closing the gap between the best known upper and lower bounds. Our concentration bound rests on a sensitivity analysis of collision count, and the matching lower bound on a sharp analysis of detecting a hidden spike in a plateau distribution.Authors: Jan van den Brand, Adam Karczmarz, Aryan Patel
We study the fully dynamic exact distance problem in unweighted directed graphs, where the graph undergoes edge insertions and deletions, and the distance between two query vertices must be reported. Under the combinatorial Boolean matrix multiplication conjecture, any subquadratic-time algorithm for this problem must use algebraic techniques. All prior work uses the polynomial matrix inverse as its algebraic tool, but within subquadratic time, this technique can only maintain distances up to a small-polynomial hop bound. So larger distances must be reassembled from short-range pieces by a combinatorial layer. This hybrid algebraic-combinatorial construction has led to a substantial slowdown for dynamic distances compared to other dynamic graph problems relying on algebraic techniques. We give the first subquadratic-time dynamic distance algorithm built on dynamically maintaining a different algebraic object than the matrix inverse. By maintaining the Frobenius form $A=KCK^{-1}$ of a dynamic generic (i.e., cyclic) matrix $A$, we can query all the powers $A^\ell = K C^\ell K^{-1}$ efficiently. For adjacency matrix~$A$, the smallest $\ell$ with $(A^\ell)_{s,t}\neq 0$ is the $st$-distance in the associated graph. So, unlike dynamic matrix inverse, we get distance information directly without hop truncation, and we no longer need to perform any combinatorial reassembly. This purely algebraic approach to dynamic distances leads to the fastest dynamic distance algorithm with $O(n^{1.58})$ update time. The earlier use of the Frobenius form maintained the dense change of basis $K$ explicitly and required $\tilde O (n^2)$ time per update [KS23]. Our key observation is that this change of basis is highly structured, which lets us maintain it implicitly. This gives the first subquadratic dynamic algorithm for the Frobenius normal form and characteristic polynomial for generic matrices.Authors: Sebastian Bruchhold, Matthias Mnich, Karolina Tammemaa, Morten Weber, Michalis Xefteris, Bart Zondervan
We study makespan minimization on unrelated machines with the additional goal of constructing diverse schedules: Instead of outputting a single schedule, we seek a collection of schedules with provable makespan guarantees and substantially different job assignments. Committing to a single schedule in advance may be undesirable. Processing times may be uncertain, and constraints or domain knowledge may emerge later, so $k$ schedules of similar quality offer meaningful alternatives. We measure pairwise diversity by the weighted Hamming distance between job assignments and study the two standard objectives in the diverse-solutions literature: max-sum diversity, which maximizes the total pairwise distance between schedules, and max-min diversity, which maximizes the smallest pairwise distance. For the max-sum objective, we show that optimal diversity can be achieved in polynomial time without sacrificing the classic makespan approximation factor. For every feasible makespan target $T$, we can compute $k$ schedules of makespan at most $2T$ whose max-sum diversity is optimal among all $k$ schedules of makespan at most $T$. Therefore, we match the classic factor-$2$ makespan guarantee of Lenstra, Shmoys, and Tardos (Math. Prog., 1990) and preserve optimal diversity. For the max-min objective, we show that the diversity problem is inherently harder. Namely, we show that, even without makespan constraints, deciding whether three schedules of given pairwise diversity exist is NP-hard. We complete this with two complementary bicriteria approximation algorithms for every fixed $k$ and $\varepsilon \in (0,1)$. The first preserves almost all of the optimal max-min diversity with makespan at most $(3\lceil12/\varepsilon\rceil+1)T$. The second keeps the makespan arbitrarily close to the classic $2$ guarantee while achieving a $\frac{1}{2}(1-\varepsilon)$ fraction of the optimal max-min diversity.Authors: Zhenyu Wang
In the Unsplittable Capacitated Vehicle Routing Problem (UCVRP), we are given a set $V$ of $n$ clients with normalized demands $d_v \in (0,1]$, a depot $r$, a unit vehicle capacity, and symmetric metric travel costs $c$ on $V \cup \{r\}$. We seek a collection of routes of minimum total cost that start and end at $r$, serve each client's entire demand on a single route, and respect the unit capacity constraint $\sum_{v \in V(R)} d_v \le 1$ on every route $R$, where $V(R)$ denotes the clients served by $R$. This models deliveries from a common depot in which each customer's order must be delivered in a single trip. UCVRP generalizes the metric traveling salesman problem (TSP) and is therefore NP-hard. Capacity constraints add a packing difficulty: when all clients are colocated away from the depot, minimizing the route cost is equivalent to minimizing the number of bins in bin packing. Consequently, UCVRP admits no polynomial-time approximation ratio below $3/2$ unless $\textbf{P=NP}$ (Grandoni, Mathieu, and Zhou, 2023). The classical $3.5$-approximation has been improved through several recent advances; in particular, Zhao and Xiao (2026) recently obtained a $(2+\ln 2+\varepsilon)$-approximation. In this paper, we give a deterministic $(5/2+\varepsilon)$-approximation algorithm running in $n^{O(1/\varepsilon)}$ time for every rational $0<\varepsilon\le1/9$, applicable to general capacity and arbitrary positive demands. Our algorithm uses local search to select routes through one client with large demand and clients with small demands. It constructs candidate routes using endpoint quota trees after rounding demands and creating vertex copies. We combine these routes with those obtained by matching and set packing, keeping their client sets disjoint. The remaining clients are served by partitioning a tour constructed using weighted graphic matroid parity.Authors: Ebrahim Ghorbani, Raul Lopes, Matthias Mnich
In the ARRIVAL problem, a token travels through a switch digraph: at every vertex, it leaves along one of two out-arcs, and the two are used alternately. The question is which of two terminals the token reaches first. ARRIVAL lies in $\mathsf{NP} \cap \mathsf{coNP}$, but no polynomial-time algorithm is known.The fastest known algorithms turn some vertices into terminals and search for consistent guesses of the numbers of tokens that these vertices send out. The first, due to Gärtner et al. [ICALP 2021], searches all vertices at once with an algorithm for fixed points of monotone maps, and the second, due to Haslebacher [ICALP 2025], searches one vertex at a time by binary search. Both search for a fixed point of the same map, which returns how many tokens arrive at the guessed vertices. We guess the vertices in blocks of $k$, between these two extremes, which needs a search in $k$ dimensions with few evaluations of this map. To do so, we build on the connection between ARRIVAL and $\ell_1$-contractions established in the second of these works. We search with $\ell_1$-centerpoints of the remaining guesses, which are guaranteed to exist by Haslebacher et al. [FOCS 2025], and which we approximate deterministically. In order to prove our results, we show how to find the least fixed points of maps from $\{0, \ldots, N\}^k$ to itself that have unit increments. For ARRIVAL on $n$-vertex switch digraphs, this gives run time $2^{\mathcal{O}(n^{1/3} \cdot \log^{2/3} n)}$, improving the previous time bound of $n^{\mathcal{O}(\sqrt{n})}$. We work with the more general \garrival problem, with many tokens and several terminals, and solve it in the same time when there are at most $2^n$ tokens.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: 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: 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.