Theory of Computing Report

Authors: Chen Xu

For two distinct binary words of length $n$, the separating words problem asks for a small deterministic finite automaton that accepts exactly one of them. Chase proved a $\widetilde O(n^{1/3})$ upper bound using a complex-analytic estimate for sparse polynomials. We replace that estimate by a finite-difference argument and a second-order real recurrence cutoff. The resulting elementary proof gives an explicit bound of $O(n^{1/3}(\log n)^{7/3})$ states.

Authors: Joshua Brakensiek, Yeyuan Chen, Aaron Putterman, Zihan Zhang, Kai Zhe Zheng

We give a deterministic polynomial-time list-decoding algorithm for Reed-Solomon codes over prime fields that approaches list-decoding capacity for every evaluation set and every constant rate.

Authors: Shashaank Khanna

Fourier-Motzkin elimination computes an inequality description of the projection of a polyhedron onto a subset of its coordinates by eliminating one variable at a time. It is used in several areas of optimisation and computer science, and it is a standard way of obtaining the entropic constraints of a causal structure, where the marginalisation over the latent variables produces such a projection. Its limitation is the growth of the intermediate systems of inequalities, which can be doubly exponential in the number of eliminated variables even though the projection itself grows only as a single exponential. In practice the computational overload of the method therefore depends on two choices: how the redundant inequalities are removed after each step, and the order in which the variables are eliminated. We consider both. We first show, by an explicit example, that Imbert's redundancy test cannot be interleaved with redundancy removal by linear programming. We show that the two methods, however, can be combined soundly if the derivation records used by Imbert's test are re-initialised after every step at which linear programming is used. We then propose a rule for choosing the elimination order of the variables that gives a significant computational advantage, however, at the cost of increased resource usage. We demonstrate this advantage on some random polytopes, where the rule reduces the running time by factors of between 6 and 25 compared with the same elimination under a fixed order. For entropic descriptions of causal structures, with more than 250 inequalities and more than 100 variables to eliminate, our rule keeps the number of inequalities handled at each step one to two orders of magnitude lower than a fixed order.

Authors: David Miloschewsky, Supartha Podder, Dorian Rudolph

Relativization is concerned with comparing computational models with black-box access to an oracle. For promise problems, black-box access is not canonical due to inputs outside of the promise being unconstrained. We study two semantics for such access. Under robust queries, a machine must correctly answer regardless of the completion of the problem,, while loose access requires that the internal choices of a machine do not change based on off-promise queries. Our first result separates the language and promise settings. Namely, we construct an oracle $O$ such that $\mathsf{P}^O = \mathsf{BQP}^O = \mathsf{AWPP}^O$, but $\mathsf{PromiseBQP}^O\not\subseteq\mathsf{PromiseP}^O_{\mathsf{/poly}}$. In particular, $\mathsf{BPP}^O = \mathsf{BQP}^O$, but $\mathsf{PromiseBQP}^O \neq \mathsf{PromiseBPP}^O$, showing that results for languages need not transfer to promises. Next, we use loose queries to strengthen the upper bound on the Quantum-Classical Polynomial Hierarchy from $\mathsf{P}^{\mathsf{PP}^{\mathsf{PP}}}$ to $\mathsf{QCPH} \subseteq \mathsf{BP\cdot PP} \subseteq \mathsf{PromiseBPP}^{\mathsf{PP}}$. The same proof also shows $\mathsf{PP}^\mathsf{PromiseBQP} = \mathsf{PP}$. Additionally, we show that $\mathsf{PromiseBQP}$, even when given quantum advice, is self-low under robust queries. Finally, we exhibit an obstruction to transferring language-level counting results to promise classes. Although $\mathsf{AWPP}$ and $\mathsf{APP}$ are low for $\mathsf{PP}$, a corresponding promise analogue would collapse the counting hierarchy as $\mathsf{GapP} \subseteq \mathsf{FP}^{\mathsf{PromiseAWPP}}$. This motivates the introduction of $\mathsf{PromisePostBQP^*}$, which restricts $\mathsf{PostBQP}$ to input-indepencent postselection. By showing that it is low for \PP, we obtain $\mathsf{PP}^{\mathsf{PromiseYQP^*}} = \mathsf{PP}$.

Authors: Sarita de Berg, Jacobus Conradi, Peter Kramer, André Nusser, Sampson Wong

The dilation of a geometric graph measures how much longer the path between pairs of points becomes when restricted to graph edges, rather than following the direct path through the ambient space. The minimum dilation tree of a point set is the spanning tree with minimum dilation, where edge lengths in the tree are given by distances in the ambient space. In the Euclidean plane, computing the minimum dilation tree is NP-hard, but no hardness of approximation result is known. On the other hand, the minimum spanning tree is an $(n-1)$-approximation to the minimum dilation tree, but no asymptotically-better approximation algorithm is known for general point sets in the Euclidean plane. We give the first sublinear approximation algorithm for the minimum dilation tree in the Euclidean plane. Our approximation ratio is $\tilde{O}(n^{14/15})$ and our algorithm runs in polynomial time. This resolves an open problem proposed by Eppstein in 1996.

Authors: Karim A. Adiprasito, Daniel Kalmanovich, Yaar Solomon

We study the Longest Edge Bisection (LEB) process as a dynamical system on the projective shape space of simplices. A long-standing conjecture going back to Adler and Rivara-Levin and motivated by finite-element mesh refinement, often taken as a standing assumption, is that this procedure is non-degenerate and, in fact, in a certain way periodic. We prove: \begin{itemize} \item There are 3-dimensional simplices such that the longest edge-bisection algorithm degenerates. \item There is an open set of 4-dimensional simplices on which the longest edge-bisection algorithm degenerates. \item If parametrizing the space of $d$-dimensional simplices by independent standard Gaussian vectors, then as $d$ increases, a random simplex degenerates asymptotically almost surely. \end{itemize} This is realized through exhibiting hyperbolic behaviour of the LEB process. We also exhibit elliptic behaviour that is nonperiodic.

Authors: Guanlin Mo, Kangke Cheng, Hu Ding

Delaunay triangulations are a fundamental class of plane spanners, and determining their worst-case stretch factor has been a longstanding problem in computational geometry. We prove an upper bound of 1.65, improving the previous bound of 1.998 and reducing the gap to the known lower bound of 1.5932 by a factor of more than seven. The result holds for every planar Delaunay triangulation, including configurations with collinear or cocircular sites. Our main contribution is a Bellman formulation of the disk-chain bound underlying the proof. By comparing shortest-path length with additive progress along the query segment, we obtain an exact recursion whose state records only the current disk, the incoming chord, and the difference between two prefix distances. We show that a bound for this chain class holds if and only if a potential satisfies three local inequalities for initialization, transitions, and termination. The associated Bellman value function is the pointwise smallest feasible potential, giving a precise target for constructing an upper bound. We construct such a potential using a function of one variable. Geometric monotonicity reduces its feasibility to inequalities that are affine in this function and its derivative. A spline construction, certified by exact arithmetic and rigorous interval bounds, yields the stretch bound of 1.65. We also give a dual certificate showing that every feasible quadratic profile under the same conditions requires a certified constant greater than 1.67.

Authors: Kangke Cheng, Guanlin Mo, Shihong Song, Hu Ding

Fairness in clustering has attracted sustained research interest, motivated by the need to ensure equitable representation of protected groups in machine learning applications. We study fair $k$-means clustering in Euclidean space, where the proportion of each protected group in every cluster must lie within specified lower and upper bounds. These constraints make it challenging to determine both cluster centers and point assignments. We propose an approximation algorithm that combines a linear programming relaxation with geometric transformations of the input to construct candidate center sets. Given a $ρ$-approximate algorithm for weighted $k$-means and any $ε>0$, our algorithm returns a fractional solution whose cost is at most $1+(3-1/Γ)ρ+O(ε)$ times the optimal integral fair cost, where $Γ\approx6.357$ is an upper bound on the integrality gap of the standard Euclidean $k$-means LP. With a PTAS as the subroutine, the approximation ratio becomes $3.8427+O(ε)$, improving the previous factor of $5+O(ε)$ to below $4$. The solution satisfies all fairness constraints exactly and can be rounded to an integral assignment with a bounded additive violation of fairness and no increase in cost. The same approximation guarantee extends to the $k$-sparse Wasserstein barycenter problem.

Authors: Tancredi Schettini Gherardini

A convex body is mono-monostatic if, resting under gravity on a horizontal plane, it has exactly one stable and one unstable equilibrium position. Smooth mono-monostatic homogeneous bodies exist (the Gömböc of Domokos and Várkonyi), and Lángi proved that (homogeneous) mono-monostatic polyhedra exist; although no explicit example appears to have been published, to the author's knowledge. We construct explicitly two such mono-monostatic polytopes, the smaller one having $56946$ faces; importantly, we certify them: the polytope is presented as an intersection of half-spaces with rational data, and a certifying verification establishes, using exact rational arithmetic for every decisive comparison, that the body has equilibrium signature $(S,H,U)=(1,0,1)$ with respect to its own exact centroid, with explicit nondegeneracy margins. We describe the geometric obstructions that make naive discretisations of smooth mono-monostatic bodies fail, the adaptive construction that overcomes them, and the certification strategy. While the result itself is not strikingly novel, we emphasise the non-standard (but increasingly more common) methodology: the entire programme, i.e. experiments, constructions and the verifier itself, was implemented by AI agents under human mathematical direction. We argue that exact certification of numerically discovered objects is the natural contract between such AI-assisted workflows and mathematical standards of rigour.

Authors: Mark Braverman, Or Zamir

Consider a permutation of $[n]$ whose values arrive one at a time. We resolve two questions about the space needed to decide natural properties of such input: First, computing the parity of the permutation requires $Θ(n)$ bits, even with randomization and constant error, and a constant number of passes. Second, every permutation pattern of length three can be detected deterministically in one pass using $O(\log n)$ bits. Together with the 2026 lower bounds of Berendsohn, this completes the classification of fixed permutation patterns; The optimal space complexity is $Θ(\log n)$ for monotone patterns and patterns of length at most three, and $Θ(n)$ for every other pattern. As a consequence, we observe that we can verify BST traversals in streaming with logarithmic memory.

Authors: Brandon Augustino, Shouvanik Chakrabarti, Enrico Fontana, Dylan Herman, Junhyung Lyle Kim, Guneykan Ozgul, Nadezhda Voronova

We establish a near-linear quantum query lower bound for high-accuracy convex optimization over an explicit family of $n$-dimensional ellipsoids. We focus on linear optimization with an explicitly given objective, where the feasible set is accessed through a membership oracle. We show that any algorithm that, for every unit linear objective, returns an exactly feasible point with additive objective error $Θ(n^{-2})$ requires $Ω\!\left(\frac{n}{\log n\,\log\log n}\right)$ membership queries. The same lower bound can be shown to hold if the returned point is only required to be approximately feasible, within $Θ(n^{-2})$ distance from the feasible set. This resolves, up to logarithmic factors, an open question posed by Chakrabarti, Childs, Li, and Wu~(\textit{Quantum}, 2020) and by van Apeldoorn, Gilyén, Gribling, and de Wolf~(\textit{Quantum}, 2020). Coupled with the upper bounds in these papers, the query complexity of high-accuracy convex optimization is characterized tightly up to logarithmic factors. The proof is built around a lower bound for determinant computation that is derived via a novel polynomial method based on Fourier-rank. In the continuous matrix phase-query model, computing the determinant of a real $n\times n$ matrix requires at least $n/2$ matrix-vector product queries. The construction also yields an $Ω(n)$ phase-query lower bound for estimating the minimum eigenvalue of a real symmetric $n\times n$ matrix to additive accuracy $Θ(n^{-2})$. These results extend the determinant and minimum-eigenvalue lower bounds of Childs, Hung, and Li~(ICALP 2021) from finite fields to the real-valued setting. Based on the same constructions, we also prove a near-optimal gradient-query lower bound for constant-accuracy optimization of smooth and strongly convex functions.

Authors: Yaowei Long, Seth Pettie, Thatchaphol Saranurak

For an undirected graph $G = (V,E)$ and a fault bound $f$, an edge-fault-tolerant connectivity labeling scheme assigns short labels to vertices and edges, so that for any vertex pair $(s,t)$ and failed edge set $F\subseteq E$ with $|F|\leq f$, the connectivity between $s$ and $t$ in $G-F$ can be answered by inspecting only the labels of $s$, $t$ and edges in $F$. In this paper, we present a labeling scheme that uses $O(\log^{2}n)$-bit labels that can be computed in deterministic polynomial time. This improves upon the previous $\tilde{O}(\sqrt{f})$ deterministic bound of [Long, Pettie, Saranurak'25], and even slightly improves the $O(\min\{f+\log n,\log^{2}n\log f\})$ randomized bound of [Dory, Parter'21] and [Long, Pettie, Saranurak'25] when $f = Ω(\log^{2}n)$. Moreover, for a general $f$, this is the first labeling scheme that produces an $\tilde{O}(1)$-size labeling which is simultaneously correct across all queries. Our approach combines the cycle-space-based labeling scheme from Dory and Parter with a recent result by [Knauer'26] on sparse cycle bases.

Authors: Eren Ercan

Let $A\in\mathbb{R}^{m\times n}$ have columns of Euclidean norm at most one. We prove that $\operatorname{disc}(A)\le2395\left(1+\log_+\frac n9\right)^{1/4}+2\sqrt2$. Here $\log_+t=\max\{0,\log t\}$. Building on Bansal and Jiang's affine spectral independence framework, we remove the $(\log\log n)^{7/4}$ factor from their bound. The fourth root comes from balancing the logarithmic decrease in the alive dimension against the fourth power of the row thresholds. Historical exponential sums control the covariance budget across size classes with summable thresholds. An exact threshold-sum certificate gives the coefficient $2395$, and rounding at most eight remaining fractional coordinates costs $2\sqrt2$. The finite construction also gives partial colourings from any prescribed starting point and at any prescribed depth, preserving existing signs. We formalize the partial- and full-colouring theorems in Lean, including the finite trajectory, exact threshold sum and final rounding, with Bansal--Jiang Theorem A.4 as the sole external research theorem assumption.

Authors: Syamantak Kumar, Purnamrita Sarkar, Kevin Tian, Yusong Zhu

Sparsity is a powerful structural resource in optimization and statistics. We develop frameworks for leveraging sparsity in sampling problems over the Hamming slice $\mathcal{X}_k^d:=\{\mathbf{x}\in\{\pm 1\}^d:|\{i:\mathbf{x}_i=1\}|=k\}$, in high-dimensional regimes where $k\ll d$ (i.e., where $\mathcal{X}_k^d$ is \emph{highly magnetized}). We use our frameworks to design improved samplers for canonical problems in the study of \emph{Ising models} and \emph{Bayesian sparse linear regression}. Our first main result considers the \emph{Sherrington--Kirkpatrick} (SK) model restricted to fixed-magnetization slices $\mathcal{X}_k^d$. We give a polynomial-time sampler for fixed-magnetization SK models at any inverse temperature $β>0$, under arbitrary external fields, provided that $k\le c_βd$ for an appropriate constant $c_β$. By combining this result with an annealing strategy for estimating normalizing constants, we obtain polynomial-time samplers for the SK model at arbitrarily low temperatures under a sufficiently strong external field of strength $h$. In the large-$β$ limit, our framework permits sampling at field strengths within constant factors of the \emph{Almeida--Thouless line} delineating the replica-symmetric and replica-symmetry-breaking regions ([dAT78]), improving polynomially over the field strength $h(β)$ required by the recent work of [BAR26]. Our second main result concerns the measurement complexity of polynomial-time Bayesian sparse linear regression. Recent work by [KSTZ25] shows how to sample from the canonical \emph{Gaussian spike-and-slab posterior} with expected sparsity $k$, at any signal-to-noise ratio, given $n\gtrsim k^3\log^3 d$ Gaussian measurements. We improve this requirement to $n\gtrsim k^{3/2}\log^2 d+k\log^3 d$, using a common sparsity-aware framework underlying both our results.

Authors: Kenny Chen, Mina Doosti, Ryan Sweke, Chirag Wadhwa

We introduce a framework for distributed quantum inference under communication constraints. In our model, $m$ distributed nodes each receive one copy of an unknown $d$-dimensional quantum state $ρ$, before communicating via a constrained one-way communication channel with a central node, which aims to infer some property of $ρ$. This framework generalizes the classical distributed inference framework introduced by Acharya, Canonne, and Tyagi [COLT 2019], by allowing quantum resources such as quantum communication and shared entanglement. Within this setting, we focus on the fundamental problem of quantum state certification: Given a complete description of some state $σ$, decide whether $ρ=σ$ or $\|ρ-σ\|_1\geq ε$. Additionally, we focus on the case of limited communication between distributed nodes and the central node: we assume each communication channel is limited to only $n_c$ bits and $n_q$ qubits with $n_c + n_q \leq \log d$. When all nodes can make use of a shared source of randomness, we show that the copy complexity of distributed state certification is $Θ(\frac{d^2}{2^{n_q} 2^{n_c/2}ε^2})$. We further demonstrate that shared randomness is necessary to achieve the above complexity, by proving an $Ω(\frac{d^3}{4^{n_q} 2^{n_c} ε^2})$ lower bound in the $\textit{private-coin}$ setting. Moreover, we develop a private-coin algorithm that matches this bound up to a $\sqrt{\log d}$ factor, showing this complexity is near-optimal. Together, our work establishes a general framework for distributed quantum inference with communication constraints and characterizes the complexity of distributed state certification with limited communication.

Authors: Florian Krowiorz, Robert Scheffler

Graph search algorithms and their corresponding graph search trees are commonly used in algorithmic graph theory. In recent years, the recognition problem of these graph search trees has received significant attention. So far, the research has focused on two types of search trees: first-in trees that behave like BFS-trees and last-in trees that behave like DFS-trees. The search tree paradigms differ from each other by the parent a vertex is connected to. In first-in trees, it is the first visited neighbor, while in last-in trees it is the last neighbor visited before that vertex. Here, we will generalize these concepts of graph search trees by allowing every preceding neighbor of a vertex to be the parent. We study the complexity of the recognition problem of these generalized graph search trees. We present NP-completeness proofs for most searches. We also show that the problem is trivial for Generic Search and polynomial-time solvable for several searches on bipartite graphs and chordal graphs. We also study the question how fixing the start vertex influences the complexity of the problem.

Authors: Yuichi Yoshida

Digraphs with constant cut balance admit nearly linear directed cut sparsifiers. This condition requires the total arc weights in the two directions of every cut to be within a constant factor of each other. We ask whether this condition also permits nearly linear spectral sparsification with respect to the energy of the nonlinear directed Laplacian. For a weighted digraph $G=(V,E,w)$, let \[ Q_G^+(x)=\sum_{(u,v)\in E}w_{uv}(x_u-x_v)_+^2, \qquad (t)_+:=\max\{t,0\}. \] This energy agrees with the outgoing-cut function on binary vectors. A spectral sparsifier is a nonnegatively reweighted subgraph that preserves $Q_G^+(x)$ within a factor of $1\pm\varepsilon$ simultaneously for all $x\in\mathbb R^V$. We show that cut balance alone does not yield nearly linear spectral sparsifiers: for constant error, the worst-case support size for simple unweighted Eulerian digraphs is $\widetildeΘ(n^{3/2})$, although Eulerian digraphs are perfectly cut-balanced and admit nearly linear directed cut sparsifiers. In contrast, we prove that every $n$-vertex tournament has a spectral sparsifier with $\widetilde O(n/\varepsilon^3)$ arcs, without any assumption on its cut balance. This includes the transitive tournament, whose cut balance is unbounded. Thus perfect balance does not guarantee nearly linear spectral sparsification, while unbounded imbalance does not preclude it. Finally, we use convex duality to show that preserving $Q_G^+$ also preserves, for every feasible demand vector, the optimum quadratic cost of a nonnegative flow. Hence the guarantee contains information beyond directed cut values.

Authors: Qiao-Long Huang, Xiao-Shan Gao

Let $A, B \in \mathbb{Z}[x_1, \dots, x_n]$ be multivariate polynomials with integer coefficients and let $G = \gcd(A, B)$. We present an algorithm for computing $G$ whose expected bit complexity is asymptotically linear in all fundamental parameters: the number of variables $n$, the term count $T = \max\{\|A\|_0, \|B\|_0, \|G\|_0\}$, the total degree $D$, and the logarithmic coefficient sizes $\log\Hi$ and $\log\Ho$, where $\Hi$ bounds the coefficients of the inputs and $\Ho$ bounds those of the GCD. The bit complexity is characterized by the clean bound \[ \widetilde{O}\bigl( n \cdot T \cdot D \cdot \log\Hi \cdot \log\Ho \bigr). \] To our knowledge, this is the first sparse GCD algorithm over the integers that achieves linear complexity in all these parameters simultaneously. The integer algorithm is built upon a new field GCD algorithm. For $A, B \in \K[x_1, \dots, x_n]$ over a field $\K$ with $\operatorname{char}(\K) = 0$ or $\operatorname{char}(\K) > °G$, we give the first algorithm that computes $G = \gcd(A,B)$ with expected \[ \widetilde{O}\bigl( n \cdot T \cdot D \bigr) \] field operations, which is both input- and output-sensitive. The key technical contribution behind both algorithms is a derivative-aided separated Hensel lifting technique introduced in this paper. By introducing an auxiliary variable and leveraging derivative information, our scheme extracts all partial exponents via a single $z^2$-lift per variable, achieving constant sequential depth $O(1)$. This stands in sharp contrast to classical Hensel lifting, which requires $O(D)$ sequential lifting steps and suffers from representation densification in the sparse setting. The field algorithm is then extended to the integer case through modular reduction and rational reconstruction.

Authors: Hongyao Ma, Will Ma, Matias Romero

On-demand platforms face the fundamental challenge of fulfilling time-sensitive jobs with independent workers who may decline offers. To minimize delays and unfulfilled jobs, platforms frequently raise the offered wage sequentially following each rejection. However, the interaction between these dynamic price adjustments and the specific sequence in which workers are approached has been overlooked. In particular, if the best-suited workers (e.g., closest to the job) are also ranked earliest in the sequence, then those workers would see the lowest offered wages and may decline, leading to poor system outcomes where less-suited workers end up seeing the raised wages and accepting the job. We study the sequential offering problem to maximize expected welfare or platform profit by jointly optimizing the ranking of workers and the pricing trajectory. Surprisingly, our main result establishes that if the reservation wage distribution exhibits a non-increasing and convex density function (e.g., Uniform, Exponential), welfare is maximized by greedy ranking and wages optimized via backward induction. For arbitrary distributions, we prove that greedy ranking achieves a tight $n/(2n - 1)$ fraction of the prophet benchmark. Numerical results for settings beyond the distributional assumptions find welfare losses well below those allowed by the universal guarantee, even in families where greedy is provably suboptimal. This suggests that rather than sending initial "low ball'' offers to worse matches, platforms should stick with greedy ranking and optimize the wage offerings by appropriately taking the continuation value of the downstream offers into consideration.

Authors: Elfarouk Harb

We improve the best known lower bound on the integrality gap for weighted unit-demand multicommodity flow on trees from $1/4$ to $2/5$, improving on the long-standing bound of Chekuri, Mydlarz, and Shepherd~\cite{CMS}. We give the proof in two stages. First, a surprisingly simple packing lemma and an inductive coloring argument give an intermediate bound of $4/11$. We then refine the argument to obtain $2/5$.

Authors: Miguel A. Mini, Flávio K. Miyazawa, Gabriel M. Silva, Yoshiko Wakabayashi

This paper presents significant upper-bound improvements for dynamic 2D square bin packing, where square items arrive and depart over time and the objective is to minimize the peak number of concurrent active unit bins. In our model, repacking is permitted only within a destination bin upon item arrival; migration between active bins is strictly forbidden. By introducing a streamlined two-list algorithm and proving a tight $5/16$ occupied-area bound for Next-Fit Decreasing Height, we reduce the upper bound on the asymptotic competitive ratio for arbitrary squares from 4.2154 down to 3.918, breaking a longstanding theoretical ceiling. For restricted variants, we establish asymptotic competitive ratios of at most 3.356 for unit-fraction side lengths and 2.211 for power-fraction side lengths.

Authors: Serge Melnikov

This paper presents a high-performance SIMD acceleration framework for the Steinhaus-Johnson-Trotter permutation generation algorithm, targeted at modern x86-64 architectures using the AVX2 instruction set. By exploiting a novel combinatorial space partitioning with pre-calculated index offsets combined with single-cycle vector byte shuffling (_mm256_shuffle_epi8), our dual-lane vectorized implementation processes two independent, concurrent permutation streams within a single 256-bit YMM register under a uniform execution mask. Empirical evaluations demonstrate a 3$x$ performance throughput increase over both Donald Knuth's Algorithm P (TAOCP Vol 4A), which we previously accelerated by 3$x$ in scalar code, and the recent Ring-Cascade algorithm by Yusheng Hu. The proposed software architecture maintains cross-compiler compliance, completely avoids store-forwarding memory stalls during hot loops, and is validated up to order $n=11$ with a benchmark performance of ~1.27 billion CPU cycles for $n=13$ on native hardware.

We invite applications for a postdoctoral position in quantum complexity theory at Concordia University in Montréal, working with Honghao Fu and Benjamin Lovitz. Funding is available until March 2028.

We welcome candidates with a strong research background in quantum complexity theory or closely related areas of theoretical computer science, quantum information, and mathematics.

Website: https://www.concordia.ca/gradstudies/postdocs.html
Email: benjamin.lovitz@concordia.ca

By shacharlovett

We present a methodology for constructing interactive proof systems. This methodology, which is implicit in prior works, consists of reducing the original claim to an iteratively generated sequence of claims such that each claim is (interactively) generated based on the prior claim. Viewing each of these interactive generation steps as solving an adequate search problem, we present composition results that support a modular construction of interactive proof systems as well as their transformations to PCIPs (aka IOPs). The development of the foregoing methodology involves the explicit introduction of a few notions, which are of independent interest. These include ``dichotomous search problems'' (to be solved by protocols analogous to interactive proofs) and oracle-aided protocols (in which the oracle is a search problem rather than a decision problem). Using the foregoing methodology, we prove that every set in uniform-$\cal NC$ has a doubly-efficient PCIP. This result was conjectured by Arnon, Chiesa, and Yogev ({\em 37th CCC}, 2022), and our construction follows their ideas. Our contribution is in adapting their ``IP to PCIP'' transformation to the context of oracle-aided protocols and applying the foregoing methodology while following the ideas of Goldwasser, Kalai, and Rothblum ({\em 40th STOC}, 2008).

In the early to mid-1970s, my university classmate Ariel Rubinstein initiated a weekend hike from Jerusalem to the Dead Sea. A group of us left Jerusalem on Friday night, planning to reach the Dead Sea early the next morning. However, due to navigation errors and other obstacles, we didn’t arrive until noon. We were all exhausted and out of water. I then hitchhiked back to Jerusalem and was picked up by a kind driver, who was driving a massive truck.

The two-lane road from the Dead Sea (−392 meters) to Jerusalem (+800 meters) was steep, and from time to time, our truck overtook other vehicles in a rather dangerous fashion. Sensing my discomfort, the truck driver shared an interesting theory:

“You see, the engine of this truck is so strong — so strong — that whenever I start to overtake, I can always complete the maneuver safely!”

This struck me as incorrect. The ability to overtake safely depends not only on engine power, but also on factors like visibility, road conditions, and the distance and speed of oncoming traffic. I thought this might be a case where pointing out the mistake could actually matter — not just to us, but to the safety of everyone on the road. I decided to offer an explanation that avoided technical jargon like “function.”

“I think you’re mistaken,” I said, “Completing an overtake safely depends on several important factors — not just the power of your engine.” I elaborated a little further, and the driver listened with interest.

“Ohh, that’s what you think?” he replied. “Now, watch this!”

With that, the truck veered into the opposite lane in an especially dangerous maneuver. A few cars coming the other way swerved to the shoulder in panic, and — by a miracle — the truck completed the overtake without a collision.

I said nothing more and sat quietly, disheartened, waiting for us to reach Jerusalem.

Left: map of the hike; Right: Ariel Rubinstein

By Gil Kalai

Authors: Yan Zhong

A degree-$d$ polynomial source is the output of a polynomial map of degree at most $d$ over $\mathbb{F}_2$ on arbitrarily many uniform random bits. Khodabandeh and Shinkar (FOCS '26) proved that $\mathrm{Ber}(1/3)^{\otimes N}$ has statistical distance $1-o(1)$ from every constant-degree polynomial source and conjectured exponentially small overlap. Independently of Khodabandeh and Shinkar, Byramji, Kane, Morris, and Ostuni (RANDOM '26) asked for an explicit target distribution at distance $1-\exp(-N^{Ω_d(1)})$. We resolve both questions. For every fixed $d\geq1$, every degree-$d$ polynomial source has overlap at most $\exp(-c_dN)$ with $\mathrm{Ber}(1/3)^{\otimes N}$, where $c_d>0$ is independent of the seed length. For quadratics, $c_2=2^{-26}$ suffices. We amplify Khodabandeh and Shinkar's uniform separation of acceptance probabilities from non-dyadic parameters (numbers not of the form $a/2^b$ for integers $a$ and $b\geq0$). The result extends to other non-dyadic Bernoulli parameters and to coordinates that are Boolean functions of boundedly many bounded-degree polynomials. We also give a uniform deterministic hierarchy between adjacent degrees. Appending the outputs of disjoint AND gates on $d+1$ inputs to uniform seed bits yields flat degree-$(d+1)$ target distributions of entropy $k$ with overlap $\exp(-Ω_d(\min\{k,N-k\}))$ against every degree-$d$ source, for $\min\{k,N-k\}\geq2(d+1)$. This entropy dependence is optimal up to constants in the exponent among flat target distributions for fixed $d$. The construction has locality $d+1$ and uses $O(N)$ field operations to sample. At $k=\lfloor N/2\rfloor$, it handles $d\leq(1-\varepsilon)\log_2N/3$ with overlap $\exp(-N^{\varepsilon-o(1)})$ for fixed $0<\varepsilon<1$. The proof combines monotonicity of Gowers uniformity norms, pairwise independence of points in a random affine cube, and relative entropy.

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

We study the approximability of rank aggregation under the Ulam metric. In the \emph{Ulam median} problem, the goal is to find a ranking (permutation) minimizing the sum of its Ulam distances to the input rankings, while in the \emph{Ulam center} problem, the objective is to minimize the maximum such distance. We prove that, for every $0<\varepsilon< 1/34$, it is $\mathrm{NP}$-hard to approximate either Ulam median or Ulam center within a factor of $35/34-\varepsilon$, even when the input consists of only four rankings. We further show that unless P = NP, neither problem admits a polynomial-time additive approximation scheme. Prior to our work, only the exact versions of both problems were known to be $\mathrm{NP}$-hard, and that too only when the number of input rankings is unbounded [Fischer et al., ESA'25 and Bachmaier et al., J. of Discrete Algorithms'15]. Furthermore, our inapproximability results are optimal in terms of the number of input rankings since for three inputs it is already known to be polynomial-time solvable [Chakraborty, Das, Krauthgamer, SODA'21]. En route, we introduce a new general framework for reducing Boolean constraint satisfaction problems (CSP) to the Ulam median with only four inputs. As a specific instantiation of the reduction framework, we obtain our hardness-of-approximation results. The corresponding hardness for the Ulam center follows from a reduction from the Ulam median.

Authors: Juntai Zhou

We formulate the generalized hidden shift problem over arbitrary finite groups and obtain upper and lower bounds for the sample complexity in terms of group theoretic data.

Authors: Gabriele Radici, Massimiliano Sala

Deciding whether a system of multivariate quadratic equations over $\mathbb F_2$ has a solution is a classical NP-complete problem, and remains so for square systems, with as many equations as variables. The hardness of this problem is one of the cornerstones of nowadays post-quantum cryptography. Let $\MQ_0(n)$ and $\MQ_1(n)$ denote the sets of square quadratic systems in $n$ variables having respectively no solutions and exactly one solution. $\cup_{n\geq 2} \MQ_0(n)$ is a coNP-complete language, while $\cup_{n\geq 2} \MQ_1(n)$ lies in DP. It is known that $\lim_{n\to \infty} |\MQ_1(n)|/|\MQ_0(n)|=1$. Here we prove the explicit finite-$n$ bounds \[ |\MQ_0(n)|<|\MQ_1(n)| \le \left(1+\frac{1}{2^n-1}\right)|\MQ_0(n)|, \] More generally, let $Q_d$ be the space of polynomial functions $(\FF_2)^n\to\mathbb F_2$ of degree at most $d$, and let $α_k$ count square systems in $(Q_d)^n$ having exactly $k$ solutions. Then \[ α_0<α_1 \le \left(1+\frac{1}{2^n-1}\right)α_0\,, \qquad 2\le d\le n \,. \] The proof combines matroid and coding-theoretic methods. We interpret $(\FF_2)^n$ as the ground set of the evaluation matroid of $Q_d$, express $α_0$ and $α_1$ through characteristic polynomials, and use a Whitney-type sign-reversing involution to show that the only terms that can push $α_1-α_0$ below $α_1/2^n$ come from the elements of a matroid port. These are identified with minimal-support words of the Reed--Muller code $\RM(n-d-1,n)=\RM(d,n)^\perp$; the required estimate then follows from the MacWilliams identity, the minimum-distance bound $2^{d+1}$, and the even-weight structure of the code.

Authors: Noah Golowich

We study the fine-grained complexity of computing approximate Nash equilibria and approximating the value of free games in the regime where the approximation error vanishes. Under the PCP for PPAD and ETH for PPAD conjectures, we show that computing $\varepsilon$-approximate Nash equilibria in 2-player $N$-action normal-form games requires time $N^{(\log(N)/\varepsilon^2)^{1-o(1)}}$, thus showing that the classical Lipton-Markakis-Mehta algorithm (2003) is optimal through all regimes of $\varepsilon = ω(1/\sqrt{N})$. While such optimality was known in the constant-$\varepsilon$ regime (Rubinstein, 2016), previous work could only rule out significantly smaller running times of $N^{O(\log(N)/\varepsilon)}$ in the regime $\varepsilon = o(1)$. Using similar techniques, we then establish an analogous tight lower bound of $N^{(\log(N)/\varepsilon^2)^{1-o(1)}}$ under ETH for $\varepsilon$-additive value estimation in free games, when $\varepsilon \geq 2^{-o(\sqrt{\log N})}$, answering a question of Aaronson, Impagliazzo, and Moshkovitz (2014).

Authors: Stuart Hadfield

Compressed quantum encodings aim to overcome hardware limitations towards tackling challenging problems at scale, with many classical variables mapped onto noncommuting observables of fewer qubits. Classically, relaxations such as the semidefinite program formulation of MaxCut trade solution quality for computational efficiency. By contrast, quantum relaxations based on compression can amplify the worst-case complexity of the problem being solved. We study quantum random access optimization (QRAO), a special case of the Pauli correlation encoding (PCE) framework that assigns up to three binary variables to the Pauli $X$, $Y$, and $Z$ observables of each qubit, with the packing choices determining the compressed Hamiltonian to be optimized. We identify explicit QRAO optimal energy promise problems complete for NP, StoqMA, and QMA, with inverse-polynomial promise gaps for the latter two. Our problem reductions preserve inverse-polynomial promise gaps without requiring gadgets or ancillas. For any prescribed packing, we show that weighted MaxCut instances compress, up to a known shift and rescaling, to arbitrary nonnegative-weight pairwise Pauli couplings allowed by the packing. For QRAO, using one aligned axis gives an NP-complete energy problem. Using two or three positive aligned Pauli axes generally gives QMA-complete problems, while their bipartite restrictions lie in StoqMA. We show that this computational hardness survives compilation and is practically relevant. Notably, this result applies directly to the current QRAO compiler implementation in Qiskit Optimization 0.7.0, confirming our hardness results are not artifacts of artificial or contrived packing rules. Altogether our results identify worst-case complexity barriers arising from quantum compression, while making no broad claims about typical cases or the performance and trainability of algorithm pipelines that use it.

Authors: Francisca Vasconcelos

We show that 2-fold Forrelation with inverse-polylogarithmic promise gap can be solved, with bounded error, by polynomial-size QAC$^0$ circuits. Unlike the standard oracle-based Forrelation algorithm, our circuits receive the input explicitly, in the same form as the AC$^0$ circuits against which Forrelation is known to be hard. At constant gap, this yields a natural promise-problem separation between QAC$^0$ and AC$^0$.

Authors: Kuize Zhang

In this paper, we characterize resilience for a labeled real-time automaton (LRTA). An LRTA is resilient if whenever a faulty event occurs, after sufficiently many events occur, the LRTA returns to normalcy and the occurrence of the faulty event is not leaked. The notion of resilience reflects the ability of an LRTA recovering from a faulty behavior, and hence can model an intelligent agent. We formulate one definition of resilience for an LRTA and give verification algorithms for the definition based on two basic tools --- concurrent composition and observer.

Authors: Mahmut Levent Doğan, Keiya Sakabe, Michael Walter

Convex optimization on polytopes arises in many areas of science. When the polytope is given implicitly or has exponentially many vertices and facets, standard methods may not apply or be ineffective. This is the case for moment polytopes, such as the entanglement polytopes, which play a foundational role in quantum information and algebraic complexity. They give rise to important entanglement measures and tensor parameters such as the quantum functionals, yet general effective methods for computing these quantities have been elusive. In this paper we address this challenge. We develop a first-order framework called Hadamard mirror descent to optimize suitable convex functions over moment polytopes and, more generally, the gradient sets of geodesically convex functions. It operates locally and does not rely on any explicit description of the polytope. Our framework extends mirror descent, an effective and widely used framework for convex optimization, from the Euclidean setting to Hadamard manifolds, and is motivated by a recent work by Hirai, which we interpret as a Hadamard version of mirror flow. Applying the framework to entanglement polytopes yields the first efficient first-order algorithms to compute the quantum functionals, the symmetric quantum functional, and the G-stable ranks, as well as a new direct algorithm for the non-commutative rank.

Authors: Cheng Xin

We study the query complexity of estimating scalar summaries of zigzag bar lifetimes from snapshot-adjacency bits. For graphs $G_1,\ldots,G_m$ on $n$ labeled vertices, let $\ell_b$ be the snapshot lifetime of a degree-one bar $b$ of the intersection zigzag. For a probability generating function $φ(x)=\mathbb{E}[x^R]$, the statistic $F_φ=\sum_bφ(\ell_b/m)$ includes normalized degree-$r$ total persistence and the mean generalized rank over a uniform time window. An exact identity underlies our algorithm: sample $R$ uniform times; the expected generalized rank between their minimum and maximum equals $F_φ$. For graphs that rank is the circuit rank of an intersection graph, so a nonlinear barcode functional becomes an average of edge and component counts, and no barcode is computed. Without spectral-gap, homology-state, or QRAM assumptions, this gives a quantum estimator with additive error $\varepsilon n$ and $\widetilde O(\sqrt{m(K+n)}/\varepsilon)$ queries when a bound $K\ge F_φ$ is supplied, against $\widetilde O(m\min\{n^2,(K+n)/\varepsilon^2\})$ classically, and an adaptive quantum variant with the same instance dependence. These estimators are optimal in two regimes. For every fixed power weight $x^r$, $r\ge2$, and for the uniform-window mean, the worst-case complexities are $\widetildeΘ(n\sqrt m/\varepsilon)$ quantum and $Θ(n^2m)$ classical. On sparse instances, under an explicit split-leakage promise met by power and binomial weights of logarithmic degree and the promise $F_φ\le K$, they are $\widetildeΘ(\sqrt{mK}/\varepsilon)$ and $\widetildeΘ(m\min\{n^2,K/\varepsilon^2\})$. The classical lower bounds hold against fully adaptive algorithms, and fewer than $m$ such statistics cannot determine the positive-lifetime histogram. All bounds concern snapshot access; with an explicit update stream, near-linear full-barcode algorithms are known.

Authors: Pramita Bagchi, Sushovan Majhi, Atish Mitra, Žiga Virk

Hilbert-space embeddings enable inference for populations of persistence diagrams, but separation between individual diagrams need not survive population averaging. We develop a framework for inference on population mean embeddings, with particular attention to the additive landmark representations PLACE and PALACE. Treating each diagram as one independent observation, we apply Hilbert-space limit theory to obtain covariance estimators, two-sample tests, and confidence balls under suitable moment conditions, without requiring a lower-distortion bound. For additive embeddings, we identify the population mean as an embedding of the mean counting measure and show that geometric separation of these measures alone cannot guarantee uniform testing power. We then introduce a model with latent template diagrams, missing features, and location perturbations. Under common or feature-specific prevalence conditions, a diagram-level lower-distortion certificate yields explicit lower bounds on population mean separation. These margins provide finite-sample uniform power guarantees, and an additional information-divergence comparison gives matching sample-complexity bounds over restricted scale ranges. Confidence sets yield lower bounds on transport separation of population mean measures and exclusion guarantees for specified structured alternatives. We also quantify how orthogonal truncation changes the certified signal and the approximation allowance needed for confidence sets targeting the full embedding, relating sample size, retained coordinates, and template separation. Simulations examine calibration, power, and coverage, and an analysis of resting-state connectivity from the Autism Brain Imaging Data Exchange illustrates the procedures.

Authors: Rostislav Staněk, Robert Arustamyan

In a weighted graph $G = (V, E)$, the maximum weight matching problem (MWM) asks for a matching (i.e. pairing) of its vertices, such that each vertex is paired with at most one other vertex and the total sum of weights of all edges connecting paired vertices is maximised. If the vertices of the graph correspond to points in the Euclidean plane and the weights to their pairwise Euclidean distances, we get the Euclidean maximum weight matching problem (Euclidean MWM). The best optimum-solution algorithm for this problem runs in $O(n^{2.5})$. Furthermore, there exists an FPTAS guaranteeing a $(1 - ε)$-approximation ratio, which runs in $O(m ε^{-1} \log ε^{-1})$ time. Heuristics with a subquadratic running time (with respect to the number of vertices $|V|$) are known, but often yield solutions of a modest quality. In this paper, we present a novel algorithm for solving the Euclidean MWM running in $O(n \log n)$ time and providing excellent solution quality, especially for larger instances. In particular, in our computational tests, the algorithm yielded optimum or near-optimum solutions for all test instances; the worst observed optimality gap was less than $1.38\%$. This makes the algorithm highly attractive for practical applications, especially when exact methods become computationally prohibitive due to the size of the instance.

Authors: Zimo Sheng, Mingyu Xiao

In \(d\)-\textsc{Hitting Set}, the input consists of a finite universe \(U\), a family \(\mathcal S\) of subsets of \(U\) with size at most \(d\), and an integer \(k\). The task is to decide whether at most \(k\) elements of \(U\) can intersect every set in \(\mathcal S\). For every fixed \(d\geq3\), we give a one-sided randomized kernel with \(O(k\log^3k)\) elements and a deterministic kernel with \(O(k^2\log k)\) elements for \(d\)-\textsc{Hitting Set}. In the one-sided randomized kernel, every NO-instance is always mapped to a NO-instance, and a YES-instance is mapped to a YES-instance with constant probability. The previously known kernels for \(d\)-\textsc{Hitting Set} contain \(O(k^{d-1})\) elements and \(O(k^d)\) sets. It has been asked in the literature whether \(d\)-\textsc{Hitting Set} allows kernels with \(O(k^{d-1-\varepsilon})\) elements for some constant \(\varepsilon>0\). In this paper, we answer this question affirmatively by giving near-linear element-kernels through a re-encoding of the instance. On the other hand, our kernel may still contain \(k^{O(d)}\) sets and the parameter $k$ may grow polynomially.

Authors: Abhinaba Chakraborty

To solve the fractional knapsack problem, Dantzig's greedy rule orders items according to their value-to-cost ratio. This ordering introduces priority issues. An arbitrarily small perturbation to the input can change the allocation if the budget is exhausted between two items with very similar ratios. To mitigate that problem, we introduce a two-stage rule. We group items sharing attributes within a radius $δ$. These groups are then evaluated in descending order of ratio, and divide their group's budget share without further ranking. Consider a group featuring an aggregate capacity $U_G$, unit costs contained in $[w^-,w^+]$, and a representative value $\widehat{v}$. The group's loss compared to the exact optimum is bounded by $\widehat{v}\, U_G\frac{w^+-w^-}{w^++w^-}+\varepsilon_v U_G$, in which $\varepsilon_v$ limits the group's internal value variation. Moreover, for any group size, this harmonic factor remains tight. The overall loss becomes restricted to the single budget-binding group whenever the grouping remains order-compatible; thus, groups containing at most $K$ items suffer a per-item loss of $\mathcal{O}(K/n)$. Should group ratio intervals exhibit an overlap of at most $ω$, an additive term $ωC$ degrades this bound. Within the separation margin between adjacent groups, the grouped allocation remains Lipschitz continuous with respect to cost data, exhibiting a modulus of $\frac{K}{w_{\min}}$. Computing this allocation takes $\mathcal{O}(n+m\log m+|Γ|\log|Γ|)$ time given $m$ groups and a boundary group $Γ$. Alternatively, the time complexity drops to $\mathcal{O}(n+m\log m)$ if a linear-time selection method identifies the boundary group's allocation.

Authors: Haolong Li, Xiaowei Wu

We study the cost-minimization prophet inequality problem, in which a decision-maker sequentially observes $n$ independent and identically distributed (IID) random variables. After each observation, the decision-maker must either accept the current realization and stop, or reject it and continue with the next variable. The goal is to minimize the selected value. Unlike the classical maximization setting, if none of the first $n-1$ values is accepted, the final realization must be selected. Esfandiari et al. (SIDMA 2017) showed that this problem does not admit constant-competitive online algorithms in general, which motivates subsequent work on restricted distribution classes, such as entire distributions (Livanos and Mehta, SODA 2024) and distributions with bounded extreme values (Livanos and Mehta, EC 2025). In this work, we focus on distributions with bounded support. For distributions supported on $[1,b]$, we characterize the competitive ratio of online algorithms as a function of both $b$ and $n$. We consider both distribution-aware and distribution-oblivious settings. In the distribution-aware case, we provide a nearly tight characterization of the optimal online algorithm, showing that its competitive ratio is at most $b^{(1-1/n)^n}$ for all $n\geq 2$. More significantly, we design a distribution-oblivious algorithm that achieves the same guarantee, with a sequence of predetermined thresholds that depend only on $b$ and $n$. Furthermore, we extend our analysis to the non-IID setting, where we show that a simple single-threshold algorithm attains an asymptotically optimal competitive ratio of $Θ(\sqrt{b})$.

Authors: Shina Guo, Weiguo Gao, Yuan Tang

Fast Fourier transforms on parallel machines incur two forms of data movement: processor-local transfers through the memory hierarchy and global redistribution between processors. Four-step FFT organizations switch the active transform dimension with one global transpose-like exchange, but this alone does not yield cache-efficient local computation. Cache-oblivious FFTs achieve asymptotically optimal local memory traffic through recursive layout transformations, whose direct materialization can require extra data-rearrangement passes and global exchanges. We present PACO, a fully cache-oblivious parallel FFT framework that reconciles these objectives. PACO executes LocalFFT -> OneGlobalPermutation -> LocalFFT. Its local stages recursively partition both transform and batch dimensions without knowledge of the cache parameters. Rather than materializing the transpose-like layouts induced by this recursion, PACO defers them, showing that they compose into a base-b digit-reversal permutation that is fused with the redistribution already required to change the local transform dimension. The resulting middle stage is a perfectly balanced parallel cache-oblivious digit-reversal permutation in which each source-destination processor pair exchanges exactly $N/p^2$ elements. Under an exact base-b slab decomposition in a hybrid ideal-cache/BSP model, PACO computes an N-point DFT exactly with maximum per-processor work $Θ((N/p) \log N)$ and maximum per-processor cache complexity $Θ((N/(pB))(1 + \log_M N))$, using exactly one global redistribution round. PACO returns canonical logical DFT coefficients under a factor-swapped target slab ownership. The single redistribution is necessary under the stated no-replication ownership model, while its communication volume is optimal for the prescribed fused permutation and source-target slab distributions.

Authors: Max Ovsiankin

This thesis investigates Euclidean-space and $\ell_p$-norm representations of different forms of data, with a focus on efficient algorithms for computing these representations in settings where the amount of data is very large. The applications of such representations are also discussed: they may be used to summarize the data in a more compact form for downstream tasks while preserving its most salient properties; and further, they may also be used to extract insights about the data that may not be apparent in its original form. This thesis presents novel algorithms for computing Euclidean representations in the case where the data comes with linear structure, as well as in the case where the data comes only with metric, or distance structure. In addition, we give algorithms for computing $\ell_p$-norm representations in linear structured cases. The analyses of these algorithms use tools from geometry, probability, and optimization, and these tools are used to illuminate other algorithms for similar problems.

Authors: Ofek I. Cohen

A query-oblivious coreset for a softmax-attention head is a subset $S$ of the key--value pairs such that attention computed from $S$ alone is within $\varepsilon$ of the full output, in $\ell_2$, simultaneously for every query in a ball. Liberty, Andoni and Kleiner proved that unweighted coresets of size $O(\sqrt d\,e^{ρ+\frac12\logρ+o(\log\logρ)}/\varepsilon)$ exist, $ρ$ being the query radius times the centred key radius, against a lower bound $Ω(\sqrt d\,e^ρ/\varepsilon)$, and conjectured that closing the gap needs new techniques. We show it does not. A spherical lift of both balls into one exponential-kernel instance lets the chaining bound of Bozzai and Rothvoss apply directly, and Chevet's inequality splits key from value dimension: unweighted coresets of size $O(e^ρ(\sqrt{d_v}+\sqrt{d_k\log(1+ρ)})/\varepsilon)$ exist and are computable in randomised polynomial time, the first with a whole-ball guarantee at the existential size up to $\sqrt{\log(1+ρ)}$. A dimension-free sampling cap $O(e^{2ρ}/\varepsilon^{2})$ completes the envelope. In fixed dimension the logarithm disappears: completing the key ball to a sphere makes the kernel an unweighted Gaussian one, so Tai's diameter-free bound gives $O_{d_k,d_v}(e^ρ/\varepsilon)$, ruling out a matching logarithmic lower bound there and answering the Gaussian-restriction case of a question of Bozzai and Rothvoss for the exponential and Hellinger kernels. We restate the Liberty--Andoni--Kleiner bound in the centred convention with a full proof, and show that the one-way communication bounds of Chen et al.\ transfer to query-oblivious coresets, where for $\varepsilon\ll e^{-ρ}$ they are the strongest floors known. The dimensional factor is the price of one signing for all queries: for a single query the discrepancy is $O(e^ρ)$, dimension-free.

Authors: Ming Hu

We consider a classical two-stage continuous-review serial inventory system with unit-sized Poisson demand of rate lambda, backlog cost rate p, lead times L_1, L_2, echelon holding-cost rates h_1, h_2, and fixed shipment costs K_1, K_2. The classical echelon stock (R,nQ) policy offers a simple operating rule: Stage 1 orders a fixed Q_1-lot, Stage 2 orders n >= 1 such lots at a time, and a Stage-1 request waits until a complete lot is available. Existing uniform guarantees restrict lead times or induced lot sizes, and the known all-instance guarantee is primitive-dependent, leaving open whether this restrictive integer-ratio class admits any uniform guarantee over the full primitive space. We develop a setup-preserving cost-allocation lower bound and show that the infimum cost within the classical class is at most 1.73 times the optimal cost over a rate-balanced admissible comparison class, for every lambda, p, L_1, L_2, h_1, h_2, K_1, K_2 >= 0. The result holds for exact integer lot sizes and under both setup conventions, one charging each positive dispatch and the other every complete lot. On the boundaries the guarantee is one, as an equality of infima, when lambda=0, p=0, or h_2=0, and improves to 5/3 when K_2=0. Numerically, across three broad parameter grids, the best-found (R,nQ) policy costs at most 1.098 times the evaluated lower bound, with a median ratio of 1.007; a deliberately adversarial stress test reports 1.6004 under the conservative lot-cost convention. At that point, finite searches under shipment-cost accounting find no benefit from allowing Stage 2 to ship an incomplete Q_1-lot, which is consistent with looseness in the evaluated lower bound. The simple (R,nQ) policy, therefore, combines a straightforward fixed-lot implementation with a uniform guarantee over the full nonnegative primitive space.

Authors: Thomas D. Ahle, Jakob B. T. Knudsen

Horner's rule evaluates a monic degree-$n$ polynomial using $n-1$ multiplications. We show that with rational preprocessing of the coefficients, any such polynomial can be evaluated using only $\lfloor n/2 \rfloor + 1$ multiplications over fields of characteristic zero or of characteristic $p>n$. This resolves the multiplication side of a conjecture of Rabin and Winograd (Comm. Pure Appl. Math 1972), who achieved $n/2 + 2\lceil\log_2 n\rceil$ multiplications and conjectured the logarithmic overhead was necessary. We show that this multiplication count can't be beaten in general, proving that three multiplications do not suffice for degree~$6$. This strengthens the lower bound of Pan (STOC 1978), who proved a tight bound for general, complex preprocessing. In characteristic~2, for every $n>1$ and every finite field of size at least $2n$, we prove that an $n$-multiplication chain cannot parametrize all value vectors at $2n$ distinct evaluation points, even with arbitrary preprocessing. We give $\lfloor n/2 \rfloor + 1$ multiplication schedules over characteristic~2, each with an explicit inverse, for every odd degree $n\le 25$ and conjecture that this is possible for all $n$. We also give an injective polynomial construction for universal hashing that uses $N$ multiplications to hash $2N$ values with a single random key. This improves the best previous construction by Daniel J. Bernstein (cryp.to).

Authors: Cheng Xin

The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an $N$-vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every $K\ge2$ and $N\ge4^{K-1}$, finds and verifies a homogeneous $K$-set using $O\!\left(2^K K\log\frac Kη\right)$ edge queries with failure probability at most $η$. At the Ramsey scale $N=2^n$, this yields a homogeneous set of order $\lfloor n/2\rfloor+1$ using $O(\sqrt N\log N\log(\log N/η))$ queries, improving on the $O(N)$ queries of the explicit classical recursion and giving, to our knowledge, the first sublinear worst-case algorithm for the Ramsey relation. We also derive an $Ω(N^{1/12})$ quantum lower bound by a reduction from collision finding. The algorithm runs the constructive recursion over implicit candidate sets. Each set is represented by a short conjunction of adjacency constraints and sampled using capped unknown-solution quantum search, and a scale-aware concentration schedule balances estimation accuracy against the increasing cost of sampling deeper sets. We complement the upper bound with an $Ω(N^{1-1/\sqrt2})$ randomized lower bound, transported from the random-Painter analysis of online Ramsey numbers, which holds on the uniform distribution $G(N,1/2)$. On that distribution a greedy quantum search uses only $\widetilde O(N^{1/4})$ queries, giving a provable polynomial quantum speedup for Ramsey search on random graphs. We also give an estimation-free size-biased recursion and extend it to every fixed number of edge colours.

Authors: Peter Robinson, Ming Ming Tan

We present the first polynomial lower bounds for several fundamental problems in the distributed graph sketching model in the tiny-error regime, which includes deterministic algorithms as a special case. In the graph sketching model, every node sends a single message to the referee who does not have any prior knowledge of the graph and must output the answer. While the work of Nelson and Yu (SODA 2019) and Yu (SODA 2021) showed that $Θ( \log^3n )$ is optimal for constructing a spanning forest or deciding whether the graph is connected with error at most $\frac{1}{\text{poly}(n)}$ , their approach does not yield any stronger bounds for significantly smaller error probabilities. Our main result is to show that solving either connectivity or spanning tree construction with error at most $δ$ requires messages of length $Ω( \min\{n, \log_2 \frac{1}δ\}^{1/3} )$, which implies that algorithms with exponentially small error must send messages of $Ω( n^{1/3} )$ bits in the worst case. Our results significantly narrows the current gap between the Jelani-Yu threshold of $Θ( \log^3n )$ and the trivial upper bound of sending $O(n)$ bits per node for deterministic graph sketching. We also extend our results to $k$-edge connectivity. For any $k=O(n^{1/7})$, we recover the same bound of $Ω( k )$ on the message length for algorithms with exponentially small error that was shown by Robinson and Tan (PODS 2026) only for deterministic algorithms. Finally, for $k=n^{o(1)}$, our result implies a stronger lower bound of $Ω_ε( n^ε )$ bits, for any constant $ε<\tfrac{1}{3}$.

Authors: Andrew M. Childs

We (the author and the AI systems that did the heavy lifting) show that the quantum query complexity of minimizing a convex function over a convex subset of $\mathbb{R}^n$ with evaluation and membership queries is $\tildeΩ(n)$, nearly matching the best known upper bound. In particular, we show this even for quadratic minimization, which is equivalent to inverting an $n \times n$ real matrix using matrix-vector queries. We also show linear or nearly linear lower bounds on the quantum query complexity of computing the trace, the sign of the determinant, and the magnitude of the determinant of a real matrix in the matrix-vector query model. We use a novel quantum lower bound technique, the determinantal witness method, based on identifying a witness whose Fourier transform vanishes on low-rank matrices and that correlates well with the function being computed.

Authors: Joshua A. Grochow, Pranjal Srivastava, Dhara Thakkar

The Group Epimorphism Problem (GpEpi) asks, given two finite groups $G_1$ and $G_2$, whether there exists a surjective group homomorphism, or epimorphism, from $G_1$ to $G_2$. When the input groups are given by their multiplication (Cayley) tables, the problem admits a quasipolynomial-time algorithm in general, but little is known about its complexity for structured classes of finite groups. In this paper, we study the computational complexity of GpEpi for several well-studied classes of finite groups. Our main results are polynomial-time epimorphism tests for several classes of groups for which polynomial-time isomorphism testing was previously known: Groups with Abelian normal Hall subgroups with cyclic complement; Groups with (product of) elementary Abelian normal Hall subgroup with elementary Abelian complement; and Groups with some constraints on their Abelian chief factors.

Authors: Ilie Dumitru, Adrian Miclăuş, Alexandru Popa

In this paper, we study \textsc{MaxMMP}, an optimization variant of the Matching-Match Puzzle introduced by Iburi and Uehara (FUN 2024). Given a graph, a partial vertex coloring, and a multiset of colored sticks, the goal is to complete the coloring and assign the sticks to graph edges so as to maximize the number of satisfied edges. We first prove that \textsc{MaxMMP} is APX-hard by an reduction from \textsc{Max-Cut}. The hardness already holds with two colors, no precolored vertices, and only bichromatic sticks. We then give a simple deterministic $\frac{2}{c(c+1)}$-approximation for completely uncolored instances, improving to $\frac{2}{c(c-1)}$ when all sticks are bichromatic. Next, we obtain a randomized $\frac{1-\frac{1}{e}}{2c}$-approximation for arbitrary instances with $c$ colors by reducing the remaining coloring choices to monotone submodular maximization under a partition matroid. On bipartite graphs, the approximation ratio improves to $\frac{1-\frac{1}{e}}{c}$. For every fixed $c$, we further obtain deterministic $\frac{1}{2c}$ and $\frac{1}{c}$-approximations on general and bipartite graphs, respectively, in time $n^{O(c^2)}$. Finally, for every fixed number of colors, we show that \textsc{MaxMMP} can be solved exactly in time $n^{O(c^2)}$ on trees and on cographs.