Theory of Computing Report

Authors: Vaneet Aggarwal

We study nonnegative submodular maximization subject to a general matroid when the offline algorithm is given an arbitrary controlled value oracle. Our main result is an adversarial resilience theorem for the Spiteful Greedy Swap Poisson Process (SGS-Poisson): without modifying its Poisson intensity, single-element exchange rule, or spiteful drop step, the algorithm retains limiting approximation factors $1/e$ for non-monotone objectives and $1-1/e$ for monotone objectives. More precisely, under every controlled oracle $\widehat f$ satisfying $|\widehat f(S)-f(S)|\le ξ$ for every set $S$, our implementation returns a feasible set with expected value at least $(1/e-\varepsilon)\OPT-O(kξ)$ and $(1-1/e-\varepsilon)\OPT-O(kξ)$, respectively, using $\widetilde O(nk^2\varepsilon^{-2})$ oracle calls. As a consequence, the offline-to-online reduction yields full-bandit CMAB algorithms for general matroid-constrained submodular rewards with exact limiting approximation-regret factors $1/e$ and $1-1/e$ and $\widetilde O(n^{1/5}k^{4/5}T^{4/5})$ regret.

Authors: Stuart Hadfield

Evaluating expectation values is a critical task for variational quantum eigensolvers, and for parameterized quantum circuits and other quantum algorithms more generally. We consider the well-studied case of the Quantum Approximate Optimization Algorithm (QAOA) for the MaxCut problem. Recent work of Wang et al. [arXiv:2511.20212] showed this task to be NP-hard in general for any QAOA depth $p\geq 2$, complementing past results showing efficiently computable formulas for $p=1$ with arbitrary problem graphs. We sharpen this dichotomy showing that for $p\geq 2$ exact or exponentially precise cost expectation value evaluation is #P-hard under deterministic polynomial-time Turing reductions. Hardness at $p\geq 2$ is shown to remain even for evaluating single pairwise correlators $\langle Z\otimes Z\rangle $, as well as for highly restricted sets of algorithm parameters. Our proof refines the NP-hardness construction of Wang et al. that recovers the maximum cut value from the largest exponent of a QAOA Laurent polynomial, utilizing a distinct and simpler construction that extracts a value proportional to the total number of maximum cuts, in addition to the optimal cut value. Thus we show that the QAOA expectation value hardness transition from $p=1$ to $p=2$ is not only from tractability to optimization hardness, but to that of counting optimal solutions. As an application we show our results imply analogous hardness results for computing gradients and Hessians of QAOA circuits.

Authors: Saptarshi Biswas, James I. Lathrop, Rana D. Parshad

The computability of real numbers and functions using Turing Machines has been a central area of theoretical computer science since the mid-20th century. In the late 20th century, it was shown that chemical reactions can serve as a basis for computation using the Chemical Reaction Network (CRN) model. Recent advances in computing real numbers using Deterministic Chemical Reaction Networks (DCRNs) have identified numerous classes of DCRN-computable real numbers. In parallel, the works of R. Landauer and C. H. Bennett, spanning the 1960s to the early 2000s, showed that reversible computing offers significant advantages over irreversible methods, particularly in energy efficiency, motivating extensive research on reversible computation. In this work, we investigate the computability of real numbers using Reversible Chemical Reaction Networks (RevCRNs). The paper has two primary contributions: (1) establishing relationships among CRN-computable real number classes including Lyapunov CRN ($\mathbb{R}_{LCRN}$), Real-Time CRN ($\mathbb{R}_{RTCRN}$), rational numbers ($\mathbb{Q}$), and RevCRNs ($\mathbb{R}_{RevCRN}$), with key results: (i) $\mathbb{Q}$ is a strict subset of $\mathbb{R}_{RevCRN}$; (ii) the set of positive algebraic numbers ($ALG$), $\mathbb{R}_{LCRN}$, and real numbers computable by 1-species RevCRN ($\mathbb{R}_{RevCRN}^{1s}$) are equal; (iii) $\mathbb{R}_{RTCRN}$ and $\mathbb{R}_{RevCRN}$ exhibit non-empty overlap; and (iv) the set of real numbers computable by detailed-balanced RevCRNs ($\mathbb{R}^{DetBal}_{RevCRN}$) is a subset of $ALG$; and (2) exploring the existence of a hierarchy within $\mathbb{R}_{RevCRN}$. Finally, we leave open the exact relationship between $\mathbb{R}_{RevCRN}$ and $\mathbb{R}_{RTCRN}$ while conjecturing a general hierarchy of RevCRN-computable reals.

Authors: Yuval Filmus, Anqi Li, Dor Minzer

A classical theorem due to Friedgut, Kalai and Naor asserts that if a function $f\colon \{0,1\}^n\to\{-1,1\}$ close to a degree $1$ function, then either $f$ or $-f$ is close to either the all $1$ function, or to $(-1)^{x_i}$ for some $i\in [n]$. We prove a version of their theorem for the Grassmann scheme over $\mathbb{F}_2$. More precisely, we prove if a function $f\colon \genfrac{[}{]}{0pt}{}{\mathbb{F}_2^n}{\ell}\to\{0,1\}$ is close to a degree $1$ function, then either $f$ or $1-f$ must be close to a function of the form $g(L) = \sum_{x\in\mathcal{X}}1_{x\in L}+\sum_{W\in\mathcal{W}}1_{L\subseteq W}$, where $\mathcal{X}\subseteq\mathbb{F}_2^n$ is a set of points and $\mathcal{W}$ is a set of hyperplanes in $\mathbb{F}_2^n$.

Authors: Tanner Finken, Jixian Li, Bei Wang, Hanqi Guo, Joshua A. Levine

Topological analysis of scalar fields yields structures such as the Morse-Smale complex (MSC) that summarize salient features across multiple scales. Existing MSC extraction algorithms typically assume an explicit representation of the input field, such as a discretely sampled mesh. However, recent advances in visualization have popularized implicit field representations, for which these assumptions no longer hold. In this work, we address the problem of extracting an MSC from an implicitly defined 2D scalar field. We present a method for constructing a triangulated piecewise-linear (PL) mesh that aims to preserve the critical points of an underlying implicit scalar field. Our central insight is that if all edges are monotonic with respect to the underlying field, then the resulting PL approximation is topologically consistent with respect to critical points. Based on this insight, we introduce a refinement procedure that mitigates monotonicity violations. Requiring only pointwise evaluations and modest mesh refinement, the approach produces PL meshes that are correct with regards to critical points in our experiments. Finally, we demonstrate that additional targeted refinement improves the geometric fidelity of MSC separatrices.

Authors: John Rick Manzanares, Jay-Anne Bulauan

We introduce Probabilistic Ball Mapper, a formulation of Ball Mapper in which each data point is assigned a probability distribution supported only on the metric balls that contain it. This assignment defines both a partition subordinate to the Ball Mapper cover and a Markov kernel from the finite data space to the cover. We study two assignment schemes: a uniform-on-support rule and a localized radial-basis rule that incorporates distance to landmarks while preserving the underlying cover. Pushing the empirical data distribution through the kernel produces a probability distribution over vertices. Drawing twice, conditionally and independently, from each pointwise distribution produces a soft-overlap matrix. This matrix is symmetric, nonnegative, positive semidefinite, and has the vertex distribution as both marginals. It therefore provides a mass-normalized refinement of classical Ball Mapper overlap rather than another unnormalized edge count. For graphs constructed on a common cover, the vertex and overlap distributions can be compared directly. For independently fitted covers, we formulate Wasserstein and fused Gromov--Wasserstein-type discrepancies that account for vertex mass, landmark geometry when a common ambient metric is available, and intrinsic graph relations. For a fixed cover, we derive explicit perturbation bounds controlled by the sensitivity of the assignment rule, the magnitude of the data perturbation, and the data mass near cover boundaries. When the cover is recomputed, landmark motion creates an additional source of variation, for which we state a transport-based stability principle rather than an unconditional theorem. The resulting framework turns Ball Mapper into a probability-valued representation suitable for quantitative comparison while retaining its geometric interpretability and computational simplicity.

Authors: Bogumil Kaminski, Pawel Pralat, Maria Sadza

This paper investigates a multi-robot search-and-visit problem involving $n$ robots starting at the origin and $k$ unknown treasures hidden on the unit circle $\mathcal{C}$. The robots move independently anywhere in the plane with a maximum speed of 1 and instantly share discovery information. The goal is to determine an algorithm that minimizes the total time needed for all robots to individually visit every treasure. To establish the foundational limits of this task, we first solve an auxiliary optimal routing problem for a single robot on $\mathcal{C}$ that possesses complete prior knowledge of the treasure locations. The exact analysis of this auxiliary problem yields explicit upper and lower bounds for the original search problem.

Authors: Andrew McGregor

We present a slightly simplified analysis of the asymmetric palette sparsification result by Assadi and Yazdanyar [TheoretiCS, 2026]. The motivation is mainly pedagogical; our approach avoids hypergeometric concentration bounds and extra constant factors in the palette size.

Authors: Anubhav Dhar, Anita Dürr, Ahmed Ghazy, Jakob Greilhuber, Karol Węgrzycki

Minimizing the weighted completion times ($P \mid \mid Σw_j C_j$) and weighted number of tardy jobs ($P \mid \mid Σw_j U_j$) on multiple identical machines are two classical NP-hard scheduling problems. As shown by Lenté et al. (2014), both problems can be solved in time ${O}^{\star}(3^n)$. In this paper, we improve these bounds to ${O}(2.755^n)$ and ${O}^{\star}(2^n)$, respectively. Our algorithm for $P \mid \mid Σw_j C_j$ exploits the meet-in-the-middle paradigm and an efficient data structure answering linear programming queries. Additionally, when the number of machines is at most $6$, we show that the running time for $P \mid \mid Σw_j C_j$ can further be improved. Both scheduling problems are generalizations of the classical Bin Packing problem, which can be solved in ${O}^{\star}(2^n)$ time. Improving this running time is an important open question. We show that, when assuming the Asymptotic Rank Conjecture (ARC), Bin Packing can be solved in time ${O}((2-\varepsilon)^n)$ for some $\varepsilon >0$. Our algorithm makes use of two main ingredients: the recent ${O}((2-\varepsilon)^n)$-time algorithm of Nederlof et al. [SICOMP'23] for Bin Packing when the number of bins is a fixed constant, and the ${O}((2-\varepsilon)^n)$-time algorithm of Björklund et al. [SODA'25] for special instances of the $3$-way Partitioning problem when assuming ARC.

Authors: Bo Peng, Zhihao Gavin Tang

We study edge-weighted oblivious bipartite matching. The weight of every potential edge is known, but its existence is revealed only when the edge is probed, and a successful probe between two free vertices must be accepted immediately. We give an explicit randomized algorithm with certified competitive ratio $0.698$, improving the previous best guarantee of $0.659$ (Huang, Sun, Wu, and Zhao, FOCS 2025). The result is computer-assisted and verified by a reproducible exact-integer computation. The same algorithm has a $0.698$-competitive online implementation for the vertex-weighted random-arrival model, improving the previous $0.696$ unweighted guarantee of Mahdian and Yan (STOC 2011) and the $0.686$ vertex-weighted guarantee of Peng and Tang (EC 2025). Our algorithm, Harmonic Ranking, is a role-symmetric generalization of \textsc{Ranking}. It assigns an independent random rank $x_z$ to each vertex and probes a potential edge $uv$ in decreasing order of \[ w_{uv}\frac{h(x_u)h(x_v)}{h(x_u)+h(x_v)}. \] This harmonic priority arises from a budget-balanced gain split and a mutual-proposal interpretation. The analysis lifts two cutoff curves into indicators, reducing the exponential-size factor-revealing problem to a polynomial-size directed minimum-cut instance. A maximum-flow computation with rounded-down integer capacities gives a rigorous certificate. Independently, we observe that the finite-grid unweighted relaxation of our factor-revealing program coincides exactly with a Mahdian--Yan program.

Authors: Adam Karczmarz, Paweł Pilarski

We study the maximum flow problem in directed networks with real capacities in the parallel setting. For a network with $n$ vertices and $m$ arcs, we show that a randomized parallel implementation of a variant of the strongly polynomial max-flow algorithm of Dadush, Orlin, Sidford, and Végh [SODA 2026] runs in $\tilde{O}(mn)$ work and $\tilde{O}(m)$ depth. This improves upon the previously described tradeoffs between work and depth for strongly polynomial parallel maximum flow algorithms: earlier $\tilde{O}(n^3)$-work algorithms have $\tilde{O}(n^2)$ depth [Shiloach and Vishkin, J. Algorithms 1982; Goldberg and Tarjan, J. ACM 1988], while the known $\tilde{O}(m)$-depth approach uses $\tilde{O}(mn^3)$ work [Orlin, Oper. Res. 1993].

Authors: Keramat Hasani, Frank Werner

This paper investigates a parallel machine scheduling problem featuring a single common server responsible for both loading and unloading operations. Each job consists of a unit-time loading operation, non-preemptive processing on one of \(m\) identical machines, and a unit-time unloading operation executed by the same server. The objective is to minimize the makespan. Unlike classical loading-only common-server models, our setting requires the server to handle an unloading operation immediately after a job's processing phase concludes. We prove that the corresponding decision problem is strongly NP-complete when the number of machines is given as part of the input. Furthermore, we analyse the worst-case performance of the List Scheduling (LS) and Longest Processing Time (LPT) heuristics. For three machines, we establish that Algorithm LS achieves an approximation ratio of at most \(5/2\). For an arbitrary fixed \(m \ge 3\), we show that the general LS bound approaches \(4-3/m\) as the number of jobs grows, whereas for Algorithm LPT, we prove the finite-instance ratio $3-\frac{2}{m}+\frac{(m-1)(m-2)}{mn}.$ Thus, for each fixed \(m\), the LPT bound approaches \(3-2/m\) as the number of jobs grows.

Authors: Tao Jiang, Minbo Gao, Shaowei Cai

Sign-nonsingularity asks whether every real matrix with prescribed entry signs is nonsingular. Polynomial-time algorithms recognize square sign-nonsingular patterns through their connection with even directed cycles, but recognition does not itself produce an exact numerical witness in the negative case. We give a deterministic polynomial-time algorithm that, for any square sign pattern $A$, either reports that $A$ is sign-nonsingular or outputs $B\in\mathbb{Z}^{n\times n}$ and $z\in\mathbb{Z}^n\setminus\{0\}$ such that $\operatorname{sgn}(B)=A$ and $Bz=0$. After normalizing a perfect matching, an even directed cycle yields two determinant terms of opposite signs. Making either term dominant produces endpoint realizations with opposite determinant signs. Changing their magnitudes one coordinate at a time exposes an affine sign-changing step, whose zero is rational; clearing its denominator gives the integer witness. Entries of $B$ have $O(n^2\log n)$ bits, and entries of $z$ have $O(n^3\log n)$ bits. The result settles Conjecture 14.12.4 in the Handbook of Satisfiability.

Authors: Nader H. Bshouty

We give a lower bound for randomized non-adaptive group testing when the goal is to find any $\ell$ defective items but the total number $d$ of defectives is unknown. Bshouty and Haddad-Zaknoon proved an upper bound of $O(\ell\log^2 n)$ tests and a lower bound of $$Ω\!\left(\frac{\ell\log^2 n}{\log \ell+\log\log n}\right).$$ We prove the matching lower bound. More generally, we show that every randomized non-adaptive algorithm that succeeds with constant probability for every defective set must use $$Ω\!\left(\ell\log^2(n/\ell)\right)$$ tests. The proof is as follows. At a fixed value of $d$, finding $\ell$ defectives requires about $\ell\log(n/d)$ bits of information. On the other hand, one fixed group test is informative only when its size is tuned to the scale of $d$; across all logarithmic scales of $d$, a single test contributes only $O(1)$ bits. Summing over all scales gives the lower bound. We also record the matching upper bound $$O\!\left(\ell\log^2(n/\ell)\right),$$ obtained by running the known-$d$ algorithm in parallel over dyadic guesses for $d$. Thus the randomized non-adaptive complexity of unknown-$d$ partial detection is $Θ\!\left(\ell\log^2(n/\ell)\right)$ for constant success probability.

Authors: Xavier Coiteux-Roy, Maxime Flin, Carlos de Gois, Marc-Olivier Renou, Jukka Suomela, Isadora Veeren

We prove that any distributed quantum algorithm that finds a $3$-coloring with probability $1$ in a cycle of anonymous identical computers has to be global, that is, it needs $Ω(n)$ communication rounds. It follows that quantum computation and communication does not help with this problem. All prior lower bounds on quantum advantage in distributed graph algorithms use arguments related to physical causality. However, it is known that such arguments cannot rule out fast quantum advantage for $3$-coloring cycles. In particular, any causality-based argument would rule out the existence of finitely dependent coloring, but Holroyd and Liggett (2016) showed that such colorings do exist. Hence to tackle this problem, we need a ``genuinely quantum'' lower-bound technique that can distinguish between (1) distributions that do not violate physical causality vs. (2) distributions that can be realized with a quantum strategy. We present the first such lower-bound technique in this context. First, we show that $1$-round quantum algorithms cannot break symmetry with probability $1$. Second, we present a wishful teleportation strategy that can be used to turn $T$-round quantum 3-coloring algorithms into $1$-round quantum algorithms breaking symmetry, while preserving success probability $1$. Put together, the lower bound follows.

Authors: Paul Dütting, Renato Paes Leme, Martin Pál, Neel Patel

The matroid secretary problem (MSP) is one of the cleanest, and most captivating open problems in online algorithms. The famous MSP conjecture stipulates that there exists a constant-competitive algorithm, yet to date the best known algorithms are $O(\log \log (\text{rank}))$ competitive. It is widely believed that all information that an algorithm for the MSP should use is information that is available through an independence oracle on the already arrived elements. Despite this, there are natural classes of matroids where a constant-competitive algorithm is known if we are given additional upfront information about the matroid; while no such algorithm is known if all the algorithm can use is an independence oracle on the arrived elements. In this work, we tackle the perhaps most appealing such class of matroids, graphic matroids. We develop an algorithm for the MSP that has access to the independence oracle only. Our algorithm runs in polynomial time, and if the underlying matroid is graphic, it produces an independent set whose weight is at least $1/36$ of the maximum-weight independent set. Ours is the first constant-competitive algorithm for MSP on unknown graphic matroids.

Authors: Xi Chen, Renato Ferreira Pinto, Nathaniel Harms, Shyamal Patel, Rocco A. Servedio

We prove a tight $Θ(n/ε)$ lower bound on the number of samples required for testing halfspaces over $\mathbb{R}^n$, in the distribution-free sample-based model where the underlying probability distribution is unknown to the algorithm, and the algorithm only receives random samples (i.e., it cannot make queries). This shows that testing is no more efficient than learning for halfspaces. We also show a matching upper bound for one-sided testers, improving on the standard (two-sided) testing-by-learning reduction, establishing that two-sided halfspace testers in this model have no advantage over one-sided testers.

TUM’s newly established Fundamentals of Programming Group invites applications for PhD and postdoctoral positions. Our research spans programming languages and type systems, program analysis and verification, logic and automata, and formal methods and AI, from foundational theory to algorithms and research tools. Review begins September 1, 2026, and continues until the positions are filled.

Website: https://www.cs.cit.tum.de/en/prog/open-positions/
Email: f.zuleger@tum.de

By shacharlovett

Enjoying Idaho while ignoring Illinois

By Lance Fortnow

Authors: Alan Li, Rahul Saha, Anton Xue, Swarat Chaudhuri, Adam Klivans, Pravesh K Kothari, Raghu Meka

AI agents are increasingly used in mathematics research, but it is often unclear how to use them effectively. Towards this, we present an extensive case study of how AI was used to improve bounds on the Grothendieck constant $K_G$, which captures the hardness between combinatorial problems and their continuous relaxations. Specifically, while the precise value of $K_G$ is not known, we recently tightened the best known bounds to \[ \frac{6π}{11} \;\le\; K_G \;\le\; \fracπ{2\log(1+\sqrt2)} - 10^{-4}. \] Crucially, these improvements were achieved using an AI research system that could arrive at insights deemed novel by domain experts. We give a detailed discussion of our experience using AI for mathematics research, particularly touching upon its strengths and weaknesses, as well as our experience with creating ideal conditions for AI to arrive at breakthrough insights.

Authors: Orr Paradise, Oliver Richardson, Yoshua Bengio, Shafi Goldwasser

When a probabilistic predictor answers many conditional-probability queries, are its answers self-consistent, and can this be verified in polynomial time? This problem is of interest for AI safety, where safety is derived from honesty about probabilistic predictions of unwanted outcomes potentially caused by an AI action. We construct an interactive PCP as follows. Let a predictive model be specified by a probability circuit P and a circuit Q which outputs confidence in predictions. Together, P and Q implicitly specify exponentially many probabilistic claims. We show a protocol in which a polynomial-time verifier can verify the approximate consistency of (P,Q). The verifier is given the pair of circuits (P,Q), which it evaluates at only a few points; alongside them it is given a proof oracle, an encoding of a witnessing probability distribution allegedly consistent with the predictions of (P,Q), which it reads at a few locations while interacting with a single untrusted prover. En route, we must ensure the existence of a sparse witnessing distribution consistent with the model's predictions. To do so, we first consider witness distributions for the consistency of explicit probabilistic claims, rather than claims specified by a predictor: say m claims, each of the form Pr[Y = 1 | X = x] = p, over n Boolean variables. Building on work initiated by Nilsson (Artif. Intell., 1986), we place l_2-approximate probabilistic consistency of explicit claims in NP, with certificates of length O(mn + log B) in the input bit-precision B; we further show how a small additive completeness-soundness gap removes the dependence on B. Together these results provide a complexity-theoretic foundation for certifying the self-consistency of probabilistic predictors. We view our interactive PCP as a first step toward training predictive models to prove their own consistency.

Authors: Ming Yang

We prove inference-time quantum coordination advantages for specified AI state-tracking tasks. A solver compresses semantic history into a future-accessible boundary state and later answers a query. We count communication $B$, persistent instance-dependent memory $M$, and local work $D$; classical recurrence, caches, tools, and recomputation are allowed and charged. The central result is a boundary-preserving semantic-compilation theorem. It maps a finite one-way, streaming, or adaptive causal task into a semantic AI interface while preserving event order and access to past input. Classical boundary-state lower bounds and quantum-memory upper bounds transfer up to explicit compiler overhead, independently of the finite-precision recurrent architecture. Two applications have classical semantics. Matched-entity synopsis QA inherits the hidden-matching separation between $O(\log N)$ qubits and $Ω(\sqrt{N})$ classical boundary bits. Continual requirements auditing inherits a Max-$k$SAT streaming separation: a recurrent solver uses $O(\log^5 n\log(1/δ))$ qubits and polylogarithmic classical workspace to obtain a $0.7172$-approximation, whereas every classical one-pass finite-information solver attaining that ratio requires $Ω(\sqrt{n})$ coordination width. As a quantum-native compiler test, a stabilizer latent-state dialogue uses $n$ qubits, while every exact finite-state classical causal online realization satisfies $B+M \ge \frac{1}{2}n^2+(\frac{3}{2}-\log_2 3)n+O(1)$. The source protocols, streaming algorithms, and stabilizer witness are imported; the new result is their architecture-independent semantic transfer. These are memory and coordination separations, not runtime or empirical advantages for present-day language models. The stabilizer result assumes exact simulation and ideal noiseless quantum memory.

Authors: Ziqi Zhao, Qingjian Ni

Shellsort's best general lower and classical upper bounds differ by an iterated-logarithmic factor. Lower bounds use signed, order-free cancellation, whereas upper bounds require positive representations respecting pass order. We develop a common certificate framework for these two geometries. A prefix Fourier phase defect lower-bounds worst-case exchanges and hence comparisons. At pass $j$, the chronological ray quotient records multiples of the current gap already eliminated by earlier passes. Its truncated, pair-weighted hole mass bounds exchanges in that pass, and adding the $np$ overhead bounds comparisons. In a sufficiently long active window, $g_j^{(n)}$ ray holes imply signed transfer length at most $4g_j^{(n)}-1$, so approximate prefix characters propagate to the current gap. Signed transfer length two can coexist with arbitrarily large ray genus; scale-local Apéry representatives control both parameters. The framework recovers Pratt's $O(n\log^2 n)$ scale and the sparse two-parent scale, and yields the following structural results. Uniformly bounded full ray genus after a fixed prefix forces $W_n=Ω(n^{1+1/j_0-o(1)})$ when $p_n-j_0=o(\log n)$. An affine family has ordinary global semigroup genus and conductor $Θ(n)$ but relevant ray genus two. Balanced three-generator full grids have terminal truncated ray genus at least $\exp(Ω((\log n)^{2/3}))$. The last result is a certificate barrier.

Authors: Shree Ganesh, Pascal Koiran, Rafael Oliveira

A tensor has border rank at most $r$ if it can be written as $T=\lim_{\varepsilon \rightarrow 0} T(\varepsilon)$ where $T(\varepsilon)$ has rank at most $r$ for all sufficiently small $\varepsilon$. It is known that the map $\varepsilon \mapsto T(\varepsilon)$ can be assumed to be a (tensor valued) polynomial in $\varepsilon$. The smallest possible degree of such a map is called the error degree of $T$. The error degree and the related notion of order of degeneration are the two key quantities that we study in this paper. One motivation comes from debordering: by polynomial interpolation on the map $\varepsilon \mapsto T(\varepsilon)$ we can upper bound the tensor rank of $T$. For order 3 tensors, exponential upper bounds on the error degree and degeneration order were given almost 40 years ago in (Lehmkuhl Lickteig, 1989) and were not improved ever since. In this paper we give bounds that apply to a wide class of tensors, exponentially improving on (Lehmkuhl Lickteig, 1989). Our results are most general for tensors with 3 slices (format $m \times n \times 3$). In this case, our main assumption is on the rank of the matrix slices. We also give bounds that apply to arbitrary rectangular formats ($m \times n \times p$). In this case, we need an additional 1-regularity assumption on one of the slices of the tensor (recall that a matrix is said to be 1-regular if its eigenspaces are 1-dimensional). Under these assumptions we show that the error degree is at most 1, which yields a nontrivial debordering result (tensor rank at most $2r$ for border rank $r$). The results in (Lehmkuhl Lickteig, 1989) rely on an upper bound on the degree of the variety of tensors of border rank at most $r$. We rely instead on more specific properties of this algebraic variety, and in particular on commutativity properties of certain matrices derived from the tensor slices.

Authors: Florian Beier, Stephan Eckstein

Clustering is a fundamental class of data analysis techniques with the most important representatives being centroid-based methods like $k$-means. Such methods are strongly connected to quantization problems, which aim to approximate general probability measures with discrete ones. For example, $k$-means corresponds to quantization with respect to the Wasserstein distance. While Wasserstein quantization clusters points within a fixed space, this paper studies Gromov-Wasserstein (GW) quantization, which additionally aims at clustering the ambient geometry of the space. We show existence of solutions to the GW quantization problem and give a characterization that justifies an analogue to the $k$-means algorithm (Lloyd's algorithm) to approximate them numerically. We further calculate the quantization rate for usual Euclidean geometries that are used in the GW context, and relate it to standard Wasserstein quantization rates. Finally, numerical experiments show that GW quantization opens up many modeling possibilities beyond normal clustering methods (e.g., for geodesic distances of 3D shapes or structured pruning of neural networks) and that the introduced algorithm leads to useful numerical solutions with approximation quality often in line with theoretically optimal rates.

Authors: Andrew McGregor

We show that a simple extension of the randomized greedy maximal independent set algorithm yields a constant approximation for the maximum matching problem. The algorithm is a simplification of an algorithm used by Assadi et al. [JACM 2026] in the context of processing data streams in the dynamic setting where edges may be inserted and deleted. In contrast to the previous work, our analysis avoids consideration of fractional matchings and yields a significantly shorter and more direct proof of the approximation factor for the basic algorithm.

Authors: Elena Grigorescu, Mehrshad Taziki

In the undirected \emph{Densest Subgraph Problem (DSG)} the goal is to output a subset $S$ of vertices of a given graph $G$ that maximizes the quantity $|E(S)|/|S|$, where $E(S)$ is the set of edges in the subgraph induced by $S$. The problem is well studied in both theory and practice, and it admits natural efficient exact algorithms, as well as near-linear time algorithms with a $(1-\varepsilon)$ approximation ratio. However, all previously-known approximation schemes incur logarithmic factors in the size of the graph or other parameters of the graph. This raises the question of whether a linear time $(1-\varepsilon)$-approximation can be obtained for all $\varepsilon>0$. We answer this question affirmatively by providing a $(1-\varepsilon)$-approximation algorithm running in time $O\left(\frac{n+m}{\varepsilon^3}\log \frac{1}{\varepsilon}\right)$, where $m$ and $n$ are respectively the number of edges and vertices of $G$. To the best of our knowledge, this is the first truly linear-time approximation scheme for the problem (when $\varepsilon>0$ is a constant). Our algorithm uses assignments arising from a flow-based formulation together with a structural carving lemma. This lemma allows us to progressively carve "sparse" parts of the graph while nearly preserving the densest subgraph, allowing us to shift heavy computations to smaller instances, which eventually yields the mentioned runtime. Our framework also yields a $(1/2 -\varepsilon)$-approximation for the \emph{Densest At-Least-$k$ Subgraph Problem}, where in addition to maximizing the density, we require the subgraph to have at least $k$ vertices. Our algorithm runs in time $O\left( \frac{(n+m) \log^2 n \log \frac{1}{\varepsilon}}{\varepsilon} \right)$. This nearly matches the known $1/2$ approximation hardness while running in near-linear time.

Authors: Emiliano Lancini, Oulin Yang

We study the minimum-weight mixed dominating set problem on threshold graphs. In this problem, vertices and edges have weights, and the goal is to find a mixed set of minimum total weight that dominates every vertex and edge of the graph. We first show that arbitrary weights can be reduced to non-negative weights without changing the asymptotic running time. We then introduce the Constrained Mixed Cover problem and reduce it to the minimum-weight edge-cover problem, obtaining an $\mathcal{O}(n^3)$-time algorithm for this subproblem, where $n$ is the number of vertices. Lastly, we obtain an $\mathcal{O}(n^5)$-time algorithm for the minimum weight mixed dominating set problem on threshold graphs.

Authors: Junho Hwang

We study the graphic $s$-$t$ path TSP on subcubic graphs (maximum degree 3): given two vertices $s,t$, find a shortest walk from $s$ to $t$ that visits every vertex. Our main result is that the optimal $5/4$ coefficient is attained for every terminal pair -- including the difficult case where deleting both $s$ and $t$ disconnects the graph. Concretely, every pair of distinct vertices $s,t$ in a simple 2-connected subcubic graph $G$ admits a spanning $s$-$t$ walk of length at most $\lfloor(5n+n_2(G))/4\rfloor-1$, where $n=|V(G)|$ and $n_2(G)$ is the number of degree-2 vertices; the asymptotic coefficient $5/4$ cannot be improved, and a simple $O(n^2)$ algorithm finds a walk of length at most $\lfloor(5n+n_2(G))/4\rfloor$. An edge-rooted even-cover theorem of Wigal, Yoo, and Yu, combined with a short conversion lemma proved here, gives a bound of this form only when $s$ and $t$ are the two endpoints of a given edge; we remove that adjacency restriction. For cubic graphs ($n_2(G)=0$) the bound reads $\lfloor 5n/4\rfloor-1$, to our knowledge the first $5/4$ bound for cubic path TSP proved directly rather than through the general path-to-tour reduction.

Authors: Krishnan Dehaleesan, Asif Khan, Pranabendu Misra

We study the problem of connectivity augmentation of a planar graph, while preserving planarity. This problem is motivated by many real-world settings such as road-networks, power-networks etc. In these settings, it is crucial to preserve the original planar embedding after augmentation. In 2009, Gutwenger and Mutzel gave a constructive algorithm showing that a connected planar graph with a fixed embedding (a plane graph) can be optimally augmented to a biconnected graph without crossings while preserving the embedding. We further this line of research, by giving an algorithm that computes a minimum set of edges that makes a connected plane graph 2-edge-connected in \(O(|V|(1+α(|V|)))\) time and linear space, where \(α\) is the inverse Ackermann function.

Authors: Antoine El-Hayek, Monika Henzinger, Da Wei Zheng

Having simple algorithms is important for the practical adoption of new algorithms. However, simplifying existing algorithms is a field that does not usually receive a lot of attention from the theoretical computer science community. It also seems like a task that LLMs might perform well. Thus, in this paper we study how well LLMs can simplify algorithms by evaluating three different LLMs on ten different algorithmic problems. Our study resulted in the discovery of two novel algorithms. The first algorithm is for vertex coloring, and gives a refined bound for the so-called asymmetric palette sparsification proposed by Assadi and Yazdanyar [SOSA 2025] with a very simple proof. The second is a further simplification of the algorithm of Saranurak [SOSA 2021] for deterministically computing a global minimum cut in an unweighted graph using expanders.

Authors: Yupan Liu, Qisheng Wang

The Uhlmann fidelity ${\rm F}(ρ_0,ρ_1) = {\rm tr}|\sqrt{ρ_0}\sqrt{ρ_1}|$ is one of the most fundamental quantities in quantum information theory for quantifying the closeness between two quantum states. Estimating the Uhlmann fidelity to within additive error $\varepsilon$ requires a number of copies of the states, or queries to their state-preparation circuits, that depends at least linearly on the smaller of the ranks of $ρ_0$ and $ρ_1$. Consequently, this rank dependence disappears when either state is pure, in which case the query and sample complexities depend only polynomially on $1/\varepsilon$. However, the known optimal estimator for ${\rm F}(ρ,|ψ\rangle\!\langleψ|)$ due to Fang and Wang (ESA 2025) requires prior knowledge of which state is pure. In this work, we remove this mathematically unnecessary prior-knowledge requirement and establish an optimal estimator for ${\rm F}(ρ, |ψ\rangle\!\langleψ|)$ under the sole promise that one of the two states is pure, without knowing which one. Our estimator is obtained by specializing the refined algorithmic Uhlmann transform of Utsumi, Nakata, Wang, and Takagi (2025) to the case where one state is pure. In this setting, the Uhlmann fidelity can be recovered as follows: apply a unitary dilation of ${\rm tr}_{\sf A}(|ψ_0\rangle\!\langleψ_1|)$ (or its inverse) to the reference register $\sf R$ of the purification $|ψ_1\rangle$ (or $|ψ_0\rangle$) on the registers $\sf A$ and $\sf R$, estimate the corresponding square-root amplitude in each case, and take the maximum of the resulting two estimates.

Authors: Amit Sharma, Mohammad Azhar Khan, Rameshwar Pratap, Keegan Kang

\texttt{TensorSketch} by~\cite{pham2013fast,kar2012random} provides efficient sketching algorithms for high-dimensional polynomial kernels $\vec{x}^{\otimes p} \in \R^{d^p}$. \cite{kar2012random} uses dense Johnson-Lindenstrauss (JL)-type projections with computational cost $O(pDd)$, where $D$ denotes the sketch dimension, whereas~\cite{pham2013fast} extends the sparse \texttt{CountSketch}~\citep{count_sketch} algorithm, yielding a faster algorithm for high-dimensional sparse inputs with running time $O\big(p(\nnz{\vec{x}} + D \log D)\big)$. However, the variance of both estimators grows exponentially with the polynomial degree $p$, scaling as $3^{p}/D$. Recent work by~\cite{pmlr-v206-wacker23a} showed that using complex-valued distribution reduces this dependence to $2^{p}/D$ for the approach of~\cite{kar2012random}. However, their method relies on dense JL-type projections with computational cost $O(pDd)$ and does not extend to the algorithm of~\cite{pham2013fast}. In this work, we introduce a simple variant of \texttt{TensorSketch}~\citep{pham2013fast} that achieves the same variance bound as~\cite{pmlr-v206-wacker23a}, while retaining its advantage of the input-sparsity running time. We validate our results with supporting experiments on synthetic and real-world datasets.

Authors: Bill Jin, Alex Zihan Xu

In this paper, we present a stable mergesort variant, "directional mergesort", that to sort an array of $n$ elements makes no more than $nH+3n$ comparisons and $1.5nH+O(n)$ moves where $H$ is the run-based entropy of the input sequence, matching the best existing algorithms in run-adaptive sorting. However, our algorithm is surprisingly minimalistic: it leverages only skip checks, i.e., bypassing the merge step when both halves are already in order, and dynamically changing the direction of merging based on the state of the subarrays. As dynamic run scanning is avoided, all merge steps remain static and derivable from $n$, enabling a reduction to $O(1)$ words of stack space (i.e. space usage excluding the merge buffer) in "directional mergesort$^{++}$", thus improving over the predecessors' $O(\lg n)$ words. Importantly, as directional mergesort adapts only to non-decreasing runs, directional mergesort$^{++}$ also applies a parallel set of rules for (strictly) decreasing runs, allowing the algorithm to also adapt to decreasing runs whilst retaining the original comparison bounds.

Authors: Liangchen Ge

We present a theoretical foundation for inverse-distance attention, from its Euclidean prototype (Resolver) to its non-Euclidean realization (Riemann GeoResolver). The Euclidean part establishes three core theorems: (1) circuit separation---IDA achieves exact retrieval with $\mathcal{O}(1)$ resources while softmax requires $Ω((\log n)^2)$ width; (2) a Polyak--Lojasiewicz inequality with $Ω(e^{Δ^2/\sqrt{d}}/Δ^2)$ stronger constant than softmax, implying linear convergence, $\mathcal{O}(\log n)$ Lipschitz scaling under a low-rank/clustering assumption, $Θ(1)$ Hessian spread, and absence of spurious local minima; (3) a width-independent effective rank bound that limits noise memorization---softmax memorizes arbitrary labels when $d_h\ge n$, while IDA limits test error to $\mathcal{O}(η^2)$. The non-Euclidean extension then builds upon this prototype, replacing Euclidean distance with hyperbolic geodesic distance for storage and spherical geodesic distance for routing. The Riemann GeoResolver framework comprises ten integrated modules: four HIDA operators spanning $Θ(n^2)$ to $Θ(1)$ per token; Hyperbolic Curvature Compression (HCC) with provable error bounds; HyperGate with gradient lower-bound theorem; Spherical Inverse Distance Attention (SIDA) with sphere-analog PL inequalities; Dynamic Memory Genesis (DMG) with $\mathcal{O}(\log T)$ regret bounds; and Geodesic Sparse Routing (GSR) with quality and communication bounds. The Euclidean theorems are proved in full; the non-Euclidean extension theorems are proved with analogous arguments. This work establishes a theoretical arc: from Euclidean attention as a special case, to hyperbolic memory, to spherical retrieval.

Authors: Yaqiao Li, Ali Mohammad Lavasani, Denis Pankratov

A set of intervals $I = \{ I_1, I_2, \dots, I_n \}$ forms a simple chain if, for every $2\leq i \leq n-1$, interval $I_i$ overlaps only with $I_{i-1}$ and $I_{i+1}$. We show that a deterministic memoryless one-directional revoking algorithm achieves a competitive ratio of $2(1 - 1/\sqrt{e}) \approx 0.786$ on the simple chain in the random order model, hence performs worse than the basic greedy algorithm without revoking that has a competitive ratio of $(1 - 1/e^2) \approx 0.864$, but better than any deterministic revoking algorithm in the adversarial model that has a competitive ratio of at most $0.75$. The proof of the latter also leads to a lower bound of $n/4$ for the advice complexity.

Authors: Chuang-Chieh Lin, Guillaume Fertin, Po-An Chen, Stéphane Vialette, Géraldine Jean, Emile Benoist, Colin Cleveland

We study envy elimination by adding goods (EEAG) when the additional pool has bounded supply and no separate budget bound. We establish a sharp type-count dichotomy for binary additive valuations. With one additional item type, EEAG is polynomial-time solvable for any number of agents. More generally, our algorithm permits arbitrary nonnegative integer per-copy values. The envy constraints form a system of difference constraints, and Bellman--Ford returns the componentwise least feasible extension. In contrast, with exactly two additional item types, EEAG is \textsf{NP}-complete even when both types have positive finite supply and the approvers of one type form a subset of the approvers of the other. This closes the two-type case left open by Bentert et al. Separately, we prove weak \textsf{NP}-completeness even for two agents with identical additive valuations, one initially endowed good, and a growing number of unit-supply item types. Thus, bounded-supply hardness appears both with two item-types and many agents and with two agents and many item-types.

Authors: Xiaoyao Huang

We prove a necessary and sufficient Hall condition for a family $A=(A_e)_{e\in E(G)}$ of hypergraphs, possibly with loops, indexed by the edges of a forest $G$. We also show that acyclicity of the index graph is sharp for this Hall characterization. As an application, we prove that every $5$-tough chordal graph is Hamilton-connected, improving earlier sufficient toughness bounds for Hamiltonicity of $18$ in 1998 and $10$ in 2017.

Authors: Theodor Misiakiewicz, Garrett G. Wen

Let $x_1,\ldots,x_n$ be independent standard Gaussian vectors in $\mathbb{R}^d$. An \emph{ellipsoid fit} is a matrix $S \succeq 0$ such that $x_i^\top S x_i =d$ for every $i$, so that all the points lie on the boundary of the centered ellipsoid $\{ x : x^\top S x = d\}$. Saunderson, Parrilo and Willsky conjectured that, as $n,d \to \infty$, this semidefinite feasibility problem undergoes a sharp transition at $n \sim d^2/4$. We prove this conjecture. If $\lim \sup n/d^2 = α^* <1/4$, then, with probability tending to one, an ellipsoid fit exists; moreover, one can choose $S$ with all eigenvalues in a fixed interval $[λ_- , λ_+] \subset (0,\infty)$ depending only on $α^*$. Conversely, if $\lim \inf n/d^2 > 1/4$, then, with probability tending to one, no ellipsoid fit exists, without any spectral restriction. Our proof builds on the Gaussian-equivalence framework developed by Bandeira and Maillard (2025) and closes the two gaps left open in their work: establishing exact fitting and removing the operator-norm constraint. On the satisfiable side, the new ingredients are a head-tail decomposition of the dual vector, exact correction of the sparse head constraints, and a Gaussian comparison principle for the low-influence tail. On the unsatisfiable side, we split a candidate into a low-rank spectral head and a Schatten-3 diffuse bulk, Gaussianize the bulk conditionally on the head, and apply a projected Gordon escape argument. The threshold is governed by the statistical dimension $d(d+1)/4$ of the positive semidefinite cone.

Authors: Prashanti Anderson, Samuel B. Hopkins, Amit Rajaraman

We study the best separable state problem (BSS), which asks for the maximum acceptance probability of a quantum measurement over unentangled states. In classical terms, the goal is to maximize $\langle(x \otimes y), M (x \otimes y)\rangle$ over unit vectors $x,y$ where $0 \preceq M \preceq I$; we call this value $\mathrm{BSS}(M)$. We study $\mathrm{BSS}$ in the "perfect completeness" regime, where given $M$ such that $\mathrm{BSS}(M) = 1$ the goal is to find the best possible solution $x,y$ -- this generalizes the problem of finding a rank-one matrix as close as possible to a given subspace of $\mathbb{R}^{n \times n}$ guaranteed to contain a rank-one matrix. The strongest known algorithmic guarantees for this problem are: (1) an algorithm which finds a solution with value $1-\varepsilon$ in time $\exp(\sqrt{n} (\log n)^{O(1)} / \varepsilon^2)$, due to Barak, Kothari, and Steurer, and (2) an algorithm which finds a solution with value $q/n$ in time roughly $n^{O(q)}$, due to Bhattiprolu, Ghosh, Guruswami, Lee, and Tulsiani. We give a much simpler approach to rounding the SoS relaxation, generalizing the canonical "global correlation rounding" technique, and obtain a better running time. Given $M$ with $\mathrm{BSS}(M) = 1$, our algorithm finds a solution with value $1-ε$ in time $n^{O(\sqrt{n/\varepsilon})}$, and a solution of value $q/n$ in time $n^{O(\sqrt q)}$. Using the same techniques, we prove a new variant of the "pinning lemma", a measure-decomposition theorem widely used in LP/SDP rounding, high-dimensional probability, and statistical physics, which we believe is of independent interest.

Authors: Slobodan Mitrović, Theodore Pan, Wen-Horng Sheu

A number of fundamental graph problems admit simple algorithms based on iterative peeling: repeatedly remove all vertices whose current degree is below a fixed threshold. This paradigm underlies algorithms for density-dependent edge orientation, density-dependent coloring, densest subgraph, and $k$-core decomposition. In this paper, we study these problems in the sub-linear MPC model and achieve the following round-approximation tradeoffs. For density-dependent edge orientation, given any integer $t > 0$, we compute an orientation with maximum out-degree at most $(2+ε)(t+1)α(G)$ in $O(\lg^{1/(t+2)} n \cdot \operatorname{poly}(\lg \lg n))$ rounds, where $α(G)$ denotes the minimum possible maximum out-degree of an orientation of $G$. In the $\operatorname{poly}(\lg\lg n)$-round regime, this gives an $O(\lg\lg n/\lg\lg\lg n)$-approximation, improving the approximation factor of the recent work by Ghaffari and Grunau [PODC 2025]. We obtain a similar improvement for density-dependent coloring. For densest subgraph, we obtain a $(4+ε)$-approximation in $\widetilde O(\lg^{1/3} n)$ MPC rounds and a $(6+ε)$-approximation in $\widetilde O(\lg^{1/4} n)$ MPC rounds. This improves the $\widetilde O(\sqrt{\lg n})$ round complexity of Ghaffari, Lattanzi, and Mitrović [ICML 2019] with a slightly larger approximation factor. This is the first $O(1)$-approximate algorithm for densest subgraph to break the $Θ(\sqrt{\lg n})$ round-complexity barrier in the sub-linear MPC model. For $k$-core decomposition, given any integer $t > 0$, we compute approximate coreness values within a factor of $(2+ε)(t+1)$ in $O(\lg^{1/(t+2)} n \cdot \operatorname{poly}(\lg \lg n))$ MPC rounds for any integer $t > 0$. This improves the $\widetilde O(\sqrt{\lg n})$ round complexity of Ghaffari, Lattanzi, and Mitrović [ICML 2019], again giving a round-approximation tradeoff.

We study shortest paths in directed graphs whose edge weights are of the form $$wt(e) = a_{e,1} \lambda_1 + a_{e,2} \lambda_2 + a_{e,3} \lambda_3 + \cdots + a_{e,d} \lambda_d + a_{e,d+1}.$$ Here, each $a_{e,i}\in\mathbb{R}$ is a fixed constant for each edge $e$, whereas each $\lambda_i$ is a shared variable across the entire graph. So, there could be different shortest paths in the graph for different values of the $\lambda_i$'s. The number of such shortest paths is of interest in several combinatorial optimization problems. This is called the Parametric Shortest Paths problem, and has been studied since the 1980s. For $d=1$, Carstensen (1983) showed that the number of shortest paths in $n$-vertex graphs is at most $n^{O(\log n)}$. She also proved a matching lower bound of $n^{\Omega(\log n)}$, which was later refined by Mulmuley & Shah (2001). For $d=2$, Gajjar & Radhakrishnan (2019) showed an upper bound of $n^{O(\log^2 n)}$. Barth, Funke & Proissl (2022) generalized their result to prove an upper bound of $n^{O_d(\log^d n)}$ for all positive integers $d$. The lower bound did not undergo any improvement over the years. In this paper, we close this long line of research by showing an $n^{O(d\log n)}$ upper bound for all positive integers $d$, exponentially improving the previous upper bound. We observe that a matching lower bound of $n^{\Omega(d\log n)}$ can be obtained by trivially extending existing lower bound constructions for $d=1$. We also show that our proof can be adapted to work for undirected graphs with positive edge weights. Furthermore, for directed graphs whose edge weights are univariate polynomials of degree at most $q$, we prove an upper bound of $n^{O(\log{n}+\log{q})}$. Finally, building upon work on the Point Location problem by Ezra, Har-Peled, Kaplan & Sharir (2020), we construct a Shortest Path Oracle which takes as input a point $\overline{x}\in \mathbb{R}^d$, and outputs a shortest path at $\overline{\lambda}=\overline{x}$ in sublinear time (for a wide regime of $d$). All earlier upper bound proofs proceeded by arranging the vertices of the graph in layers, splitting the graph across its middle layer into two "halves", and then recursing on each half-graph. We deviate from this proof methodology by "halving" the graph in a different way: we eliminate all the odd-numbered layers and retain only the even-numbered layers, whilst maintaining requisite shortest paths of the original graph. We then view shortest paths in the half-graph as convex objects in $d$-dimensional space, which leads us to the required recurrence.

Authors: Hao Wu, Yaqiao Li

We present a top-down depth-four circuit lower bound for Majority function by extending recent work of Göös, Riazanov, Sofronova, and Sokolov (FOCS 2023), who gave a top-down proof of a depth-four circuit lower bound for Parity which relies on the robust sunflower to construct a mirror set and the block unpredictability to find the local limits. The main challenge for the case of Majority is to construct a corresponding mirror set, the difference is that to flip the value of Majority function, one may have to flip many bits of the input Boolean string, while for Parity, flipping one bit suffices. We avoid this flipping by considering slices of the Boolean cube, that is, Boolean strings of fixed Hamming weight approximately $n/2$.

Authors: Jikai Jin

We prove a sharp lower bound for smooth nonconvex stochastic optimization with uniformly bounded gradient noise. In the \(K=1\) fresh-sample model, every randomized adaptive algorithm requires $$Ω\left( \frac{ΔL}{ε^2} + \frac{ΔLσ^2}{ε^4} \right)$$ queries to find a point with expected gradient norm at most \(ε\). This matches the standard upper bound and, to the best of our knowledge, resolves the question raised by [Arjevani et al. 2023] of whether almost-surely bounded oracle error permits a better rate than bounded variance. The proof was independently generated with GPT-5.6 Sol in Codex's Ultra mode during a two-hour session. The human author supplied the prompt and was responsible only forchecking the proof and revising and polishing the manuscript.

Authors: Marshall Ball, Jiaxin Guan

A Proof of Space, PoS, as introduced by Dziembowski et al. [CRYPTO'15], is a two-phase protocol that enables a Prover to convince an efficient Verifier that it has allocated a large amount of persistent memory to storing some information. To our knowledge, all existing PoS protocols are only known to be secure in the random oracle model (or under ad hoc assumptions about cryptographic assumptions). We provide an elementary framework for constructing PoS from a combination of derandomization assumptions and cryptographic assumptions. We provide a few simple instantiations of the framework. We show that non-trivial PoS follow from (a) $\mathsf{E}=\mathsf{DTIME[2^{O(n)}]}$ is hard for exponential-size nondeterministic circuits (an assumption introduced to show $\mathsf{AM}=\mathsf{NP}$), and (b) collision-resistant hash functions. We also show that PoS with nearly optimal parameters and interaction pattern follows from assumption (a) above and (c) SNARGs for $\mathsf{P}$.

Authors: Michal Garl\'\ik, Svyatoslav Gryaznov, Hanlin Ren, Iddo Tzameret

Given two symbolic matrices $X$ and $Y$ of dimensions $m\times n$ and $n\times m$, the *weak rank principle* (WRank) states the equation $XY = A$ is unsatisfiable when $m>n$ and rank of $A$ exceeds $n$. We study this principle as an algebraic generalisation of the weak pigeonhole principle (WPHP). As a strengthening of WPHP, it admits proof complexity lower bounds in settings where none are known for WPHP, while still supporting analogous applications. *Generators for PCR$_{F_2}$*: We prove exponential size lower bounds for algebraic, perfect matching, and bamboo-tree encodings of WRank in PCR$_{F_2}$. The latter encoding is the most relevant for applications to circuit lower-bound formulas, as considered by Alekhnovich, Ben-Sasson, Razborov, and Wigderson (SIAM J. Comput., 2004) and Razborov (Ann. Math., 2015). Using a standard iteration technique we amplify the stretch to exponential. This resolves the open problem concerning the construction of proof complexity generators with good stretch for PCR$_{F_2}$. *Generators for Sherali--Adams:* We develop a new size lower-bound technique showing that WRank, encoded as a bamboo-tree CNF, serves as a proof complexity generator for SA. Our method introduces a pseudoexpectation tailored specifically to the rank principle (and incompatible with WPHP). *Circuit lower bound formulas:* We show that PCR$_{F_2}$ does not admit short proofs of lower-bound statements against Boolean circuits, nor against weak models of algebraic circuits. This settles the open problem raised by Razborov (Ann. Math., 2015) concerning the provability of such lower bounds in PCR$_{F_2}$. *Strength of the weak rank principle:* Finally, we show that WRank is *necessary* for proving NC$^2$ circuit lower bounds and, for odd primes $p$, *sufficient* within the theory corresponding to AC$^{0}[p]$ for deriving AC$^{0}[p]$ lower bounds.

Authors: Haoxing Lin

We prove lower bounds for $k$-OV, $k$-XOR, and $k$-SUM in nonuniform AC$^0$, tracking how the circuit-size exponent scales with $k$ and using no running-time hypothesis. Our framework gives depth-zero projections from colored subgraph isomorphism to the three targets at dimension, row count, or bit width $O(k\log n)$, without increasing depth or size, and preserving gate orientation. For every fixed depth and every sufficiently large fixed $k$, we obtain unconditional bounds $n^{Ω(k)}$ for $k$-OV and $(n/k)^{Ω(k)}$ for $k$-XOR and $k$-SUM, with an absolute exponent-rate constant independent of both $k$ and the depth, while the onset threshold may depend on $(d,k)$. For growing $k = n^{o(1)}$, we obtain, for every fixed depth $d$, the unconditional floor $n^{Ω_d(\min\{\sqrt{k},\log n\})}$. This strengthens to $n^{Ω(k)}$ at depth two for both top-gate orientations, i.e., top conjunction and top disjunction. Assuming a pattern-uniform strengthening of the Li--Razborov--Rossman source lower bound, the same projections complete the subpolynomial frontier with $n^{Ω_d(k)}$ at depth three for both orientations and for every fixed depth $d \geq 4$. All direct $k$-XOR bounds stated above concern odd $k$; a black-box odd-to-even lift transfers any such lower bound through a supplied admissible parameter decomposition. The $k$-SUM projection works for both parities. At the bit width $m = Θ(k\log(en/k))$ used by our projection, a block-carry $Σ_3$ upper bound of size $(n/k)^{O(k)}$ matches the fixed-$k$ specialization of the top-disjunction depth-three lower bound $(n/k)^{Ω(k)}$ up to constants in the exponent. The remaining upper-versus-lower-bound gaps concern depth two, top-conjunction depth three, and other width regimes.

Authors: Masayuki Miyamoto

We study gap amplification of the class $\mathsf{QMA}^{+}(2)$ characterized by unentangled quantum proofs whose amplitudes are nonnegative in the computational basis. This class was recently introduced by Jeronimo and Wu (STOC 2023), and its behavior depends sharply on the completeness-soundness gap: although it captures the power of $\mathsf{NEXP}$ for some small constant gap, it is equal to $\mathsf{QMA}(2)$ for larger constant gap. This is in stark contrast to $\mathsf{QMA}(2)$ where strong gap amplification is known due to the product test by Harrow and Montanaro (FOCS 2010, JACM 2013). In this paper, we prove for every completeness $c$ and soundness $s$ with $c-s=1/\mathrm{poly}(n)$, \[ \mathsf{NEXP} = \mathsf{QMA}^{+}(2,c,s) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14+\frac1{\mathrm{poly}(n)}\right). \] Our result gives a clean complexity phase transition for $\mathsf{QMA}^{+}(2)$ since we have \[ \mathsf{QMA}^{\mathbb R}(2) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14-\frac1{\mathrm{poly}(n)}\right), \] where $\mathsf{QMA}^{\mathbb R}(2)$ denotes $\mathsf{QMA}(2)$ with witnesses restricted to real amplitudes. Our amplification is thus optimal in the sense that a slight improvement of our soundness would have the collapse \[ \mathsf{QMA}^{\mathbb R}(2)=\mathsf{NEXP}. \] Our proof combines symmetric-subspace projections with the relation $\mathsf{QMA}^{+}(1)=\mathsf{NEXP}$ of Bassirian, Fefferman, and Marwaha (ITCS 2024). The main technical ingredient is a dimension-independent de Finetti theorem in Hilbert-Schmidt norm that applies when the number of registers under consideration grows logarithmically.

Authors: Arkopal Dutt, Dale Jacobs, John Jeang, Saeed Mehraban, Vladimir Podolskii

Learning algorithms for structured quantum unitaries and Hamiltonians have primarily considered classes of processes that are local or sparse in the Pauli basis. We turn our attention to learning $n$-qubit quantum unitaries $U$ and Hamiltonians $H$, given query access to $U$ or the unitary evolution of $H$, that may be dense in the Pauli basis but still admit concise Clifford decompositions. Specifically, we consider unitaries (or Hamiltonians) of the form $U = \sum_i α_i C_i$ over Cliffords $C_i$ with bounded Clifford extent $\sum_i |α_i|$. To extract this Clifford structure, we introduce an agnostic tomography protocol for Clifford unitaries that given query access to an unknown unitary $U$ with optimal Clifford fidelity $\textsf{opt}$, outputs a Clifford unitary witnessing fidelity $\geq \textsf{opt} - \varepsilon$ for some error $\varepsilon > 0$, in time $\textsf{poly}(n,(1/\varepsilon)^{\log(1/\varepsilon)})$. We then apply this protocol to obtain tomography protocols for unitaries and Hamiltonians that have bounded Clifford extent. This extends learnability of Hamiltonians from those with sparse Pauli decompositions to those that are dense (i.e., has sparsity $Ω(2^n)$) in the Pauli basis but are Clifford structured.

Authors: Zhi-Long Chen, Nicholas G. Hall

Vehicle platooning offers significant benefits, including reduced energy consumption, lower emissions, improved road utilization, enhanced safety, and reduced driver fatigue. As intelligent driving technologies continue to advance, platoon sizes are expected to increase substantially, making the efficient sequencing and resequencing of vehicles increasingly important. We study the vehicle platoon sequencing and resequencing problem on road networks with varying segment lengths under two fundamental objectives: minimizing total energy consumption and minimizing the maximum energy consumption of any vehicle. For the typically encountered combinations of vehicle and road characteristics, we provide a complete computational complexity classification, either developing polynomial-time algorithms or proving computational intractability. For several intractable cases, we design fully polynomial-time approximation schemes and polynomial-time heuristics with provable performance guarantees. A computational study demonstrates that the proposed heuristics achieve average solutions within 1\% of optimal. We also consider settings in which only limited information about position-dependent energy savings is available and develop a heuristic with bounded worst-case performance. In addition, we present an efficient algorithm for on-road vehicle resequencing when only limited position changes are permitted. Together, these results provide a comprehensive algorithmic framework for energy-efficient vehicle platoon sequencing and resequencing.