OPML feed of all feeds.
Subscribe to the Atom feed, RSS feed to stay up to date.
Thank you to arXiv for use of its open access interoperability.
Note: the date of arXiv entries announced right after publication holidays might incorrectly show up as the date of the publication holiday itself. This is due to our ad hoc method of inferring announcement dates, which are not returned by the arXiv API.
Powered by Pluto.
Source on GitHub.
Maintained by Nima Anari, Arnab Bhattacharyya, Gautam Kamath.
from ECCC Papers
from ECCC Papers
from ECCC Papers
Authors: Steven Heilman, Chris Jones, Giulio Malavolta
We determine the hundredths digit of the real Grothendieck constant by proving $1.773 \leq K_G \leq 1.7799$. Furthermore, numerical heuristics suggest the estimate $K_G \approx 1.779$. We start by simplifying the Gaussian duality theory of $K_G$, based on Hermite projection games and Krivine rounding schemes. The bounds are obtained by a heuristic primal/dual search for these objects, followed by rigorous {\em certification} of their values. The search and certification are performed using AI tools, and in particular the rigorous certificates are very large (analytical reductions to thousands of numerical inequalities).Authors: J. Andres Montoya
We investigate the computational complexity of analyzing the structural and behavioral properties of deterministic k-pebble automata, which represent a natural framework for studying minimal programmable machines. First, we provide an explicit construction of a three-pebble automaton U capable of simulating any deterministic finite automaton (DFA) on a given input word, establishing a link between pebble automata capabilities, Kolmogorov complexity, and automatic complexity. Next, we restrict our architectural framework to two-pebble programmable machines U(2,N) simulating DFAs with at most N states. We analyze the decision problem ANAL(U(2,5)), which asks whether a five-state program can separate two distinct finite words. By establishing a polynomial-time reduction from the quasi-identity checking problem for finite semigroups, we prove that ANAL(U(2,5)) is NP-complete. Finally, we explore the complexity of separating binary strings under the Exponential Time Hypothesis (ETH), showing how computational hardness implies polynomial lower bounds for the size of the smallest DFAs separating binary strings.Authors: Stuart Hadfield
Classical approximation complexity asks what solution quality can be guaranteed with polynomial-time computation. The classes APX, PTAS, and FPTAS distinguish a fixed approximation ratio, approximation to any fixed accuracy, and approximation schemes whose running time is also polynomial in inverse accuracy. Their randomized counterparts are R-APX, R-PTAS, and R-FPTAS. We define bounded-error quantum counterparts BQ-APX, BQ-PTAS, and BQ-FPTAS. Membership requires a uniform quantum algorithm that, on every input, returns a feasible classical solution achieving at least the claimed approximation ratio with probability at least 2/3. Scores (objective values) must be efficiently classically computable. Running time includes parameter selection, preparation, measurement, decoding, and repetition. Many quantum optimization methods are used heuristically, and high benchmark scores alone do not establish these guarantees. We further establish a conditional hierarchy for logarithmic, polynomial, and exponential approximation factors. Assuming NP $\subsetneq$ BQP, the quantum classes form a strict hierarchy. Problems based on prime factorization and discrete logarithms give conditional quantum-classical separations. Certified Maximum Order has an exact quantum algorithm, while any randomized polynomial-time algorithm guaranteeing at least an inverse-polynomial approximation ratio on every input would yield efficient factoring. Discrete-Logarithm Fitting has an exact quantum algorithm and a deterministic one-half approximation, but any fixed improvement over one half would give a randomized polynomial-time algorithm for the safe-prime discrete logarithm problem. Our results show, under explicit complexity assumptions, that quantum computation can improve worst-case approximation guarantees. A quantum-classical gap for common problems such as MaxCut or MaxSAT remains open.Authors: Mingyu Lee, Sanghyun Lee, Kabgyun Jeong
Pebble games model computations under a fixed space budget. Spooky pebbling allows quantum memory to be released by measurement, with the resulting phases corrected later. We study two-input computations with binary-tree dependencies and determine the optimal work and parallel depth for complete binary trees. Our key idea is to clean up the tree in blocks, reducing repeated recomputation of intermediate values. For the complete tree $B_h$ with $n=2^h-1$ vertices and every space budget $h+1\le s\le n$, we give an algorithm with asymptotically optimal work $Θ(nh/\log(s+1))$. At the minimum budget $s=h+1$, this improves the $O(n\log n)$ bound of Kornerup, Sadun, and Soloveichik to $Θ(n\log n/\log\log n)$, resolving their time-optimality question. We also construct a parallel schedule with optimal depth \[ Θ\!\left(h+\frac ns \max\!\left\{\frac{h}{\log(s+1)},\,1+\log^*h\right\}\right). \] Our lower bounds hold for every full binary tree. We also show that achieving optimal parallel depth can require asymptotically more work than minimizing work alone. Applying our schedule to the RNS point-addition trees in the public implementation of Chevignard, Fouque, and Schrottenloher reduces their Toffoli/AND gate count by $20.86\%$ for a P-224 instance and $22.66\%$ for a P-256 instance, using the same arithmetic circuits and peak workspace.Authors: Shuhong Gao
The Aharonov-Regev proof that $\mathrm{GapCVP}_{c\sqrt n}$ lies in $\mathsf{NP}\cap \mathsf{coNP}$ uses a verifier that tests dual lattice vectors; its proof gives $c=100$. We study this verifier through a linear program in which a certificate is modeled as a sample from a probability distribution on the dual lattice. This viewpoint gives an exact analysis of the close-target tests: adding gradient and Hessian checks increases the certified close radius from $σ^{-1}/4$ to $σ^{-1}\sqrt{3/16}$, and higher derivatives cannot improve it within this framework. With Gaussian certificates for far targets, we obtain $$\mathrm{GapCVP}_{c\sqrt n},\ \mathrm{GapSVP}_{c\sqrt n}\in \mathsf{NP} \cap\mathsf{coNP}$$ for every $c>2/(π\sqrt3)\approx0.3676$. An appendix gives a finite-bit implementation of the verifier. We also show that the Gaussian certificate is not always optimal and solve the unbounded-support program exactly for targets of order two, where its value is determined by the spectral capacity of an odd dual coset.Authors: Arip Asadulaev
Language models are more and more often asked for structured output: JSON that follows a schema, or a tool call with typed arguments. A small machine, an automaton, enforces the format by forbidding the tokens that would break it. We observe that this machine has a rare property: from any of its states, each token leads along exactly one path. Graphs in which only a few paths join any two points are a classical object of complexity theory, and our theoretical result settles an open question about them: one can decide whether such a graph connects two points while verifying that it really has few paths, with very little memory. Precisely, the problem lies in the classes ReachUL, LOGDCFL, C=L and SC2, and needs only O(log2 n/ log log n) space, below the classical O(log2 n) of Savitch's theorem. The constructions behind the proofs become an inference engine: text the format forces is written without running the model, the mask is recomputed on the GPU without any table, recursive formats use a small stack, every output stays valid under a token limit, and independent fields are decoded in parallel and verified. On one 16 GB Apple M2 Pro with Qwen3.5-2B and 4B, against MLX with llguidance, the standard setup for this hardware, schema-constrained extraction finishes 1.2- 1.3x sooner with the same answers, a grammar costs 3 MB instead of up to 1.5 GB, one server holds sixteen grammars where tables run out of memory, and sixteen tool-calling agents finish 2.5x sooner.Authors: Markel Zubia, Nils Jansen
Identification is the task of recovering the parameters of an unknown ground-truth model from sampled data. When parameters other than the ground truth induce the same output distribution, data alone does not provide enough information to recover the ground truth, and the model is thus called unidentifiable. We study the identifiability problem for hidden Markov models (HMMs): given an HMM, is it identifiable? Existing work on HMM identification establishes conditions under which the ground-truth HMM can be identified. However, most of these conditions are sufficient but not necessary, meaning that, when a model does not satisfy them, its identifiability remains inconclusive. We instead take a computational perspective: is there a sound and complete algorithm that decides whether a given HMM is identifiable, and if so, what is the complexity of this decision problem? We consider the decision problems arising from the various notions of identifiability in the literature, including deterministic, generic, global, local, state-permutation- invariant, and finite-alphabet identifiability. We show that all of these problems are decidable in PSPACE, via reductions to the theory of the reals at various levels of its quantifier-alternation hierarchy. We further show that the deterministic variants are already coETR-hard (and hence coNP-hard) for simply parameterized families.Authors: Yohan Finet, Victor Drouin-Touchette
Comb inequalities are important cutting planes for the symmetric travelling salesman problem, yet the complexity of their exact separation has remained a longstanding question in polyhedral combinatorics. We present a reduction from 3-SAT proving that deciding whether a comb inequality is violated is NP-complete and that the corresponding separation problem is NP-hard. This result holds even when the input vector belongs to the subtour elimination polytope, every edge value is zero, one half or one and the support graph is nonplanar with maximum degree four. The reduction constructs a graph in which six-vertex ladder gadgets encode Boolean relations and cubic graphs enforce consistency among occurrences of each logical variable. For a propositional logic formula with $v$ variables and $m$ clauses, the constructed graph has $40v+70m+30$ vertices and a linear number of positive edges. The reduction also proves hardness when every permitted tooth has two or four vertices with half of the tooth in the handle. We discuss consequences for approximating the maximum comb violation, optimization over the comb relaxation and explain why hardness of separation does not automatically transfer to larger inequality families.Authors: Vincent Liew
SAT solvers are empirically known to perform poorly when reasoning about multiplication. Yet for over a decade we have lacked a theoretical explanation for this phenomenon. CDCL SAT solvers implicitly search for resolution proofs, and no lower bound on proof size has ruled out the existence of short proofs that solvers simply fail to find. We give the first lower bound of this kind by showing that general resolution proofs of the associativity of $n$-bit multiplication require size $2^{Ω((n/\log n)^{1/4})}$. This lower bound holds for a broad class of multiplier encodings based on partial product summation, including the standard array and Wallace-tree multipliers used to bit-blast multiplication in SMT solvers. This result resolves an open problem of Beame and Liew. The proof constructs a reduction from a perfect-matching principle on bounded-degree bipartite expander graphs to multiplier associativity. Itsykson, Slabodkin, and Sokolov proved that this principle is hard for resolution. The lower bound for multiplier associativity follows. The same reduction, when combined with Håstad's recent lower bound for the perfect-matching principle of the odd grid, yields an exponential lower bound for multiplier associativity in the stronger bounded-depth Frege proof systems.Authors: Alex Meiburg
The existential theory of the reals asks whether polynomial constraints with integer coefficients have a real solution. We give a proof placing this problem in the counting hierarchy. The first argument is intended to expose the essential steps, and a separate analysis lowers the bound to $\exists \mathbb{R}\subseteq\textsf{BPP}^{\textsf C_3\textsf P}\subseteq\textsf C_4\textsf P$, the fourth level of the hierarchy. For each fixed $w$, sentences with $w$ alternating real quantifier blocks lie in $\textsf C_{9w+17}\textsf P$. We then treat exact semidefinite feasibility, PosSLP, square-root sum, geometric real counting, Euler characteristic, and complex feasibility in separate applications. The corresponding bounds include $\textsf{BPP}^{\textsf C_2\textsf P}$ for general SDP, $\textsf{BPP}^{\textsf{PP}}\cap\textsf{P}^{\textsf{NP}^{\textsf{PP}}}$ for PosSLP and square-root sum, and $\textsf{FP}^{\textsf C_4\textsf P}$ for total geometric real counting. Note: These proofs were discovered by ChatGPT after a series of conversations ending on September 29th 2026. A group of researchers has been working to digest the proof, and while the most essential arguments appear correct, we are endeavoring to give this result the treatment it deserves and a proper exposition and development to benefit of the community. However, on October 6th, OpenAI released a very similar result, with a slightly weaker bound. While we work to improve our exposition of this proof, the current version has been uploaded as a service to the community to compare the different proof techniques. While the listed author takes responsibility that the proofs appear to be correct, he has not played a nontrivial role in developing them, and believes the human value will be in good exposition and canonicalization of the results.Authors: Subhransu S. Bhattacharjee, Dylan Campbell, Rahul Shome
Procrustes-Wasserstein alignment jointly estimates a matching and rotation without supplied correspondences, but alternating minimization can stop at suboptimal solutions. Rubix solves the equally weighted planar problem globally under squared Euclidean loss. Each matching $σ$ of two centered $n$-point sets defines a complex correlation $z_σ=\sum_i\bar x_i y_{σ(i)}$. Their convex hull is the permutation polygon: supporting vertices give optimal matchings at fixed rotations, and the farthest vertex gives the global alignment. We prove the sharp bound of $n(n-1)$ vertices for $n\ge2$, answering Rote's rotation-assignment open problem. In exact arithmetic, assignment queries recover the polygon in $\mathcal O(n^5)$ operations. Assignment-based bounds extend the approach to three-dimensional rotations and partial matching at a supplied translation through branch-and-bound. On timed MPEG-7 shape pairs, Rubix attains every numerical reference value in 12 ms on average, 50 times faster than a rotation grid at the same accuracy. Its distances improve gravity-aligned matching of real 3D scans, shape retrieval and noisy crystal classification over alternating minimization.Authors: James Fox, David P. Woodruff
Given value-oracle access to a symmetric submodular function $f:2^V\to\mathbb{R}$ with $|V|=n$, a nontrivial minimizer can be found using $O(n^3)$ value queries. We study the weaker comparison model, in which a query on $S,T\subseteq V$ reveals only whether $f(S)$ is smaller than, equal to, or larger than $f(T)$. We give a deterministic polynomial-time algorithm that finds a nontrivial minimizer of any symmetric submodular function using $O(n^3)$ comparisons, matching the best-known deterministic value-oracle bound despite not knowing the function values. More generally, the same $O(n^3)$-comparison bound holds for minimization over the nonempty members of any downward-closed family. Our algorithm combines the minimum-capacity ordering recently introduced by Iwata and Konno with the contraction framework of Goemans and Soto. Applying this result to weighted graph cut functions resolves the main open question of Cohen-Addad et al., who gave an $\widetilde{O}(n^3)$-comparison algorithm that runs in exponential time and asked whether a weighted minimum cut can be found in polynomial time using comparisons. For graphs with $m$ edges of integer weight at most $B$, we also give a deterministic polynomial-time algorithm that finds a minimum cut using \[ \widetilde{O}\!\left(n^2+\min\!\left\{mB,\,nB^2\right\}\right) \] comparisons, improving on the $O(n^3)$ bound when $B$ is small. Finally, we show that every randomized algorithm that outputs a minimum cut with probability at least $2/3$ makes $Ω(n \log n)$ expected comparisons in the worst case. Under the stronger assumption that all edge weights are polynomially bounded integers, we obtain an $Ω(n \log \log n)$ expected comparison lower bound. These bounds contrast with the value-oracle model, where no $ω(n)$ lower bound is known even for deterministic algorithms.Authors: MohammadTaghi Hajiaghayi, Danny Mittal, Saeed Seddighin
The (min,+)-convolution of two sequences A and B of length n is the sequence C with C[k] = min_{i+j=k} (A[i]+B[j]). For bounded inputs, whose entries are integers in {0,...,O(n)}, prior work computes it in truly subquadratic time when the inputs are monotone; the algorithm of Chi, Duan, Xie, and Zhang (STOC 2022) takes expected O~(n^{1.5}) time. We introduce a monotonicity measure ranging from 0 (monotone) to 1/2 (entirely non-monotone): a sequence has monotonicity alpha if it can be partitioned into O(n^alpha) monotone subsequences, and by the Erdos-Szekeres theorem every sequence has monotonicity at most 1/2. We show that truly subquadratic time is achievable even when just one input is barely monotone, that is, has monotonicity 1/2 - Omega(1): if A has monotonicity alpha, we compute the convolution in expected time O~(n^{5/3+2alpha/3}) for every bounded B. If B has monotonicity beta as well, the expected time improves to O~(n^{(3+alpha+beta)/2}), which matches the monotone case for alpha = beta = 0; this algorithm also allows infinite entries placed arbitrarily. We complement these algorithms with fine-grained reductions. Bounded (min,+)-convolution reduces to bounded monotone (min,+)-convolution of length N = O(n^{1.5}), so an O(N^{4/3-eps})-time algorithm for monotone inputs would give an O(n^{2-3eps/2})-time algorithm for bounded inputs. Similarly, entries bounded by n reduce to entries bounded by N^x on sequences of length N = Theta(n^{2/(1+x)}). We also show that if only A has entries in {0,...,M}, we can compute the convolution in O~(n(M+1)) time, and in O~(n^{1.5} sqrt(M)) time if A may also contain +infinity.Authors: Travis Gagie, Gonzalo Navarro
Taxonomic classifiers such as Kraken assign each $k$-mer of a reference database to the lowest common ancestor (LCA) of the genomes containing it, but this works less well as databases grow, because more and more $k$-mers are shared across species. Cliffy (Ahmed, Boucher and Langmead, 2025) instead uses variable-length exact matches found with an r-index, and can list approximately the genera containing each match; on 16S rRNA it is more accurate than Kraken~2, but its index is large and expensive to build. We present KATKA, which finds the maximal exact matches (MEMs) of at least a given length in each read with Boyer--Moore--Li on a run-length compressed suffix array, counts the occurrences of each MEM in each genus exactly with a complete, run-length compressed tag array, and gives each genus credit in proportion to those counts. On the SILVA 16S rRNA database, KATKA's default index takes 1.44\,GB and can be built in minutes on a desktop computer; it classifies a read in 66\,$μ$s with one thread and reaches 93.8\% genus-level accuracy, close to what Cliffy reports for its 9\,GB index. Grammar-compressing the runs of the tag array shrinks the index to 1.04\,GB, at 75\,$μ$s per read. On the same machine and reads, it is more accurate than Kraken~2 (79.3\%) and Tagger (81.7 to 92.8\%, depending on how mates that disagree are scored). Indexing minimizer digests instead of the sequences makes the index three times smaller and classification 1.7 times faster, at a cost of 1.3 points of accuracy. KATKA is available at github.com/TravisGagie/KATKA.Authors: Przemyslaw Uznanski
In this note, we extend the analysis underlying a recent matrix-multiplication result by OpenAI to rectangular products and prove that $ω(1,k,1)\le 2$ for $0\le k\le \frac{1}{2}$ and $ω(1,k,1)\le 1+k+\frac{1}{4k}$ for $k\ge \frac{1}{2}$. In particular, $ω(1,\frac{1}{2},1)=2$ and the dual exponent satisfies $α\ge \frac{1}{2}$. We use the shared-leg entropy inequality and polynomial-multiplication degenerations from that work, retaining two-leg symmetry and the orientation of each sector. Logarithmic averaging produces homogeneous auxiliary profiles. Their powered versions have a common asymptotic slope, and bounding their intercepts gives the spectral constraint $b\le 4a(1-a)$. This yields the rectangular curve by tensor-spectrum duality. As an application, Zwick's algorithm for all-pairs shortest paths in directed unweighted graphs runs in $O(n^{2.5})$ time. Combining the rectangular bound with the $(\min,+)$-product improvement of Alman and Vassilevska Williams further gives $O(n^{2.4999})$ running time.Authors: Kun He, Zhidan Li, Kuan Yang
We study approximately uniform sampling of satisfying assignments from random $k$-SAT formulas. For every sufficiently large $k$ and density $0 < α\le 2^k/k^{16}$, we prove that, with high probability over the formula, there is a sampler whose output distribution is within total variation distance $\varepsilon$ of the uniform distribution on satisfying assignments and whose expected running time is at most $(nk(α+1)/\varepsilon)^C$, for a universal constant $C$. Our algorithm improves the counting and sampling algorithms obtained by Chen, Lonkar, Wang, Yang, and Yin (STOC 2025) at the density $2^k/\operatorname{poly}(k)$ with running time $(n/\varepsilon)^{\operatorname{poly}(k,α)}$. Our result achieves this density region for sampling with a polynomial degree independent of both the width and the density. Our algorithm separates a high-degree core from the remaining variables, and combines a recursive sampler for the residual formulas with approximate block heat-bath updates on the core. We adapt the recursive insertion-chain framework of Jain, Mizgerd, and Pham (2026) from $2$-trees to ordinary connected violation sets. Expansion and random literal signs yield uniform moment bounds for the resulting correlated lists across all residual formulas, allowing the signed-flow analysis to give a universal polynomial running-time degree. A polymer expansion and an exploration bound establish a polynomial spectral gap for the core dynamics.Authors: Lixi Ye, Baitian Li
We show that the subset sum problem can be solved in time $O(2^{0.499999n})$, breaking the $2^{n/2}$ meet-in-the-middle barrier. Our approach builds on the representation technique framework of Randolph and Węgrzycki (STOC 2026). We choose a representation for which testing the compatibility of pairs of partial solution vectors is exactly the partial match problem. To beat exponent $1/2$ for subset sum, it then suffices to give a nontrivial partial match algorithm in a certain parameter regime. We achieve this by designing a depth-2 linear circuit for the partial match matrix, which yields an efficient algorithm via the framework of Alman and Li (FOCS 2025).Authors: Alina Harbuzova, Saba Lepsveridze, Mahbod Majid, Ankur Moitra
We give a polynomial-time algorithm for approximating the partition function of mean-field mixed $p$-spin models to arbitrarily high accuracy throughout the second-moment regime. This improves the quasipolynomial-time algorithm of Bencs, Huang, Lee, Liu, and Regts (arXiv:2507.15616) and answers their open question. In particular, our result covers the entire replica-symmetric regime of the Sherrington--Kirkpatrick model. The algorithm is deterministic, runs in time polynomial in $n$ and $1/\varepsilon$, and succeeds for every typical realization of the disorder. Our main technical contribution is a new algorithmic application of color coding to the classical high-temperature expansion introduced by Aizenman, Lebowitz, and Ruelle in their study of fluctuations of the Sherrington--Kirkpatrick partition function. We combine this approach with the zero-freeness established by Bencs et al. (arXiv:2507.15616) to convert additive approximations into multiplicative ones.Authors: Qisheng Wang
Rényi entropy estimation has been comprehensively investigated by Acharya, Orlitsky, Suresh and Tyagi (SODA 2015; IEEE Trans. Inf. Theory 2017) and consequent works, whereas only the sample complexity of Rényi entropy estimation of integer order has been settled. In this paper, we settle the sample complexity of Rényi entropy estimation of noninteger order, thereby completing the complexity picture of Rényi entropy estimation. Specifically, we show that for any noninteger $α> 0$, it is sufficient and necessary to use \[ Θ\!\left(\frac{d^{\max\{1/α,1\}}}{\varepsilon^{1/α}\log(d)} + \frac{d^{|1-1/α|}}{\varepsilon^2}\right) \] samples to estimate the Rényi entropy of order $α$ of an unknown discrete distribution over an alphabet of size $d$ to within additive error $\varepsilon$. For the upper bound, we reduce the bias using a refined polynomial approximation estimator for large probabilities. For the lower bound, we employ a different hard instance equipped with a new moment matching construction. The constructive moment matching has constant bounded high-order moments, while attaining a fixed ratio between the $α$-th moments, which is of independent interest.Authors: Nick Fischer, Ce Jin, Yinzhan Xu
Min-Plus Convolution is a central problem in fine-grained complexity, and the associated Min-Plus Convolution Hypothesis forms the basis for a wide range of conditional lower bounds for fundamental problems. It is closely connected to the APSP and 3SUM Hypotheses, and in fact implies both, making it a unifying hypothesis for two of the main pillars of the area. In this work we establish several strong results related to Min-Plus Convolution. We design a universe reduction, showing, under a plausible additive combinatorics assumption, that the Min-Plus Convolution Hypothesis is equivalent to the Strong Min-Plus Convolution Hypothesis. We also obtain tight conditional lower bounds for multiple long-standing problems, including Min-Max Convolution and Bounded Monotone Min-Plus Convolution. Our approach is inspired by Fischer's recent equivalence between several variants of APSP [STOC '26], but extending that technique to the arithmetic setting requires overcoming deep obstacles. To this end, we develop a novel additive structure theorem that can be viewed as a higher-order substitute of the Balog-Szemerédi-Gowers (BSG) theorem, allowing us to extract strong additive structure even from weakly structured sets. Building on this structural result, we show that certain structured 3SUM instances (namely, sets with low rank) can be solved in truly subquadratic time. This algorithm forms the main algorithmic ingredient in our reductions. Besides, it generalizes all previously known truly subquadratic-time special cases of 3SUM, and is therefore of independent interest.Authors: Zimo Sheng, Tian Bai, Mingyu xiao
An interval graph is the intersection graph of a family of intervals on the real line. \textsc{Interval Completion} asks whether a given graph can be transformed into an interval graph by adding at most $k$ edges. Although the problem is fixed-parameter tractable when parameterized by $k$, whether it admits a polynomial kernel has long been an open question. We resolve this question by giving the first polynomial kernel for \textsc{Interval Completion}. Our main contribution is a parameter-preserving polynomial-time reduction from \textsc{Interval Completion} to \textsc{Odd Cycle Transversal} (OCT). Combining this reduction with the known randomized and deterministic polynomial kernels for OCT and a polynomial-time reduction back to \textsc{Interval Completion}, we obtain a randomized kernel with $\widetilde O(k^{18})$ vertices and $\widetilde O(k^{36})$ edges, and a deterministic kernel with $O(k^{36})$ vertices and $O(k^{72})$ edges. Here, $\widetilde O$ suppresses polylogarithmic factors in $k$.Authors: Mihail Stoian
We present a deterministic reduction from min-sum subset convolution to min-plus matrix product. We show that if the min-plus product of two $D\times D$ matrices with $β$-bit integer entries can be computed in $D^{3-δ}\operatorname{poly}(β,\log D)$ time for a fixed rational $0<δ<1$, then min-sum subset convolution on an $n$-element universe can be solved in $(2+2^{-δ})^n 2^{O(\sqrt n\log(n+1))}\operatorname{poly}(n,β)$ time. Instantiating this reduction with the recent breakthrough on subcubic min-plus matrix product by Alman and Vassilevska Williams gives a Las Vegas algorithm with expected running time $O^*(2.9987^n)$ and a deterministic algorithm with running time $O^*(2.9997^n)$, strictly breaking the longstanding $3^n$ computational barrier. Notably, these speedups translate directly to database query optimization, yielding the same expected and deterministic running-time bounds for join ordering under the $C_{\mathrm{out}}$ cost function.Authors: Yuan Ma, Yiqun Lisa Yin
In the cow-path problem, a cow must find a goal lying at an unknown distance on one of $w$ paths connected only at the origin, and performance is measured by competitive ratio. Kao, Reif and Tate designed an efficient randomized algorithm in which the cow visits the paths in a fixed cyclic order. They proved the algorithm is optimal for $w=2$, and subsequently Kao, Ma, Sipser and Yin proved its optimality for all $w$, with a claim that no algorithm does better than the best cyclic one. This note provides a detailed proof of that claim.Authors: Nick Fischer, Adam Polak, Jonas Schmidt
We show that if the 3SUM problem on integer-valued inputs can be solved in truly subquadratic time, then it can also be solved in truly subquadratic time on real-valued inputs. This answers an open problem posed by Chan, Vassilevska Williams, and Xu [STOC 2022], and constitutes the first such tight real-to-integer self-reduction in fine-grained complexity. Our proof relies on a surprising combination of the Frank--Tardos theorem from optimization with Freiman-type theorems from additive combinatorics.Authors: Stepan Zharkov, Krish Singal, Ashwin Padaki, Alexandr Andoni
Sparse attention mechanisms estimate attention over $n$ tokens using a small subset of keys. Many existing approaches use maximum inner product search (MIPS) to retrieve the heaviest keys, which motivates the following question: given black-box access to a MIPS oracle, how many keys must be retrieved to output an $\varepsilon$-accurate attention estimate? We answer this question by unifying prior approaches through the framework of priority sampling. With a single MIPS index, we show that $Θ(\sqrt{n}/\varepsilon)$ retrieved keys are both sufficient and necessary. With $Θ(\log n)$ indices, we give an algorithm that retrieves only $O(\log n+1/\varepsilon^2)$ keys and prove that this is near-optimal. More generally, we design algorithms that establish a smooth tradeoff between the number of MIPS indices and number of retrieved keys. We then show that if we allow augmentation of keys and queries, we can bypass the above lower bounds: there exists a simple priority-sampling estimator using a single MIPS index and $O(1/\varepsilon^2)$ retrieved keys. When integrated into LLM inference, our algorithms outperform top-$k$ and sampling approaches used in prior work and yield attention approximation that scales favorably to long contexts.Authors: Mark Braverman, Zhongtian He
The undirected multiple-unicast conjecture [LL04] asserts that network coding offers no throughput advantage over multicommodity flow. We refute this conjecture by constructing a deterministic linear network code over $\mathbb{F}_9$ on a 182-vertex bipartite subgraph of the point-line incidence graph of $\mathrm{PG}(2,9)$. The construction supports $157$ independent unicast sessions at common coding rate at least $1$, while every fractional multicommodity flow has common rate at most $147/157$. By the amplification theorem of~[BGS17], this yields a family of undirected multiple-unicast instances with coding gap $Ω((\log n)^\varepsilon)$ for some $\varepsilon>0$. We also introduce a nondeterministic model of network coding based on locally verifiable certificates, which guides our construction and may be of independent interest. Building on the high-girth graph and error-correcting code framework of [BH25], we use GPT-6 to find a nondeterministic counterexample based on a new choice of Reed--Solomon local codes, and then convert this example into a causal code using an edge orientation and local search.Authors: Ergute Bao, Graham Cormode, Xiaokui Xiao, Ting Yu
Finding heavy nodes in a tree---those whose counts exceed a given threshold---is a building block for analysis and learning over structured data. Achieving record-level differential privacy (DP) without sacrificing accuracy is challenging because each record contributes to counts along an entire root-to-leaf path, allowing privacy costs to accumulate across levels. Existing methods account for the multiple threshold comparisons for each record incur additive error margins of $Ω_{\varepsilon,δ}(\log h)$ or $Ω_{\varepsilon,δ}(\sqrt{\log h})$ for tree height $h$. We introduce \textsc{BetweenCut}, an $(\varepsilon,δ)$-DP algorithm with an additive error margin of $O_{\varepsilon,δ}(\log\log h)$, improving the existing bounds for deep trees. This error holds simultaneously for all nodes and is independent of the input database size.Authors: Weitian Tong, Yao Xu
We give a deterministic polynomial-time $1.6908$-approximation for Maximum Weighted $3$-Set Packing, breaking the $\sqrt3$ locality-gap barrier of squared-weight local search. The approximation ratio for this problem progressed from Berman's $2$ [Ber00] to Neuwohner's $2-\frac{1}{63{,}700{,}992}+ε$ [Neu21]. Thiery and Ward then obtained $1.786$ [TW23], while Thiery subsequently improved the bound to $1.761+ε$ and finally to $\sqrt3 \approx 1.732051$ through a layered exchange analysis [Thi23]. Thiery also proved that $\sqrt3$ is a locality-gap lower bound for the squared-weight objective even with exchanges of arbitrary size. Our algorithm performs in two phases and combines two objectives. Phase~I computes a bounded-exchange local optimum for the squared-weight potential and analyzes it through Thiery's layered framework, while strengthening the terminal analysis by preserving internal tree-edge slack for nonsingleton components and exploiting the incidence structure of $3$-sets for final singletons. This yields an augmented structural inequality with residual positive claw gain under the original objective. Phase~II switches to the original objective and recovers sufficient residual gain through an auxiliary weighted $9$-Set Packing instance. A covering argument transfers the structural bound through the high-girth lift used only in the analysis.Authors: Zhiqiang Xu
We give a deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs. For every finite simple bipartite graph of maximum degree at most an integer $Δ\ge3$, the algorithm assigns signs to its edges so that the signed adjacency matrix has operator norm strictly less than $2\sqrt{Δ-1}$. Our algorithm builds on the randomized recursive repair framework of Jadbabaie, Saberi, and Sra~\cite{JSS26}, with deterministic rules for sign selection and vertex deletion.Authors: Eden Chlamtáč
We give an $n^{0.3+\varepsilon}$-approximation algorithm for the Steiner $k$-Forest problem, for any constant $\varepsilon>0$. As a function of $n$, this improves over the $O(\min\{\sqrt{n},\sqrt{k}\})$-approximation of Gupta et al. [ESA'07, TALG'10] which has stood for nearly two decades for the general case, as well as the later $n^{0.448}$-approximation of Dinitz et. al [APPROX-RANDOM'14, TALG'17] for the uniform weight case. On the other hand, we show that, due to lower bounds on the Densest $k$-Subgraph problem, the $O(\sqrt k)$-approximation for Steiner $k$-Forest likely cannot be improved. Specifically, we show that for any sufficiently small $\varepsilon>0$, an $O(k^{1/2-\varepsilon})$-approximation for Steiner $k$-Forest would surpass known degree-$n^{Ω(\varepsilon^2)}$ Sum-of-Squares integrality gaps for Densest k-Subgraph and refute the corresponding dense-versus-random conjecture.Authors: Zhe Hou, Jingcheng Liu, Yixiao Yu
We study sampling from the Gibbs distribution of the Sherrington-Kirkpatrick (SK) model with Glauber dynamics. For every fixed inverse temperature $0\leqβ<1$ and every fixed $M,D>0$, we give a polynomial-time simulated annealing algorithm whose output distribution is within $n^{-M}$ total-variation distance of the Gibbs distribution, with probability at least $1-n^{-D}$ over the interaction matrix. The algorithm starts from uniform product spins and uses Glauber dynamics along an increasing inverse-temperature schedule. The same approach also yields partition-function estimates with relative error $n^{-M}$. The key ingredient is a quantitative weak Poincaré inequality. Building on the stochastic-localization approach to weak Poincaré inequalities [Davies, Lee, Sandhu, and Shi, arXiv:2607.08160, 2026], we use Gaussian isoperimetry to directly compare exact stochastic localization paths. Our comparison tolerates failures of local Lipschitz continuity of the posterior mean by controlling their accumulated cost. The local Lipschitzness comes from approximating the posterior means by stationary points of the Thouless-Anderson-Palmer (TAP) free energy in locally strongly convex regions located by approximate message passing, a paradigm introduced by algorithmic stochastic localization [El Alaoui, Montanari, and Sellke, 2025; Celentano, 2024]. The approximation errors are roughly characterized by the validity of the TAP gradient equations, but in a different coordinate. To show that the errors rarely accumulate too much, we need a strong concentration control. A direct argument would require solving a variant of an open problem by Talagrand [2010, Research Problem 1.7.9]. We bypass this open problem with an intermediate conditioning step and transfer the control back by establishing the stability of the TAP gradient under deletion of coordinates.Authors: Akanksha Agrawal, Fedor V. Fomin, Petr A. Golovach, Vinod Gupta, Yash Hiren More, Vidya Sagar Sharma
Bentert, Fomin, Golovach, Korhonen, Lochet, Panolan, Ramanujan, Saurabh, and Simonov (SODA 2025) initiated the parameterized study of Edge-Disjoint Shortest Cycle Packing: given a weighted graph $G$ and an integer $k$, decide whether $G$ contains $k$ edge-disjoint cycles of minimum weight. They showed that the problem admits an algorithm running in time $n^{O(k^6)}$ and asked whether it is fixed-parameter tractable or $W[1]$-hard parameterized by $k$. We resolve this question by proving that Edge-Disjoint Shortest Cycle Packing is $W[1]$-hard parameterized by $k$, even on unweighted subcubic graphs. The same lower bound also applies to the vertex-disjoint variant. For planar graphs, they provides a construction of a kernel with $O(k^2)$ vertices and an algorithm running in time $k^{O(k)} \cdot n^{O(1)}$, and explicitly asked whether the problem admits a single-exponential algorithm of running time $2^{O(k)} \cdot n^{O(1)}$. Rather than addressing this question in isolation, we introduce a more general framework, Diverse Shortest Cycle Coverage, which asks for $k$ shortest cycles that may overlap in a controlled way while maximizing the total weight of covered edges. This framework simultaneously captures edge-disjoint shortest cycle packing, the problem of finding diverse shortest cycles, and the problem of maximizing edge coverage by shortest cycles. Our main algorithmic result shows that Diverse Shortest Cycle Coverage can be solved on planar graphs in time $2^{O(k)} \cdot n^{O(1)}$, thereby giving a single-exponential algorithm for Edge-Disjoint Shortest Cycle Packing as a special case. The key idea of our algorithm is a structural analysis of the Laminar Shortest Cycles Tree, a tree-like decomposition that reveals a laminar interaction pattern among shortest cycles in planar graphs and enables an efficient dynamic programming algorithm.Authors: Saeed Amiri, Sebastian Siebertz
For every fixed proper minor-closed class $\mathscr C$ and every $ε>0$, we give a deterministic LOCAL algorithm that returns a dominating set of size at most $(2a(\mathscr C)+1+ε)γ_f(G)$ on every $G\in\mathscr C$. Here $a(\mathscr C)$ is the supremum edge-to-vertex ratio in~$\mathscr C$, and $γ_f(G)$ is the fractional domination number. The class also admits a deterministic $(1+ε)$-approximation for fractional dominating set and a randomized algorithm that always returns a dominating set and has expected size at most $(1+ε)γ(G)$. In each case, the number of rounds depends only on $\mathscr C$ and~$ε$. None of these algorithms requires the number of vertices or the maximum degree as part of the input. For planar graphs, this gives the deterministic guarantee $(7+ε)γ_f(G)$. Together with the lower bound of Hilke, Lenzen and Suomela, it determines the infimum of the deterministic constant-round approximation ratios for planar minimum dominating set as~$7$, settling a question that had remained open since their work. The corresponding infima, measured against the integral optimum, are $7$ for graphs of Euler genus at most any fixed $g\ge0$, $2t-3$ for $K_t$-minor-free graphs with $3\le t\le9$, and $2r+1$ for graphs of treewidth or pathwidth at most any fixed $r\ge1$. We also prove that, for every integer~\mbox{$r\ge1$}, no deterministic constant-round LOCAL algorithm achieves an approximation ratio below~\mbox{$2r+1$} on the $r$-th powers of paths, even when every vertex knows the number of vertices. This gives a new proof that the limiting constants are optimal for planar graphs, graphs of bounded treewidth or pathwidth, and $K_t$-minor-free graphs with $3\le t\le9$. For triangle-free planar graphs, the corresponding infimum is $5$.Authors: Robert Bredereck, Eva Deltl, Tanmay Inamdar, Pallavi Jain, Pranjal Pandey
When an envy-free allocation of indivisible goods does not exist, monetary transfers can restore envy-freeness. Existing work on fair division with subsidies, however, typically assumes that these payments are provided by an external source, an assumption that may be unrealistic in many applications. We address this limitation by allowing only monetary transfers between agents, with each agent's payments constrained by their individual budget. We show that while it is polynomial-time tractable to determine whether a given allocation can be made envy-free by payments under individual budgets, the general problem of computing such an allocation from scratch is NP-hard, even when agents have relatively large budgets. Motivated by this intractability, we conduct a parameterized complexity analysis, establishing fixed-parameter tractability with respect to the number of goods or to the joint parameter number of agents and good types, and we provide efficient algorithms in several special cases. For explicitly listed items, our type-based algorithm answers the envy-freeness part of an open question of T. T. Nguyen and J. Rothe, "Complexity Results and Exact Algorithms for Fair Division of Indivisible Items: A Survey."Authors: Lei Dong, Dennis Wong, Bowie Liu, Rui Bao, Lin Chen, Chan-Tong Lam, Sio-Kei Im
A graph $G$ is $k$-degenerate if there exists an ordering $v_1, v_2, \dots, v_n$ of its vertices such that each vertex $v_i$ has at most $k$ neighbors $v_j$ in $G$ with $j < i$. A well-ordered $k$-degenerate graph is a labeled graph on the vertex set $\{1, 2, \dots, n\}$ in which every vertex $i$ has at most $k$ neighbors among $1, 2, \dots, i-1$. We present the first simple algorithms that generate, rank, and unrank cyclic pivot Gray codes for well-ordered $k$-degenerate graphs, where consecutive graphs differ by the addition, removal, or pivoting of a single edge. Our algorithm generates each well-ordered $k$-degenerate graph in constant amortized time per graph, using $O(n^2)$ space, while ranking and unranking take $O(n^2)$ time and $O(n^2)$ space.Authors: Jihan Wang
We prove conditional lower bounds for approximating dynamic time warping (DTW) over the uniform metric on three symbols. Let $N, M$ be the two string lengths and $n, m$ their respective numbers of runs. Under the Gap Block Disjointness (GBD) hypothesis, for every fixed $κ\in (0,1/6)$ and $δ\in (0,1)$, no deterministic algorithm $N^{κδ}$-approximates DTW on two explicit strings of length $N$ in $O(N^{2-δ})$ time. This matches the known tradeoff between approximation and running-time exponents for deterministic algorithms within any fixed factor greater than six in the approximation exponent. For run-length encoded strings, the Orthogonal Vectors Hypothesis (OVH) rules out any constant-factor approximation in $\widetilde{O}((nm)^{1-δ})$ time for every constant $δ>0$. More generally, for every fixed $η\in (0,1)$, it rules out $(N+M)^{1-η}$-approximation in the same running time. These bounds extend to every fixed metric with at least three points, including absolute distance on $\{0,1,2\}$. Both reductions use long runs to force equal-symbol matches in low-cost alignments. For explicit strings, we combine Boolean gadgets with deterministic gap amplification to obtain a polynomial approximation gap. For run-length encoded strings, an encoding of regular-expression membership gives accepting instances an alignment whose cost does not increase as selected runs grow. Rejecting instances have distance at least the chosen run length, while the number of runs stays fixed.Authors: Yiwen Kou, Yimeng Wang
Standard diffusion samplers generate samples through repeated evaluations of a learned score function. Parallel sampling methods seek to accelerate generation by trading additional evaluations for fewer sequential rounds. This raises the question of how much sequential dependence is unavoidable, even when many score queries can be made simultaneously. We establish the first polynomial parallel-round lower bounds for diffusion sampling with approximate scores. Specifically, we prove (1) a $\widetildeΩ(d^{1/3})$-round lower bound for sampling smooth, near-isotropic Gaussian mixtures in $R^d$, and (2) an $Ω(d)$-round lower bound for uniform sampling from anisotropic axis-aligned boxes contained in the unit ball. Both bounds hold for arbitrary randomized algorithms making polynomially many queries per round at arbitrary locations and noise levels, with inverse-polynomial score error and constant total variation accuracy. The linear bound is tight for our box family. Our constructions use fixed approximate score oracles that enforce sequential access to hidden information while satisfying the accuracy guarantee at every noise level.Authors: Masoud Seddighin, Saeed Seddighin
Huffman coding is one of the oldest and most fundamental problems in computer science. Given a string of length $\TextLength$ over a general alphabet, the goal is to assign a binary codeword to each character so that no codeword is a prefix of another and the total encoded length of the string is minimized. Huffman coding is widely used in practical compression systems, including file compression. As modern datasets continue to grow, it is natural to study whether a Huffman code can be constructed efficiently in the massively parallel computation (\MPC) model. The celebrated Huffman coding algorithm admits two straightforward \MPC implementations: for any constant $ε\in(0,1)$, one uses $O(\TextLength^ε)$ memory per machine but requires $Θ(\log \TextLength)$ rounds, while the other runs in $O(1)$ rounds but requires $Θ(\sqrt{\TextLength})$ memory per machine. We give the first nontrivial \MPC algorithm for Huffman coding that bypasses both limitations. For every constant $ε>0$, our algorithm uses $O_ε(\log\log \TextLength)$ rounds and $\softO(\TextLength^ε)$ memory per machine, while its total memory and total computation are $\softO(\TextLength)$. This provides a rare example in which an exact solution to a problem whose classical algorithm is sequential in nature can be obtained in a sublogarithmic number of \MPC rounds.Authors: Nicolas Bousquet, Remy El Sabeh, Amer E. Mouawad, Naomi Nishimura
In neutral-atom quantum computers, atoms are moved to target positions along paths of empty positions, and a target position may be reserved for one species of atom. Motivated by this task, we introduce Single-Move Labeled Token Routing: every source and every target vertex of a graph is assigned a set of labels, and tokens occupy the sources. A solution consists of a matching that assigns each source to a compatible target (one whose label set intersects its own), a route for each matched pair, and a movement order in which, when a token is moved, its route contains no other token. The problem is known to be polynomial-time solvable when every source is compatible with every target, and $\mathsf{NP}$-complete on grid graphs when each source is compatible with exactly one target. We prove that the latter case remains $\mathsf{NP}$-complete on grids and on planar graphs of maximum degree four even when some solution has pairwise edge-disjoint routes. On trees, the problem is known to be $\mathsf{NP}$-complete even for maximum degree three. We study trees through the solution edge multiplicity, the largest number of routes of a solution sharing an edge, and the candidate edge multiplicity, the largest number of compatible pairs whose paths share an edge. We prove that on trees of maximum degree three, the problem is $\mathsf{W}[1]$-hard parameterized by a bound on the solution edge multiplicity, even when a movement order is given, and that on trees of unbounded degree, it is $\mathsf{NP}$-complete even when the candidate edge multiplicity is at most eight. We show that on trees the problem is fixed-parameter tractable parameterized by the maximum degree together with the candidate edge multiplicity, and also by the candidate vertex multiplicity, the same count at vertices. Unless $\mathsf{P}=\mathsf{NP}$, neither the maximum degree nor the candidate edge multiplicity can be omitted.Authors: Calum MacRury, Rian Neogi, Kanstantsin Pashkovich, Sahil Singla, Siddarth M Sundaram, Chaitanya Swamy
For the online combinatorial allocation problem with subadditive valuations, Correa and Cristi (STOC 2023) proved the existence of a $6$-competitive online algorithm, improving on the previous best $O(\log\!\log m)$-competitive online algorithm due to Dütting, Kesselheim, and Lucier (FOCS 2020), where $m$ is the number of items. However, Correa and Cristi's result is existential, and it was left open whether a constant competitive ratio is attainable via an efficient online algorithm that uses a polynomial number of demand oracle queries. In this work, we answer this affirmatively, giving an expected-polynomial-time $(6 + ε)$-competitive online algorithm for any constant $ε> 0$. Our techniques also recover, in the offline setting, the $(2 + ε)$-approximation result of Feige (STOC, 2006). Finally, when the buyers' valuations are drawn from identical distributions, we exploit symmetry to obtain an improved $(60/11+ε)$-competitive algorithm. Starting with the natural configuration LP relaxation for the problem, our main technical contribution is a recursive Bundle Score Generator (BSG) that resolves item conflicts by assigning correlated scores to the items requested by each buyer. Unlike the Random Score Generator whose existence is shown by Correa and Cristi, our BSG is efficiently computable in expected polynomial time. Moreover, it satisfies a stochastic dominance property that is sufficient to recover both Feige's offline result and Correa and Cristi's online result.Authors: Adrian Calinescu, Gruia Calinescu
Let f:2^N --> \cZ^+ be a polymatroid (an integer-valued non-decreasing submodular set function with f(emptyset) = 0). A k-polymatroid satisfies that f(e) <= k for all e in N. We call a subset S of N independent if f(S) equals the sum of f(e) over the elements e of S and f(e) > 0 for all e in S. Finding a maximum-size independent set in a 2-polymatroid has been studied and polynomial-time algorithms are known for linear polymatroids. For k >= 3, the problem is NP-hard, and an approximation algorithm with ratio approaching 2/k is known and is obtained by swapping as long as possible a "large" subset from the current solution by a set with one more element. Here we give a simple analysis of the more particular two-for-one repeated swapping heuristic, obtaining a (weaker) 2/(k+1)-approximation.from Sophie Huiberts
My community is under attack by commercial interests. Since last week, speedrun.com refuses to distribute our database of speedrun accomplishments under the agreed-upon Creative Commons license. This licensing dispute is a major breach of trust and an abdication of SRC's responsibilities to the community. Individual game's communities are all scrambling to find a new home for their leaderboards. SRC has the audacity to say its for our own good.
My other community is also under attack by commercial interests. OpenAI and Anthropic are telling their models to solve open mathematical problems, presumably to evaluate their models' capabilities. Sure, if that is productive then I won't judge that. What I do disapprove of, is that OpenAI is yeeting all their exhaust onto the internet.
When you prove a theorem, you are imparted a responsibility to the field. At minimum you need to explain what you did, including which steps required new ideas and which steps are already well-known. More substantively, you are expected to nurture the literature. If an important idea was poorly explained in its first incarnation, then you have to explain it better in your work. These demands are broadly accepted and are not controversial. Any time you meet the demands, the resulting paper is highly appreciated and valued.[1] The responsibility is yours because you have the opportunity to publish a paper on the subject.
OpenAI is doing the exact opposite. They do not care about their 'manuscripts'. They don't bother putting in appropriate attribution of ideas, their work contains errors, and they don't even bother with consistent presentation or formatting. This actively sets back the state of the literature.
Why are they doing this? Is there a benefit to their releasing this exhaust? Does science benefit? OpenAI says these results took 3 hours of LLM time on average with their internal model. Likely their public models can achieve the same outcomes when instructed by expert guidance. That's why they keep scooping their own customers.[2] A scooping that, I will add, is only possible because OpenAI outputs such sloppy work.
If an expert prompts a result, they take up the mantle of responsibility I describe above. OpenAI not only refuses to take their responsibility, but they prevent their own customers from doing so. And they have the audacity to say they do it for the good of science.
| [1] | One example of such a valued paper is Daniel and I's smoothed analysis paper. Yes we proved better running time bounds, but mostly using ideas that were in the literature already. The contribution of the paper was that it was nice to read, unlike the notoriously opaque literature that came before it. It would have been difficult to justify the time we spent writing this all up nicely if we hadn't also improved the result quantitatively, hence the responsibility. The paper remains my most visible piece of work, still accruing more citations per year than later follow-up work. |
| [2] | Here is one example from today of OpenAI customers who got scooped because they were spending their time writing up a nice paper instead of staking a flag on github dot com. |
Dear PTReview readers, we are in the brave new world of LLM assisted math papers. The total number of papers we need to look through each month has almost tripled, so apologies if your paper get missed. Please email little.oh.of.n@gmail.com with a link to an arXiv or ECCC paper. In general, we would appreciate sending us such an email as soon as your paper gets public, to make it easier for the editors to keep track of property testing papers.
We have a large collection of eleven (!!) papers, which we arrange by subtopic.
Query Complexity of Testing Structured Parenthesis Languages by Tim Jackman, Diptaksho Palit, and Sofya Raskhodnikova (arXiv). This paper and the next study the classic problem of testing Dyck languages, which are formed by correct parenthetical strings. When there is only one parenthesis type, then there are \(O(poly(1/\varepsilon))\) query property testers. When there are two or more parentheses types, the complexity jumps to somewhere between \(\Omega(n^{1/5})\) and \(O(n^{2/5+\delta})\). This paper proves an (almost) optimal lower bound of \(\Omega(n^{2/5})\), even for adaptive algorithms. A non-adaptive lower bound of \(\Omega(n^{1/2})\) is also proven. In addition, the paper proves that complexity is \(\Theta(\varepsilon^{-2})\) for single parenthesis type setting.
Near-Optimal Bounds for Testing Residual-String Equality and Parenthesis Languages by Hadar Strauss (arXiv). The primary result of this paper is the same: the adaptive \(\Omega(n^{2/5})\) and non-adaptive \(\Omega(\sqrt{n})\) lower bounds. This paper also shows a non-adaptive upper bound of \(O(n^{1/2+\delta})\) (for any \(\delta > 0\)), and gives an improved dependence on \(\delta\) for the adaptive setting. The lower bound constructions in both papers go via a “hidden” or “residual” string equality problem, wherein binary strings are padded with a dummy \(*\) symbol. The aim is to determine properties of the binary string after the dummy symbols are removed.
Collision Detection is Instance \(\widetilde{O}\)ptimal Under the Birthday Threshold by Omri Ben-Eliezer, Tomer Grossman, Václav Rozhoň, and Jakub Tětek (arXiv). Consider the classic problem of collision detection in a function \(f:[n] \to [n]\). So we want to find \(x \neq y\) such that \(f(x) = f(y)\). As our readers will likely know, if \(f\) is random, a standard birthday paradox argument shows that \(O(\sqrt{n})\) samples suffice. Suppose we knew something about the function \(f\), such as the structural properties of \(f\): then it is quite plausible we can beat the birthday paradox bound. This paper shows there is an instance optimal algorithm that is \(O(\log n)\)-competitive. This means, even if we design a tailormade algorithm that is optimized for a specific \(f\), the algorithm of this paper will take at most \(O(\log n)\) factor more queries. It is also known that this overhead cannot be beaten.
Testing the Binary Rank with Polynomial Query Complexity by Michal Parnas (arXiv). Consider an \(n \times m\) Boolean matrix \(M\). The binary rank is the smallest \(d\) such that \(M = AB\), where \(A, B\) are Boolean matrices. And \(A\) has dimension \(n \times d\), and \(B\) has dimension \(d \times m\). The multiplication is done over the integers (not over \(\mathbb{F}_2\), which would correspond to the Boolean rank). This paper studies the property testing version, where distance is naturally measure by (fractional) Hamming weight. The main result is an adaptive two-sided property testing, with query complexity \(\widetilde{O}(d^3/\varepsilon^2)\). Previous results have query complexities exponential in \(d\).
Testing Bipartite in the Bounded-Degree Graph Model, Revisited (A digest of the paper of Fei and Rubinfeld (2026)) by Oded Goldreich (ECCC). As the title says, this paper is an exposition of a recent Fei and Rubinfeld on a simpler analysis of the classic bipartiteness tester for Goldreich-Ron. It lays out the key differences of the Fei-Rubinfeld result, and gives an accessible explanation of the main ideas.
Private Graph Property Testing by Hendrik Fichtenberger, Abigail Gentle, Tamalika Mukherjee, Sayantan Sen (arXiv). Differential privacy (DP) and property testing have a lot in common. At its heart, DP is about the sensitivity of algorithms to their input. It feels like property testers should be differentially private, since they make inferences on the input by only sampling a small portion of the input. This paper makes the connections rigorous for graph property testing. For graph inputs, there are various notions of DP, called edge-DP and node-DP (depending on whether we want to preserve the privacy of node existence or edge existence). The paper provides a nice framework that connects graph property testers with DP. One of the main results, using canonical property testers for dense graphs, gives edge-DP and node-DP property testers for any property. The private query complexity is only a constant factor more than the non-private canonical tester. For bounded degree graphs, the paper gives a private version of the classic bipartiteness tester, using privacy preserving random walks. There are also results for hyperfinite graph properties.
On the Power of Adaptivity in Testing Quantum States in Fidelity by Jan Seyfried, Sayantan Sen, Marco Tomamichel (arXiv). This paper is on testing of quantum states, a topic that has seen much research over the past couple of years. This problem is the quantum equivalent of distribution testing: consider a known quantum state \(\sigma\). Given input to an unknown quantum state \(\rho\), we wish to distinguish \(\rho = \sigma\) from \(\rho\) being far from \(\sigma\). Typical results measure distance in terms of a trace norm, but this paper focuses on an alternate distance notion called fidelity. For the original trace norm distance, various problems (certification, equivalence, and independence) all have basically the same complexity of \(\widetilde{\Theta}(d^{3/2}/\varepsilon^2)\), where \(d\) is the dimension of the quantum states. It was known that adaptivity does not help. For fidelity, the bounds change for the various problems, and adaptivity does give a provable improvement for equivalence and independence testing.
Distributed Quantum Property Testing with Quantum Carrier Pigeons by Kenny Chen, Mina Doosti, Ryan Sweke, Chirag Wadhwa (arXiv). This paper studies the same problem of quantum state testing, but in a distributed setting. Imagine that there are multiple nodes (called distributed nodes) that carry copies of the quantum state to be tested. They all communicate with a central node that has to solve the inference task. This model is inspired by a classic version of distributed distribution testing. There is a limit of classical bits (\(n_c\)) and qubits (\(n_q\)) that can be sent from each distributed node to the central node. When \(n_q\) is larger than the number of qubits in the quantum state, the entire state can be sent to central node. The interesting case is when \(n_q\) is smaller. This paper shows that with public randomness, there are non-trivial distributed algorithms, but there are lower bounds for private randomness.
Optimal Quantum State Testing Even with Limited Entanglement by Chirag Wadhwa, Sitan Chen (arXiv). Another paper on quantum state testing, but looking at the power of entanglement. The testing algorithms need to be multiple copies (or samples) of the input quantum state. But in previous optimal algorithms, these have to be entangled, which allows for a copy complexity \(\widetilde{O}(d/\varepsilon^2)\). Without any entanglement, the complexity jumps by a quadratic factor. This paper studies what happens if the entanglement is limited to \(t\). The complexity achieved is (essentially) \(\widetilde{O}(d^2/\sqrt{t}\varepsilon^2)\), giving a smooth tradeoff between the extreme cases.
Good Quantum Locally Testable Codes from Product Expansion by Mitali Bafna, Anqi Li, and Quynh T. Nguyen (arXiv, ECCC). A locally testable code (LTC) is one for which the property of codewords has a constant query property tester. The tester is defined by a collection parity checks over subsets. A constant number of these checks are sampled uniformly at random to get the property tester. This paper shows that, assuming a conjecture about product expansion of Reed-Solomon codes over binary extension fields, there are quantum LTCs with constant rate, distance, soundness and locality.
Streaming Hypergraph Coloring via Palette Sparsification by Artur Czumaj, Pan Peng, Ruizhe Shi, Christian Sohler (arXiv). Formally, this is not a property testing paper, but palette sparsification is a fundamental tool in sublinear algorithms. So this is a good paper for our readers to check out. Let us leave aside the actual streaming results (which are interesting!). Palette sparsification is a technique where each vertex gets a subset of randomly sampled colors. One proves that there is a legal coloring where each vertex only picks from its “local palette”. This was a critical tool in sublinear graph coloring algorithms, and this paper generalizes the tool for hypergraphs. For coloring hypergraphs, we only need that no edge is monochromatic. One can prove that \(\Theta(\Delta^{1/(k-1)})\) colors suffice for a proper coloring, where \(\Delta\) is the maximum degree and all hyperedges have arity \(k\). The main theorem shows that \(\Theta(\sqrt{\log n})\) length lists suffice for each vertex.
from Scott Aaronson
… then they came for Navier–Stokes and I said nothing because I never worked on Navier–Stokes. But when they came for RL vs. L I realized that things are serious
–friend-of-the-blog Omer Reingold (shared with permission)
Last night my 9-year-old son was taunting my wife, complexity theorist Dana Moshkovitz, as follows: “mommy, I heard you got cooked! I heard that a robot solved the math problem you worked on for your whole career! OOF!”
While my son was being a brat, he also wasn’t wrong. Whether you’re thrilled, depressed, angry, or whatever else about it, yesterday was surely one of the biggest days in mathematical history. And yes, among the 372 huge results released yesterday by OpenAI, on the recommendation of its advisory group of Timothy Gowers, Edward Witten, and other distinguished mathematicians, was a proof of Subhash Khot’s Unique Games Conjecture (UGC), a statement that my wife has worked toward proving for the entire time I’ve known her. (The UGC implies that a whole slew of optimization problems really are NP-hard, even if you just want an approximation that’s slightly better than what you get from semidefinite programming relaxation, which is one of our main tools.)
Or at least, we’re pretty sure that it’s a proof! There’s a Lean certificate, as there are for some of the other 372 breakthrough results (not all of them). But it also appears that no human has understood just about any of these proofs yet; the race to do so has just started. If you want an on-the-ground sense of what that race is going to be like, here’s some of what Dana texted me last night:
It feels like something written by someone who’s on psychedelics. So much unclear and doesn’t make sense. Lots of name dropping of previous work without discussing why it can be used despite impossibility results
Basically the paper is so horribly written that it’s impossible to read it without AI help
I asked Astra for reasonable completeness and soundness claims of the noise gadget and it gave them by combining claims from all over the paper
They also have direct optimal NP hardness of approximation proofs for the main applications of the UGC (Max Cut and all CSP) that bypass the UGC.
The UGC proof invents a completely new bizarre code with a noise test. It’s some crazy recursive construction.
It’s not the long code, not the short code – some alien craziness
I still think that there maybe is a proof that uses the half space code (which is natural)
The citations are often irrelevant and confusing
A possible future is a math world that’s heavenly if you have vision/creative ideas that AI could help check and implement.
And of course there’s a lot for us to learn from the aliens
If you’re wondering what emotions Dana is feeling—well, probably all of them! Even while a central career aspiration has fallen to a robot, there are at least two mitigating factors for her. First, she can feel vindicated that the UGC was true after all, something she never doubted even while many of her colleagues did! Second, all of us in math and theoretical computer science and mathematical physics, at least those who cared about solving crisply-stated problems, are now in the same boat.
Besides the Unique Games Conjecture, here’s a small sampling of the treasures from Aladdin’s cave that I’ll probably be paying the most attention to over the coming weeks:
Any of the above, alone, could easily have been “result of the year” in some area (and in some cases, like Unique Games and L=BPL, in all of CS theory). And there’s a lot that I’ve left out—feel free to share in the comments whatever is making your eyes bug out! There are equally astounding wonders in number theory, combinatorics, algebraic geometry, analysis, and pretty much every other area of math, most of which I’ll never understand, although I’ll note that it includes partial progress toward the Riemann hypothesis and the Hodge Conjecture and the Birch-Swinnerton-Dyer Conjecture (i.e., the majority of the remaining Millennium Problems).
We can take solace in what’s missing from the list. P≠NP isn’t there, nor even P=BPP or NEXP⊄P/poly, and surely not for lack of trying. Apparently the greatest open problems of theoretical computer science are indeed pretty hard!
Oh, lest I forget: one day before the OpenAI dump, meaning Monday evening, Virginia Williams and Josh Alman posted an arXiv preprint that solves the 3SUM problem in O(n1.9992) time, and the All-Pairs Shortest Paths problem in O(n2.9995) time, refuting half-century-old conjectures that the correct answers were n2-o(1) and n3-o(1) respectively. In this case, it wasn’t an OpenAI model that supplied the crucial idea; it was an Anthropic one! But Anthropic then took a different approach from OpenAI: rather than post the undigested solutions to the world, it gave Virginia and Josh the opportunity to write and announce a digested version in exchange for compensation.
These have emerged as the two main models for communicating AI math breakthroughs, and they both have strengths and weaknesses. The “OpenAI model” sets up a crazy race among humans to digest and explain a messy AI proof (work that could easily be some combination of thankless, barely-credited, competitive, and unfun), while the “Anthropic model” puts a private company in the position of picking and choosing which human mathematicians get to be the emissaries of the AI. Dunno, what do you guys think?
For those who are wondering: apparently, the AI model that produced all these wonders was not bespoke contraption of 10,000 agents burning millions of dollars worth of compute, as was used for example to construct a finite-time blowup for the Navier-Stokes equations. Instead, it was simply the latest internal OpenAI model—one that might be released to paying ChatGPT customers within the next couple of months, depending on the recommendations of OpenAI’s safety board! (My 9-year-old son: “Oh they definitely shouldn’t release that. If it could solve all those math problems, it can’t possibly be safe.”) Apparently they used about 3 hours of GPT-Pro level compute on average per problem solved.
Also, if you were wondering: apparently they tried the model on about 8,000 problems. So, right now it “merely” solves ~5% of the longstanding open mathematical problems that it’s asked about, the problems that whole communities have spent years on, after a single 3-hour attempt on them.
I’ve been glad to see the CS theory community rising to the occasion. At the Simons Institute in Berkeley, here at UT Austin, and elsewhere, I’ve hearing stories of researchers rushing to pore over the manuscripts and make sense of them and explain them—because what else do we do? How else do we continue the craft to which we’ve devoted much of our lives?
If you want some sense of what things feel like now in math, imagine a hunter-gatherer who’s spent his entire life learning to survive deep in an unforgiving rainforest, then a giant resort hotel springs up right next to him with a helipad and heated pools and AirBnBs, and without missing a beat, the hunter-gatherer says: “alright fine, so now my new job is to run wilderness retreats for the tourists, or something.”
In Quanta magazine, Jordana Cepelewitz attempted a different metaphor:
It’s as if you were teleported to the peak of a tall mountain. Surrounded by fog, you have no idea where you are, or what’s around you. You do not know how your mountain connects to others, and you have no equipment to help you explore, no way to help someone else join you. If you had climbed the mountain yourself, you would have experienced how the human body adapts to altitude and changes in oxygen levels. You might have had to invent tools to navigate, to climb steep cliffs, or to make a shelter. You might have encountered a fellow explorer, gotten lost together in a hidden valley, and found a plant that could be turned into a life-saving medicine.
Instead you’re perched on the peak but in the dark, while the maker of the teleportation machine tells you that it can explore the wilderness better than any human.
For any one of these mountains, if we care enough, I feel optimistic that we can do as we always have: clear the fog and figure out the path, except now using the teleportation machine to help guide us. The bigger challenge will be to nurture a community that still cares about the heroic adventure of finding the paths up these mountains in the world with the machine. (Oh, and I think one place where the metaphor breaks is that we still do have each other, as much as we ever did before!)
Experience has shown that, even now, there will still be people explaining in patronizing tones why none of this is real and none of it counts. If such people were capable of being impressed by anything that happens in the empirical world, of updating on anything, they would’ve already been impressed and already updated several years ago, long before things had reached the point of an actual Mathocalypse.
So, they’ll say, maybe the alleged solutions are not solutions at all, but just “AI slop.” Or maybe none of the 372 well-known open problems that were solved were real math problems, they were all just glorified contest puzzles and trivialities. (After all, there’s still no Riemann Hypothesis!) Or maybe the entire 4000-year-old discipline of mathematics needs to be jettisoned: turns out that it was all just puzzle-solving and trivialities; all that’s different is that now the triviality stands unmasked. In any case, what really matters is that the true inner sanctum of human creativity hasn’t been breached and probably never will be, and also, that Sam Altman and Dario Amodei are contemptible little nerds.
If you’re still a proponent of that doomed worldview, still aboard the sinking ship, I encourage you in the strongest possible terms to read yesterday’s other great contribution to AI discourse, besides the OpenAI Mathocalypse dump: namely, Scott Alexander’s open letter to Steven Pinker. I feel some responsibility for this, as the person who first introduced Steven Pinker to the existence of the rationalist community, and who also first introduced Steven Pinker and Scott Alexander to one another (they had both been fans of each other’s writing). And now Scott is challenging Steve to a literal duel, with guns!
For whatever it’s worth: Steve is a lifelong intellectual hero of mine, just as he is for Scott, and I also have to privilege of calling Steve my friend. But I found Scott’s post to be one of the most devastating rejoinders to anything that I’ve ever read. And I thought Scott’s conclusion was exactly right: when it comes to AI risk, Steve’s great challenge is now to accept and start using a more “Pinkerite” epistemology.
Last night, while I should’ve been poring over some of OpenAI’s hundreds of papers and/or writing this post, I decided to spend some time with my kids instead. They wanted a movie night, so I suggested something they’d never seen before (and that I hadn’t seen for decades), and that seemed chock-full of no-nonsense, practical guidance for the world in which they’re going to grow up: Terminator 2.
Update: As several people have pointed out, cryptography is a subfield that’s extremely conspicuous by its absence from OpenAI’s list of 376 papers! But my sources tell me that the AI companies have now started, gingerly and discreetly, investigating whether their latest internal models can break important cryptographic protocols and primitives. If they can, then it would certainly be nice to get ahead of things before the rest of the world figures out the same.
Another Update: The statement put out the Advisory Group on Mathematics and Artificial Intelligence is very carefully phrased, neither endorsing nor condemning what OpenAI did, and is worth a read:
As announced a few weeks ago, OpenAI has released a large collection of mathematical results generated by an internal model, reporting solutions to hundreds of open questions. This is an important event for mathematics, with consequences both for mathematics and for the mathematical community that extend far beyond the individual results.
AGMAI’s advisory role should not be interpreted as a judgment of the impact of these results or an endorsement of the process by which OpenAI obtained them. We do not speak on behalf of the entire mathematical community, and only the mathematical community can undertake the assessment that is needed.
Making this work public is a first step. This release is the beginning, not the completion, of the process of human understanding and the incorporation of the work into mathematical knowledge. At the same time, the future of mathematical research cannot consist only of understanding results produced by AI labs. Mathematicians must be able to formulate their own questions, develop their own approaches, and explore directions that have not been selected as examples of an AI system’s capabilities. Equitable access to powerful research tools and adequate computational resources are essential to that freedom.
We reaffirm our published recommendations on responsible release. We have discussed them with OpenAI and appreciate the company’s willingness to engage. While we consider these discussions constructive, it is ultimately up to the mathematical community to assess the extent to which our recommendations were followed successfully, and whether there are others we should suggest. We remain committed to engaging with any frontier AI lab on these questions and have already been in contact with several of them.
from Hung Le
Recent OpenAI Math dump have solutions to many long standing probems in Math and TCS. In the dump, two problems that I and my friends, notably Arnold Filtser, have studied for more than a decade, and published a few papers about this:
It is unsettling and hard to swallow. I have not looked at the details yet, and will be doing so in the next few days. On a positive note, I hope to learn new techniques in planar graphs. I always believe that we have not been able to solve these problems because we lack a serious understanding of planar metrics. Now that they are solved, learning what the serious understanding is exciting.
A clear next prediction (not included among Open AI solution) is a solution of the conjecture that that minor-free graph metrics are embeddable into $\ell_1$ with constant distortion. Using the Robertson-Seymour decomposition, one basically could reduce this conjecture to bounded treewidth and planar graphs. At this point, I feel that understanding the two results above are more important than churning out another result.
Will udpate my understsanding of the two papers above.
I intentially do not mention other big results. What a strange time to be alive.
Updates:
from ECCC Papers
I wrote the post below last week. That was a quaint and quiet time. Last night OpenAI released a treasure trove of 722 manuscripts solving 372 major open problems in mathematics including from theoretical computer science:
Adam Bouland, Andrew Huang, Anand Natarajan, Itay Shalit and Avishay Tal posted a paper giving an oracle where \(\mathrm{BQP}\) is not in \(\mathrm{IP}\) (interactive proofs). Now \(\mathrm{BQP}\) is in \(\mathrm{IP}\) since \(\mathrm{BQP}\subseteq\mathrm{PSPACE}=\mathrm{IP}\), but the \(\mathrm{IP}=\mathrm{PSPACE}\) proof doesn't relativize and Bouland et al. show you can even get an oracle that puts \(\mathrm{BQP}\) out of \(\mathrm{IP}\).
The paper also states "Together with recent work due to Scott Aaronson, Anand Natarajan, Avishay Tal, and Ági Villányi, our work also gives the first oracle separation between IP and MIP, answering a question dating back to Fortnow's thesis." \(\mathrm{MIP}\) is the set of languages with multi-prover interactive proofs.
When I saw this paper, I pulled my PhD thesis off the shelf and indeed on page 40 I wrote "What is the relation between MIP and IP? Is there, for instance, an oracle separating the two classes".
When I wrote the thesis in 1989 we didn't know yet that \(\mathrm{IP}=\mathrm{PSPACE}\) and \(\mathrm{MIP}=\mathrm{NEXP}\) so we really didn't have any idea whether multiple provers actually gave you more power than one prover. When László Babai, Carsten Lund and I proved \(\mathrm{MIP}=\mathrm{NEXP}\) a year later, we had strong evidence that \(\mathrm{IP}\neq\mathrm{MIP}\) since we believe that \(\mathrm{PSPACE}\neq\mathrm{NEXP}\). However since the proof that \(\mathrm{MIP}=\mathrm{NEXP}\) doesn't relativize either, the question of the oracle separation between \(\mathrm{IP}\) and \(\mathrm{MIP}\) remained open until the Bouland et al. paper.
Finally, Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee, Shachar Lovett, Avishay Tal and Emanuele Viola gave new exponential correlation bounds for polynomials. The authors use that bound to give a new pseudorandom generator against \(\mathrm{AC}^0[\oplus]\) circuits.
When I saw the paper I realized one could use this generator to show that \(\text{Almost-}\oplus\mathrm{P}=\mathrm{BPP}^{\oplus\mathrm{P}}\), answering a question I had wondered about in the 90s. Here \(\text{Almost-}\oplus\mathrm{P}\) is the class of languages \(L\) such that \(L\in\oplus\mathrm{P}^R\) with probability one for a random oracle \(R\). This in turn could be used to give an alternative proof of Toda's theorem. Ken Regan and Jim Royer showed that relative to a random oracle the polynomial-time hierarchy is contained in \(\oplus\mathrm{P}\), so \(\mathrm{PH}\subseteq\text{Almost-}\oplus\mathrm{P}=\mathrm{BPP}^{\oplus\mathrm{P}}\). It would take me a long time to work out and write up the details so I had Claude do it for me.
I still have many more open problems, see for example my survey of open oracle questions. I'd be happy to see them solved. Feel free to use AI but verify the proof. You too could get mentioned on this blog.
By Lance Fortnow
I wrote the post below last week. That was a quaint and quiet time. Last night OpenAI released a treasure trove of 722 manuscripts solving 372 major open problems in mathematics including from theoretical computer science:
Adam Bouland, Andrew Huang, Anand Natarajan, Itay Shalit and Avishay Tal posted a paper giving an oracle where \(\mathrm{BQP}\) is not in \(\mathrm{IP}\) (interactive proofs). Now \(\mathrm{BQP}\) is in \(\mathrm{IP}\) since \(\mathrm{BQP}\subseteq\mathrm{PSPACE}=\mathrm{IP}\), but the \(\mathrm{IP}=\mathrm{PSPACE}\) proof doesn't relativize and Bouland et al. show you can even get an oracle that puts \(\mathrm{BQP}\) out of \(\mathrm{IP}\).
The paper also states "Together with recent work due to Scott Aaronson, Anand Natarajan, Avishay Tal, and Ági Villányi, our work also gives the first oracle separation between IP and MIP, answering a question dating back to Fortnow's thesis." \(\mathrm{MIP}\) is the set of languages with multi-prover interactive proofs.
When I saw this paper, I pulled my PhD thesis off the shelf and indeed on page 40 I wrote "What is the relation between MIP and IP? Is there, for instance, an oracle separating the two classes".
When I wrote the thesis in 1989 we didn't know yet that \(\mathrm{IP}=\mathrm{PSPACE}\) and \(\mathrm{MIP}=\mathrm{NEXP}\) so we really didn't have any idea whether multiple provers actually gave you more power than one prover. When László Babai, Carsten Lund and I proved \(\mathrm{MIP}=\mathrm{NEXP}\) a year later, we had strong evidence that \(\mathrm{IP}\neq\mathrm{MIP}\) since we believe that \(\mathrm{PSPACE}\neq\mathrm{NEXP}\). However since the proof that \(\mathrm{MIP}=\mathrm{NEXP}\) doesn't relativize either, the question of the oracle separation between \(\mathrm{IP}\) and \(\mathrm{MIP}\) remained open until the Bouland et al. paper.
Finally, Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee, Shachar Lovett, Avishay Tal and Emanuele Viola gave new exponential correlation bounds for polynomials. The authors use that bound to give a new pseudorandom generator against \(\mathrm{AC}^0[\oplus]\) circuits.
When I saw the paper I realized one could use this generator to show that \(\text{Almost-}\oplus\mathrm{P}=\mathrm{BPP}^{\oplus\mathrm{P}}\), answering a question I had wondered about in the 90s. Here \(\text{Almost-}\oplus\mathrm{P}\) is the class of languages \(L\) such that \(L\in\oplus\mathrm{P}^R\) with probability one for a random oracle \(R\). This in turn could be used to give an alternative proof of Toda's theorem. Ken Regan and Jim Royer showed that relative to a random oracle the polynomial-time hierarchy is contained in \(\oplus\mathrm{P}\), so \(\mathrm{PH}\subseteq\text{Almost-}\oplus\mathrm{P}=\mathrm{BPP}^{\oplus\mathrm{P}}\). It would take me a long time to work out and write up the details so I had Claude do it for me.
I still have many more open problems, see for example my survey of open oracle questions. I'd be happy to see them solved. Feel free to use AI but verify the proof. You too could get mentioned on this blog.
from Gil Kalai
This is a draft lecture notes written under my guidance for today’s lecture. Blue text represent my further comments.) The lecture will be on Oct 7 at IAS, at 3:30, in the Seminar room.
I will speak at the IAS about the wonderful theory of intersection homology, introduced by Mark Goresky and Bob MacPherson, and some of its connections to combinatorics. This post is an extended description of the lecture and a set of notes toward it. I would like to explain the basic definitions, then discuss three directions that particularly interest me: the missing ring structure behind toric -vectors, the search for intersection homology in face rings, and extensions involving several perversities.
These questions continue discussions from the pleasant informal seminar we had here in 1995 with Bob MacPherson, Mark Goresky, Tom Braden, and a few others. I will try to keep the discussion self-contained and easygoing. Throughout, coefficients are rational unless another field is specified.
I will start by briefly discussing convex polytopes , the parameter
, rigidity, and the theorem of Walter Whiteley.
For a closed oriented manifold of dimension , Poincaré duality gives a perfect pairing between homology in degrees
and
. Singular spaces need not satisfy this duality. Intersection homology repairs it by controlling the way chains meet the singularities.
Start with a stratified pseudomanifold, with filtration
The strata are manifolds, the top stratum is dense, and a neighborhood of a point in an -dimensional stratum looks like
, where
is the open cone on a compact link. We initially exclude codimension-one strata.
A traditional perversity is an integer function satisfying
For a PL -chain
, the allowability condition is
A negative bound means that the intersection must be empty. The chain and its boundary must satisfy their respective conditions. These chains form a complex ; its homology is
. One uses compatible subdivisions in the PL construction. A singular-chain formulation instead requires
for every simplex occurring with nonzero coefficient in the chain or its boundary. Requiring the boundary to be allowable is essential: allowable simplices alone do not form a chain complex. [1, 2]
Why do complementary perversities occur? If chains of dimensions and
meet a codimension-
stratum in their allowed dimensions, a general-position intersection there has dimension at most
For and
, this bound is
. Thus complementary cycles can intersect in the regular part, where signed intersection numbers make sense.
The theorem of Goresky and MacPherson says that, for a compact oriented pseudomanifold without boundary and complementary traditional perversities, this produces a perfect pairing
Traditional intersection homology is independent of the chosen suitable stratification. On a manifold it recovers ordinary homology. These are substantial theorems: the definition itself visibly uses the strata. [1, 2]
The cone as a first exampleLet be a connected closed manifold of dimension
. For the cone stratification, the finite-chain cone formula, in positive degrees, is
The zeroth group is . A cycle on the link becomes a boundary when its radial cone is allowable. For example, at a cone point of codimension three,
prohibits a two-dimensional filling from meeting the vertex, whereas
permits it. This is a useful local calculation to keep in mind throughout the lecture. [1, 6]
The two middle perversities are
They are complementary. They agree in even codimension and differ by one in odd codimension. A complex algebraic variety admits a stratification with even real codimensions, so the distinction disappears there. Middle intersection homology is consequently self-dual. For projective varieties it also has a hard Lefschetz theorem, with the action of an ample class. [2]
Toric h and g vectorsHere is a combinatorial definition that fixes our convention. For a -polytope
, recursively define
including the empty face, with and
. For a point,
. Write
where . These are the toric h and g vectors, extending the usual simplicial definitions. For a polygon with
vertices, the recursion gives
For rational , place the origin in its interior and take the fan of cones over its proper faces. Its projective toric variety
has
This convention uses the face fan of , equivalently the normal fan of its polar. Using the normal fan of
itself gives the convention for the dual polytope.
Duality gives ; hard Lefschetz gives
. Combinatorial intersection cohomology of fans extends the theory beyond rational polytopes, and Kalle Karu proved hard Lefschetz in that generality. [3]
The paper of Tom Braden and Bob MacPherson, Intersection homology of toric varieties and a conjecture of Kalai, proves my monotonicity conjecture for rational polytopes using intersection homology. Braden’s subsequent paper, Remarks on the combinatorial intersection cohomology of fans, explains the extension to arbitrary polytopes, further properties of toric -vectors, and the connection between
and rigidity. [11, 12]
There is also a striking relation between a four-dimensional polytope and its polar: $latex g_2(P)=g_2(P^)$. I discussed it in my post A Mysterious Duality Relation for 4-dimensional Polytopes. Braden’s work places such relations in a broader framework involving exact sequences and Koszul duality. Stanley’s Subdivisions and local h-vectors* is another central reference: it develops local invariants of subdivisions and identities connecting the toric invariants of dual face lattices. [12, 13, 14]
But there is a further question. Is the toric g vector of every convex polytope an M-sequence? That means it is the Hilbert function of a standard graded algebra:
This asks for more than nonnegativity. Macaulay’s inequalities constrain the growth of such a Hilbert function; already
For a simplicial polytope, its Stanley–Reisner ring provides the mechanism: take an Artinian reduction by a linear system of parameters, then quotient by a Lefschetz linear form. The Hilbert function of this last quotient is the -vector.
For a general polytope we have intersection cohomology and Lefschetz operators, but no natural internal multiplication on fixed middle-perversity intersection cohomology that supplies this argument. There are products involving different perversities, and an action of ordinary cohomology; neither automatically gives the needed standard graded algebra. This is the missing ring problem. A suitable substitute might be enough: an algebra realizing the primitive dimensions, or another mechanism enforcing Macaulay’s inequalities. The numerical M-sequence question and the construction of a geometrically meaningful multiplication are related, but distinct problems.
I discussed the search for a product—or a weaker substitute, perhaps resembling a Massey product—in my 2004 report, Combinatorial expectations from commutative algebra. This remains a useful reference for the missing ring problem and its broader combinatorial motivation. [17]
3 Witt spaces and an upper bound conjecturePaul Siegel’s Witt condition enlarges the class of spaces with self-dual middle intersection homology beyond spaces with only even-codimension singularities. At every singular stratum of odd codimension , its link
has dimension
. The rational Witt condition is
On a Witt space the natural comparison from lower-middle to upper-middle intersection homology is an isomorphism. Compact oriented Witt spaces therefore have a self-dual middle theory. The condition is local and depends on the coefficient field. [4]
For a concrete example, the cone on a two-torus fails the Witt condition because . The cone calculation gives lower-middle
and upper-middle
. In contrast, the cone on
satisfies the condition. The obstruction is precisely the middle homology of the link.
Paul Howard Siegel developed Witt spaces in his 1979 MIT thesis, with crucial guidance from Mark Goresky. Goresky introduced him to the problem, and their conversations were central to its solution. Edward Y. Miller was the formally listed thesis supervisor. Siegel’s paper appeared in 1983. His later career took him into information theory, coding, and data storage, through IBM Research and UC San Diego. I find this a lovely connection between a beautiful idea about singular spaces and a quite different area of mathematics and engineering. [5]
The upper bound theorem says that a -polytope with
vertices has no more
-faces than the cyclic polytope
. Here is the simplicial Witt-space conjecture I would like to discuss:
Conjecture. Let
triangulate a compact oriented Witt pseudomanifold of dimension
, with
vertices. If
is even, additionally assume
. Then
The global vanishing assumption is additional to the local Witt condition. Every closed oriented manifold is a Witt space, so the local condition alone cannot impose all cyclic-polytope bounds. For example, the seven-vertex triangulation of the torus has 21 edges, while the boundary of a three-dimensional cyclic polytope with seven vertices has 15.
Novik proved the bound for even-dimensional manifolds with vanishing middle homology. Her ICM survey states the Witt-space conjecture and discusses further cases and stronger upper-bound questions. The hoped-for bridge is an algebraic interpretation of intersection homology that interacts with face enumeration. [7]
4 Looking for intersection homology in face ringsLet be a simplicial complex on
. Its symmetric face ring is
Its exterior face ring is
Both record faces; their additional algebraic structures record much more.
In the exterior ring there is a particularly direct illustration. Multiplication by gives a differential
, since
. Its cohomology in degree
is the reduced simplicial cohomology
: the monomial basis is the face basis, and the differential adds one vertex with the usual signs. Thus ordinary cohomology already lives in this algebra.
On the symmetric side, local cohomology and graded resolutions encode the homology of links and induced subcomplexes. For triangulated manifolds, Schenzel’s formula and the work of Novik and Swartz show how ordinary Betti numbers enter Artinian reductions and their socles. These results provide models for what one might seek for intersection homology. [8, 9]
The question is to recover, for each traditional perversity,
through algebraically defined complexes, subquotients, or filtrations associated with either face ring, without supplying a separate stratification. Here “arbitrary perversities” initially means arbitrary traditional Goresky–MacPherson perversities; more general stratum-dependent or superperversities require separate invariance hypotheses.
Merely recovering ordinary homology is insufficient. In the cone on the torus, ordinary positive-degree homology vanishes, while lower-middle intersection homology retains two degree-one classes. Any proposed face-ring construction must distinguish these phenomena.
A possible direction is to use generic linear forms and their flags to express allowability algebraically. On the exterior side this suggests kernels of contraction operators; on the symmetric side, Koszul complexes, annihilators, and local cohomology suggest candidates. These are research directions, not established replacements for the intersection-chain definition.
For the algebraic background, see also Braden’s Koszul duality for toric varieties and the paper with Valery Lunts, Equivariant-constructible Koszul duality for dual toric varieties. These concern categories of sheaves associated with dual cones; they provide a further connection between intersection cohomology and homological algebra. [15, 16]
There are several useful tests. On manifolds, a candidate must recover ordinary homology for every traditional perversity. On cones, it must reproduce the correct perversity-dependent truncation. It must survive subdivision and produce the complementary-perversity pairing. To help with upper bounds, it must also relate the resulting groups to dimensions or multiplication in the face ring. The last requirement is what makes this a combinatorial project rather than just another way to calculate topological groups.
5 Multiperversities and the project with Greg FriedmanHere I will talk about my (dubious) vision.
In our paper, A multiperversity generalization of intersection homology, Greg Friedman and I replace one perversity by a finite collection . Let
be the span of singular
-simplices allowable for at least one member of
. Then
Different simplices may use different perversities, and the boundary may use different choices again. Consequently this is generally not the sum of the single-perversity intersection-chain complexes. If has a greatest member, the construction reduces to that member; incomparable perversities are the interesting case.
We established subdivision, Mayer–Vietoris, product results, and a cone formula. The paper left independence of stratification open. Its motivation was to find further invariants of singular spaces and, eventually, further combinatorial invariants of polytopes. [6]
Topological invariance is the central issue. An extra subdivision of a manifold must not create new invariants by adding artificial strata. More generally, the same underlying singular space, described by different suitable stratifications, should give canonically comparable groups. Henry King’s intrinsic-stratification approach gives a strategy; Greg’s later short proofs of ordinary intersection-homology invariance offer further guidance. [10]
One can see why collections of perversities introduce extra bookkeeping. For a link of dimension , define
These are the labels under which an -cycle can be filled radially in the cone. As
changes, the collection changes. One must therefore track the maps between theories for subcollections, not just the dimensions of the groups. Images of these maps can matter even when the separate groups are known.
The question is whether this local information can be assembled into a proof that the theory is unchanged under intrinsic aggregation of strata. A proposed proof must keep the comparison maps compatible with inclusions of collections, cone constructions, and the passage from local charts to the whole space. Duality for multiperversities is another question; it does not follow just by complementing each member of a collection.
I hope (do I really hope it?) these directions will eventually reinforce one another: more flexible topological invariants, algebraic constructions inside face rings, and new inequalities for face numbers. For the lecture, I would like to emphasize both the remarkable strength of the classical theory and the concrete questions that remain.
References and further readingfrom Gil Kalai
With Danny and Sharon Kleitman and Michel Goemans at the MIT Endicott house.
Sharing AI progress on mathematics (OpenAI)A few hours ago, Open AI shared solution to a few hundred mathematical problems. Certainly this is an amazing milestone for mathematics, and the results will needs to be verified and digested by human mathematicians in the months to come. Several of the problems were discussed here on the blog over the past two decades and I will try to give a more detailed update regarding these problems and other “Math for AI” recent achievements. This is an amazing development!
Both the Open AI list and some news from colleagues from the last days are relevant to my lecture around Borsuk’s conjecture on Friday in Jeff-Fest.
My Lecture TourI am currently in the middle of a nostalgic and hectic tour, visiting Brown University, MIT, Yale, IAS, Rutgers (for Jeff Kahn’s conference celebration), and Princeton University. It is a pleasure to meet old friends and (both young and old) mathematicians that I did not meet before. I truly love both mathematics and the community of mathematicians, and I hope my lectures and posts reflect this feeling.
Right now I am writing from Avi and Edna’s home at the IAS, having just returned from a lovely mathematics department event welcoming the new academic year. Tomorrow, I will be speaking here about intersection homology and combinatorics. Later in the evening, I am giving a short lecture in the “discussion series” about my work on quantum computation, which I hope will spark an engaging conversation. It will be quite a challenge to present quantum computation and my two decades of research on the subject in a 20-to-30-minute lecture tailored for a general audience.
I also have a rather intense blogging plans: I am planning three posts based on my lectures: one on algebraic shifting at MIT, one on intersection homology and combinatorics at the IAS, and one on problems around Borsuk’s conjecture at “Jeff Fest.” Here is how I plan to go about it: I will feed an AI tool my abstract and a rough outline of the talk, and let it prepare detailed lecture notes that I can use for the presentation itself. (For the MIT talk, I only thought of this approach after the fact!) Later on, I will edit those lecture notes into blog posts. It is quite interesting—and a little amusing—to note that the AI writes not only about the technical matters but also attempts to capture “my” feelings and hopes.
I also plan a post with a candidate for “the most outrageous conjecture,” alongside an entertaining double-feature “test your intuition” post.
OpenAI’s New Mathematical Results: Connections to Earlier PostsAs I mentioned above, OpenAI released an impressive collection of mathematical results produced by an internal AI model: 722 manuscripts grouped into 372 families. Many of these concern problems that have appeared on this blog over the years.
Three disclaimers: first, the collection includes results with different stages of verification; their proofs will need to be checked and digested by the mathematical community. Second, even Lean verification may have issues, and third, there were a variety of other AI based results, also related to earlier blog posts that I did not collected; among those let me mention the Irrationality of , the Navier Stoke problem, The Komlos conjecture, Chvatal’s conjecture, and the KLS conjecture.
Here are twenty connections to earlier posts, with related results occasionally grouped together.
It is remarkable to see so many familiar questions in a single announcement. There is a great deal here to read, check, understand, and build on!
Authors: Mark Chen, Xi Chen, Hao Cui, William Pires, Jonah Stockwell
We show that computing an approximate mixed Bayes-Nash equilibrium in a discrete first-price auction with correlated priors is PPAD-complete. The key intermediate step in our reduction is the PPAD-completeness of computing an approximate Nash equilibrium in a new normal-form game, the hypergraph discrete first-price auction, which may be of independent interest.Authors: Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi
Understanding the limits of list-decodability of Reed-Solomon codes has been one of the most important open problems in algebraic coding theory. Recently, Brakensiek, Chen, Putterman, Zhang, and Zheng, in a remarkable breakthrough, showed that Reed-Solomon (RS) codes over fields of large characteristic are algorithmically list-decodable all the way up to capacity. Building on this result, Jeronimo subsequently extended these techniques to solve the proximity-gaps question for RS codes. In this article, we give a unified and transparent exposition of these results.Authors: Damiano Abram, Agni Datta, Archisman Dutta, Lawrence Roy
Extremely Lossy Functions (ELFs) are a standard model primitive that captures many useful properties of random oracles (Zhandry, Crypto 2016). While there are many variations of ELFs with additional properties, every construction (excluding obfuscation) has followed essentially the same template of bootstrapping from a sequence of ELFs secure only against fixed-size adversaries, and every construction was based on only the exponential hardness of DDH (or $k$-Lin), an assumption that is only reasonable over elliptic curves. We introduce and construct Extremely Lossy Trapdoor Hashing (ELTDH), a stronger notion that implies all known variations of ELFs. Our construction achieves ELTDH in one go, without bootstrapping from schemes secure for only fixed-size adversaries, which makes it simpler and more efficient than existing ELFs. We assume exponential security of the small-exponent discrete logarithm, together with polynomial security of decisional composite residuosity (DCR). Exponential security is only required in the size of the secret exponent, not the size of the group, so the assumption plausibly holds for multiplication modulo $N^2$ (and for many other cryptographic groups), despite the subexponential-time discrete logarithm attacks from index calculus. Our results diversify the assumptions underlying ELFs, while also giving a simpler construction.Authors: Zhewei Wei
We show that the worst-case combinatorial discrepancy of $n$ points in the plane with respect to axis-parallel rectangles is $Θ(\log^{3/2}n)$. The known bounds were $Ω(\log n)$ and $O(\log^{3/2}n)$; we prove the matching lower bound. It holds for random point sets: for every $A>0$, there is a constant $c_A>0$ such that, with probability at least $1-e^{-An}$, every coloring of $n$ independent uniform points in the unit square has an anchored rectangle with imbalance at least $c_A(\log_2n)^{3/2}$. The proof is surprisingly simple and elementary. It reveals one coordinate digit by digit. With overwhelming probability over the points, the conditional gains of an oscillation potential add up to $Ω(\log^{3/2}n)$ over $Θ(\log n)$ digits. Bounded differences control the fluctuations well enough for a union bound over all colorings.Authors: Mikkel Abrahamsen, Jacobus Conradi, Asbjørn Lind
The 2026 ACM SIGSPATIAL GIS Cup posed the following geometric challenge: Given a set of simple, pair-wise disjoint polygons, compute $k$ antennas (points) on polygon boundaries, maximizing the number of polygons with at least a fraction $τ$ of their perimeter visible from the antennas. Contestants had 24 hours to produce the best possible solutions. We describe an approach that separates geometric visibility preprocessing from a portfolio of incremental combinatorial searches. A construction pool provides initial solutions with antennas restricted to polygon vertices; simulated annealing explores one-for-one antenna swaps, complemented by exact discrete one-swap descent, ruin-and-recreate, and elite crossover. A secondary objective rewards progress toward the service threshold without overriding the primary score. Candidate antennas are later expanded to include points in polygon-edge interiors. Our submitted solutions cover between 261 and 16,273 buildings across the nine parameter combinations, and the team was invited to present as one of the top entries. The code is available at github.com/JacobusTheSecond/giscup.Authors: Hariharan Narayanan
We study $\varepsilon$-relative approximation of mixed volumes of a fixed number $k$ of full-dimensional convex bodies in $\mathbb{R}^n$, given membership oracles and a known bound $B_n\subseteq K_i\subseteq R_0B_n$. We present a randomized algorithm that estimates any prescribed mixed volume within relative error $\varepsilon$ with probability at least $1-δ$, using polynomially many oracle calls and bit operations in $n$, $\log R_0$, $\varepsilon^{-1}$, and $\logδ^{-1}$ for fixed $k$.Authors: Joshua Brakensiek, Aaron Putterman, Amatya Sharma, Santhoshini Velusamy
We study the one-pass streaming complexity of CSPs over a fixed finite relation $R$ under three natural objectives: $\textsf{SAT}(R)$, deciding whether all constraints can be satisfied; $\textsf{Min}$-$\textsf{CSP}(R)$, approximately minimizing the number of unsatisfied constraints; and $\textsf{Exact-CSP}(R)$, exactly computing the maximum number of satisfied constraints. Sharma and Velusamy (ESA 2026) characterized the streaming complexity of satisfiability for CSPs with literals using the non-redundancy parameter $\textsf{NRD}_n(R)$, which roughly measures the largest instance in which every constraint is independently necessary. For the most general setting without literals, they obtained the corresponding characterization for Boolean relations and showed obstacles to extending their techniques to larger domains. Kol, Paramonov, Saxena, and Yu (ITCS 2023) similarly characterized the streaming complexity of $\textsf{Exact-CSP}(R)$ for Boolean CSPs with literals in terms of the degree deg$(R)$ of the relation when written as a polynomial, while without literals, the corresponding result was known only for $\textsf{Max-Cut}$. For all three of the objectives we study, we give tight characterizations for unweighted CSP instances over arbitrary finite domains. The streaming algorithms we provide are deterministic, while the corresponding bounds are tight up to polylogarithmic factors, even against randomized algorithms. The central idea in all three results is a reduction of $R$ to its core, a canonical subrelation of $R$ which admits gadgets that allow for the hard-pinning (or fixing) of variables.Authors: Anup Bhattacharya, Suryendu Mondal, Pinki Pradhan
We design an almost instance optimal algorithm for the sum estimation problem using weighted sampling. We show that the sample complexity for sum estimation is closely related to the $\ell_2$ norm of the weighted sampling distribution. We show an almost instance optimal lower bound for this problem as well. We also study the moment estimation problem and design an algorithm that has better instance-wise sample complexity bounds.Authors: Arnab Mallick, Indraveni Chebolu
Byzantine quorum safety relies on correct replicas refusing to sign conflicting values. A replica that loses its protocol state during recovery but retains its identity and signing key may forget an earlier vote. We study certificates formed by matching signed votes from at least $q$ of $n$ replicas, assuming that each correct replica avoids conflicting votes between recoveries. If two conflicting certificates form, their overlap has size between $2q-n$ and $b+c$, where $b$ counts Byzantine replicas and $c$ counts correct identities that recovered during the execution considered. Our main result decomposes the slack $b+c-(2q-n)$ into four nonnegative counts: extra signers in the first certificate, extra signers in the second, identities in neither certificate, and Byzantine or recovering identities outside their overlap. Zero slack forces an exact signer partition. With $n=3f+1$ replicas, threshold $q=2f+1$, at most $f$ Byzantine replicas, and exactly one correct recovery event, any conflicting pair forces exactly $f$ Byzantine replicas, all in the overlap together with the recovered replica; each certificate has a disjoint side of $f$ correct replicas. A minimal protocol attains this form. We distinguish certificate formation from acceptance, give a sufficient check using configured fault and recovery caps, and explain why durable vote records written before signature release prevent the conflict.Authors: Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, Chinmay Sonar, Vaishali Surianarayanan, Jie Xue
Given a complete graph whose edge weights represent dissimilarities, Metric Violation Distance asks whether at most $k$ weights can be changed to form a metric. Motivated by metric repair for noisy data, the problem admits a polynomial-time $O(\log n)$-approximation due to Cohen-Addad, Fan, Lee and de Mesmay [SIAM J. Comput., 2025]. In the context of parameterized complexity, Fan, Gilbert, Raichel, Sonthalia and Van Buskirk [SWAT 2020] gave a $k^{O(k)}n^{O(1)}$-time algorithm. Fomin, Golovach and More [IPEC 2026] obtained an $O(k^2)$ kernel and a single-exponential algorithm for the ultrametric case. They asked whether general metrics admit a single-exponential algorithm and a polynomial kernel, and whether the tree-metric analogue is fixed-parameter tractable. We answer all three questions. We give a $2^{O(k)}n^{O(1)}$-time algorithm and prove that, unless ETH fails, no $2^{o(k)}n^{O(1)}$-time algorithm exists, even when all input distances lie in $\{1,2,3\}$. We also give a kernel with at most $6k$ vertices. The kernel supports solution lifting and can precede any approximation algorithm. Combined with the $O(\log n)$-approximation of Cohen-Addad, Fan, Lee and de Mesmay, it yields an $O(\log \mathrm{OPT})$-approximation at no asymptotic cost in running time. Both results extend to an interval generalization in which each edge $e$ has an observed value $M_e$ and an admissible range $[A_e,B_e]$ within which it may be reassigned; the kernel then has $7k$ vertices. Finally, Tree Metric Violation Distance is fixed-parameter tractable and solvable in $k^{O(k)}n^{O(1)}$ time.Authors: Eric Dai, Maxwell Fishelson
Probability forecasts are calibrated when predicted probabilities match empirical outcome frequencies: among events assigned a probability $p$, we'd hope that the fraction of positive outcomes is close to $p$. We study the problem of sequential forecasting of binary outcomes. The classical $O(T^{2/3})$ bound on expected cumulative $\ell_1$-calibration error established by Foster and Vohra stood for over two decades until Dagan et al. reduced the exponent $2/3$ by an unspecified constant. We establish a new two-phase recursive labeling strategy for the sign-preservation-with-reuse game that yields the bound $O(n^αt^β)$ for all choices of space and time. We then sharpen the reduction from upper bounds on sign preservation to calibration by modifying the equivalence of Dagan et al. to use only $O(\log T)$ instances of the sign-preservation-with-reuse game. This lets us establish an explicit bound of $O(T^{0.662942288})$, the first explicit exponent below $2/3$ for sequential calibration, by combining both improvements and choosing explicit feasible parameters.Authors: Hanqing Li
We give a deterministic reduction for maintaining simultaneous approximate single-source distance estimates in online decremental directed graphs. For positive integer weights in $[1,W]$, the algorithm maintains an explicit array of integer $(1+\varepsilon)$ upper estimates, identifies unreachable vertices exactly, and answers numerical queries in constant time. Let $N=m+n$, $S=N+\lceil1/\varepsilon\rceil$, and assume $\log W=\operatorname{polylog}(S)$. Initialization and all updates take $O(Δ)+(N+Δ_{\mathrm{eff}}+\mathcal{L}/\varepsilon)S^{o(1)}$ time, where $Δ$ counts raw updates, $Δ_{\mathrm{eff}}=O(m(1+\log W)/\varepsilon)$ counts filtered updates, and $\mathcal{L}$ measures finite distance growth weighted by the current indegrees of the reachable subgraph. Removed edges and vertices that become unreachable incur no subsequent growth charge. Consequently, the worst-case bound is $O(Δ)+(N/\varepsilon)S^{o(1)}$, which is almost linear for subpolynomial inverse accuracy. The reduction uses the dynamic minimum-ratio cut and exact reachability algorithms of van den Brand et al. (FOCS 2024). A degree-weighted clipped logarithmic potential turns constant relative cut balance into accuracy at every target; a successor cut then restores strict feasibility. A distance warm start and the energy released by decreasing return coefficients yield the refined growth bound. Return mass also amplifies the accuracy of the existing change detector. The public estimates can be monotone, with $O(n+\mathcal{J}/\varepsilon)$ array writes for an unweighted finite-growth measure $\mathcal{J}\le\mathcal{L}$. Execution uses rational arithmetic. A separate reduction extends the worst-case guarantee to nonnegative integer weights. The algorithm maintains numerical estimates and does not provide fast path reporting.Authors: Hanqing Li
We give an exact algorithm for continuous separable convex quadratic programming with an integer equality matrix and nonnegative variables. The number of rational arithmetic operations and comparisons is polynomial in the dimensions and the encoding length of the constraint matrix, independently of the right-hand side, linear costs, and all nonnegative quadratic weights. Intermediate rational encodings are polynomial in the complete input. This yields a strongly polynomial algorithm for every integer matrix class with polynomially bounded entry encodings, including arbitrary matrices with entries in $\{0,\pm1\}$. The local solver compresses a quadratic objective on an integer box and solves only the compressed continuous problem. Two-sided proximity on boxes with rational bounds transfers its solution to a nearby original optimum; integer optima are used only in the proof. A single linear program supplies an error bound and a dual potential, while tight-coordinate revelation and fixed feasible anchors ensure termination and control encoding lengths. An explicit lifting extends the result to convex piecewise quadratic functions of signed integer affine features, with operation counts independent of breakpoints and objective coefficients. Applications include continuous multicommodity flow with shared capacities and piecewise quadratic costs of aggregate congestion.Authors: Moran Feldman, Alan Kuhnle
Maximizing a submodular function subject to a matroid constraint is a cornerstone problem in combinatorial optimization. The state-of-the-art algorithm for this problem obtains $0.401$-approximation~\cite{buchbinder2024constrained}, and the state-of-the-art hardness result shows that no polynomial time algorithm can obtain better than $0.478$-approximation for this problem~\cite{oveisgharan2011submodular}. In this work, we present the first improvement in $15$ years for the hardness result, showing that no polynomial time algorithm in the value-oracle model can obtain better than $8/17 \approx 0.471$-approximation, even for the special case of a cardinality or (simplified) partition matroid constraint.Authors: Purv Patel, Ajay D. Kshemkalyani
Causal message ordering provides essential semantics for distributed applications, yet ensuring it within an asynchronous system subject to Byzantine failures presents fundamental theoretical and practical challenges. Prior research establishes that algorithms cannot guarantee both strong safety and liveness without using cryptography under these conditions. Existing Byzantine-tolerant solutions make synchrony assumptions or suffer from $O(n)$ message space overheads and $O(n^2)$ message complexity, where $n$ is the number of processes in the system, or use cryptography, but may not guarantee strong safety. In this paper, we present a novel Byzantine-tolerant causal ordering algorithm that achieves an optimal $O(1)$ application message space overhead for point-to-point messages. Our approach uses a Sender Permission to Send (SPS) invariant and an \textit{Isolated-Buffer Optimistic Model} for the memory management architecture. To circumvent Byzantine state-pinning and head-of-line blocking attacks, instead of unified causal buffers, we use isolated, per-peer queues equipped with event-driven \textit{Cascading Space Evictions}. We formally prove that our algorithm guarantees system-wide liveness and satisfies a weakened causal safety abstraction called \textit{Congestion-Relaxed Causal Delivery}. Under this model, weak causal safety is strictly preserved for all honest-to-honest communications unless extreme network latency or Byzantine withholding attacks exceed quantifiable local buffer capacities, forcing optimistic queue evictions. This formal guarantee successfully balances causal ordering with high throughput, constant message space overhead, low computational overhead, and strictly bounded local space.Authors: Jerry Anunrojwong, Akshit Kumar, Rachitesh Kumar
We study an online trading problem where a trader, given a sequence of i.i.d. prices drawn from a known distribution $F$ on $[0,1]$, must make irrevocable buy, sell, or hold decisions subject to storage constraints. We investigate achievable algorithmic performance measured in terms of regret, the difference between the expected profit of the hindsight optimal policy that knows the entire price sequence and an online algorithm. We analyze finite atomic and continuous distributions characterized by their local behavior around the median which we capture using a parameter $β$. The parameter $β$ quantifies how the mass of prices accumulates around the distribution median. We identify a new driver of algorithmic performance, demonstrating that median gaps coupled with an initial inventory level of zero can force regret scaling of $Ω(T^{(β+ 1)/(2β+4)})$ --- establishing a novel spectrum of fundamental limits on algorithmic performance. We then study STARS, short for Storage Trading by Averaging Repeatedly across multiple Scenarios, which simulates possible future price scenarios to approximate the value-to-go function and make buy/sell/hold decisions. We show that STARS obtain near-optimal algorithmic performance (upto poly-logarithmic factors) across a broad range of distributions. In particular, it achieves $O(\log T)$ regret for finite atomic prices, $\widetilde{O}(T^{β/(2β+2)})$ for continuous distributions without a median gap and $\widetilde{O}(T^{(β+1)/(2β+4)})$ for continuous distributions with a median gap for $β\geq 0$.Authors: Victor Lagerkvist
The constraint satisfaction problem over a set of relations $Γ$ (CSP($Γ$)) is the computational problem of deciding if a set of constraints admits at least one solution. The classical complexity for finite-domain CSP($Γ$) is settled by the CSP dichotomy theorem: it is tractable if $Γ$ satisfies a non-trivial algebraic invariant and is NP-complete otherwise. However, not all these algebraic invariants result in efficient algorithms despite being theoretically tractable. A notable case that generalizes linear equations is that of Maltsev CSPs: an $n$-variable instance with $m$ constraints is solvable in roughly $O(n^8 \cdot m)$ time by Bulatov and Dalmau (SIAM J. Comput. 2006) or $O(n^4 \cdot m)$ time by Dyer and Richerby (SIAM J. Comput. 2013). At the same time, arguably, most "natural" and efficiently usable polynomial-time algorithms rarely exceed a quadratic or cubic time bound. In this paper we revisit Maltsev constraints with this question in mind and find a $O(n^2 \cdot m)$ algorithm (for finite languages, for infinite languages we in addition need to take the total size of the instance into account). The main novel idea is to not attempt to improve the bottleneck in Bulatov and Dalmau (the Fix-Values procedure) but to avoid it altogether with a slightly more refined approach that allows us to search through a smaller space.Authors: Anupam Gupta, Guru Guruganesh, Honghao Lin, Vahab Mirrokni, Renato Paes Leme, David P. Woodruff
In online inverse linear optimization, a learner recommends an action and then observes the choice of an expert who maximizes a fixed, unknown linear objective on $\mathbb{R}^{d}$; the goal is to learn to optimize this objective without observing it. Sakaue recently obtained the optimal regret $O(\sqrt d)$ with a randomized algorithm making $(dT)^{O(d)}$ linear optimizations per round, and asked whether it can be attained in polynomial time. We answer positively: our deterministic algorithm has regret $O(\sqrt d)$ for every horizon $T$ and runs in time polynomial in $d$ and $T$. It is a variant of the variable-metric algorithms of Sakaue et al.\ and Cai et al., in which a metric update is revoked once the query point moves far enough from where the update was made.Authors: Daniel A. Spielman, Xifan Yu
We prove that the probability that Gaussian elimination with partial pivoting on $n \times n$ random matrices has growth $ρ$ is at least inverse quasi-polynomial: $Ω(\exp(-c \log^2 (ρ)\log(n)))$ for some constant $c > 0$. This lower bound breaks standard conjectures in the smoothed and average-case analysis of Gaussian elimination. To the best of our knowledge, it is the first non-trivial lower bound on the probability of large growth for Gaussian random matrices.Authors: Cameron Ibrahim, S M Ferdous, Erdal Mutlu, Ilya Safro, Mahantesh Halappanavar
When optimizing computing architecture for specific computationally intensive tasks, such as evaluating or training a neural network, it is important to identify what computational subtasks will offer the greatest decrease in cost (e.g., wall clock time or energy usage). This problem is known as Hardware-Software (HS) Partitioning, and it has a variety of formulations, many of which are NP-Hard. In this paper, we will define a family of HS Partitioning formulations which admit an exact fixed parameter tractable algorithm based on the directed pathwidth of the given task graph and show that this family of problems contains multiple existing formulations such as makespan minimization. Finally, we examine task graphs with small directed pathwidth that arise in real world applications and show that our algorithm can provide a speed up of up to 200x over a comparable linear programming approach utilizing the Gurobi ILP Library.Authors: Emile Anand, Jan van den Brand, Peter Chen
The Gram-Schmidt Walk is a randomized vector-balancing algorithm whose subgaussian guarantees support applications in discrepancy, experimental design, and data compression; however, these theoretical guarantees are established in exact arithmetic, whereas implementations must approximate least-squares directions, boundary updates, and sampling probabilities in finite precision. This is important because small numerical errors can change which coordinates freeze and thereby alter the subsequent trajectory. We analyze the concentration of the perturbed Gram-Schmidt walk directly under bounded, potentially biased and history-dependent errors. For $n$ input vectors of Euclidean norm at most one, we obtain a modified MGF bound depending on key error sources which recovers the original result as the error goes to zero. We also construct a full-column-rank instance in which bounded update errors produce bias of order $\min\{n^2\varepsilon,n\}$, showing that updates accumulate error unavoidably under this model. Finally, we validate our findings in a variety of settings by ablating on the bit precision and problem size.Authors: Benjamin Lovitz
We construct explicit n x n x n tensors of border rank at least 3n-o(n), improving the previous record of (2 + $\varepsilon$)n due to (Landsberg and Michalek 2025). We also prove that the linear flattening method cannot be used to establish lower bounds on border rank beyond 2n-1. When n is odd, we prove that this bound is achieved by Koszul flattenings. When n is even, a result of (Landsberg 2015) shows that Koszul flattenings can achieve 2n-2, leaving an open gap of size one. Our 2n-1 bound improves the best known 6n-4 linear flattening barrier due to (Garg et al. 2019) and (Buczyński 2026). Combined, these results show that our 3n-o(n) construction, as well as the construction of Landsberg and Michalek, provide explicit examples of tensors with higher border rank than any linear flattening can achieve.Authors: Marcia Fampa, Jon Lee
The maximum-entropy sampling problem (MESP) seeks, for an order-$n$ covariance matrix $C$, a principal submatrix of order $s$ with maximum log-determinant. Mostly for convenience, we assume that $C$ is nonsingular. Al-Thani and Lee (2023) solved MESP in $O(n^5)$ time when $C$ or $C^{-1}$ is tridiagonal. We show that the inner maximization of their recursion depends only on a prefix of the index set and that no piece of a solution is longer than $s$; this gives an $O(ns^2)$-time algorithm that returns the optimal value for every budget $t\le s$. When $C^{-1}$ is tridiagonal, $C$ is, up to scaling, the covariance matrix of an Ornstein--Uhlenbeck process observed at unevenly spaced times, and MESP becomes choosing points on a line under a concave gap function with the Monge property; this gives an $O(ns)$-time algorithm and, in the first-order autoregressive case, a closed-form solution. Given only $C$, we solve MESP in $O(n^2)$ time whenever $C$ or $C^{-1}$ is tridiagonal, up to a symmetric permutation, and we recognize these cases within the same bound. For spiders, we make explicit, and sharpen, the dependence on the number of legs, and, drawing on a hardness result of Ohsaka for stars, we observe that, unless $\mathrm{P}=\mathrm{NP}$, the exponent of the running time must grow with the number of legs.Authors: Nader H. Bshouty
We study isomorphism decision and basis construction for finite Abelian groups of known order $n$. We measure complexity by the number of additions performed in the groups and by the total running time. We give a randomized isomorphism decision algorithm that performs $\tilde O(n^{1/4})$ group additions and runs in $\tilde O(n^{1/4})$ time. This improves the $\tilde O(\sqrt n)$ upper bound of Chen and Fu and matches Bshouty $Ω(n^{1/4})$ lower bound up to polylogarithmic factors. We also prove that finding a basis with success probability at least $2/3$ requires $Ω(\sqrt n)$ group additions in the worst case. This matches the $\tilde O(\sqrt n)$ upper bound of Chen and Fu up to polylogarithmic factors. These results separate isomorphism decision from basis construction in finite Abelian groups: their optimal worst-case complexities are $\tildeΘ(n^{1/4})$ and $\tildeΘ(\sqrt n)$, respectivelAuthors: Zhangsong Li
Consider the $\mathbb Z_2$ synchronization problem \[ \boldsymbol{Y} = \fracλ{\sqrt n} θθ^{\top} + \boldsymbol{Z}, \] where $θ$ is uniform on $\{-1,1\}^n$ and $\boldsymbol{Z}$ is an independent Gaussian Wigner matrix with off-diagonal variance one. We give a polynomial-time posterior sampling algorithm for every fixed $λ>1$, for which the conditional output law converges to the posterior in total variation, in expectation over the observation. The construction combines sequential TAP proposals with an independence Metropolis correction. The key is to control signed overlaps after logarithmic pinning and conditional TAP approximations along a random revealing path, which give an efficiently evaluable proposal with a polynomial density-ratio bound outside a set of vanishing posterior mass. To the best of our knowledge, this is the first polynomial-time posterior sampler for $\mathbb Z_2$ synchronization with a total-variation guarantee throughout the supercritical regime. For comparison, the diffusion-based sampler of \cite{montanari2023posterior} gives normalized Wasserstein guarantees at sufficiently large fixed signal-to-noise ratio.from Emanuele Viola
I was just pointed to https://arxiv.org/abs/2610.06783v1 wow! Another item for my growing list of disproved conjectures in my book… told ya that P=NP!
from ECCC Papers
from Ben Recht
Hi there, argmin readers! Today’s post is a live blog of Class 10 of my graduate seminar “Forecasting: A Critical Retrospective.” The syllabus and list of past posts are here.
All of my cybernetically inclined friends are into Friedrich Hayek, but my research and teaching keep bringing me back to John Maynard Keynes. These two gentlemen occupy the two poles of the dialectic of the American Experiment. Hayek famously introduced the notion of markets as distributed computers, where prices carry knowledge across the economy. Keynes, with his economic theory of central banking, set the stage for centralized computing of economic variables to govern those markets.
In Keynes’ paradigm-shifting 1936 work, The General Theory of Employment, Interest, and Money, he lays out an oxymoronic formula for central planning in capitalist societies.1 The basics of the Keynesian model are laid out in the appendix of Robert Evans’ paper from this week’s reading. The national economy has four key variables: the amount of investment firms make into the economy, the amount of savings firms accumulate in financial instruments or by paying down debt, the demand for money in the economy to facilitate purchases and sales, and the supply of money from the government. To change these variables, the government can enact various policies. For example, it can invest in infrastructure, raise taxes, increase the money supply, or change interest rates. Keynes argues that the government can dictate the economy’s output—and hence the general welfare of all citizens, who are players in the big macroeconomic game—by properly executing its policy apparatus.
This would set the stage for the subsequent 90 years of democratic capitalist monetary policy. The government has to make policy to ensure a well-run economy. To do this, it has to know the current state of national investment and savings. It also has to be able to forecast what these variables will be if no policy changes are enacted. This last requirement has driven the major investment in macroeconomic forecasting.
Forecasting in macroeconomics is thus primarily a tool of control. Here I mean control in the academic sense: the theory of dynamical systems with inputs and outputs and the design of subsystems to drive outputs to desired targets. Keynes casts the economy as a giant control problem, where the goal is to deftly change policy to ensure a particular state of economic output and employment. It should be no surprise that tools from control, notably the work of Rudolf Kalman on optimal filtering and control of linear systems with quadratic objectives, play a central role in macroeconomics.
Now, to filter and control, we need to make predictions. Keynes didn’t tell us how to generate those predictions. But his disciples, in what is often called “Keynesian” macroeconomic forecasting, write down structural equations of the economy, fit the parameters of these equations using varied means, and then make forecasts directly from the fitted models.
This program of prediction ran into several obstacles. First, it requires mathematical equations that predict all of the aspects of the economy needed to precisely determine optimal policies. Second, it requires a massive measurement system to pin down all the relevant factors in the model. Both were terribly daunting and required a great deal of expert judgment.
Economists want their methods to be “scientific,” since they influence decisions with major consequences. However, with so many variables, so little stationarity in economic conditions, and so much politics involved, building a truly objective and replicable system seems like a fool’s errand. Beatrice Cherrier details some of the typically arbitrary, political nature of macroeconomic sausage-making in this blog post. Evans details the amount of analytical flexibility and expert judgment forecasters necessarily employ in their predictive techniques.
Beyond these nuances of modeling and measurement, however, a fundamental problem of feedback control remains insurmountable. The models have a ton of parameters that are fit to historical data. Different policies yield different parameters. These parameters change when a policy changes. And you can’t predict what the parameters will be after a policy changes. So what on earth are we doing?
The critique in the previous paragraph was levied at macroeconomic forecasting by Robert Lucas in 1976. That macroeconomic forecasting is still an influential practice 50 years later certainly tells us something. Macroeconomic forecasters occupied positions of power and held a sense of civic duty. So they took Lucas’ critique as a challenge, not a reason to close up shop.
I’m not going to hash out the various attempts to build complex, nonparametric macroeconomic models that add ornate complexity while failing to dodge the fundamental problem. Theoretical critiques can carry only so much weight. The fact that the Great Recession was substantially caused by terrible financial policy and inadequate forecasting should have been the nail in the coffin. In 2003, Robert Lucas himself declared that macroeconomics had been a great success:
“My thesis in this lecture is that macroeconomics in this original sense has succeeded: Its central problem of depression prevention has been solved, for all practical purposes, and has in fact been solved for many decades.”
Oops.
Economists didn’t see a problem with the deep instability created by hyperfinancialization. Indeed, though Evans did his ethnographic research on macroeconomists a decade before the crash, his point rings true:
“...[E]conomic policy cannot be based on a quantitative calculus of costs and benefits and must, instead, rest on the considered judgement of a community of experts. Macroeconomic modellers may be those experts, but to expect anything more from them is to expect too much.”
So who should we trust? The Obama administration hoped economists could help get us out of the mess. But 8 years of attempted neoliberal patching of the American system ended in such broad dissatisfaction that… well, you know what happened. We’ve since had a decade of federal unrest as we try to unmoor ourselves from the expertise of economists. While I don’t believe the Biden and Trump administrations have found themselves a suitable alternative, I make no predictions about whose policy advice we’ll be deferring ot next.
The quote from last week’s post was from a rebuttal Keynes wrote to critics of this book.
By Ittai Abraham, Clément Burgelin, Antoine Murat, Joachim Neu
from ECCC Papers
Authors: Christine Li, Natalie Parham
We identify a barrier that helps explain why proving stronger quantum state-preparation lower bounds has been so difficult. In particular, we establish a quantum analogue of the Razborov-Rudich natural proofs barrier for state-preparation lower bounds. We call a property of quantum states \emph{natural} if it holds for a sufficiently large fraction of Haar-random states and can be efficiently tested when given all of the state's amplitudes. Under a standard cryptographic assumption, we show that no natural property can prove superpolynomial state-preparation lower bounds even against a fixed level of the Magic Hierarchy. We show that several existing state-preparation lower-bound techniques are natural in our sense, including arguments based on approximate degree, not being a unique ground state of a local Hamiltonian, and mutual information.Authors: Mark Bun, Joao F. Doriguello, John Kallaugher, Nadezhda Voronova
We study the one-way communication complexity of the $f$-Boolean Hidden Partition problem. Here, Alice is given an $n$-bit string and Bob is given $Ω(n)$ disjoint blocks of its indices together with a string of labels. Under the promise that the evaluations of $f$ on these blocks either agree with all of the labels or disagree with all of them, Bob must determine which is the case using a single message from Alice. This problem generalizes the Boolean Hidden Matching and Hidden Hypermatching problems, which capture the special case where $f$ is the parity function. We establish classical and quantum communication bounds for $f$-Boolean Hidden Partition in terms of the sign degree $d$ of $f$, proving a conjecture of Doriguello and Montanaro (TQC 2020). Their prior work gave logarithmic communication upper bounds for classical protocols when $d \le 1$ and quantum protocols when $d \le 2$, as well as polynomial lower bounds for certain structured functions with larger sign degree. We show that for every $f$ of sign degree $d \ge 2$, the randomized classical communication complexity of this problem is $Θ(n^{1-1/d})$ while its quantum communication complexity lies between $Ω(n^{1-2/d})$ and $\bO{n^{1-1/\lceil d/2 \rceil} \log n}$. This completely characterizes the functions $f$ admitting polynomial quantum advantage as those for which $d \ge 2$, with a new infinite family of exponential separations given by the case $d = 2$.Authors: Berta Casas, Diego García-Martín, Yuxuan Zhang
Clifford and matchgate circuits are canonical families of classically simulable quantum circuits. Their intersection, the matchgate-Clifford group, plays an important role in randomized fermionic protocols and in matchgate synthesis. Its adjoint action is isomorphic to the group of unit-determinant signed permutations of $2n$ Majorana modes, and we study optimal exact synthesis in this group. That is, given a target unitary and a gate set, output an $n$-qubit circuit implementing the target using the fewest operations. We show that the complexity of this problem strongly depends on the gate set. In particular, we study gate sets consisting of Majorana braids with different connectivity graphs. For path and complete graphs, we prove that the problem is classically solvable in $\mathcal{O}\left(n^2\right)$ time, and we provide explicit gate-optimal compilers. In addition, we prove that when the connectivity graph is a tree, the decision version of the optimal synthesis problem becomes NP-complete. Finally, we benchmark our optimal compiler on chains of up to $n=80$ qubits against those of \texttt{Qiskit} and \texttt{Tket}, obtaining circuits with constant factor improvements $\times2.57$ and $\times2.28$ in the total number of gates, respectively.Authors: Anssi Yli-Jyrä
We introduce recurrent incidence automata (RIAs), a new automaton model motivated by a decomposition of certain two-stack visibly pushdown computations. The decomposition separates vertex-local finite-state computations from recurrent one-stack interfaces connecting consecutive vertices. The construction is motivated by a two-stack visibly pushdown encoding of arbitrary ordered graphs whose strings admit a unique factorization into center-foldable vertex-local factors and whose auxiliary stack is empty at every factor boundary. Folding each factor into a sequence of pair symbols yields a local interface transformation. An RIA consists of a finite-state unit that computes these transformations and a recurrent layer that composes them across consecutive factors. Rather than manipulating an internal pushdown store, RIAs externalize long-range stack memory into recurrent interfaces between local computations. We show that nondeterministic RIA languages are closed under union, intersection, concatenation, Kleene-*, and reversal. Deterministic RIAs are closed under Boolean operations, although emptiness remains undecidable.Authors: Alper Cakan, Kai-Min Chung, Wei-Hsiang Hung, Tzu-Yi Yang
Since the introduction of the complexity class QMA as a quantum-verifier analogue of NP (Kitaev, 1997), many have wondered whether quantum proofs are necessary or classical proofs suffice - that is, whether QMA = QCMA or QCMA != QMA (Aharonov and Naveh, 2002; Aaronson and Kuperberg, CCC '07). This longstanding question was recently answered by works of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC '26) and Bostanci, Huang, and Vaikuntanathan (FOCS '26), which showed that quantum proofs are more powerful than classical ones in the classical-oracle setting. However, it remains unclear what exactly makes quantum proofs more powerful than classical ones. In the information-theoretic setting, a family of quantum states is not classicalizable if and only if it is unclonable. Indeed, these recent works also explicitly highlight the unclonability of their quantum proofs as a key mechanism behind their separations, and their arguments crucially rely on this property. This raises the question of whether unclonability is necessary for quantum proofs to be more powerful than classical ones. In this work, we show that even clonable quantum proofs can be more powerful than classical ones relative to a classical oracle by constructing a classical oracle O such that QCMA^O != ClonableQMA^O. This resolves the open question of Nehoran and Zhandry (ITCS '24), who established the analogous separation relative to a quantum oracle. We also show a classical-oracle separation between BQP/clonableqpoly and BQP/poly, and give applications of our results to quantum cryptography.Authors: Szilárd Zsolt Fazekas, Xinhao Huang, Robert Mercaş
The universality index corresponding to a word is the largest integer k such that every word of length k over the given alphabet occurs in it as a subsequence. Relative to languages this notion can be investigated with respect to both existential and universal quantifiers, with the former corresponding to the existence of a word in the language with universality index at least k, while the latter considers the index across all words that the language contains. In this work we study the existential (exists-universality) and universal (forall-universality) subsequence universality (as introduced in [Adamson et al., ISAAC 2023]) for binary languages consisting of all words with a fixed number of letters a, letters b, and subsequences ab. We prove that both exists- and forall-universality admit exact arithmetic characterizations for these languages. Extending the above notions, we end the paper by initiating the analysis of the probability of a fixed word occurring as subsequence of the words in such a language. To this end, we prove that, for every fixed pattern word w and an error tolerance, given as input the subsequence counts describing a language, the ratio of words in the language having the pattern w as a subsequence admits an additive approximation scheme that is polynomial-time in the binary encoding of the input counts.Authors: Andrew Huang, Akshar Ramkumar, John Wright
A major open problem in quantum complexity is the question of unitary synthesis---namely, is it possible to efficiently implement any unitary, given the ability to evaluate any classical function in superposition? Inspired by a recent work by Brakerski and Yuen (CRYPTO 2026), we propose an ``average-case'' unitary synthesis problem, which asks whether it is possible to efficiently implement a Haar random unitary given access to a random Boolean function. We then demonstrate a superpolynomial query lower bound, establishing that unitary synthesis in this model is impossible. Along with our main result, we settle in the negative a question Brakerski and Yuen pose, of whether scalable pseudorandom unitaries (PRUs) can be implemented in the ROM-PRU model. In particular, we show that in the ROM-PRU model, no $Ω(N^{1+γ})$ unitary design on $n$ qubits, where $N=2^n$, can be efficiently achieved for any $γ> 0$. On the other hand, we construct an $O(N)$-design in $\text{poly}(n)$ queries in the same model, surpassing the previously best known results which constructed $O(\sqrt{N})$-designs.Authors: Swastik Kopparty, Rishabh Kothary, Shanthanu S. Rai
We study the problem of constructing highly nonlinear vectorial maps $F: \mathbb F_2^n \to \mathbb F_2^m$. Concretely, we want an $F$ and an $A = A(m,n)> 0$ as small as possible, so that for every affine map $L: \mathbb F_2^n \to \mathbb F_2^m$ (of the form $L(x) = M x + b $) we have: $$\mathrm{agree}(F, L) := |\{ x \in \mathbb F_2^n \mid F(x) = L(x) \}| \leq A.$$ Such questions have been studied by Nyberg (1991,1993), Carlet and Ding (2004,2007), Liu, Mesnager and Chen (2017), Nagy (2025), and Biryukov, Turecek, and Udovenko (2026). There is a classical method of constructing such functions from bent-functions and Fourier analytic ideas; the best bound achievable by this method is: $$ A(m,n) = Θ(2^{n-m} + 2^{n/2}),$$ and in particular, is never smaller than $2^{n/2}$. In this work, we show how to construct highly nonlinear functions beyond this Fourier bound. Concretely, we show how to construct for every $γ>0$, a function $F: \mathbb F_2^n \to \mathbb F_2^m$ with $m = O_γ(n)$, achieving $$ A(m,n) \leq (1 + γ)^n.$$ Surprisingly, we even achieve the same quantitative behavior for the much harder question of having low agreement with $m$-tuples of degree $d$ polynomials $Q: \mathbb F_2^n \to \mathbb F_2^m$, with $m = O_{γ, d}(n)$. Here the previously best bounds were of the form $A(m,n) = O( 2^{-\frac{n}{2^{d+1}}} \cdot 2^n )$ of Ben-Sasson and Kopparty (2010), based on Gowers-norm-type arguments. All our results generalize to all finite fields $\mathbb F_q$ in place of $\mathbb F_2$. Our methods are based on a new connection to classical results on counting solutions to systems of polynomial equations via algebraic methods. This connection brings us to basic questions in combinatorics, about graphs and hypergraphs with simultaneously a small number of edges and independent sets.Authors: Quinten Tupker
Intermediate measurements let quantum computations discard information and reuse their workspace. Deferring all measurements can require storing their entire history, which need not preserve logarithmic space. Fefferman and Remscrim proved that measurements can nevertheless be eliminated with two-sided bounded error, and asked whether the same holds with one-sided error [FR21]. We prove RQLΓ = RQULΓ for the standard gate set Γ = {H, T, CNOT}, preserving polynomial time, logarithmic space, and exactly zero acceptance on no-instances. Our proof extends the density-matrix doubling method of Girish, Raz and Zhan [ GRZ21 ] to general channels, including resets and classical memory. We also prove measurement elimination for broader finite gate sets with exact inverses, including suitable gates with transcendental entries, and establish gate-set independence for a specified family of algebraic gate sets. A separate history-checking construction proves QMAL1,G = QUMAL1,G under explicit gate assumptions: measurements can also be eliminated from logarithmic-space quantum verification while preserving perfect completenessAuthors: Olivier Bournez, Johanne Cohen, Laura Cohen, Adrian Wurm
We study the verification problem for deep narrow ReLU neural networks: given a network of bounded width computing a piecewise-affine map on [0,1], does some input satisfy a prescribed output constraint? Classical NP-hardness proofs for ReLU verification use one neuron per Boolean variable and say nothing about networks of small constant width, while width-1 networks are easy to verify. We show that verification of ReLU networks is NP-complete at width 4 for arbitrary inputs in [0,1]. When inputs are restricted to a natural discrete encoding set, NP-completeness already holds at width 3. Together with polynomial-time decidability at width 1, this leaves open only width 2 on the encoding set, and widths 2 and 3 on [0,1]. The technical core is a fractal preprocessing gadget: a width-2 ReLU subnetwork whose iterate vanishes precisely near a finite Cantor-like subset of [0,1] with 2^n points. It reduces verification of a continuous function on [0,1] to verification on 2^n discrete points without increasing the width, and is the missing ingredient for width-bounded hardness reductions. The same construction yields further results at width 3 on the encoding set: the universal problem is coNP-complete, counting zeros is #P-complete, a majority variant is PP-complete, and approximating the minimum output within a constant gap inherited from Max-3Sat is NP-hard. The NP, coNP and inapproximability results lift to all of [0,1] at width 4; lifting counting and majority, and lifting at width 3, remain open.Authors: Vasilis Pollatos, Andreas Kontogiannis
We study the complexity of Nash equilibrium computation in discrete Colonel Blotto games. For two-player general-sum Colonel Blotto with monotonic piecewise-constant battlefield payoffs, we show that computing an inverse-polynomial approximate Nash equilibrium is PPAD-hard, even with only two battlefields and a constant number of pieces per battlefield, thereby resolving an open question of [KPF+25]. Allowing more battlefields, the hardness persists when every battlefield payoff is $2$-piecewise constant with respect to either player's allocation. A general PPAD-membership theorem for multiplayer Blotto with arbitrary local reward functions then implies PPAD-completeness for both hardness results. Motivated by fixed-rank bimatrix games, we then identify a tractable frontier within two-player general-sum Colonel Blotto. If the social payoff has rank-$r$ structure, then, for every fixed $r$, an $\varepsilon$-Nash equilibrium can be computed in time polynomial in $B_1,B_2,k$, and $1/\varepsilon$. Thus constant-rank two-player Colonel Blotto remains tractable despite its exponentially large pure strategy spaces. Finally, we study multiplayer winner-takes-all Colonel Blotto with player-specific battlefield values and uncover a sharp tie-breaking frontier. If every highest bidder receives her full battlefield value, an exact pure Nash equilibrium can be computed in polynomial time for arbitrary binary-encoded budgets. In contrast, under ordinary equal splitting among highest bidders, we prove that computing an inverse-polynomial-accuracy Nash equilibrium is PPAD-hard even with only five players. This resolves an open question posed in concurrent work by Bichler and Ghosh [BG26], who established PPAD-hardness in the same player-specific equal-splitting setting when the number of players grows with the instance and asked whether hardness persists for a constant number of players.Authors: Boyu Liu, Zihe Wang
We prove that finding a fixed point of a monotone map on the nine-dimensional grid $[N]^9$ requires $Ω((\log N)^3)$ deterministic queries, even when the fixed point is unique and each query returns the entire function value. The proof gives a construction that raises the dimension from $d$ to $4d+1$, preserves uniqueness, and adds a logarithmic factor to the lower bound. Iteration gives $Ω((\log N)^{r+2})$ queries in dimension $(7\cdot4^r-1)/3$, for every fixed nonnegative integer $r$, with an implicit constant that may depend on $r$. Consequently, no finite logarithmic exponent bounds the query complexity in all fixed dimensions.Authors: Ryan Anselm, Michelle Ding, Dar Gilboa, Sabee Grewal
We establish optimal quantum-classical separations in communication complexity for search problems. We introduce a total search problem called Pelagic Fourier Fishing and show that it admits an $n$-qubit quantum one-way protocol, whereas every randomized two-way protocol requires $Ω(2^n)$ bits of communication. We then introduce a variant of this problem whose solutions can be verified in polynomial time. This variant also admits an $n$-qubit quantum one-way protocol, while every randomized one-way protocol requires $Ω(2^n)$ bits of communication. We also construct a family of efficiently verifiable total search problems achieving an $n$ versus $Ω_d(n^d)$ separation between quantum one-way and randomized one-way communication for every fixed $d \ge 2$. In the quantum protocol, Alice prepares her message using a single unitary from the $d$th level of the Clifford hierarchy, and Bob performs a Clifford measurement. This separation is asymptotically optimal under this restriction on Alice's message. For $d = 2$, Alice's message is a stabilizer state and Bob's measurement is Clifford, so the protocol uses no magic, yet achieves an optimal quadratic quantum advantage. Finally, we discuss how these separations can be adapted to near-term quantum advantage experiments in which the demonstrated advantage is both unconditional and efficiently verifiable.Authors: Siu On Chan, Jeff Xu
We give a classical polynomial-time algorithm that strongly refutes random quantum $3$-SAT at sufficiently large constant constraint density, thereby disproving the quantum analogue of Feige's random $3$-SAT hypothesis. This stands in sharp contrast to classical random $3$-SAT, for which polynomial-time strong refutation is known only at constraint density $Δ\gtrsim n^{1/2}$. Although quantum $3$-SAT shares the pairwise-independence barrier of its classical counterpart, our SDP-based refutation overcomes this barrier by exploiting the noncommutativity of quantum constraints.Authors: Chenghua Liu, Boning Meng
We prove a complete complexity dichotomy for planar graph homomorphism counting with any fixed symmetric nonnegative matrix of arbitrary finite order, giving an explicit criterion for tractability. We also characterize exactly which fixed positive vertex weights preserve tractability, with both classifications extending from algebraic weights to fixed real weights in a prescribed exact representation. Our proof hinges on an entropy-based continuation argument: maximal logarithmic support identifies distance kernels as maximum-entropy completions, extending their positive definiteness throughout the parameter interval. This enables distance geometry to recover hidden product coordinates even when planar gadgets cannot distinguish colors; counting-hardness arguments then force the factors to be zero-field Boolean Ising interactions. The classification also yields complete tractability criteria for clock models, coupled Ising systems, and planar contractions of stoquastic imaginary-time kernels. All results have been formally verified in Lean 4.Authors: Yannis Tzitzikas
Is the classical question $P \stackrel{?}{=} NP$ the right one for understanding the complexity of real-world computation? Traditional worst-case analysis characterizes complexity solely as a function of input size $n$. Yet tasks whose cost is exponential in general often run in polynomial or even linear time once specific structural constraints or partial inputs are known. For instance, the Partition Problem is solvable in linear time, a constant-time core step following linear-time verification, when its inputs satisfy a simple structural property, although no polynomial-time algorithm is known for it in general; Integer Factorization, by contrast, resists structural knowledge: no checkable property of the input is known to improve on the sub-exponential number-field-sieve bound. Classical worst-case analysis cannot explain this difference, because it collapses a whole spectrum of difficulty into a single pessimistic bound. This paper formally develops a comprehensive parametric and uncertainty-aware framework for computational complexity. We introduce the notion of \emph{Sensitivity to Uncertainty} (SU) and formalize the cost variation $Δ_P(n, K)$ under a given input property $K$; we define the uncertainty-vanishing metric $Ψ(n, K)$ and prove a fundamental \emph{Uncertainty Reduction Theorem} bridging cost variation and input uncertainty; and we introduce the parametric classes $P_U[K]$ and $NP_U[K]$ as a more practical, instance-level foundation, focused on certifiable structure, rather than distributional typicality, that resolves the gap between theoretical complexity and real-world tractability. We further show how the same uncertainty analysis supports practice: it enables deterministic SLA via Design-by-Contract informs tool-use and reasoning splits in agentic AI, and provides an explanation of when quantum computers achieve exponential speedup.Authors: Gabriel Istrate
Rossman, Servedio, and Tan proved that the polynomial hierarchy is infinite relative to a random oracle. This paper strengthens this celebrated result by considering \emph{strong separations}, witnessed by immune languages. The main result of the paper shows that with respect to a random oracle the levels of the polynomial hierarchy separate with immunity. Specifically, with probability one over a random oracle $A$, for every $k\geq 1$ there is a language in $Σ_{k}^{P,A}$ that is immune to $Π_{k}^{P,A}$, and, symmetrically, a language in $Π_{k}^{P,A}$ that is immune to $Σ_{k}^{P,A}$. We thus extend classical results due to Bennett and Gill and Vereshchagin. We accomplish this by developing a "rare-or-wrong" approach to strong separations. We highlight the flexibility of the approach by strengthening other separations with respect to a random oracle from the complexity-theoretic literature.Authors: Dax Enshan Koh, Triscia Mundo, Iosif Sakos, Antonios Varvitsiotis
Variational quantum algorithms (VQAs) generally rely on classical optimization to train parameterized quantum circuits. This training seeks to minimize an objective function, and its efficiency is central to the practical success of these algorithms. However, globally minimizing such training objectives over the circuit parameters is known to be $\mathsf{NP}$-hard, limiting the prospect of general guarantees for efficient training. In this Letter, we prove that even the weaker task of finding a local minimum of such VQA training objectives is strongly $\mathsf{NP}$-hard, including when the objective admits efficient classical evaluation. Moreover, we show that this hardness persists even for the task of finding a parameter vector within $\ell_p$-distance strictly less than $π/2$ of some local minimizer, for every $p\geq 1$. Our central technical result is that approximating a local minimizer of a Hermitian trigonometric polynomial is strongly $\mathsf{NP}$-hard. By explicitly constructing quantum circuits whose training objectives reproduce these hard instances, we obtain a polynomial-time reduction to VQA training. Our results establish a fundamental computational barrier to variational quantum training: even reaching the vicinity of a local minimum remains hard in the worst case.Authors: Mitali Bafna, Quynh T. Nguyen, Tina Zhang
The quantum PCP conjecture is one of the major open problems in quantum complexity theory. It has resisted attack in part because many primitives used in the proof of the classical PCP theorem, such as locality-preserving gap amplification and alphabet reduction, have no obvious quantum analogues due to quantum no-cloning. Locality-preserving gap amplification is a procedure that takes as input a local Hamiltonian problem instance and produces a new instance with a larger promise gap, without increasing the locality of the Hamiltonian, and instead moderately increasing its local qudit dimension. Obtaining this kind of control over the locality during gap amplification is critical to the success of many known strategies for proving the classical PCP theorem. In this work, we put forth the first known viable template for quantum locality-preserving gap amplification, and we prove that our procedure amplifies the combinatorial gap of local Hamiltonians. Our work introduces a new framework for reasoning about quantum gap amplification in terms of fault-tolerant computation, and illuminates a route toward importing one of the central ingredients in classical PCPs into the quantum setting. In particular, we build upon ideas from the recent classical PCP of Bafna--Minzer--Vyas based on high-dimensional expanders, and the circuit-to-Hamiltonian construction of Anshu--Breuckmann--Nguyen, in addition to several recent advances in quantum coding theory.Authors: Jin-Yi Cai, Jin Soo Ihm
We prove a complexity dichotomy theorem for $\mathrm{Holant}^*$ problems over complex-valued symmetric constraint functions $\mathcal{F}$ on domain size $3$. We give a decidable tractability criterion and prove that if $\mathcal{F}$ satisfies the criterion, then $\mathrm{Holant}^*(\mathcal{F})$ is solvable in polynomial time, and otherwise it is #P-hard. This is the first Holant dichotomy for a set of complex-valued constraint functions on higher domains. We show that complex-valued constraint functions have a rich structure not observed in real-valued constraint functions. This structure is only revealed when we analyze them in a bipartite Holant setting with a non-standard bilinear form and provides the backbone to the proof of the dichotomy. We use group actions and the spin representation of $\mathrm{SL}(2, \mathbb{C})$ in $\mathrm{SO}(3, \mathbb{C})$ and the generalized orthogonal group to facilitate this analysis. We also introduce $\textit{frames}$ and $\textit{shells}$. Frames linearize the group action and provide a unified framework for proving #P-hardness when used in conjunction with shells. Furthermore, we characterize the lower dimensional constraint functions by $\textit{annihilators}$, which makes it possible to analyze $\textit{essentially Boolean domain}$ functions in domain size $3$.Authors: Yoshiki Nakamura, Yuya Uezato
We study the fine-grained complexity of evaluating Boolean bounded-variable first-order queries over sparse relational structures. For every fixed $k \ge 2$, every relational signature, and every fragment between $k$-variable primitive positive ($\mathrm{PP}^{k}$) and first-order ($\mathrm{FO}^{k}$) logic, we prove, assuming the Sparse MAX-$3$-SAT hypothesis, a dichotomy theorem for evaluation in $O(m^{k-\varepsilon})$ time, where $m$ is the number of tuples in the input structure. The only tractable cases fall into three families: (1) three-variable fragments, (2) two-variable fragments, and (3) fragments over unary signatures. On the hard side, for every fixed $k \ge 4$ and every $\varepsilon > 0$, there is a fixed sentence $\varphi_\varepsilon$ in $\mathrm{PP}^{k}$ over a single binary relation symbol, depending on $\varepsilon$ but not on the input structure, whose evaluation cannot be performed in $O(m^{k-\varepsilon})$ time. For the tractable cases, we show that the evaluation problem can be solved in $2^{O(|\varphi|)} \cdot m^{k-\varepsilon}$ time for some $\varepsilon > 0$. Moreover, every tractable fragment reduces, with a $2^{O(|\varphi|)}$ blowup in formula size under DAG representations, to one of the following query languages: (1) Tarski's calculus of relations, (2) a new Boolean modal logic for sparse model checking, and (3) one-variable counting logic.Authors: Sanjay Jain, Frank Stephan, Haoyun Tang
We present a complete complexity classification and fine-grained analysis for the Strictly Unfriendly $k$-Partition problem ($\text{SU}k\text{P}$), which asks whether the vertices of a graph can be partitioned into $k$ classes such that every vertex has strictly more neighbors in each of the other $k-1$ classes than in its own. We first establish a sharp tractability-intractability threshold with respect to the maximum degree $Δ$: for $k \in \{2, 3\}$, $\text{SU}k\text{P}$ is solvable in polynomial time when $Δ\le 2$, but becomes $\mathbf{NP}$-hard and ETH-hard immediately on subcubic graphs ($Δ= 3$), resolving the degree limitations in prior work and establishing subcubic graphs as the precise frontier of intractability. Furthermore, under the Exponential Time Hypothesis (ETH), we establish the first fine-grained lower bounds via direct reductions from $(3,3)$-SAT. On general graphs, we establish a uniform lower bound across all partition parameters $k \ge 2$, revealing a striking complexity convergence where the core exponential complexity remains invariant despite technical divergences in gadget constructions. On subcubic graphs, we formally quantify the "cost of sparsity," deriving explicit lower bound constants to demonstrate how enforced structural degree restrictions degrade reduction efficiency.Authors: Jeremy Ahrens Huang
Despite the importance of the non-uniform Polynomial-Time Hierarchy (PH/poly) in classical complexity understanding the collapse conditions of the Polynomial-Time Hierarchy (PH), a quantum equivalent of PH/poly has yet to be studied in the literature. We introduce the non-uniform computational Quantum Polynomial-Time Hierarchy (QCPH/mpoly), the quantum equivalent of PH/poly, and show that it collapses if and only if QCPH, the quantum equivalent of PH introduced by Gharibian et al. (comput. complex. 2022), also collapses. We also show that QCPH collapses if coQCMA is contained in QCMA/mpoly. These results are analogous to those of Yap (TCS 1983) commonly used to invoke the collapse of PH in classical complexity. QCPH/mpoly is analogous to QCPH with non-uniform quantum verifier circuits.Authors: Dimitrios Myrisiotis
Exactly computing the maximum function is a standard test case for studying depth in ReLU networks. Two hidden layers are known to suffice for up to twelve inputs through computer-assisted constructions. For six real inputs, we give an explicit hexagon identity whose local structure yields a self-contained analytical proof of this depth bound. The identity was found by computer-assisted search; we prove it through explicit cancellations that can be checked entirely by hand, without executing a verification program. The identity also yields an explicit network with hidden widths $17$ and $41$, zero biases, and rational weights.Authors: Ezekiel Cochran, Atul Mantri
We prove optimal query bounds for recovering a single qubit from black-hole radiation in the Haar random oracle model, when the remaining black hole contains at most one sixteenth of the system's qubits. Recovery with any constant Haar-averaged advantage over trivial decoding requires queries proportional to the Hilbert-space dimension of the remaining black hole. The lower bound is unconditional for decoders chosen independently of the sampled unitary, allows arbitrary computation between queries, and access to $U, U^\dagger, U^*, U^\mathsf T$ along with the controlled variants. An existing decoder using only forward and inverse queries attains a matching bound. The proof uses a path recording oracle to compare real and maximally mixed states. As applications, we obtain an efficiently preparable, statistically far, computationally indistinguishable (EFI) pair and quantum commitments relative to a public Haar oracle, as well as prove a tight linear rank lower bound for Uhlmann transformation on a fixed-target family.Authors: Klaus Jansen, Dirk Nowotka, Lis Pirotton, Corinna Wambsganz, Max Wiedenhöft
Patterns are words with terminals and variables. The language of a pattern is the set of words obtained by uniformly substituting all variables with words that contain only terminals. In their original definition, patterns only allow for multiple distinct occurrences of some variables to be related by the equality relation, represented by using the same variable multiple times. In an extended notion, called relational patterns and relational pattern languages, variables may be related by arbitrary other relations, achieved by using regular patterns and relating individual variables independently from the patterns structure separately. We extend the ongoing investigation of the main decision problems for patterns (namely, the equivalence problem, the inclusion problem, and the membership problem) to relational pattern languages under a wide range of relevant individual relations, providing a comprehensive foundation in all three research directions.Authors: Animesh Maiti, Prakhar Shukla, Subhash Bhagat
Given a set of point robots $\mathcal{R}$ in the Euclidean plane and a target circle $\mathbf C$ enclosing all robot positions, the \textsc{Min-Max Uniform Circle Formation (MMUCF)} problem requires the robots to move to distinct positions on $\mathbf C$ such that the final configuration forms a regular $n$-gon while minimizing the maximum distance traveled by any robot. Uniform circle formation is a fundamental coordination task in swarm robotics with applications in perimeter monitoring, surveillance, boundary coverage, and pattern formation. The literature does not address the optimization of the maximum individual displacement during the formation process. In this work, we study the min--max versions of the circle formation and uniform circle formation problems, where the goal is to minimize the maximum distance traveled by any robot. We consider these problems under the $\mathcal{ASYNC}$ model, where robots are autonomous, anonymous, identical, homogeneous, oblivious, and silent, and operate under the \textit{Look--Compute--Move} model with non-rigid motion. We first give necessary conditions for a deterministic solution and then present deterministic, distributed, and collision-free algorithms that form a circle and a uniform circle in finite time while minimizing the maximum movement. The algorithms ensure that robots reach distinct positions on the circle and, in the uniform case, equally spaced positions on $\mathbf C$ under the considered model.Authors: Prakhar Shukla, Animesh Maiti, Shivam Kumar, Subhash Bhagat
We investigate the mutual visibility problem for a swarm of $n\ge3$ autonomous mobile robots under the budget-constrained mobility fault model. The robots are opaque, so if three robots are collinear, the middle robot obstructs the visibility between the other two. Each robot is assigned a finite movement budget, reflecting its limited energy, that bounds the total distance it may traverse during the execution. Moreover, an arbitrary number of robots may become permanently immobile due to mobility faults. The objective is to design a distributed algorithm that enables the non-faulty robots to coordinate their movements so that, within a finite time, every non-faulty robot attains unobstructed visibility of all robots in the system, including the faulty ones, while respecting the prescribed movement budget. We consider luminous robots operating under the $\mathsf{SSYNC}$ model with non-rigid movements, without any agreement on their local coordinate systems, and equipped only with a {\it common fixed reference point}. We present a deterministic distributed algorithm that solves the problem despite an arbitrary number of mobility faults. The algorithm guarantees mutual visibility for the non-faulty robots, respects the movement budget of every robot, provides collision-free movements for the robots, and uses only 12 light colors.Authors: Aoran Zhang, César A. Uribe
The Gromov-Wasserstein (GW) problem compares structured distributions without requiring a shared feature space or known correspondences, but its nonconvex objective and coupled marginal constraints make computation challenging. Bregman alternating projected gradient (BAPG) uses inexpensive alternating row and column updates, yet its fixed-penalty relaxation leaves a persistent feasibility gap. We propose Adaptive KL-BAPG (A-KL-BAPG), which combines a finite fixed-penalty burn-in with a guarded increasing-penalty phase. At each tail iteration, the method reuses BAPG's alternating updates and backtracks a delayed-power step until a Sinkhorn-inspired projective-diameter safeguard is satisfied. We prove finite termination of the backtracking at each iteration and show that the feasibility gap vanishes asymptotically. We further establish a best-iterate $O(1/\log N)$ bound for the weighted squared corrected residual and, under a support regularity condition, the existence of a stationary accumulation point for the original GW problem. This distinguishes A-KL-BAPG from fixed-penalty BAPG, whose stationarity guarantees are given for the relaxed problem. Experiments show that A-KL-BAPG achieves a favorable balance of accuracy, objective value, feasibility, and stationarity relative to BAPG variants, projection-based methods, and task-specific baselines. For synthetic and real graph alignment problems, it closely matches the accuracy and objective value of fixed-penalty KL-BAPG while reducing the marginal feasibility gap by 62-99% and the projected stationarity residual by 28-98%. Heterogeneous domain adaptation experiments show a similar pattern: A-KL-BAPG maintains comparable target accuracy and objective values while achieving better feasibility and stationarity than fixed-penalty KL-BAPG.Authors: Animesh Maiti, Prakhar Shukla, Abhinav Chakraborty, Subhash Bhagat
We study the \textit{optimal gathering} problem over a finite set of designated \textit{meeting nodes} for \textit{asynchronous, anonymous,} and \textit{oblivious} mobile robots on an infinite grid under crash faults. The robots have global visibility and strong multiplicity detection, but share neither a coordinate system nor chirality. The objective is to gather all non-faulty robots at a \textsc{Weber Meeting Node}, minimizing the total Manhattan distance from their initial positions. Up to $n-2$ robots may crash permanently, and such crashes are indistinguishable from arbitrary delays. Existing approaches often rely on a designated robot to break symmetry, whose crash may block the remaining robots indefinitely. Instead, our approach enables every robot to independently select the same target from its snapshot, while target-dependent restricted shortest paths preserve the target as a \textsc{Weber Meeting Node}. We prove that, under strong multiplicity detection, optimal gathering is impossible from certain fully symmetric configurations. For all remaining configurations, our algorithm \textsc{CrashTolerantWeberGathering()} selects a unique common target, preserves its optimality throughout the execution, and allows non-faulty robots to progress without waiting for crashed robots, thereby guaranteeing gathering in finite time.Authors: Josh Alman, Virginia Vassilevska Williams
We give the first polynomial improvements over the textbook algorithms for $3$SUM and All-Pairs Shortest Paths (APSP): we show how to deterministically solve $3$SUM on $n$ integers of polynomial size in $O(n^{1.9992})$ time and APSP on directed $n$-vertex graphs with polynomially bounded integer weights in $O(n^{2.9995})$ time. This refutes the $3$SUM and APSP hypotheses. Using known reductions, we also refute the real-valued versions of the $3$SUM and APSP hypotheses, the Exact Triangle hypothesis, the Zero-Weight $k$-Clique hypotheses, and the three rectangular hinted Online Matrix--Vector conjectures of van den Brand, Nanongkai, and Saranurak, and we give polynomial speedups for a variety of other problems. All of these results follow from a single new algorithm for thin matrix products. Let $X$ be an $N\times D$ integer matrix and $Y$ a $D\times N$ integer matrix with $D\le N^{1/18}$, and let $W$ be any set of at most $N^2/\sqrt D$ positions. We compute the entries $(XY)[I,J]$, $(I,J)\in W$, in $O(N^2/D^{0.063})$ operations, which is polynomially less than the time needed to write down $XY$ or to compute $N^2/\sqrt D$ inner products one by one. We design this algorithm by modifying a variant of Coppersmith's rectangular matrix multiplication algorithm, built from a ten-multiplication identity of Schönhage, to perform only the operations needed for the entries in $W$, and show that few operations are needed. Interpreted as a graph algorithm, this solves the All-Edges Sparse Triangle problem in truly subquadratic time on sparse lopsided tripartite graphs where two parts have $n$ vertices but one part has $n^{\varepsilon}$ vertices for $\varepsilon<0.12$. By known reductions, Exact Triangle, and hence $3$SUM and APSP, reduce to this problem. We also give a data structure version that answers queries for single entries of $XY$, not known in advance.Authors: Xiaoyu Chen, Kuikui Liu
We design the first polynomial-time algorithms for approximately counting and almost uniformly sampling common bases of two matroids given by their independence oracles. Moreover, our algorithms generalize far beyond this to Hadamard products of two probability measures on the Boolean cube satisfying a simple nonnegative curvature condition. These algorithmic primitives have myriad applications in statistical physics, polyhedral combinatorics, the study of quantum many-body systems, and beyond. Our approach has two key ingredients. $\bullet$ We relax the intersection by imposing an overlap penalty on the product measure formed by the two input measures. We prove, via an integrated Bochner-type method, that this "$\textit{soft intersection}$" satisfies a Poincare inequality uniformly over all external fields. $\bullet$ We solve a dual maximum entropy convex program to compute external fields under which the hard constraint is satisfied with high probability under the soft intersection measure. We bound this success probability directly using the uniform Poincare inequality and smallness of the gradient norm. $\textbf{AI Disclosure}$ GPT-5.6 Sol Ultra and GPT-6 Astra Ultra were heavily used to develop the ideas in this paper. A more complete discussion is included in the acknowledgments.Authors: Thomas Depian, Robert Ganian, Jakob Greilhuber, Marlene Gründel, Simon Wietheger
A classical well-quasi-ordering result guarantees the existence of non-uniform linear-time algorithms for all problems in Strict NP on relational structures of bounded treedepth; however, this provides neither a procedure for constructing these algorithms nor computable bounds on their parameter dependence. We turn this existential result into a uniform algorithmic metatheorem. Given a Strict NP sentence $\varphi$ and a relational structure $\mathcal{R}$, our algorithm decides whether $\mathcal{R}\models\varphi$ in time $f(|\varphi|, td(\mathcal{R})) \cdot |\mathcal{R}|$ for a computable function $f$, where the treedepth of $\mathcal{R}$ is measured on the Gaifman graph. The algorithm also constructs witness relations, with the polynomial exponent depending on their arity, and provides a unified framework for settling hereditary graph problems parameterized by treedepth. We also present several applications - among others, our result resolves open questions on the fixed-parameter tractability of computing the stack number, queue number, track number and twin-width parameterized by treedepth.Authors: Simon Apers, Roman Edenhofer, Benjamin Mathieu-Bloise, Partha Mukhopadhyay
The concept of subspace designs was introduced by Guruswami and Xing (STOC'13), and explicit constructions were given by Guruswami and Kopparty (FOCS'13). These are families of subspaces that have small intersection with any given subspace of a fixed dimension. We introduce \emph{robust subspace designs}. Informally, these are a quantitative extension in which we demand that not too many subspaces of the family contain directions that lie close to any given subspace of a fixed dimension. We give a probabilistic construction of such a robust subspace design of polynomial size, as well as a non-trivial explicit construction of superpolynomial size. Our main application of this new concept is a quantum space-bounded variant of the Valiant-Vazirani theorem (Theor.Comput.Sci.'86), which shows that restricting $\mathsf{NP}$-complete problems to instances with at most one accepting witness preserves hardness under randomized reductions. For quantum witnesses, the analogous quantity is the dimension of an accepting witness subspace. We use our probabilistic construction of robust subspace designs to isolate a unique witness for space-bounded quantum Merlin-Arthur protocols with perfect completeness and an acceptance gap outside their perfectly accepting subspace. As further applications, we give a randomized reduction of well-conditioned nullity testing to space-bounded quantum Merlin-Arthur protocols with perfect completeness. Using a similar idea, we find that ordinary subspace designs allow us to recover the classical $\mathsf{C_= L}$ containment of Allender, Beals, and Ogihara (STOC'96) for general nullity testing through a simpler proof.Authors: Jonas Friemel, Tilo Hoitz, Phillip Keldenich, Arne Schmidt
We consider a matching problem in which the cost of each edge is a vector with $k$ components. The cost of a matching is the sum of the bottlenecks over all components, and we ask whether there is a perfect matching of cost at most some value $Z$. This type of matching has applications in heavily synchronized job-shop scheduling problems and in reconfiguration problems, where movement is restricted to a single direction per step. In this paper, we analyze the problem from a parameterized complexity perspective and provide various results including FPT-membership for parameters $k$ and $Z$ combined, as well as W[P]-membership and W[SAT]-hardness for each of the two parameters individually. The reduction also implies para-NP-hardness parameterized by either maximum degree or treewidth. We further show hardness of approximation within a super-logarithmic factor for the optimization variant and provide a $k/d$-approximation algorithm for any constant $d \leq k$ as well as an efficient approximation scheme parameterized by $k$. With parameter $Z$, we show that no FPT-time $F(Z)$-approximation algorithm is possible for any computable function $F$, unless W[1] = FPT.Authors: Pascal J. Gollin, Tesshu Hanaka, Ekkehard Köhler, Martin Milanič, Yushi Uno
A clique transversal of a graph is a set of vertices intersecting every maximal clique. We prove that deciding whether a graph has an inclusion-wise minimal clique transversal of size at least $k$ is W[1]-hard when parameterized by $k$.Authors: Yonggang Jiang, Xiaoming Sun, Penghui Yao, Zekun Ye, Jialin Zhang, Zhijie Zhang
We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint $k$ on an $n$-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected $(1/2-\varepsilon)$-approximation using only $O_\varepsilon(\log n)$ queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above $1/4$ requires $Ω(n/\log n)$ queries (Li, Feldman, Kazemi, and Karbasi, 2022), establishing an exponential separation in query complexity. For cardinality-constrained maximization, we give a bounded-error quantum algorithm that achieves a $(1-1/e-\varepsilon)$-approximation using $\widetilde O_\varepsilon(\min\{\sqrt n,n/k\})$ queries. When $k=o(n)$, our algorithm achieves at least a quadratic speedup up to logarithmic factors over classical randomized algorithms (Mirzasoleiman, Badanidiyuru, Karbasi, Vondrák, and Krause, 2015; Peng and Rubinstein, 2025). Moreover, when $k=cn$ for any fixed rational $c<1-1/e-\varepsilon$, the query complexity reduces to $O_{\varepsilon,c}(\log n)$, yielding an exponential separation from the classical $Ω(n/\log n)$ lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of $\exp(Ω(\varepsilon^2n))$ queries for achieving a ratio beyond $1/2+\varepsilon$ without constraints, and $\exp(Ω(\varepsilon^2k))$ queries for exceeding $1-1/e+\varepsilon$ when $k/n\le\varepsilon$. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.Authors: Barak Gorodissky, Tal Wagner
A kernel $k(x,y)$ is LSHable if there exists a locality sensitive hashing scheme $H$ such that $k(x,y)=\Pr_{h\sim H}[h(x)=h(y)]$ for all $x,y$. This notion plays a key role in efficient kernel methods in high dimensions. In this work, we show that the $p$-exponential kernel $k(x,y)=\exp(-\lVert x-y \rVert_p)$ is LSHable in bounded regions for all $1Authors: Ruizhe Zhang
Estimating the volume of a high-dimensional convex body is a fundamental problem in theoretical computer science. Given a quantum membership oracle for a convex body $K\subset\mathbb{R}^d$, we show that estimating $\mathrm{vol}(K)$ to relative error $\varepsilon$ takes $\widetilde O(d^{5/2}+d^{3/2}/\varepsilon)$ queries. This improves the previous quantum upper bound $\widetilde O(d^3+d^{9/4}/\varepsilon)$ of Chakrabarti et al. (ACM TQC 2023) and Cornelissen--Hamoudi (SODA 2023), and achieves a larger quantum speedup over the currently best classical upper bound $\widetilde O(d^{7/2}+d^3/\varepsilon^2)$ of Jia et al. (JACM 2026). Our quantum algorithm combines two new ingredients: an input-dependent effective spectral-gap analysis of quantum walks based on uniform classical warm-start mixing bounds, and a single quantum estimator for products of normalizer ratios in simulated annealing based on classical bridge sampling. We also prove an $Ω(d)$ quantum query lower bound for constant relative error, improving the previous $Ω(\sqrt d)$ lower bound.Authors: Mohammad Ansari, Sina Azizeddin, AmirMohammad Bandari, Pouria Mahmoudkhan, Hamid Zarabi-Zadeh
Diversity maximization is a fundamental optimization problem with applications in machine learning, data summarization, information retrieval, and recommendation systems. In many such applications, the data are partitioned into groups, and the selected subset must satisfy prescribed group quotas. We study Fair Diversity Maximization: given a set of points in a metric space partitioned into $m$ groups, the goal is to select exactly $k_i$ points from each group $i$ while maximizing the minimum pairwise distance among the selected points. The best previously known approximation guarantee is $m+1$, which grows linearly with the number of groups. We show that this dependence on $m$ is not fundamental. We present a new local-search framework that yields a $4$-approximation for any constant number of groups, with no restrictions on the metric space or on the size of the selected set. To the best of our knowledge, this is the first constant-factor approximation whose guarantee is independent of the number of groups in this general setting. Our framework maintains all group quotas exactly while progressively eliminating violations of the diversity objective. We further develop a specialized algorithm for two groups that achieves a $2$-approximation, improving the previous best factor of $3$. This factor is optimal: unless $\mathrm{P}=\mathrm{NP}$, no polynomial-time algorithm can achieve an approximation factor strictly better than $2$, even for the unconstrained case.Authors: Sriram Bharadwaj, Di Luo, Leo Zhou
We study a Continuous-Variable Quantum Approximate Optimization Algorithm (CV-QAOA) for high-dimensional continuous optimization. Our formulation extends an earlier CV-QAOA proposal with a variationally optimized initial state and recovers the convergence guarantees of Quantum Hamiltonian Descent (QHD) in the high-depth limit. We prove rigorous performance guarantees of CV-QAOA on several families of cost functions. First, we show $d$-step CV-QAOA minimizes any $d$-dimensional strictly convex quadratic function with $2d$ quantum queries to the cost function. We then analyze a family of nonconvex "Rotated Double Well" (RDW) functions with $2^d$ local minima introduced by arXiv:2311.00811. While prior work showed QHD reaches its global minimum with $\tilde O(d^3)$ queries, we prove that 1-step CV-QAOA solves RDW with just two quantum queries. Although general-purpose classical solvers need superpolynomial time for RDW and structure-awareness can reduce the cost to polynomial time, we show that the 1-step CV-QAOA protocol can be efficiently dequantized, and that a gradient-aligned line search succeeds with $O(d)$ queries, nearly matching the information-theoretic $Ω(d/\log d)$ query lower bound. To move beyond the dequantizable regime, we introduce a ``Rotated Square Well'' (RSW) problem, whose globally flat landscape suppresses useful local gradient information. For this family, we show that an adiabatic evolution simulated by CV-QAOA can reach the global minimum using $d^{o(1)}$ queries. On the other hand, any classical algorithm that learn the hidden rotation in RSW provably requires $Ω(d^2/\log d)$ queries, a bound we nearly match with an explicit $Θ(d^2\log d)$-query classical algorithm.Numerical simulations on deflected corrugated spring and Easom functions illustrate the promising performance of CV-QAOA on more general problems.Authors: Alvan Arulandu, Sitan Chen, Ziyun Chen, Jerry Li, Eric Ma
We study agnostic tomography of pure bosonic Gaussian states: given copies of an arbitrary $n$-mode bosonic state $ρ$, the goal is to output a pure Gaussian state whose infidelity with $ρ$ is at most $\mathrm{opt} + ε$, where $\mathrm{opt}$ is the minimum infidelity achievable by any pure Gaussian state. We give efficient protocols achieving this in both the high and low fidelity regimes. When $\mathrm{opt}$ is below some universal constant, our protocol has runtime and copy complexity which is strongly polynomial in $n, 1/ε$ and $\log \log E$, where $E$ is the energy of the closest pure Gaussian state. For arbitrary $\mathrm{opt}$, our protocol uses $(n+1)^{\mathrm{poly}(1/ε)} \mathrm{poly}\left(1+\log\log(E)\right)$ copies and runtime. As a corollary, we obtain the first truly tolerant Gaussianity testing protocol for distinguishing whether $\mathrm{opt} > c + ε$ or $\mathrm{opt} < c - ε$, for any threshold $c\in(0,1)$. We also prove $\mathrm{poly}(n,1/ε)$ runtime is impossible, unless $\mathrm{NP}\subseteq\mathrm{BQP}$. Our protocols follow a shared paradigm: first, we iteratively use general Gaussian measurements combined with techniques from classical robust statistics to obtain a good warm start estimate, then we leverage non-Gaussian measurements to refine this warm start using convex and non-convex optimization methods. Interestingly, we prove that non-Gaussian measurements are necessary to match the strong agnostic guarantees we obtain, and in fact these guarantees are provably superior to what is possible for robustly estimating classical Gaussians.Authors: Dutch Hansen, Jerry Li
We consider the problem of quantum 1-PCA: given copies of an unknown $n$-qubit mixed state, recover a classical description of its leading eigenvector. Our goal is to do so using non-adaptive and single-qubit measurements. For an $n$-qubit state with top eigenvalue $λ$ and spectral gap at least $Δ> 0$, we give an algorithm that recovers the leading eigenvector to fidelity at least $1 - \varepsilon$ with high probability using $\tilde{O}\left( {2^n \cdot η^2} / {Δ^3 \varepsilon^3}\right)$ copies and $\tilde{O}((2^n/Δ\varepsilon) \cdot \operatorname{poly}(η/Δ\varepsilon))$ time, where $η= \max (1 - λ, \varepsilon)$. All of our measurements are non-adaptively chosen, and performed in single-qubit Pauli bases. When the spectral gap is constant and the desired accuracy is comparable to the noise level, i.e. $\varepsilon = Ω(η)$, our runtime and copy complexity become $\tilde{O} (2^n / \varepsilon)$. This generalizes the guarantees of Grewal et al. [arXiv:2601.04444], who achieved similar rates, but under the assumption $η= 0$, i.e., that the state was pure. Our results show that the same rates hold in the presence of state misspecification, up to polylogarithmic factors. From a technical perspective, our algorithm works by recursively constructing low-dimensional subspaces that approximately preserve the target eigenvector. To achieve nearly linear runtime dependence on the dimension of the Hilbert space, we develop a novel structured Pauli sampling scheme that enables fast batched computation of exponentially many projected Pauli matrices.Authors: Alexander Schmidhuber, Alexander Zlokapa
The Sachdev-Ye-Kitaev model is a strongly interacting fermionic system that has been well-studied in condensed matter and high energy physics. It is highly quantum: Gaussian states are far from the thermal state (Hastings and O'Donnell, STOC'22) and representing the thermal state requires large polynomial-size quantum circuits (Anschuetz et al., QIP'25). Very recently, it was nonetheless proven that classical algorithms can estimate local thermal expectations at sufficiently high temperature in quasipolynomial time (Zlokapa, FOCS'26). We show that classical algorithms can in fact estimate local observables at all constant temperatures in polynomial time. Our techniques also extend straightforwardly to classical systems: we resolve an open question about computing thermal expectations of a classical spin glass up to its phase transition (Bencs et al., STOC'26). Our proof develops a fully rigorous quantum cavity method. Due to the success of the classical cavity method in optimization, sampling, inference and learning, we expect the quantum cavity method to find further applications of independent interest. As an example, we give a quantum algorithm that learns SYK Hamiltonians from the Gibbs state at any constant temperature with polynomial time and sample complexity.Authors: Junzhao Yang
For $κ>1$, a directed graph is $κ$-conditioned if it is $κ$-mixing and its stationary distribution is approximated by the uniform distribution within a factor of $κ$. We present a deterministic algorithm that approximates the stationary distribution of a $κ$-conditioned graph to inverse polynomial relative error in $O((\log n + \log^2 κ) \log \log n)$ space. In the regime $κ= \exp(Θ(\log^αn))$ for any $α\in (0, 2/3)$, our result improves the best-known $O(\log n \sqrt{\log κ} / \sqrt{\log \log n})$ space bound for approximating $κ$-step random walks in general directed graphs by [Hoza, RANDOM 2021]. We release this preliminary version due to recent rumors of LLM-based progress on related problems and uncertainty about when those results may appear. Further implementation details will be provided in a subsequent version.Authors: Nadezhda Voronova
How can random order change the role of quantum memory in streaming? Later classical input can restore the usefulness of a quantum state consumed by earlier queries. We call this replenishment. We construct an artificial problem based on Hidden Matching, with repeated coordinate data and online matching requests. It admits a one-pass quantum algorithm using polylogarithmic space in uniformly random order, but unconditionally requires polynomial space both classically in random order and quantumly when all updates precede the requests. To prove the quantum lower bound, we strengthen the consumability bounds of Gilboa, Jain, and McClean for Multiple Hidden Matching. Without prior entanglement, any quantum encoding supporting $r$ independent matching requests requires $Ω(r)$ qubits for $r\le N^{1/2-δ}$ and every fixed $δ\in(0,1/2)$, even with simultaneous revelation and arbitrary joint decoding. For sequential requests, the linear bound extends through $r=Θ(\sqrt N)$. We also adapt Kallaugher's triangle-counting algorithm to uniformly random streams in which every edge is repeated equally often. Rebuilding the quantum sketch and resampling the classical estimator improve its expected-space bound in suitable parameter regimes. Finally, we extend the robust Noisy Gap Cycle framework of Assadi and Sundaresan to quantum streaming. A quantum communication lower bound for Block Hidden XOR yields an $Ω(n)$ space lower bound in random edge order for large enough cycles, with consequences for several graph problems. Thus random order can enable replenishment of small quantum representations, while substantial space requirements persist for other tasks.Authors: Yang P. Liu, Richard Peng, Alicia Stepin, Colin Tang
We give optimal bounds, up to polylogarithmic factors, for rounding convex bodies to near-isotropic position. A convex body $B(0,r)\subseteq K\subseteq B(0,R)$ in $\R^n$ can be rounded using $\Ot(n^3)$ membership queries; the upper bound extends to logconcave distributions. We prove a matching $\Omegat(n^3)$ lower bound, even when $R/r=n^{O(1)}$. The key lemma states that if $B(0,1)\subseteq K$ and $\Cov(\Unif(K))\preceqκI_n$, with $κ\ge1$, then approximate uniform sampling from an initial density bounded by a constant times the uniform density uses $\Ot(n^2\sqrtκ)$ expected membership queries. We prove this by simulating reflected kinetic dynamics using the analysis of Eberle and Lörler~\cite{EL26:journal}. Combining this sampler with the ideas of Jia, Laddha, Lee, and Vempala~\cite{JLLV26:journal} for rounding well-rounded bodies yields our $\Ot(n^3)$ query rounding algorithm. We also give a counterexample to an ellipsoid-growth conjecture from previous papers on this topic.Authors: Shyam Dhamapurkar, Mohit Garg, Manaswi Paraashar, Jaikumar Radhakrishnan
We consider the following data compression problem. Given a string $x \in \{0,1\}^m$ of Hamming weight at most $n$, compress it into a shorter string $y \in \{0,1\}^s$ so that any bit $x_i$ of $x$ can be retrieved without any error using at most $t$ quantum queries to the standard oracle encoding of $y$. If queries are allowed to be adaptive we show how optimal compression up to a logarithmic factor can be achieved. If the queries are required to be made non-adaptively, we show schemes whose space is optimal in its dependence on $m$ except for a logarithmic factor, and is at most quadratically worse when compared to the optimum in its dependence on $n$.Authors: Chenxin Dai, Alicia Stepin, Colin Tang
We give a fast algorithm for solving min-cost $k$-commodity flow. The basic idea is to construct an auxiliary linear program that has low rank and whose minimum value is at most $1/k$ times the minimum value of the original problem (thus, solving this auxiliary linear program will make at least $1/k$ fraction of progress in the original problem). Low-rank linear programs can be solved quickly using black-box techniques. Thus, our algorithm runs in time $\tilde{O}(\operatorname{poly}(k)(n^{2.5}+m\sqrt{n}))$ on a directed graph with $n$ vertices and $m$ edges. We do not rely on any fast matrix multiplication.Authors: Dario Fiorenza, Daniele Gorla, Ivano Salvo
Braess paradox originates when latency at Wardrop equilibrium in traffic networks decreases because of removing edges. The graph-theoretic property of networks suffering from the Braess paradox was called vulnerability by Roughgarden in 2006; it was then characterized and algorithmically checked both for undirected and for directed nets. In this paper, we provide a decremental algorithm of linear amortized complexity to check vulnerability for dynamically evolving networks. The basic idea of our dynamic algorithm is to use a static algorithm that marks some edges as irrelevant for the vulnerability of the graph and ignore those edges for all subsequent runs of the decremental procedure. To get a linear amortized cost for every edge remotion, we also provide a new version of such a static algorithm that improves its complexity from O(n m^2) to O(m^2), that is in turn aligned with the cost of the best state-of-the-art static algorithm for vulnerability.Authors: Fan Chen, Sinho Chewi, Jianfeng Lu, Matthew S. Zhang
We study deterministic and randomized midpoint discretizations of Langevin dynamics for a target $π\propto e^{-V}$, where $0 \prec αI\preceq\nabla^2V\preceqβI$ and $κ=β/α$. To achieve $\sqrtα\,W_2\leqslant\varepsilon$, we show that deterministic Heun uses at most $\widetilde O(κ^{4/3}d^{1/3}\varepsilon^{-2/3})$ gradient queries, and underdamped exponential midpoint uses $\widetilde O(κ^{5/4}d^{1/4}\varepsilon^{-1/2})$. The proofs exploit cancellation at stationarity and smoothing using techniques from Malliavin calculus, outperforming previous upper bounds based on standard couplings. At bounded condition number, a lower bound matches the $d$ and $\varepsilon$ powers of both deterministic methods. To contrast, for the randomized midpoint methods and Poisson midpoint with at least two grid points (both overdamped and underdamped variants), a simple Gaussian calculation yields a lower bound $d^{1/3}\varepsilon^{-1/3}$ to get an $\varepsilon$-close sample despite starting at a benign initialization. This shows surprisingly that in high dimensions, deterministic discretizations can outperform their random counterparts.Authors: Daniele Carnevale
A temporal graph is a sequence of graphs on a common set of $n$ vertices, its snapshots, one for each time step. An agent, knowing the entire sequence in advance, may at each time step wait or move along an edge of the current snapshot, and the temporal graph is explored once the agent has visited every vertex. We consider always-connected temporal graphs, in which every snapshot is connected, and ask how long exploration can be forced to take when the underlying graph, the union of all snapshots, has maximum degree at most~$Δ$. Two lower bounds were known in this setting, $Ω(Δn)$ and $Ω(n\log n)$, realised by different constructions. We establish a stronger lower bound, answering a question of Bastide, Groenland, Michel and Rambaud. Specifically, for every $n$ and $Δ$ with $Δ_0\leΔ\le n-1$ we construct an always-connected temporal graph on $n$ vertices with underlying maximum degree at most~$Δ$ that cannot be explored in fewer than $γ\,Δn\,(1+\log(n/Δ))$ time steps from any start vertex, where $γ>0$ and $Δ_0$ are absolute constants. The construction is deterministic, and every snapshot is a spanning tree with exactly one vertex of degree greater than three. Time is divided into phases. In each phase, a rotating-cycle gadget prevents the agent from reaching more than half of the trees attached to it. Between phases, we reassign target vertices among these trees using walks on a constant-degree expander, and a Gray code order of the targets keeps the underlying degree bounded. The reassignment guarantees that, for any walk of the agent, some target remains unvisited throughout all phases.Authors: Sourav Das, Ashwin Jacob, Arpit Kumar, Diptapriyo Majumdar
In this paper, we study CONFLICT-FREE EDGE CUT (CF-CUT), which is a recently introduced conflict-free version of the MIN-CUT problem that asks to find the minimum number of edges to disconnect a connected graph. The CF-CUT takes as input a connected undirected graph G = (V, E), a conflict graph $\widehat{G}$ such that $E(G) = V(\widehat{G})$, and the objective is to decide whether there exists $F \subseteq E(G)$ such that $G - F$ is disconnected and $F$ is an independent set in $\widehat{G}$. Rauch et. al. [IPL-2025] proved that CF-CUT is NP-Complete and also provided some results on the parameterized complexity of CF-CUT. A related variant MIN CONFLICT-FREE EDGE CUT (MIN-CF-CUT) takes a connected graph $G$, a conflict graph $\widehat{G}$ such that $V(\widehat{G}) = E(G)$, and an integer $k$ as input and asks if there is a set $F$ of at most $k$ edges such that $G - F$ is disconnected and $F$ is an independent set in $\widehat{G}$. In this paper, we extend the work of Rauch et al. [IPL-2025] and provide a systematic study on the CF-CUT and MIN-CF-CUT from the perspective of parameterized complexity and polynomial kernelization. We prove that CF-CUT is NP-hard when the dissociation number of the input graph is at most two. We also complement it by proving that CF-CUT is poly-time solvable when the dissociation number of an input graph is at most one. Additionally, for MIN-CF-CUT, we consider both solution size and various structural parameters of the input graph as parameters, and provide fixed-parameter tractability and W[1]-hardness results when the conflict graph is restricted to various graph classes. We also prove that unless NP $\subseteq$ coNP/poly, MIN-CF-CUT admits no polynomial kernel when parameterized by the vertex cover number of the input graph; and also when parameterized by the sum of the solution size and the vertex integrity of the input graph.Authors: Sepideh Mahabadi, Jakub Tarnawski
In this work we consider the Maximal Independent Set (MIS) problem and the metric Steiner Forest problem in the sublinear time setting, under the adjacency/distance matrix query model. First, we give an algorithm that estimates the size of an MIS up to a multiplicative factor of $(1+\eps)$ using $\tO(n^{4/3}/\eps^2)$ queries. This improves the best previous algorithm by Mahabadi, Roghani, Tarnawski, and Vakilian (SODA 2026), which had a query complexity of $\tO(n^{3/2}/\eps^2)$. Via a reduction from that work, this would automatically imply the same improvement for the problem of estimating the metric Steiner Forest cost up to an $O(\log n)$ factor. However, as our second contribution, we consider the Steiner Forest problem directly and provide an algorithm with $\tO(n)$ query complexity that is very simple and does not proceed via MIS.Authors: Wataru Inariba
The Independent Chip Model (ICM) converts the chip stacks of the players remaining in a poker tournament into finishing-place probabilities and prize equities. It is the standard model in tournament solvers, but its definition considers all possible finishing orders, and exact computation has been regarded as intractable for large fields. The same mathematics appears in other fields; for instance, the ICM is a Plackett-Luce ranking model with stacks as weights. We present DE-ICM, a deterministic algorithm that computes the placement probabilities of all $n$ players for all paid places in $O(M n^{2})$ time, where the number $M$ of quadrature nodes is fixed for the admissible inputs and the target accuracy. Its numerical scheme allows the target to be set close to the accuracy of double-precision arithmetic. The algorithm evaluates a classical integral representation in which, conditional on a player's exponential clock, the number of players ahead is Poisson-binomial. A double-exponential quadrature on a single grid evaluates every integral; its truncation errors have closed-form bounds, and the step size, which controls the discretization error, follows from the field size. A numerically stable deconvolution then recovers each player's leave-one-out coefficients in $O(n)$ time from one shared product. On exactly solvable instances with up to 4,000 players, the worst observed relative error of an equity is $4.0 \times 10^{-14}$ and the worst absolute error of a placement probability $1.1 \times 10^{-14}$. The full placement matrix for 1,000 players takes 0.2 seconds on one CPU core.Authors: Yiyi Cai, Yongtao Zhan, Alexander Zlokapa
The Sachdev-Ye-Kitaev (SYK) model is a strongly interacting fermionic system. Its dynamics are difficult to analyze with Lieb-Robinson bounds and cluster expansions due to its all-to-all disordered interactions. We prove that, with high probability over the disorder, the SYK model admits a quantum Gibbs sampler with a system-size-independent spectral gap at sufficiently high constant temperatures. This yields polynomial-time preparation of SYK Gibbs states on a quantum computer. While prior non-rigorous computations that suggested SYK thermalization were limited to studying local correlators, we emphasize that our result holds up to arbitrary inverse polynomial trace distance. Our proof introduces the pseudo-Lindbladian approach to fermions and uses an especially simple SYK analysis based on a comparison to classical dynamics.Authors: Yoshiteru Ishida
Every balanced instance of the stable marriage problem with strict complete preferences has a unique finest partition into prime blocks, and that single partition simultaneously factors three different structures: the reachable execution digraph as a Cartesian product, the proposal-prefix antimatroid as a direct sum, and the stable-matching lattice as a direct product. The converse fails, and fails at every size from two on: two explicit families share the identical Boolean-cube execution while one is maximally decomposable with a single stable matching and the other is prime with n. Uniqueness yields an exact census, a recursion counting the prime instances at every size, under which exactly 88,478,208 of the 110,075,314,176 profiles with four agents on each side are decomposable and the decomposable fraction is asymptotically n! / n^(2n). The blocks are characterised as the square components of the mutual-rank filtration, so the partition is computable in polynomial time and the factorisation is a tool rather than only a fact.Authors: Jessica Enright, Melissa A. Huggan, Ethan Hunter-Frankland, Margaret-Ellen Messinger, Dylan Pearson
The Firefighter Problem models a spreading process (originally a fire, alternatively an infection or rumour, for example) on a graph. A defender saves a single vertex per turn; after each defence, the fire spreads to the unburned and undefended neighbours of all burning vertices. Deciding whether a strategy exists for the defender to protect some targeted number of vertices is computationally hard in graphs in general, but tractable in some restricted cases. Inspired by research into spreadable rabies vaccines for bats, we study a variant of the Firefighter problem in which defence also spreads. Some approximation results are already known for this problem; we provide algorithmic and hardness results, as well as containment results for the infinite $n$-dimensional Cartesian and strong grid graphs.Authors: Mahmoud Abo Khamis, Hubie Chen
We present Guanaco, an algorithm for performing conjunctive query evaluation where, for each Boolean conjunctive query, and positive epsilon, the algorithm achieves polynomial time with exponent equal to the submodular width plus epsilon. The algorithm and its running time generalize smoothly to general conjunctive queries. We believe the algorithm and its analysis to be notably simple, indeed, together we believe they form a highly simple argument that conjunctive query evaluation can be performed in essentially submodular width time. In the case of Boolean conjunctive queries, the algorithm is based on interleaving three simple primitives: a subroutine for establishing a form of consistency; a subroutine for establishing global uniformity, which, briefly speaking, partitions relations as needed to control discrepancies between average degree and maximum degree; and, a simple step that joins pairs of existing relations to form new relations.Authors: Hyundong Jin, Hyunki Hong, Yo-Sub Han
Time series often contain recurring structural patterns, and efficiently mining such patterns into compact representations is essential for scalable analysis of long sequences. Cartesian tree (CT) equivalence provides a well-established structural abstraction that preserves hierarchical order structure while discarding exact values and fine-grained ordinal variations. By grouping multiple ordinal patterns into a shared structural form, CT equivalence offers a principled way to compress recurring temporal structure. However, mining frequent CT-equivalent patterns at scale remains computationally expensive. A naive pairwise approach repeatedly constructs and counts CT representations over subsequences, requiring $O(n^4)$ time for a sequence of length $n$, which severely limits its applicability to long sequences. We propose a new Cartesian pattern mining algorithm based on a Cartesian suffix tree that compactly organizes CT-equivalent subsequences and reuses shared structural information. Our method reduces exhaustive CT-pattern occurrence collection from $O(n^4)$ to $O(n^2)$ time, and we formally prove the correctness and complexity bounds. We further show that this computational gain translates into effective compact representations. Across diverse time-series datasets, a small set of mined CT patterns preserves meaningful clustering structure, and comparisons with finer-grained order-preserving representations show that CT equivalence reduces redundant ordinal distinctions under limited feature budgets. Our implementation is available at github.com/hyundong98/CT-Miner .Authors: Dennis Joyce
In the matroid secretary problem, weighted elements arrive in random order, and an online algorithm must irrevocably accept elements forming a high-weight independent set. Dynamic Thinning is a recent, conceptually simple $3.1462$-competitive algorithm for the matroid secretary problem that maintains a random reference set. Given this reference set, the elements in its maximum-weight independent subset have been accepted independently with a time-dependent probability. We extend this approach by replacing the single reference set with a finite hierarchy of nested reference sets. For every fixed $\eps>0$, the resulting algorithm is $(e+\eps)$-probability-competitive for arbitrary matroids, with $O_\eps(n^2)$ queries in the worst case.Authors: Simone Faro
A collage system is a grammar-based compression model that extends straight-line programs with repetition and substring truncation. Internal collage systems additionally require every nonterminal to be structurally reachable from the start symbol. Migita, Uehata, and I (CPM 2026) showed that any collage system of size $m$ can be converted into an internal one generating the same string with size at most $9m$, and left the improvement of this constant as an open problem. We show that a simple refinement of their top-down conversion reduces the bound to $5m$. The proof combines three elementary ideas: canonicalization of generated truncations that remain aligned with a target endpoint; a repetition decomposition that absorbs every complete copy of the repetition base into a maximal core; and monotonicity of structural reachability, which prevents an input truncation rule from both becoming structurally reachable and later acting as a hidden target at which endpoint alignment is lost. The conversion runs in deterministic $O(m^2)$ worst-case time in the stated unit-cost random-access machine model. Consequently, for every string, the minimum size of an internal collage system is at most five times the minimum size of a general collage system.Authors: Dmitry Kamenetsky
Balanced discrete optimal transport between n sources and n targets of unit mass is exactly the minimum-cost assignment problem-a bipartite perfect matching-and is therefore solvable exactly by industrial matching engines in milliseconds to seconds. We ask when the exact approach beats the standard approximate alternatives, entropic Sinkhorn and its accelerated variant Greenkhorn, and make the sparse-exact side certified by a textbook LP dual-feasibility clip. Three contributions. (i) Measurement: on dense 2-D instances, exact matching (Jonker-Volgenant) is faster and strictly more accurate than either approximate method throughout the moderate-n regime (0.01 s at n=500 to 11.5 s at n=8000); reaching a 1% quality target on the same hardware requires roughly 10-80 min for Greenkhorn (factors 4e2-6e4 over exact; plain Sinkhorn is 20-650x slower still), a rough power-law projection beyond the measured range. Greenkhorn's measured speedup over plain Sinkhorn is only 1.0-1.5x on most converged cells. (ii) A simple kNN-pool gap certificate: given a pool matching and its Blossom dual, a one-pass O(n^2) clip produces a dense-feasible lower bound; combined with the Sinkhorn dual potential (valid at every iterate, not just at convergence), the bound is valid on all 45 measured configurations and tightens monotonically with k. (iii) A multi-robot task-allocation sanity check where the discrete plan is the deliverable: per-round exact assignment costs 0.1-68 ms, while a Sinkhorn-plus-hardening pipeline costs 0.12-15.9 s and accumulates 6-27% extra travel over 15 rounds. The Sinkhorn family's large-n dense regime is acknowledged and left untouched. Code, data, and results under MIT: github.com/dimkadimon/OT-Blossom.Authors: Simon Frisk, Sungjin Im, Paraschos Koutris, Benjamin Moseley, Hung Ngo, Kirk Pruhs, Hangdong Zhao
$\mathsf{Datalog}^\circ$ has been introduced as an extension to Datalog that increases expressiveness, yet retains simple least fixpoint semantics and admits optimization techniques such as semi-naïve evaluation and demand transformation. $\mathsf{Datalog}^\circ$ accomplishes this by generalizing the {\em or} and {\em and} operators of Datalog to addition and multiplication over a semiring. Finding a (minimal) fixpoint of a $\mathsf{Datalog}^\circ$ program is equivalent to finding a solution to a system of polynomial equations over the underlying semiring. Solving these systems of polynomial equations is not only a fundamental problem in the theory of $\mathsf{Datalog}^\circ$, but also has many applications in computer science, such as in databases, program analysis, and optimization. This paper resolves a key open problem in the theory of $\mathsf{Datalog}^\circ$: we prove a tight upper bound on the number of steps until convergence of iterative methods for solving these polynomial equation systems over a commutative $p$-stable semiring. In particular, we show that the number of steps until convergence is $O((p+1)n)$ where $n$ is the output size of the $\mathsf{Datalog}^\circ$ program. As the number of steps until convergence is only a proxy for the runtime of $\mathsf{Datalog}^\circ$ evaluation, we also consider the number of semiring operations used and show that, for a natural class of algorithms, $O((p+1)mn)$ is a tight upper bound, where $m$ is the maximum number of semiring operations per iteration.Authors: Vaneet Aggarwal
We study nonnegative, non-monotone $k$-submodular maximization with $k\ge2$ labels under support constraints, and show how the certified approximation coefficient improves as the support region permits more uniform selection. For a compact convex down-closed support region $P\subseteq[0,1]^n$, the diagonal level $ζ(P)=\max\{t\in[0,1]:t {\bf 1} \in P\}$ ranges from $ζ=0$, which carries no geometric promise, to $ζ=1$, which is unrestricted support. Our main structural result is a comparator-uniform linearization of the multilinear extension, built from an objective-independent action and a comparator-independent update field. For $k\ge3$, its validity reduces, independently of the number of elements, to four polynomial inequalities of degree at most three in one or two variables, only one of which depends on $k$. Explicit parameter choices give a nondecreasing certified profile $\underlineα_k(ζ)$, in closed form on all of $[0,1]$ when $k=2$. At $ζ=0$ we certify $0.4456\ldots$ for $k=2$ and $0.4541\ldots$ for every $k\ge3$, improving the recent $\sqrt2-1$ guarantee for one matroid or one knapsack, as well as the $1/3$-type guarantees for a fixed number of budgets; at $ζ=1$ we certify $1/2$ for $k=2$, $(\sqrt{17}-3)/2$ for $k=3,4$, and $k/(2k-1)$ for $k\ge5$, whose excess over $1/2$ is of order $1/k$ rather than the previous $1/k^2$. Value-retaining rounding transfers these guarantees to matroid and knapsack constraints, and the same field yields $O(\sqrt T)$ approximate regret online under gradient or post-decision value feedback.Authors: Simon Frisk, Paraschos Koutris
We study constant-delay enumeration for conjunctive queries with negation ($\texttt{CQ}^{\neg}$). Prior work defined \emph{signed-acyclicity}, which characterizes the class of queries where linear preprocessing time is achievable, but little has been known beyond this. We introduce a new hypergraph width measure for $\texttt{CQ}^{\neg}$, the \emph{signed fractional hypertree width} ($\textsf{sfhw}$), defined by requiring that a single variable order simultaneously handle every subset of the negative atoms. We show that $\textsf{sfhw}$ strictly generalizes signed-acyclicity (recovered when $\textsf{sfhw} = 1$) and fractional hypertree width (recovered on queries without negation). Our main algorithmic result is a variable-elimination algorithm that achieves constant-delay enumeration on input $I$ for any full $\texttt{CQ}^{\neg}$ query with preprocessing time $O(|I|^{\textsf{sfhw}})$. We further show that using multiple variable orders can improve this bound, exhibiting an $O(|I|^{3/2})$ algorithm for $k$-cycle queries with at least one negative edge.Authors: Lucas de Oliveira Silva, Lehilton Lelis Chaves Pedrosa
We study the minimum Vertex Cover problem under two non-adaptive offline advice models, where predictions about a fixed optimum solution are provided once as part of the input. These forms of prediction were introduced independently by Cohen-Addad, d'Orsi, Gupta, Lee, and Panigrahi (2024) and by Ghoshal, Makarychev, and Makarychev (2025). In Partial Predictions, independently revealed vertices come with correct membership labels. For every sufficiently small fixed $\varepsilon>0$, we give a randomized polynomial-time algorithm that has expected approximation ratio at most $2-(2-o(1))\frac{\log\log(1/\varepsilon)}{\log(1/\varepsilon)}$. In Noisy Predictions, every vertex instead receives a mutually independent noisy membership label of bias $\varepsilon$. For every sufficiently small fixed $\varepsilon>0$, we give a randomized polynomial-time algorithm that has expected approximation ratio at most $2-(1-o(1))\frac{\log\log(1/\varepsilon)}{\log(1/\varepsilon)}$. Our Noisy Predictions bound matches the leading asymptotic improvement below $2$ obtained by Aamand, Chen, Gollapudi, Silwal, and Wu (2025), despite using only one noisy label per vertex rather than a separate independent label for each endpoint of each incident edge. Both our bounds hold as $\varepsilon$ goes to $0$ and are strictly below $2$, the optimal approximation threshold for minimum Vertex Cover without advice under the Unique Games Conjecture, as shown by Khot and Regev (2008).Authors: Xi Chen, Ruiquan Gao, Yuhao Li, Aviad Rubinstein, Mihalis Yannakakis
We study the query complexity of finding a Tarski fixed point over $[n]^k$. Previous work has left a large gap between $\smash{Ω(\log^2 n)}$ and $\smash{\log^{O(k)}n}$. We show that both of the previous upper and lower bounds were far from tight: for every $k\geq 3$, \[ Ω\left((\log n)^{\frac{1}{2}\lceil \log k\rceil}\right)\le \operatorname{Tarski}(n,k)\le O\left(5^k(\log n)^{\lceil \log k\rceil}\right). \] Succinctly, up to the fixed-parameter factor of $5^k$, the complexity is settled at $(\log n)^{Θ(\log k )}$. In particular, we obtain the first super-polynomial query lower bound for this problem.Authors: Rong-Hua Li, Yichun Yang, Junjie Zhou
We study the fundamental problem of computing Personalized PageRank (PPR) on an undirected and unweighted graph $G$. We focus on the $\eps$-error guarantee introduced by Andersen, Chung, and Lang [ACL; FOCS 2006 $\&$ Internet Math 2007]. Their classic local push method computes an approximate PPR vector satisfying the ACL $\eps$-error guarantee in $O((α\eps)^{-1})$ time, where $α$ is the teleportation parameter. In this paper, we eliminate the dependence on $α$ and present an algorithm that achieves the same error guarantee in $O(\eps^{-1-o(1)})$ time. Consequently, we obtain a nearly optimal algorithm for PPR computation under the ACL error guarantee, and a nearly linear algorithm for local graph clustering with complexity independent of $φ$.Authors: Ali Karim Lalani
We provide potential function proofs of the competitive ratios of DoubleCoverage for the hard $k$-taxi problem on HSTs and general weighted trees of bounded depth. Buchbinder, Coester, and Naor (2023) obtained these ratios using time-reverse dual fitting and noted that they did not know a pure potential proof beyond $k=2$. We observe that the minimum matching distance between the online and offline taxi configurations can be expressed as an integral over the rooted tree of the absolute difference between their taxi counts below each point. This representation lets us analyse DoubleCoverage over short movement intervals and apply the resulting estimates to potentials that remain unchanged when both serving taxis are relocated from pickup to destination.from ECCC Papers
from ECCC Papers
from CCI: jobs
The Joint Center for Quantum Information and Computer Science (QuICS, http://quics.umd.edu) is seeking exceptional candidates for the QuICS Hartree Postdoctoral Fellowships in Quantum Information and Computer Science. Apply at: https://umd.wd1.myworkdayjobs.com/en-US/UMCP/job/QuICS-Hartree-Postdoctoral-Fellow-1_JR104987
Website: https://umd.wd1.myworkdayjobs.com/en-US/UMCP/job/QuICS-Hartree-Postdoctoral-Fellow-1_JR104987
Email: quics-coordinator@umiacs.umd.edu
Authors: Ihar Babushkin, Oliver Melchert, Ayhan Demircan, Uwe Morgner
In directed logic (DL), electronically controlled optical elements serve as photonic gates. Such electro-optical elements are of mixed nature: they have two inputs--electronic and optical--but only one, optical, output. This makes cascading such gates without repeated conversion between optical and electronic representations cumbersome. This problem can be largely overcome using the nested cascading scheme proposed by Shamir and Hardy [Opt. Express, 17, 150 (2007)]. Although promising as a solution to the cascading problem, the Shamir-Hardy scheme has so far been proved or implemented only for a few simplest cases. Here, we develop a general rigorous theory of nested cascading, valid for an arbitrary number of gates. We propose a variant of the algorithm which easily extendable to large number of gates, and rigorously prove its validity. Furthermore, we analyze how nested cascading scales with the size of the corresponding Boolean formula. We show that good (linear) scalability is guaranteed in many important cases, while the average scaling with respect to the corresponding Boolean formulas is only moderately polynomial, with an exponent of approximately 3/2. Yet, the worst-case scaling remains exponential with respect to more general Boolean circuits allowing sharing and reuse of intermediate results.Authors: Eric Culf
Constraint satisfaction problems (CSPs) with operator assignments to the variables provide a well-structured setting to study the decision complexity of the entangled value of classes of nonlocal games. Due to the CSP dichotomy theorem, the complexity of constraint satisfaction problems with classical assignments can be fully understood by studying the symmetries of the CSP, in terms of the polymorphisms of the underlying relational structure. In this work, we show that the polymorphism-based reductions between CSPs can be generalised to gap-preserving reductions between entangled CSPs based on an entangled analogue of the polymorphisms. This reduction allows us to show undecidability of entangled graph colouring with more than three colours, a problem that has proved resistant to prior hardness reductions based on commutativity gadgets.Authors: Jiawei Li, Zhiyang Xun, Lijie Chen, Jonah Brown-Cohen
As powerful AI systems reach and sometimes surpass the abilities of human experts across a range of cognitively demanding tasks, the problem of accurate oversight and supervision of these systems has become increasingly urgent. One promising approach is AI debate, which seeks to leverage a debate between two powerful AIs to break complex questions down into simpler claims that can be easily judged directly. Theoretical work on debate has formalized this intuition in the language of computational complexity theory, where the goal is to design protocols (i.e., rules of the debate game) that provide rigorous guarantees on correctness for judging solutions to complex problems with limited supervision. Specifically, the current best protocol has been shown to work for all problems that have sufficiently stable decompositions into subproblems. In this paper, we design a new protocol for this same class of problems that improves on the prior work in several ways. First, correctness holds in a worst-case rather than an average-case sense. Second, being honest and correct is a dominant-strategy equilibrium for both debaters, rather than a Stackelberg equilibrium. Finally, we prove black-box lower bounds, showing that our new protocol is instance-wise optimal. That is, no protocol for this class of problems can outperform ours while making only black-box queries to human judgments. We obtain these results by relating the notion of stable problem decompositions to the concept of fractional block sensitivity from query complexity.Authors: Eshan Chattopadhyay, Noam Ringach, Nicholas Spooner
We give a proof of the existence of two-sided product expanding codes which, unlike the earlier result of Kalachev and Panteleev (FOCS, 2025), does not rely on explicit constructions of asymptotically optimal locally testable codes ($c^3$-LTCs). For every fixed number of component codes and dimensions whose rates are bounded away from zero and one, we show that independent random linear codes over a sufficiently large prime field have constant two-sided product expansion with probability tending to one. The tradeoff is that our proof requires the characteristic to grow with the block length, while [KP25] takes extensions of $\mathbb{F}_2$. To replace the use of $c^3$-LTCs, we develop several new techniques that we view as interesting in their own right. Instead of working directly over finite fields, we work over the reals and use random Rademacher matrices for the generator matrices of the component codes. From here, we we show that the extendability of $\varepsilon$-closed sets can be reduced to controlling the operator norm of sparse restrictions of carefully chosen Gram matrices. Applying the trace power method to bound this norm reduces to bounding the number of possible labelings of certain closed walks on bipartite graphs, which we bound using the sparsity of the operators and bounds on the number of equivalence classes of weak Wigner words from Anderson and Zeitouni (Probab. Theory Relat. Fields., 2006), which were originally applied to band matrices. Due to our techniques not relying on explicit $c^3$-LTCs, we believe that they form a promising starting point towards showing the existence of product expanding tensor codes where the component codes have non-trivial automorphism groups and coboundary expanding codes that could be used as the local codes of non-cubical complexes, such as simplicial complexes.Authors: Xin Li, Yan Zhong
We construct explicit non-malleable affine extractors for every constant entropy rate, with linear output length and exponentially small error, against any fixed number of affine tamperings without fixed points. For every fixed $0<η<1$ and $t$, we also obtain entropy threshold $C_{η,t}n/\log n$, output length $\lfloor n^{1-η}\rfloor$, and error $2^{-n^{1-η}}$ against $t$ tamperings. Our extractors, as well as the directional affine extractors of Li and Zhong (CCC 2024), yield explicit Boolean functions with correlation $2^{-Ω(n)}$ against weakly read-once linear branching programs of size $2^{Ω(n)}$. For non-oblivious decision trees, we prove linear depth lower bounds for queries of each fixed degree $r\ge2$. Applying Li's sumset extractor (FOCS 2023) gives depth $Ω_δ((n/\ell)\log\ell)$ for growing locality $\ell\le n^{1-δ}$, where $0<δ<1$ is fixed. In the same range, directional affine extractors give correlation $2^{-Ω(n/\sqrt\ell)}$ against local trees of depth $c(n/\ell)\log\ell/\log\log\ell$, for a sufficiently small constant $c>0$. Our extractors derandomize the lossless lifting of Efremenko and Itsykson (STOC 2026). For every fixed $0<ξ<1$, this gives explicit polynomial-size unsatisfiable CNFs on $N$ variables whose $\mathrm{Res}(\oplus)$ refutations of resolution depth at most $N$ require size at least $2^{(1-ξ)N}$. Separately, parity substitutions give polynomial-size CNFs on $N$ variables with polynomial-size ordinary-resolution proofs for which every $\mathrm{Res}(\oplus)$ refutation of size $S$ and depth $d$ satisfies $d\log(2S)=Ω(N^2)$. This removes the $\log^2 N$ loss in the tradeoff of Itsykson, Podolskii, and Shekhovtsov (CCC 2026).Authors: Alper Cakan
Whether some problems require quantum proofs has been a central question in quantum complexity (Aharonov and Naveh, 2002; Aaronson and Kuperberg, CCC 2007). Recently, breakthrough work of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC 2026), followed by a simpler separation due to Bostanci, Huang, and Vaikuntanathan (FOCS 2026), established a classical oracle separation between $\mathsf{QMA}$ and $\mathsf{QCMA}$. However, while they are not in $\mathsf{QCMA}$, the problems used in both separations still lie in $\mathsf{AM}$: they admit a two-message public-coin proof system with a classical verifier. In this work, we ask whether some problems truly require quantum proofs. More formally, we consider the complexity class $\mathsf{QCIP}$, introduced by Buhrman, Le Gall, and Weggemans (2024), where an efficient quantum verifier interacts with an unbounded prover over a classical channel for an arbitrary polynomial number of rounds. We construct a classical oracle $\mathcal{O}$ such that $\mathsf{QMA}^{\mathcal{O}}\not\subseteq\mathsf{QCIP}^{\mathcal{O}}$, thus showing that some languages indeed require quantum proofs, with no classical replacements. Since $\mathsf{QCMA}=\mathsf{QCIP}[1]$, this strengthens the earlier $\mathsf{QMA}$--$\mathsf{QCMA}$ separations, which now follow as a special case of our result. As a technical contribution, we extend to the complexity theory setting the techniques developed by Cakan, Goyal, and Shmueli (CRYPTO 2026) in the context of cryptography for analyzing classically interacting quantum machines. We believe this may be of independent interest.Authors: Adam Bouland, Matthew Ding, Siddhartha Jain
We show two unconditional quantum space advantages in the random-order streaming model. First, we show the Yamakawa--Zhandry Code Intersection problem admits exponential quantum advantage in the streaming model when its inputs are streamed in random order. This means quantum computers exhibit exponential space advantage even when simply receiving $(x,f(x))$ pairs for a uniformly random function $f$ in a uniformly random order. Our lower bound is shown using density-restoring partitions as in the work of Göös, Gur, Jain, and Li (STOC 2025) combined with a convex potential, similar to the work of Raz (J.ACM 2018) on parity learning and its generalization by Garg, Raz, and Tal (STOC 2018). Second, we use our framework to show quantum space advantage for the Optimal Polynomial Intersection (OPI) problem in certain regimes via a streaming version of the Decoded Quantum Interferometry algorithm (Nature 2025; arXiv:2510.10967). In particular, we show that for degree $d$ and $n$ evaluation points, attaining $1/2 + Ω(\sqrt{d/n})$ fraction of satisfied OPI constraints via streaming requires $Ω(n)$ classical bits of memory but only $O(d\log n)$ qubits. This yields provable quantum advantage in a "low-rate" regime when the number of evaluation points is much larger than the degree, with a space advantage that can be as large as exponential in certain parameter settings.Authors: Shih-Han Hung, Han-Hsuan Lin
Marriott and Watrous showed that quantum Merlin--Arthur games admit generic error reduction without increasing witness size [Computational Complexity, 2005]. In this work, we show that this state-size-preserving amplification property does not hold for polynomial-time quantum computation with quantum advice. In particular, we present decision problems for which even a vanishing additive error reduction requires longer advice. More precisely, for every polynomially bounded advice length $m(n)\geq n^4$ and every error bound $\varepsilon(n)$ that stays below $1/2$ by at least an inverse polynomial, there is a positive function $δ$ with $δ(n)=O\bigl(\min\{(\log m/m)^{1/4},\ \sqrt{\log m/m}\,/(1/2-\varepsilon(n))\}\bigr)$ such that $\mathsf{BQP}_{\varepsilon}/\mathsf{q}m \subsetneq \mathsf{BQP}_{\varepsilon + δ}/\mathsf{q}m$; for constant $\varepsilon$ the gap is $O(\sqrt{\log m/m})$. Here, $\mathsf{BQP}_\varepsilon/\mathsf{q}m$ is the class of languages recognizable with error at most $\varepsilon(n)$ by a polynomial-time quantum algorithm with an $m(n)$-qubit advice state that only depends on the input length $n$. We show this by proving a stronger separation $\mathsf{P}_{\varepsilon+δ}/\mathsf{r} m \not\subset \mathsf{BQP}_{\varepsilon}/\mathsf{q} m$, where $\mathsf{P}_{\varepsilon}/\mathsf{r}m$ is the class of languages recognizable with error at most $\varepsilon(n)$ by a deterministic polynomial-time algorithm with an $m(n)$-bit advice string sampled from a distribution that depends only on $n$.Authors: Erin Chambers, Shankha Shubhra Mukherjee, Katharine Turner
Reeb Transforms offer a compact representation of how shapes in $\mathbb{R}^n$ change when sliced along varying directions. We define the Reeb Transform as the family of Reeb graphs induced by height functions along all directions in the unit sphere. In this paper, we develop a rigorous treatment of Reeb Transforms for o-minimal definable sets, with particular emphasis on one-dimensional stratified spaces embedded in $\mathbb{R}^d$ and on surfaces in $\mathbb{R}^3$. We establish injectivity of the Reeb Transform in multiple settings, including compact surfaces in $\mathbb{R}^3$, capturing the essential topological features needed to uniquely reconstruct such surfaces. However, in dimensions above three, the Reeb Transform ceases to be injective, indicating the limitations of this descriptor in higher-dimensional settings.Authors: Pankaj K. Agarwal, Esther Ezra, Micha Sharir
This paper presents data structures for nearest-neighbor (NN) searching problems involving points, lines, segments, and triangles in 3-space, achieving significantly better performance than the previously best-known results for these problems. For example, we present a linear-size data structure for answering NN queries with lines or segments amid $n$ points in 3-space with $O^*(n^{1/2})$ query time (where the $O^*(\cdot)$ notation hides subpolynomial factors). We also present a data structure of $O^*(n^4)$ size that answers such queries in $O^*(1)$ time. For the converse problem, in which we seek the nearest neighbor of a query point amid $n$ lines, segments, or triangles in 3-space, we present a linear-size data structure with $O^*(n^{2/3})$ query time. These results constitute a significant improvement over previous solutions. We obtain improved solutions for the two extreme regimes of (near-)linear storage and of fast query time. These results also yield trade-off bounds between the query time and the size of the data structure. Our results rely on several combinatorial and algorithmic results on arrangements of surfaces in 3-space and 4-space, particularly on recent results on vertical decompositions of substructures in such arrangements established by the authors.Authors: Francisco Escudero Gutiérrez, Junseo Lee, Sebastian Zur
We establish lower bounds for Hamiltonian property testing with access to the time-evolution operator but not its inverse. Each experiment may query the time-evolution operator multiple times, and distances between Hamiltonians are measured in the normalized Frobenius norm. In this model, we show that testing whether a Hamiltonian is $k$-local or $\varepsilon$-far from every $k$-local Hamiltonian requires $Ω(1/\varepsilon^2)$ total evolution time, matching the upper bound of Kallaugher and Liang (TQC'25). We also prove that testing whether an unknown Hamiltonian equals a target Hamiltonian or is $\varepsilon$-far from it requires $Ω(1/\varepsilon^2)$ total evolution time, matching the upper bound of Sinha and Tong (2025). These are the first lower bounds for natural problems in Hamiltonian learning and testing that rule out Heisenberg-limited scaling of $1/\varepsilon$. As a third result, we show that amplitude estimation to precision $\varepsilon$ requires $Ω(1/\varepsilon^2)$ total time evolution, recovering the result of Tang and Wright (QIP'26) in the continuous-time query model. All three results follow from the hardness of distinguishing the zero Hamiltonian from a suitably chosen ensemble of random Hamiltonians. We establish this hardness by adapting the continuous-time adversary method to forward Hamiltonian evolution.Authors: Arthur Braida, Joseph Cunningham, Jérémie Roland
An analog device implements a local Hamiltonian H, but a polynomial P (H) is in general not local, so the device cannot implement it. We carry P (H), to any prescribed accuracy, as the action of a single time-independent local Hamiltonian on an explicitly described invariant subspace. Short chains of ancilla qubits are attached to H. A chain of 2m sites has a unique isolated eigenvalue that is an analytic function of the input vanishing to order exactly 2m, because the input must cross the chain and come back before it can shift the energy at the far end. Chains of different lengths therefore form a triangular family, and a weighted sum of them reproduces a prescribed polynomial term by term. Even chains give the even part and odd chains the odd part, so any polynomial is reached. We prove uniqueness, analyticity and coefficient bounds uniform in the chain length for inputs H of norm below any r < 1. Where the circuit model pays degree 2l in 2l sequential oracle calls, the result here is one Hamiltonian of locality two more than that of H, which pays the degree in O(l^2 + log2^(1/eps)) ancillas and in energy scale. As an application we filter a marked eigenstate of a local Hamiltonian. Composing a synthesised square along the Chebyshev doubling identity works, but its energy scale grows quasi-polynomially with the degree. Iterating instead the exact eigenvalue branch of the two-site chain k times gives a filter on k + 1 ancilla qubits whose error decays geometrically in k, at an energy scale polynomial in the inverse passband width and independent of k, the locality growing by one per stage. In adiabatic optimisation with a rank-one driver, the construction replaces that non-local driver, by a Hamiltonian with O(log n) ancillas and O(log n)- body terms, at an energy scale polynomial in n. Simulations including every ancilla reproduce the spectrum of the ideal algorithm.Authors: Kleitos Papadopoulos
We study single-item lot sizing with piecewise-concave production and holding--backlog costs over $T$ periods. Production has $m$ common positive finite breakpoints, and stock costs and domains have $K$ common finite boundary levels. For fixed $m,K$, we give an exact deterministic algorithm using $\OmK(T^{m+2}α(T+2))$ arithmetic operations and a Las Vegas algorithm using $\OmK(T^{m+2})$ expected operations, where $α$ is the inverse Ackermann function. The algorithms retain nonlinear concave cost pieces and cover backlogging, common-grid stock limits, and explicit terminal-stock policies. A structural decomposition at stock boundary levels yields breakpoint-only prefix and suffix tables. Batching transitions by a designated production period produces implicit matrices that are Monge double staircases on each production piece. Established matrix searches, merged state orders, and backward evaluation provide the bounds. A simpler rectangle/SMAWK variant requires $\OmK(T^{m+2}\log(T+2))$ operations. On 300 no-backlogging benchmark cases, its objectives agree exactly with the predecessor dynamic program and an inventory-state oracle. Geometric-mean paired time ratios are \GeoUncap\ for uncapacitated cases and \GeoCap\ for capacitated cases, with ratios above one favoring matrix searching. A 640-case base-model validation suite and a separate 624-case generalized-model suite pass. The timing study does not benchmark the generalized models or the stronger staircase routines. All bounds assume exact arithmetic, constant-time cost queries, and explicit closed-domain concavity conditions.Authors: Kou Hamada, Satoru Iwata
The matroid parity problem serves as a fundamental framework that generalizes both graph matching and matroid intersection. Although the general version is intractable, Lovász (1981) developed a polynomial-time algorithm for the linear matroid parity problem, assuming the availability of matrix representations. Subsequently, Gabow and Stallmann (1986) presented an augmenting path algorithm, which has long been recognized as one of the fastest deterministic algorithms. Since shortest augmenting paths improved algorithms for graph matching (Micali & Vazirani, 1980) and linear matroid intersection (Cunningham, 1986), extending these techniques to linear matroid parity appears to be a natural progression. However, such an algorithm has remained elusive for four decades. In this paper, we present the first shortest augmenting path algorithm for linear matroid parity. Our approach synthesizes the augmenting path algorithm of Gabow and Stallmann with the synchronized blossom formation of the Micali$\unicode{8211}$Vazirani framework. Our key technical contributions are threefold: (i) a linear-algebraic argument that bounds the lengths of shortest augmenting paths for linear matroid parity, which generalizes Cunningham's bound for linear matroid intersection; (ii) an a priori characterization of shortest search paths through lower bounds on their lengths; and (iii) an extension of the structural properties for graph matching established by Izumi, Kitamura, and Yamaguchi (2025) to the linear matroid parity setting. Our algorithm deterministically solves the linear matroid parity problem in ${\rm O}(nr^2\log r)$ time, where $n$ is the ground set size and $r$ is the matroid rank. By incorporating fast matrix multiplication, this complexity can be further reduced to ${\rm O}(nr^2)$. These results improve upon the long-standing deterministic bounds of ${\rm O}(nr^3)$ and ${\rm O}(nr^ω)$.Authors: Suho Kang, Rajan Udwani
Search advertising platforms routinely spend beyond an advertiser's average daily budget on high-traffic days, so long as total spending over the month stays within the monthly budget. Motivated by this practice, we study a $D$-day generalization of the Adwords problem (Mehta et al. 2007), where each advertiser $i$ has a nominal (average) daily budget $B_i$ and a total horizon (monthly) budget $DB_i$. Given a flexibility parameter $δ$, the platform may spend at most $δB_i$ on advertiser $i$ on any single day, subject to the horizon spending limit of $DB_i$. We quantify the power of $δ$-flexible budgets by benchmarking against the inflexible offline optimum, which may spend at most $B_i$ on advertiser $i$ on each day. We show that no amount of flexibility helps direct generalizations of the classical algorithm of Mehta et al. (2007). By contrast, for every fixed $δ$, we design an algorithm whose competitive ratio converges to $1-e^{-δ}$ as $D\to\infty$, and we show that this is asymptotically optimal. Perhaps surprisingly, this matches the optimal competitive ratio in a more permissive setting where the algorithm receives a fresh spending limit of $δB_i$ each day and may spend up to $δD B_i$ over the horizon. Along the way, we characterize the exact optimal competitive ratio for every pair $(D,δ)$ on high-traffic instances, where the offline benchmark exhausts every advertiser's budget on every day.Authors: Rudransh Kumar, Nima Nasiri, Jared Paul, Sathish Gopalakrishnan
A battery-powered device, such as a delivery drone that works from a depot, must stop to recharge between jobs, and the time spent recharging delays every job that follows. Scheduling models that fix the duration of a recharge do not describe a device whose recharge takes longer when it acquires more energy. We study a single device that executes a batch of non-preemptive jobs with known execution times, energy demands, and optional deadlines. Under \emph{partial recharging} the device may acquire any amount of energy between jobs; under \emph{complete recharging} every recharge fills the battery. Four objectives and four relationships between execution time and energy demand give 32 variants. When acquiring $q$ units of energy takes $q$ time units, we show that 14 of the 16 partial-recharging variants are polynomial, and we give a tight 2-approximation for the average completion time, one of the two NP-hard variants. Under complete recharging, the four variants with equal energy demands are polynomial and the other 12 are NP-hard; for makespan we give a $5/4$-approximation. When each recharge also incurs a fixed \emph{setup time} $h$, the equal-energy variants remain polynomial and the other 24 are strongly NP-hard if $h$ is part of the input. For these we give exact algorithms that are exponential only in the number of jobs, and approximation algorithms for makespan and, when the battery starts empty, for the weighted average completion time. Experiments on synthetic and trace-derived job sets compare the algorithms with exact optima. The model is offline and deterministic, and we have not validated the schedules on hardware.Authors: Cyril Nicaud, Pablo Rotondo
In recent years, several variants of classical hash table schemes have been developed by engineers in order to take advantage of the processor's internal parallelism using SIMD instructions, which make it possible to operate on multiple bytes simultaneously. At a small additional memory cost, this enables a significant speedup, making it a data structure that is increasingly popular in practice, when very high performance is required. In this article, we provide a detailed theoretical analysis of the dynamics of such hash tables. From a methodological standpoint, we use and adapt a technique developed by Wormald in the 1990s to study dynamic graphs. This approach, which can be adapted to many variants, enables us to accurately estimate the quantities of interest by capturing the dynamics of the data structure through systems of differential equations. Although complex, we provide an explicit description of the solutions of these systems, which can furthermore be efficiently approximated numerically. Our main results are stated with high probability, which is significantly more precise than average-case analyses, and they match experimental results remarkably well, even for hash tables of moderate size.Authors: Philip N. Klein
This paper addresses the following problem: given a planar embedding graph, compute a representation of the shortest-path trees rooted at all the boundary nodes of the graph. Klein gave an $O(n \log n)$ algorithm for this problem; the algorithm subsequently became an essential ingredient in dozens of algorithms, addressing problems ranging from distance oracles to edit distance. However, the correctness and analysis in that original paper is complicated and messy and hard to understand. In this paper, we give a simple and clear analysis.Authors: Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Noah Golowich, Tuomas Sandholm, Brian Hu Zhang
There has been a surge of recent work on correlated equilibrium concepts in Markov games. However, existing results focus on concepts weaker than normal-form correlated equilibria (NFCEs), leaving open the more challenging question of computing such equilibria, which goes back to the seminal work of Papadimitriou and Roughgarden (JACM'08). Here, we establish the first efficient algorithm for NFCEs in finite-horizon Markov games with a fixed number of players $n$. In particular, with $S$ states, horizon $H$, and at most $A$ actions per player, it computes an $ε$-NFCE in time $S(AH/ε)^{O(n)}$. This is the first algorithm polynomial in $1/ε$ and the description of the game for NFCEs in an interesting class of problems beyond the normal-form setting. Moreover, under the usual assumption that recommendations are independent across states, we show PPAD-completeness---that is, computational equivalence to Nash equilibria---either in many-player games or when the precision is exponentially small. The key idea behind our approach is to run backward induction on a sequence of auxiliary stage games, but with the twist that in each step we compute a constant-expectation correlated equilibrium. This is a natural refinement of correlated equilibrium in which the conditional expected payoff from obeying is independent of the recommendation. In fact, our reduction goes both ways, establishing an equivalence between constant-expectation CEs and NFCEs in Markov games. For a fixed number of players, we observe that a constant-expectation CE can be computed approximately by combining linear programming with suitable discretization. In contrast, it is PPAD-hard in i) polymatrix (many-player) games at constant precision, and ii) two-player games at exponentially small precision. The latter result follows from an unexpected connection to rank-2 two-player games.Authors: Sherzod Turaev, Mary John, Mamoun Awad
We model an academic curriculum as a generator of a language of feasible study plans: prerequisites are monotone Boolean formulas in conjunctive normal form, degree requirements are credit-threshold covering constraints, and a study plan is a sequence of terms bounded by a per-term credit capacity. Within this model, we settle the complexity of the two natural planning objectives, the number of terms to a degree and the total credit load, and we isolate the structural commitment responsible for each source of hardness. Time to degree is polynomial whenever the per-term capacity is unbounded, for arbitrary disjunctive prerequisites and arbitrary electives, so disjunction never contributes to its hardness, yet it becomes strongly NP-hard as soon as capacity binds, even without any prerequisite. Load is complementary: disjunction and overlapping electives are each strongly NP-hard in isolation and their complexity does not depend on capacity, while load is polynomial on the conjunctive, mandatory fragment. The two objectives therefore have disjoint sources of hardness. We show that the delay-factor component of the standard curricular-complexity metric is a polynomially computable upper bound on time to degree, exact on the conjunctive fragment and loose elsewhere by a quantity we name the disjunctive slack, and we prove that program subsumption is coNP-complete and consensus prerequisite recovery is NP-complete. Instantiating the model on a corpus of twenty-two universities, we find that 88 percent of prerequisite-bearing courses are purely conjunctive and that capacity, not prerequisite logic, is the operative constraint on time to degree. The curriculum corpus is openly available (doi.org/10.5281/zenodo.22334674), and the analysis and figure-generation code accompany the paper.Authors: Dylan Herman, Jacob Watkins, Guneykan Ozgul, Jiayu Shen, Brandon Augustino, Junhyung Lyle Kim, Shouvanik Chakrabarti
We investigate algorithms for the quantum simulation of the Schrödinger equation on a Riemannian manifold, where the kinetic operator is defined by the Laplace--Beltrami operator corresponding to the metric. Our first algorithms are based on a global spectral method based on the identification of an efficient transform to the eigenbasis of the Laplace--Beltrami operator. We use this method to provide explicit, efficient, quantum simulation algorithms for the Riemannian Schrödinger equation on tori and spheres with their standard metrics, simplices with the Wright--Fisher metric, truncated positive orthants and their invertible affine images with the log-barrier Hessian metric, and $\ell_p$ balls with a metric induced by the Duffy map. Our second algorithm is based on a coherent simulation of local spectral methods on multiple charts, and is in principle applicable to any compact manifold. We first analyze this algorithm in the continuum and derive conditions under which a polynomial spectral cutoff suffices. We also provide a discretization analysis of a polynomial spectral cutoff for tensor-products of constant-dimensional manifolds. Finally, we consider applications of these methods to optimization and physical simulation. For optimization, we provide results including a generalization and convergence analysis of Quantum Hamiltonian Descent for geodesically convex functions that leads to explicit algorithms on the sphere and simplex, and a Riemannian generalization of the Real-Space Adiabatic Algorithm. For physical simulation, we show that our algorithms can simulate certain spatially discretized field theories, including a variant of the nonlinear sigma model.Authors: Shuchi Chawla, Trung Dang
We study single-sample prophet inequalities for online combinatorial allocation. Our main contribution is a general reduction from combinatorial to single-item prophet inequalities for valuation classes admitting suitable supporting prices. The reduction uses a free-disposal value to separate buyer-side combinatorial constraints from item-side supply constraints, yielding a modular framework that applies in the stronger Game of Googol model. This framework yields a $\frac{1}{6\sqrt{3}}\approx\frac{1}{10.4}$-competitive single-sample prophet inequality and a $(β_{k-1}/4)$-competitive $k$-sample prophet inequality for XOS valuations, where $β_k$ is the competitive ratio of a $k$-sample single-item prophet inequality, improving upon the work of [DKL+24]. Both results extend directly to divisible resources with capped-XOS valuations. Along the way, we obtain new results for online free disposal and an optimal single-sample prophet inequality for fractional knapsack in the Game of Googol model.Authors: Peter Kiss, Arash Kooroshnezhad
We give a sublinear-time algorithm for estimating the size of a maximal independent set in a graph using adjacency-query access with expected running time $\tilde{O}(n^{1+1/3})$, improving over the previous $\tilde{O}(n^{1+1/2})$ bound of Mahadabi et al. [MRTV26]. As a consequence of a reduction of [MRTV26], this also improves the running time for sublinear metric Steiner forest. We further show that a bi-criteria estimate of the $k$-center objective in general metrics can be obtained via a reduction to maximal independent set size estimation.Authors: Anupam Prakash, Shree Hari Sureshbabu, Dylan Herman, Shouvanik Chakrabarti
A quantum orthogonal polynomial transform (QOPT) is an algorithmic primitive that maps a superposition of standard basis states $\sum_k α_{k} \ket{k}$ coherently to a basis of normalized univariate polynomials orthogonal with respect to a probability measure $μ(x)$. We provide new discrete and continuous QOPTs for polynomial families in the Askey scheme extending the results for the quantum Hermite transform (Jain et al., STOC'26). Our efficient QOPT algorithms require time $O(\text{polylog}(N, 1/ε))$, where $N$ is the grid size and $ε$ is the error, for the discrete Charlier, Meixner and Krawtchouk transforms and for the integer-order Laguerre transform in the continuous setting. The efficient QOPTs are obtained by uncovering the links between Askey scheme polynomials and Gaussian quantum optical gates and developing a compilation framework for $SU(2)$ and $SU(1,1)$ optical gates on Cartesian grids extending the framework developed by Iyer et al. (arXiv:2602.15180). Further, we reduce the continuous Jacobi transform to the discrete Hahn transform and provide an $O\!\left(N\operatorname{polylog}((N+α+β+1)/ε)\right)$-time Hahn transform, a quadratic speedup over the naive implementation. This is based on a more efficient compilation of the Clebsch--Gordan transform for coupling $\mathrm{SU}(2)$ representations with spins $(j_{1}, j_{2})$. Finally, we develop a new framework for Laguerre transforms for all orders $ν>0$ by fast-forwarding the corresponding radial oscillator using a 3-term chirp decomposition and an efficient algorithm for the Quantum Hankel Transform on a logarithmic grid.Authors: El-Mehdi Mehiri, Nabil Absi, Elodie Suzanne
Why are some dynamic lot-sizing problems polynomial? We address this question by introducing Grid Theory, a structural framework based on cumulative production and the additive structure of production bounds. For a general single-item dynamic lot-sizing model with lower and upper production bounds, there exists an optimal extreme solution in which, within each regeneration interval, all but at most one production quantity lie on a boundary value. This induces additive grids, and the Main Grid Theorem establishes that an optimal cumulative production trajectory can be restricted to these discrete sets. Although the resulting grids may be exponentially large, we introduce the notion of additive dimension to capture production-bound profiles whose boundary sums admit a low-dimensional representation. We show that bounded additive dimension yields a polynomially constructible grid envelope and a polynomial time grid-based dynamic programming algorithm. The framework extends to separable concave costs and establishes polynomial solvability of several families, including constant capacities, minimum order quantities, a fixed number of capacity levels, fixed-degree polynomial capacities, periodic capacities, and piecewise polynomial capacities. In particular, polynomiality may hold even when the number of distinct capacity values grows with the planning horizon. Grid Theory thus identifies additive structure, rather than the number of distinct resource values, as a sufficient mechanism for polynomial solvability.Authors: Yash Khanna
In network speed scaling, jobs arrive over time at a network of servers whose speeds can be tuned, every job must be processed by the servers along one of its allowed routes, and the goal is to minimize the total flow time plus the total energy. For stochastic arrivals, the competitive ratio of Vaze and Nair depends on the network, through the lengths of the routes it uses. We show that this dependence can be removed: we give an algorithm, which routes the jobs by solving a convex program and runs every server at a fixed speed, whose competitive ratio depends only on the power functions; for $P(s)=s^2$, it is at most the golden ratio $\varphi\approx1.618$. The key idea is a lower bound on the optimal cost which, like the cost of our algorithm, is a sum over the servers of a function of each server's load, so the analysis reduces to a single server. We also show that the routing rule of Vaze and Nair can be a factor $Ω(L)$ away from optimal, where $L$ is the length of the longest route.from CCI: jobs
The School of Computer Science at McGill University (Montreal, Canada) invites applications for a tenure-track appointment at the rank of Assistant Professor. We are seeking candidates with a PhD (or close to finishing) in Computer Science and expertise at the intersection of quantum computing and computer science.
Website: https://mcgill.wd3.myworkdayjobs.com/en-US/McGill_Careers/job/Tenure-Track-Faculty-Position-in-Computer-Science–Quantum-Computing_JR0000080250
Email: brigitte.pientka@mcgill.ca
from Scott Aaronson
This semester, I’ve been teaching a brand-new course, entitled CS395T AI Alignment Theory. Here’s the course description:
The astounding progress of AI over the past decade has been accompanied by a rising fear: do we really understand how to align and control powerful AI systems—how to get them reliably to do what we wanted, or would want them to do on reflection, rather than merely what we said? If we succeed at building general-purpose superhuman intelligences along the current paradigm, should we expect that development to go well for humanity? Can we modify the design, training, monitoring, or scaffolding of those intelligences to help ensure that it goes well? While there’s been a great deal of recent empirical work touching on these questions, this course will concentrate mainly on theoretical and mathematical foundations. As a warning, the theoretical foundations of AI alignment have not yet gelled into any one coherent body of results accepted as canonical by the field. Nevertheless, in this course, we’ll read and debate many of the conceptual and mathematical works that have been most influential in the AI alignment field, from both before and during the current LLM revolution. Student presentations, reports, and projects will play a central role.
I vividly remember encountering Eliezer Yudkowsky and his Sequences 20 years ago. I remember thinking: even if these people talk and act like crazy cultists, still, let me bend over backwards to be epistemically virtuous, and entertain their ideas on their merits, as very few academics would. Even if, of course, I ultimately end up rejecting the ideas, on the simple ground that powerful AI is such an absurdly remote prospect that it’s almost impossible to say anything useful about it today, outside the realm of speculative fiction.
For my failure to see what was coming, it seems like an appropriate punishment that I’m now, in 2026, effectively teaching a course on Yudkowsky Studies. And it’s the most important course I can teach.
Well, for some definition of “teach.” The thing about AI alignment is that there’s no textbook (though apparently ILIAD is working on one), no core of nontrivial theorems considered canonical by the field, no real body of mathematical theory at all. This makes it extremely different from the courses I’m used to teaching, like Quantum Information Science or Computability and Complexity.
So we’ve been running the course as a discussion seminar. Every session, a “rapporteur” presents an AI alignment research paper or other reading; then I and others ask questions and discuss. Some of the readings (like Omohundro on the “basic AI drives,” or Hadfield-Menell et al. on the off-switch game) predate the current LLM revolution, while others (like the METR report on the HuggingFace incident or Dario Amodei’s “We Must Pace the Frontier”) are so timely that they were only released while the course was underway. Most are somewhere in between.
I expected to have to make a case to students about why AI alignment is a pressing concern, why it’s no longer science fiction, etc. There was huge demand for the course, and while of course there’s a selection effect, the students who’ve shown up have been extremely engaged, sometimes criticizing the assigned papers for not taking existential risk seriously enough.
Perhaps unsurprisingly, we didn’t get that criticism about our very first assigned reading, which was Eliezer Yudkowsky’s 2022 essay AGI Ruin: A List of Lethalities—one the most canonical statements of what Eliezer believes and why that’s shorter than a book. Which brings me to the topic of the rest of this post! Our rapporteurs are not merely presenting the papers in class; they’re also submitting written reports about what the papers said, what their own thoughts were, and what were the highlights of the class discussion. And, with student permission, I’ll be sharing those reports on this blog!
So, without further ado, I present to you our first report, on Eliezer’s list of lethalities, by Tennyson Bardwell, who I thank for his work. Feel free to discuss in the comment section; some of the students might also chime in. Expect more reports here over the coming weeks.
“AGI Ruin: A List of Lethalities” by Eliezer Yudkowsky: Rapporteur Report by Tennyson BardwellUT Austin has a new Computer Science course this fall. Alongside familiar graduate-level classes such as Advanced Computer Networks and Convex Optimization sits CS 395T: AI Alignment Theory, taught by Scott Aaronson. This is one of a growing number of AI Alignment courses taught at academic institutions. Just as concerns over catastrophic consequences for misaligned AGI systems reach a broader public discourse, Eliezer Yudkowsky—one of the loudest voices in the field and author of the first assigned reading in Professor Aaronson’s course—is declaring the cause hopeless.
Thus, the students of AI Alignment Theory began their semester by reading a laundry list of critical problems in AI Alignment research, how failure to solve those problems will result in catastrophic consequences, and the reasons to be pessimistic about both past and future progress on these problems. The essay by Eliezer, titled AGI Ruin: A List of Lethalities and posted to his popular community-driven website LessWrong in 2022, is divided into three sections.
Section A roughly describes the magnitude of the AI Alignment problem. That is, the magnitude of the consequences for a complete failure to align an AGI system to human values before construction. It posits that AGI would quickly catch up to all human knowledge simply by learning from existing human productions (colloquially referred to as “eating the internet”) and then, nearly as quickly, begin to meaningfully surpass human knowledge. AlphaGo Zero is presented as a model both for how this might happen, and how it might be difficult to correctly predict beforehand. Many believed that AlphaGo’s success in the board game Go was chiefly attributed to its ability to learn from the extensive history of human-played games. Less than a year after AlphaGo beat the best human player, the successor system AlphaGo Zero surpassed the original AlphaGo. Unlike its predecessor, AlphaGo Zero was trained in just three days by exclusively playing against itself without seeing a single human game.
This quick ramp from AGI to super-intelligence would pose a different sort of problem than humans are generally used to dealing with. Unlike traditional problems in science and engineering, the consequence for a failed attempt might not leave room for another try. An intelligent entity with a misaligned goal would be well aware that it stands in opposition to humans, and might act deceitfully until in a position to act openly against humans without jeopardizing its own survival. Since most goals benefit from control of power and resources, it seems likely that nearly any goal-driven intelligence would have ample opportunity to be misaligned with human desires.
Section B describes reasons why, by default, any AGI that humans build using current methods is likely to be unaligned even if considerable attention is paid to the topic. This “current method” is gradient descent. That is, incremental progress with respect to some loss function which “punishes” a model for undesirable behavior. A notoriously elusive property of such trained models is the ability to generalize out of their training distributions. To train a primitive model to be aligned to humans might involve learning a great many behavioral rules. However, the sorts of rules needed to keep a drastically smarter agent in check might not always be relevant to simpler models (e.g., “do not emotionally dysregulate humans you speak with” might not be relevant to a simpler model that is less able to reliably get under the skin of humans it operates with, or which is assigned tasks in training which do not benefit from such anti-social behavior).
Eliezer focuses on the misalignment of humans with their creators (evolution or evolutionary pressures) as a critical data point for reasoning about misaligned intelligent systems. Despite being a generally slow process, evolution eventually created a runaway intelligent system (Homo sapiens) which proceeded to dominate the globe, decimate related species, and eventually (it is forecasted) effectuate population decline. That last development is arguably in opposition to the sole imperative demanded by evolution: to reproduce.
Section B also makes time for criticism of the most popular paths toward AI alignment, including interpretability (unworkable, and attempting to train on it evokes Goodhart’s law, incentivizing deceit), using multiple AIs to maintain a balance of power (it is not clear how multiple strong AIs unaligned with humanity results in better outcomes for the weak humans), and corrigibility (it seems impossible to motivate an AI system to effect outcomes without also motivating it to desire its own survival to effectuate said outcomes).
Section C describes a bleak state of affairs in which veterans in AI alignment are unsatisfied with current progress and do not have a plan to deliver tangible solutions before the advent of AGI systems. In particular, Eliezer describes recent results as showy but useless. He believes that even with additional funding, the lack of appropriate evaluation mechanisms will prevent the most effective researchers from rising to the top.
A summary of the landscape, as described by Eliezer, in the flowchart below.
Figure 1: A flow chart of (select) paths described by Eliezer in his essay. A common feature of this flow chart is that many “good states”—such as disabling a misbehaving AGI or choosing not to build an AGI—are not “final” states in the sense that they are not permanent solutions. Such a state merely represent the avoidance of a single potential disaster, rather than the emergence of a new stable world state. Hence, these nodes posses back-arrows.
Despite the bleak content, Eliezer’s colorful prose inspired a lively class discussion. Before this discussion started, a survey was taken of the class’s predictions for various outcomes of the AGI in the coming years (with the full results below in figure 2). This survey asked students for their opinion of a number of statements. Each of these individual statement, if true, would reduce concerns of catastrophic AI-driven disasters. For example, when asked “How much do you agree with the statement: Humans will choose to not build AGI” half of respondents said they strongly disagreed with high confidence (agreement = 1, confidence = 5). Students also generally disagreed with the statements:
There was a divergence in responses regarding interpretability, corrigibility, and “other” AI alignment research. In the latter two cases, a plurality of respondents (about a quarter) agreed strongly with statements that such research would defang AGI (agreement = 4, confidence=4), while most other responses express various levels of agreement with low confidence. However, when asked about the likelihood of interpretability research defanging AI, the pessimistic voices were more united. A quarter of responses still expressed the same optimism, but roughly half expressed pessimism (agreement ≤ 2) with half of those expressing at least moderate confidence (confidence ≥ 4). Based on the following discussion, this might have been caused by more familiarity with interpretability research, including first-hand experience.
The only statement with general agreement was “(hyper-)AGI will understand human intentions better than we can code it.” However, it should be noted that no statement such as “AGI will respect human desires, as it understand them” was asked on the survey.
Figure 2: Class Survey Results; conducted before a class-wide discussion. Note that students were instructed to answer confidence = 1 when they had not previously considered the statement, to answer confidence = 3 when they felt there were strong arguments on both sides, and to answer confidence = 5 when they possessed well-considered resolve.
After the survey was completed, the results were displayed as an open discussion began. Similar to recent empirical research from frontier labs, interpretability research received more airtime than in Eliezer’s article. Students disagreed first about the definition of interpretability: whether it refers to the ability to interpret a model’s behavior solely by its weights, to interpration via repeated probing of the model in a sandbox, or whether it can also refer to the modern chain-of-thought traces. Regardless of how it was defined, however, participants were either pessimistic or very pessimistic about interpretability research broadly. One student criticized common misunderstandings of chain of thought. Rather than being a verbatim copy of the models internal dialog, it is instead a superficial summary of the complete thought state and routinely produced gibberish, such as rarely used Chinese characters in the middle of otherwise English reasoning.
A popular topic was the exact shape and speed of a recursive self-improvement loop. If it takes place slowly, then what might we learn from “near misses” such as the Hugging Face incident? The number of near misses we are able to learn from before AI possesses sufficient power to prevent further iterations could depend on this curve, with some students arguing that the sheer number of humans, as well as their default robustness in the physical world compared to AI systems means that AI-driven extinction events are still a long way off. Bolstering this “slow take-off” opinion are rumors that AI already plays a major role in model development which could be interpreted as the start of this process.
Some criticized a focus on “solving ethics” as a needlessly high bar that distracts from the more mundane tasks dominating AI alignment work. In particular, the student volunteer who presented this paper (and the author of this report) included a section on “Ethical Dilemmas” in their presentation. Among arguments against focusing on abstract moral philosophy, Professor Aaronson cites Eliezer to emphasize that any alignment at all is difficult, not just in morally gray cases:
When I say that alignment is difficult, I mean that in practice, using the techniques we actually have, “please don’t disassemble literally everyone with probability roughly 1” is an overly large ask that we are not on course to get.
In response, I argue that some examination of everyday decisions with a critical lens—such as telling white lies to loved ones or consuming animal products—can help disabuse us of the notion that goodness emerges in every sufficiently intelligent agent.
One of the most interesting discussions was about the difference between state-of-the-art LLMs and the theorized AI agents long discussed in rationalist discourse. Since current LLMs “mimic the human distribution,” they come preloaded with extensive understanding of human social norms and moral behavior. This makes constitutional alignment (the current practices of using system prompts to establish ground rules) extremely effective. This might either fundamentally change the orthogonality thesis, or provide a new tool to better approximate human judgment in complicated situations.
Of all the points made, the one I found most interesting was simply (paraphrased):
I think human-alignment is just very tractable
Here, “human-alignment” refers not to AI alignment with human values, but cooperation between different humans. More specifically, it refers to the ability for human societies to choose not to rush recklessly into larger-and-larger AI systems. In an academic course focused on the technical problem of AI alignment, this was a reminder to not completely discard policy discussions in the believe that they lack any value. After all, many destructive technologies have been previously contained by international agreements. Notable examples include nuclear weapons and engineered plagues. However, even this was a contentious topic. The main criticisms were (1) the extreme “dual-use” nature of AIs for both peaceful growth and warfare, and (2) the greater danger for AI escapes even after taking precautions to prevent it. However, in the interest of ending on an optimistic note—unlike the assigned reading—it is on this belief in human cooperation that I will leave you.
(This was written about 9 months ago. Its not out of date... yet)
People think that AI is going to DESTROY some jobs and CREATE some jobs. It may be too early to tell if this is true. Even so, here are some thoughts.
1) Who will win? Who will lose?
2) Historically in the long term society was better off after a tech change (e.g., we live longer now than we did in the farm-era). Will that happen here as well?
3) We have some sense of what kinds of jobs will be destroyed. But what kind will be created? Will they be interesting? See later in this blog for a job you might not have thought of.
4) Many jobs will change. If you are over X years old then think about how much technology has changed your job even before the AI revolution. (The value of X may vary depending on how high-tech you are.)
For an intelligent view of the questions above, see here.
For my view of one aspect of this, read on.
There is one job which has been either created or expanded by AI:
Annotator.
(See here for an ARTICLE about these jobs, from which I got most of the rest of this post. The word ARTICLE is in caps so when I refer to it later you'll know what I am referring to.)
The job consists of looking at pictures and labeling things.
Here is a direct quote from the manual:
LABEL real items that can be worn by real people.
Does Lady Gaga count as a real person? She sometimes wears dresses made of meat. Should that count? See here for a real article about her and see here for the Weird Al parody of Born that Way. Note that this is Weird AL, not Weird Artificial Intelligence. (See here for the Weird AI for Weird AL problem.)
They do this to create data for AI.
a) The jobs don't pay well though there are some exceptions.
b) The jobs are boring though there are some exceptions (and that may depend on the worker).
c) This job is needed because AI keeps running into edge cases. This may have happened with AI's attempts to solve my GROUP ONE-GROUP TWO prez-VP problem from a prior blog post here or my baseball-brother-pitchers post here.
c) KEY: People in AI used to think this is a temporary thing and these jobs will soon be automated. This might not be the case. There are SO MANY edge cases that AI encounters. The more we expect from AI the more edge cases there will be.
A quote from page 26 (of the ARTICLE pointed to above) which is informative if you can parse it. I think.
Put another way, ChatGPT seems so human because it was trained by an AI that was mimicking humans who were rating an AI that was mimicking humans who were pretending to be a better version of an AI that was trained on human writing.
By gasarch
(This was written about 9 months ago. Its not out of date... yet)
People think that AI is going to DESTROY some jobs and CREATE some jobs. It may be too early to tell if this is true. Even so, here are some thoughts.
1) Who will win? Who will lose?
2) Historically in the long term society was better off after a tech change (e.g., we live longer now than we did in the farm-era). Will that happen here as well?
3) We have some sense of what kinds of jobs will be destroyed. But what kind will be created? Will they be interesting? See later in this blog for a job you might not have thought of.
4) Many jobs will change. If you are over X years old then think about how much technology has changed your job even before the AI revolution. (The value of X may vary depending on how high-tech you are.)
For an intelligent view of the questions above, see here.
For my view of one aspect of this, read on.
There is one job which has been either created or expanded by AI:
Annotator.
(See here for an ARTICLE about these jobs, from which I got most of the rest of this post. The word ARTICLE is in caps so when I refer to it later you'll know what I am referring to.)
The job consists of looking at pictures and labeling things.
Here is a direct quote from the manual:
LABEL real items that can be worn by real people.
Does Lady Gaga count as a real person? She sometimes wears dresses made of meat. Should that count? See here for a real article about her and see here for the Weird Al parody of Born that Way. Note that this is Weird AL, not Weird Artificial Intelligence. (See here for the Weird AI for Weird AL problem.)
They do this to create data for AI.
a) The jobs don't pay well though there are some exceptions.
b) The jobs are boring though there are some exceptions (and that may depend on the worker).
c) This job is needed because AI keeps running into edge cases. This may have happened with AI's attempts to solve my GROUP ONE-GROUP TWO prez-VP problem from a prior blog post here or my baseball-brother-pitchers post here.
c) KEY: People in AI used to think this is a temporary thing and these jobs will soon be automated. This might not be the case. There are SO MANY edge cases that AI encounters. The more we expect from AI the more edge cases there will be.
A quote from page 26 (of the ARTICLE pointed to above) which is informative if you can parse it. I think.
Put another way, ChatGPT seems so human because it was trained by an AI that was mimicking humans who were rating an AI that was mimicking humans who were pretending to be a better version of an AI that was trained on human writing.
from ECCC Papers
from CCI: jobs
U. Colorado Boulder CS seeks applications for a TT Asst. Prof. position in Quantum Computation. We invite applications from all areas of QC; priority consideration will be given to:
– Quantum computation theory: quantum algorithms, quantum complexity, quantum information, & quantum error correcting codes
– Applications of QC to important or emerging areas such as quantum optimization & quantum ML
Website: https://jobs.colorado.edu/jobs/JobDetail/Tenure-Track-Faculty-in-Quantum-Computation/74741
Email: jgrochow@colorado.edu
from Gil Kalai
My host at Brown University was the fascinating Basilis Gidas whom I first met in Rio in 2018. Basilis has had a remarkable career, taking him from electrical and mechanical engineering through quantum field theory to many areas of applied mathematics. In the context of AI, Basilis told me about a well-known passage in Plato—new to me—expressing concern that reliance on writing (new technology at the time) would weaken human memory. Overall, Basilis thinks that the most creative aspects of mathematics will remain human.
I had a wonderful and very intense time in Providence, where I gave an applied mathematics colloquium on my work on quantum computing. During my visit, I met and talked with quite a few mathematicians, chemists, physicists, computer scientists, and an economist Oded Galor.
Regarding quantum computation, I heard many excellent new questions about my point of view (I have collected earlier questions in this post), and learned about topics in chemistry and physics closely related to my work. I still have quite a bit to digest from these conversations. I also had a lovely dinner discussion about the notorious “measurement problem.”
Here are the slides of my talk: The Quantum Computer – A Miracle or Mirage.
The talk has five parts, and the audience and I concentrated on the second, devoted to my conjectures on correlated errors.
A few days ago I uploaded to the arXiv my paper The Fully Depolarizing Noise Conjecture for Entangled Physical States: A Twenty-Year Perspective, that is going to appear in: Fields of Logic and Computation IV: Essays dedicated to Yuri Gurevich, editted by: Guillermo Badia, Manfred Droste, Andreas Blass, and Nachum Dershowitz. (I noticed two even newer papers on the arXiv, on quantum cryptography by Yael Kalai!)
Of course, I also learned about advances in computer science and mathematics close to my other interests, heard new perspectives on the AI revolution in mathematics and the emotions it evokes, reconnected with old friends, and made some new ones. Let me mention Eli Upfal, now a distinguished computer scientist. Eli and I were graduate students at HUJI at the same time (he studied with Eli Shamir), and I had not seen him for several decades.
Greetings from Boston! For those who attended my talk here on “algebraic shifting,” here are the handouts. (There were not enough copies for everybody.) I plan to return to my Boston visit and to algebraic shifting a little later.
A bit of nostalgia: Providence was the first US city I set foot in, in 1978. It was my first trip outside Israel: I spent two weeks at a summer school in Montreal, then got a lift to Providence, where I took a bus to Boston. My hosts in Boston, Israeli sailing champions, took me sailing on the (then polluted) Charles River. They invited me to take the helm, and shortly afterward we all found ourselves in the water.
from ECCC Papers
from CCI: jobs
Max Planck Institute for Informatics (Saarbrücken) seeks Postdocs and Group Leaders in Algorithms & Complexity and related areas. Flexible start dates; strong research environment and travel support. Apply by 15 Dec 2026 with CV, publications, research plan, and 3 references.
Website: https://www.mpi-inf.mpg.de/d1/offers/postdoc
Email: join-d1@mpi-inf.mpg.de
from ECCC Papers
from ECCC Papers
from ECCC Papers
from ECCC Papers
Authors: Omar Al-Ghattas, David Gamarnik, Bobak T Kiani
We introduce a method for studying state preparation complexity in dense quantum $p$-spin Hamiltonians on $n$ qubits, going beyond bounds based only on circuit lightcones. The key input is the class's effective profile complexity, which is derived from the metric entropy of its Pauli profiles. These profiles record expectations of all Pauli operators supported on exactly $p$ qubits. Classes with uniformly bounded quadratic effective profile complexity remain separated from the ground-state energy by a positive multiple of $\sqrt n$ for sufficiently large fixed $p$. At subquadratic effective profile complexity, the class cannot outperform a suitable benchmark class at leading order, with product states providing a universal benchmark. The proof combines an adaptation of a nonsymmetric quantum de Finetti theorem of Berta et al. (arXiv:1810.12197) with Gaussian process entropy bounds. Applying this framework, we show that attaining near-ground-state energy requires $Ω(n^2/\log n)$ one- and two-qubit gates, even with arbitrary discardable ancillas. We also obtain depth-width tradeoffs, entanglement-depth and matrix product state bond-dimension lower bounds, and obstructions for both orientations at every fixed level of Parham's magic hierarchy (arXiv:2504.19966), with total circuit width $O(n)$. In first-level reverse magic, a shallow circuit is followed by an unrestricted Clifford circuit. The latter can spread local observables across the system, preventing a direct application of small-lightcone bounds. For this first-level class, our bounds also allow arbitrarily many clean ancillas at fixed shallow-circuit depth. A sharper benchmark shows that Clifford+$T$ circuits with $o(n)$ $T$-gates have no leading-order energy advantage over product stabilizer states, even with unrestricted Clifford operations and arbitrary discardable ancillas.Authors: Daniel Grier, Jackson Morris, Kewen Wu
In this work we study the robustness of $\mathsf{QAC}^0$ with respect to error tolerance and modifications to its gate-set. First, we investigate whether the non-zero error typically allowed for $\mathsf{QAC}^0$ circuits computing Boolean functions is truly necessary. We show that the error inherent in the parallel $W$-test of \cite{grier_morris_wu} can be eliminated entirely via a novel application of exact amplitude amplification in the many-copies context. Consequently, we find that $\mathsf{QAC}^0$ can \textit{exactly} simulate $\mathsf{TC}^0$ with polynomially many copies of the classical input and that for every fixed prime $p$ exact $\mathsf{QAC}^0$, $\mathsf{EQAC}^0$, can compute total Boolean functions outside of $\mathsf{AC}^0[p]$. Second, we ask to what extent the computational power of $\mathsf{QAC}^0$ follows from the fact that arbitrary single-qubit gates may be used at any point in the circuit. We find that $\mathsf{QAC}^0$ is in fact robust to restrictions on which single-qubit gates are permitted: every $\mathsf{QAC}^0$ circuit can be approximately implemented by a $\mathsf{QAC}^0$ circuit consisting of just generalized Toffoli, $S$, and Hadamard gates. Moreover, this approximating circuit can be constructed efficiently from a classical description of the original circuit.Authors: Benoît Dubus, Julien Ladeuze, Jérémie Roland
Transducers (Belovs, Jeffery and Yolcu, 2024) are a quantum computing framework describing a quantum algorithm as a unitary converting an input state into a target state using a catalyst, an auxiliary vector that is left unchanged. They are a powerful tool in quantum algorithm design, especially in the context of quantum query complexity: feasible points of the (dual) adversary semidefinite program directly translate into transducers and the optimal transduction complexity is equal to the adversary bound, i.e. the Las Vegas complexity, which is known to characterize bounded-error quantum query complexity. Moreover, contrary to bounded-error algorithms, transducers compose exactly, which limits overheads due to controlling errors in algorithms constructed by composition. Constructing efficient, let alone optimal, transducers in terms of quantum query complexity nevertheless remains a hard task since it still requires solving the adversary SDP and constructing the unitary to obtain an explicit algorithm. In this paper, we show how using the symmetry group of state-conversion problems simplifies both steps. First, using a symmetrization argument, we prove an optimal catalyst can always be chosen covariant under a representation of the symmetry group. Second, we prove that the transducer intertwines two different representations of the group and can thus be chosen block diagonal in the isotypic decomposition of the Hilbert space. Using those methods, we then derive optimal transducers, with optimal constants, for different widely used quantum algorithmic primitives, such as unstructured search, amplitude amplification and amplitude estimation. Our approach extends previous work on the use of representation theory to compute adversary lower bounds (Høyer, Lee, and {\v S}palek, 2007; Ambainis, Magnin, Roetteler and Roland, 2011) to the systematic construction of optimal algorithms.Authors: Shaowei Cai, Ziqun Li
It is an open problem in proof complexity whether every unsatisfiable CNF formula has an FPT-sized resolution refutation parameterized by incidence treewidth. In this paper, we establish several upper bounds on resolution refutation length related to this problem. Consider an unsatisfiable CNF formula $F$ with $n$ variables, $m$ clauses, maximum clause width $k$, and incidence treewidth $\mathrm{tw}^*(F)$. In this paper, we introduce two variants of incidence treewidth. Their definitions can be stated informally as follows. The first is log-weighted incidence treewidth $\mathrm{tw}_{\log}^*(F)$, which is the treewidth of the weighted incidence graph, in which variables have weight one and each clause has weight equal to the logarithm of its width. The second is partially log-weighted incidence treewidth $\mathrm{tw}^*_{\mathrm{plog}}(F)$, which is a refinement of log-weighted incidence treewidth. In this variant, for a nice tree decomposition of the incidence graph, each clause has weight one along a path selected for that clause and elsewhere has weight equal to the logarithm of one plus the number of its literals whose variables do not appear in any bag on that path, and variables have weight one. For every unsatisfiable CNF formula $F$, we prove the existence of (i) an FPT-sized resolution refutation parameterized by log-weighted incidence treewidth, with width at most $\mathrm{tw}_{\log}^*(F)+k$; (ii) a resolution refutation of length $(n+m)k^{O(\mathrm{tw}^*(F))}$ and width at most $\mathrm{tw}^*(F)+k$; (iii) an FPT-sized resolution refutation parameterized by partially log-weighted incidence treewidth; and (iv) an FPT-sized regular resolution refutation parameterized by log-weighted incidence treewidth. Our main idea is to construct FPT-sized $k$-DNF resolution refutations parameterized by incidence treewidth, and then convert them into resolution refutations.Authors: Alessandro Chiesa, Ziyi Guan, Burcu Yildiz
AI systems increasingly produce outputs from confidential data, such as a fitness-for-duty assessment from medical records or the predicted properties of a drug candidate from its secret structure. It is important to verify that such outputs are correct without revealing the underlying data. A recent line of work studies verification of AI outputs via interactive proofs and debate for oracle-aided computation, where correctness may depend on an oracle such as human judgment, a physical experiment, or the web. These works focus on verification by a verifier that runs much faster than the computation. However, such efficient verification is impossible for general oracle-aided computation, and these works therefore rely on additional assumptions. We focus instead on privacy: allowing the verifier to run in time polynomial in the computation, we ask whether interactive arguments for oracle-aided computation can be zero knowledge, so that the verifier learns nothing about the confidential data beyond the correctness of the output. We prove that, in general, they cannot. In the random oracle model, there are no zero-knowledge proofs for all oracle-aided computations, even if both the prover and the verifier are allowed to run much longer than the computation itself. The impossibility extends to debate, a canonical model for scalable oversight. On the positive side, we show that if the oracle attaches a cryptographic signature to each of its answers, then every oracle-aided computation can be verified in zero knowledge with an efficient prover and verifier, assuming only collision-resistant hash functions. Beyond privacy, this also gives an alternative approach to scalable oversight that relies neither on an honest opponent, as in debate, nor on the robustness of the computation, as in prior single-prover protocols.Authors: Minki Hhan, Hojune Lee
Random Clifford operators have numerous applications in quantum computing, including randomized benchmarking, classical shadows, and quantum authentication. However, sampling and implementing uniformly random $n$-qubit Clifford incur near-quadratic complexity due to the size of Clifford group. We introduce a cryptographic way to overcome these barriers: trapdoored Clifford operator distributions whose samples are computationally indistinguishable from uniformly random Cliffords, yet implementing them can be much faster given the trapdoor. We construct a distribution of trapdoored Clifford operators whose elements can be sampled and implemented in near-linear time under a variant of the learning parity with noise assumption. Our constructions allow fast tableau action on Pauli labels for classical simulation, and also can be optimized to admit polylogarithmic-depth implementation. Along the way, we construct trapdoored matrices over finite fields that support efficient multiplication by both a matrix and its inverse, resolving an open question left by Vaikuntanathan and Zamir [SODA'26]. We use these constructions to obtain faster protocols based on random Cliffords. We also explore their applications to the worst-case to average-case reductions for matrix and Clifford problems including the iterated matrix multiplication and Clifford circuit synthesis. In particular, we show the hardness of batching Clifford circuits: synthesizing circuits that apply the same Clifford to multiple registers is at least as hard as worst-case matrix multiplication, even when synthesis succeeds on a small constant fraction of random Cliffords. This extends to approximate implementations by general quantum circuits.Authors: Isaac Rudich, Louis-Martin Rousseau
Strassen showed that two 2x2 matrices can be multiplied with 7 multiplications instead of 8. Applied recursively, his algorithm multiplies two nxn matrices with O(n^2.807) multiplications, beating the naive O(n^3). The best known 3x3 recursive matrix multiplication algorithm uses 23 multiplications O(n^2.854). The best published lower bound of 21 (on algorithms with integer constants) leaves room for an algorithm with O(n^2.771) multiplications, and thus does not rule out the possibility of an algorithm that would beat Strassen's. We prove a lower bound of 22 multiplications for any 3x3 recursive algorithm with integer constants, proving that no such algorithm can do better than O(n^2.814) multiplications, and eliminating the possibility of a 3x3 algorithm that beats Strassen's 2x2 method. The proof builds on a recent decomposition method from Wang, who approached the problem by turning it into 496 subproblems. We provide exact solutions for 359 of them. The proof is in Lean; verification requires auditing only a few short files. The Lean formalization directly encodes statements about the limitations of recursive algorithms for matrix multiplication, as opposed to just a statement about the rank of the problem.