Theory of Computing Report

We study depth-$5$ algebraic circuits over small finite fields with restricted fan-in of the top product gates. We show that there exists an explicit degree-$d$ polynomial $P(\mathbf{x})$ such that any $\Sigma \Pi^{[\mathrm{poly(d)}]} \Sigma \Pi \Sigma$ circuit, computing $P(\mathbf{x})$, over a small finite field, requires size $2^{\Omega(\sqrt{d})}$. Our work builds upon and strengthens the work of [Kumar-Saptharishi'19], who showed $2^{\Omega(\sqrt{d})}$ lower bounds against $\Sigma \Pi^{[\mathcal{O}(\sqrt{d})]} \Sigma \Pi \Sigma$ circuits over small finite fields. It is known that proving $2^{\omega(d^{1/3} \log n)}$ lower bound for $\Sigma \Pi^{[a]} \Sigma \Pi$ circuits with $a = 2^{\mathcal{O}(d^{1/3} \log d)}$, over fields of characteristic $0$, implies VP $\neq$ VNP. In pursuit of this, we also prove superpolynomial lower bounds over small finite fields for $\Sigma \Pi^{[a]} \Sigma \Pi$ circuits where $a = 2^{\mathcal{O}(d^{\lambda} \log d)}$, for any constant $\lambda < 1/3$. We use evaluations of the shifted partial derivatives to prove our lower bounds. We follow the same outline as [Kumar-Saptharishi'19], but with a more delicate analysis of the complexity measure. We use a family of the Nisan-Wigderson polynomials as a hard polynomial. We show that over small finite fields, setting the parameters of our measure and the hard polynomial with care, the method of shifted partial derivatives can yield lower bounds well beyond the homogeneity restriction on depth-$4$ circuits. We also show an exponential gap between depth-$3$ and homogeneous depth-$4$ circuits over small finite fields. Previously, only a superpolynomial gap was known using [Chillara-Mukhopadhyay'17] and depth reduction of polynomials in VP until homogeneous depth-$4$. We use the complexity measure of [Grigoriev-Karpinski'98], and we use the Product of the Inner Product polynomial to show the separation.

Authors: Dean Doron, Tal Leonov, Jonathan Mosheiff, Henrique Navas, Nicolas Resch, João Ribeiro

We prove that random linear codes have nearly optimal discrepancy properties in a broad range of regimes. Our main results are two general theorems: one controlling all translates of a fixed test, and another controlling large families of Fourier-pseudorandom tests. Two motivating applications follow. First, random linear codes match unstructured random codes for list-decoding from errors above capacity. If $C\subseteq\mathbb F_q^n$ is a random linear code of rate $1-\frac1n\log_q |B_ρ|+ε$, where $B_ρ$ is a radius-$ρ$ Hamming ball, then with high probability $$ |C\cap B|=(1\pm o(1))\frac{|C||B|}{q^n} $$ simultaneously for all radius-$ρ$ Hamming balls $B\subseteq\mathbb F_q^n$. This extends the classical result that such codes have covering radius at most $ρn$ whp (Blinovsky, 1987). Second, over prime fields, random linear codes match unstructured random codes for zero-error list-recovery above capacity. For prime $q>2$ and $2\le \ell\le q-1$, a random linear code of rate $1-\log_q\ell+ε$ satisfies, with high probability, $$ |C\cap S|=(1\pm o(1))\frac{|C|\ell^n}{q^n} $$ simultaneously for all rectangles $S=S_1\times\cdots\times S_n$ with $|S_i|=\ell$. As a consequence, there are abundant $n$-party linear ramp secret sharing schemes over $\mathbb F_q$ with privacy threshold about $n/(2\log q)$ and reconstruction threshold about $5n/(2\log q)$, resilient to balanced local leakage; prior existence results required thresholds above $n/2$ even in this case. The translate result, hence the list-decoding application, holds over arbitrary finite fields, even growing with $n$. The list-recovery and leakage applications hold over prime fields under moderate growth, e.g. $q\le n^{1/5-o(1)}$. The proofs use a refined second-moment analysis tracking intersection sizes as random generators are added to $C$.

Authors: Rosemary U. Adejoh, Andreas Jakoby, Sneha Mohanty, Christian Schindelhauer

We establish that the two-dimensional ray tracing problem with thin lenses and plane mirrors is Turing-complete, thereby resolving an open question posed by Reif et al. in 1994 as to whether three-dimensional space is necessary for computational universality in optical systems. To this end, we consider the standard approximation of reflection and refraction, namely the ABCD model for paraxial optics, which describes ray propagation through lenses (refraction) via a 2 x 2 matrix, combined with the geometric reflection model for plane mirrors. In the absence of mirrors, two-dimensional ray tracing using any combination of lenses in this ABCD matrix model can be described by a single 2 x 2 matrix-vector product, where the matrix has real entries and determinant 1. Conversely, we show that any such matrix with determinant 1 can be represented as a composition of exactly three appropriately spaced thin lenses. When mirrors are combined with lenses, the ray tracing problem can be described by a flowchart using only two variables, which establishes Turing computability for rational-valued inputs, spaces and matrix entries. Building on this observation, we present a construction of ray tracing that simulates a reversible Turing machine. We begin with a restricted version of the reversible flowchart problem, in which only two variables and certain linear functions are permitted. We prove that this restricted variant is Turing-complete. We then show that such a flowchart admits a geometric realization using lenses and mirrors in our model, thereby establishing the main result: Turing-completeness of the two-dimensional ray tracing problem with ABCD-model lenses and mirrors.

Authors: Jie Wang

Wang~\cite{Wang2026} introduced the Stochastic-Oracle Turing Machine (SOTM) framework and defined token complexity as the minimum expected cost of interacting with a stochastic oracle needed to attain a specified solution quality for a task. This paper develops an analogous notion for certifying the reliability of a stochastic oracle on a given domain. Certification token complexity is the minimum expected token cost required, with controlled error probability, to distinguish oracles that meet a target reliability level from those that fall below a lower reliability threshold. We construct an SPRT-based certification SOTM that queries the oracle, computes binary correctness scores, and stops when the accumulated log-likelihood evidence crosses a decision threshold. The SOTM halts almost surely, satisfies the desired two-sided error guarantee over the reliability regions to be certified, and yields an explicit upper bound on certification token complexity in terms of the reliability thresholds, the error bound, and the expected per-turn token cost. We then establish a matching information-theoretic lower bound: even with adaptive queries, every error-bounded certification SOTM must incur the same leading-order expected token cost as the SPRT-based construction as the prescribed error bound tends to zero. Together, these bounds characterize the leading-order certification token complexity in the small-error regime.

Authors: Louis Desruisseaux, Simon Ducharme, Gurleen Padda, Dave Touchette

For many information processing tasks, de Finetti-style theorems can often simplify the analysis in worst-case input scenarios for which the task exhibits some permutation-invariance symmetry, as they can allow for a reduction from an analysis on worst-case inputs to that of i.i.d. inputs. If further information is available on the inputs, it might be advantageous to reflect this information in the de Finetti reduction. In our work, we focus on a form of such constraint, based on the type of the input. This allows us to obtain a conceptually simple proof of a new de Finetti reduction for classical probability distributions, derived from elementary properties from the method of types. We apply our constrained de Finetti reduction to the compression of quantum interactive communication protocols with classical inputs, and prove that the prior-free quantum information cost equals the worst-case input amortized quantum communication cost.

Authors: Fabien Feschet, Jacques-Olivier Lachaud

Full convexity is an interesting alternative to classical digital convexity since it guarantees connectedness and even simple connectedness in digital spaces Z d , for any dimension d. This paper aims at giving a better understanding of the monotonicity properties of fully convex digital sets, since earlier works showed that the question was difficult for thin fully convex sets. To decipher the hierarchy of fully convex sets ordered by inclusion, we study how we can peel a fully convex set progressively while keeping its full convexity. We provide a characterization of peelable points and fast algorithms to identify them. Furthermore we show that fully convex set can be peeled one point at a time till reduced to the empty set, similarly to digitally convex sets in the classical sense. The peeling of a fully convex set can be seen as an analog to homotopic thinning processes, but with an additional geometric property.

Authors: Barbara Giunti, Elizabeth Munch

In this paper, we provide a new construction for studying parameterized persistence, called a canopy. We give two versions of this construction: the A-canopy, retaining all information about points on the diagonal of the persistence diagram; and the D-canopy, encoding the information of the "standard" persistence diagram. We do this by making a simple but major modification in the persistence bundle representation information: namely, rather than tracking a point in the persistence diagram, we instead track some choice of pairs of simplices that created said point. This viewpoint is a combinatorial version of tracking the chain complex information rather than just the output of persistence. We show how to construct the canopies from any filtered filtration function, proving, using the algebraic structure of filtered chain complexes, that different choices of pairs result in homeomorphic structures. Finally, we showcase the power of our approach by using canopies to define vines even in the presence of points with multiplicity; to discuss monodromy; and to obtain some immediate results linking non-trivial monodromy in the persistent homology transform with the existence of non-Hausdorff points in the canopy.

Authors: Sanjeev Khanna, Aaron Putterman, Junkai Song

We settle the classic question of the parallel complexity of computing a matroid basis, as first posed in the seminal work of Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988). Our algorithm runs in $O(n^{1/3}\log^{1/3}n)$ rounds, matching the lower bound of KUW up to a $\log^{2/3}(n)$ factor.

Authors: Juul Sanders, Sebastiaan Brand, Arend-Jan Quist, Tim Coopmans

The decision diagram (DD) data structure enables fast linear-algebra calculations by bringing vectors into a normal form and subsequently merging equivalent ones, yielding a minimally-sized DD modulo the equivalence relation. A fruitful application area is quantum-circuit simulation, where the vectors represent quantum states. The Local Invertible Map Decision Diagram (LIMDD) type, merges LIM-equivalent (typically Pauli-gate equivalent) vectors, can efficiently simulate Clifford circuits as well as some high-T-count circuits, and has theoretically been proven exponentially faster for simulation than other well-developed data structures, including other common DD variants. However, these exponential advantages have not fully materialized yet in existing implementations, for which the normal-form procedure, which is a highly complex algorithm, is either absent or only partially implemented. We here present a novel normal-form algorithm for Pauli-LIMDDs, achieving a worst-case speedup from $O(n^3)$ to $O(n^2)$ for an $n$-qubit DD node with a single child node while keeping the $O(n^3)$ run time in case of two distinct children nodes. We implement the algorithm as part of QolDDer, our Pauli-LIMDD simulator for quantum circuits, written from scratch in C/C++. The implementation realizes the theoretically-proven advantages of Pauli-LIMDDs on Clifford circuits, is significantly faster than the existing LIMDD simulators on such circuits, and on a public quantum-circuit data set often outperforms them by an order of magnitude. In the future, we envision that our work will enable further application and development of LIMDD variants, not only for quantum design tasks, but also for analysis of linear-algebra-based systems in general.

Authors: Nicolas Gast, Bruno Gaujal, Adrien Obrecht

In this paper we consider a M/G/1 queue for which we want to minimize the expected response time. We show how to compute indices from $n$ samples of the job size distribution such that the corresponding index policy is asymptotically optimal as $n$ grows. This construction is based on a discretization of the bounded support of the job size distribution and a shift of the samples to their nearest discrete point to the right. We show that the Gittins index of the empirical distribution of these shifted samples is close to the Gittins index of the original distribution. This translates to the asymptotic optimality of the corresponding index policy for minimizing the expected response time. Numerical comparison with other approaches further confirm the efficiency of our approach.

Authors: Minghao Chen, Jiale Zheng

Spectral filtering recently delivered substantial pruning for \emph{static} subgraph matching: Laplacian interlacing rejects candidates whose neighborhoods cannot host the query. We study whether such aggregate structural tests can accelerate \emph{continuous} subgraph matching (CSM) over dynamic graphs, and answer in three parts. First, lazily maintained spectral bounds are infeasible exactly where spectral pruning has value: we characterize the tightest safe rule over a formalized perturbation relaxation and show that even it loses essentially all pruning power within four touching updates. Second, exact maintenance is affordable when selective: pruning utility and recomputation cost are anti-correlated across vertices -- hubs provably never prune -- so recomputing small-neighborhood spectra on touch sustains exact local spectra at microseconds per update, complete by construction. Third, integrated into a decoupled CSM benchmark against an identical-minus-spectra control, the tests remove up to $51\%$ of candidates or safely skip up to $47\%$ of update enumerations, yet enumeration intermediates remain unchanged -- beyond the gates' skipped first-level bindings, typically zero -- across two engines, four real graphs, two stream types, and $77$ solved queries; a constructed radius-stratified workload confirms the instrument detects the exception when one exists ($-99.9\%$ intermediates, $748\times$ faster). Aggregate tests accelerate what scales with candidate sets -- construction, list scans -- never adjacency-guided exploration. We distill an intermediate-invariance methodology for evaluating CSM filters and release a reusable dynamic local-spectra index.

Authors: Tim Dortmann, Markus Vieth, Bertil Schmidt

Efficient genomic k-mer indexing depends on approximate membership query (AMQ) structures that must deliver high throughput, low false-positive rates (FPR), and modest memory footprints. The Super Bloom filter (SBF) is attractive for this scenario because minimizer-guided sharding and the Findere scheme exploit the redundancy of overlapping k-mers. However, those same features cause high per-k-mer compute cost, severe register pressure, and irregular memory accesses, which hinder an effective GPU implementation. We present cuSBF, an open-source, header-only CUDA library that implements SBF for sequence-native workloads. cuSBF's design merges sectorized shards, cooperative shared-memory tiling, warp-level shard sharing, and segmented warp reductions, turning super-k-mer locality into scalable GPU parallelism. Across real genomic workloads on RTX PRO 6000 Blackwell and GH200 systems, cuSBF achieves the highest throughput among all evaluated sequence-capable baselines. On the RTX PRO 6000, it surpasses the cuCollections blocked Bloom filter baseline by up to 9.1x for insertion and 7.7x for query, while reaching up to 92x and 234x speedups over the multi-threaded CPU Super Bloom reference implementation. It also outperforms GPU-based dynamic AMQs (Cuckoo, Two-Choice, Quotient filters) by 1.5-3400x depending on workload characteristics. A parameter sweep identifies (s = 28, m = 16, H = 4) as Pareto-optimal for k = 31, yielding significantly lower FPR than cuCollections at matched memory budgets. Crucially, cuSBF's architecture-aware design sustains 85% streaming multiprocessor utilization even for out-of-cache filters - proving that sequence locality, not raw bandwidth, is the key to GPU-accelerated genomic indexing.

Authors: Enoch Peserico, Michele Scquizzato

In any real system a newly computed datum begins its existence in the processor rather than in external memory, and thus does not inevitably incur a cold miss. This was captured by early I/O models, but not by the Sleator-Tarjan one that has come to underpin competitive analysis of paging. If one corrects the Sleator-Tarjan model by charging no cost for the first access to newly computed data, optimal offline algorithms such as LFD remain optimal, but no online paging algorithm can be competitive, even if randomized, even with arbitrary resource augmentation, even against request sequences that are not tailored against it but are instead representative of widely used computational techniques. The proofs are simple, and appear robust against any reasonable assumption/model adjustment, including virtually all tools developed to make competitive analysis less pessimistic. In other words, while competitive analysis does predict the good performance exhibited in practice by online paging algorithms such as LRU, these predictions seem just a fortuitous artifact of an incorrect assumption that has crept into the underlying model several decades ago. And there are implications beyond paging, too: for example, the same issue undermines the Ideal Cache model on which the popular Cache-Oblivious and Cache-Adaptive algorithmic frameworks are based.

Authors: Martin Darmüntzel, Christian Rosenke, Mark Scheibner

Flood-It is a single-player game played on a precolored graph $G$, where the objective is to make $G$ monochromatic using as few flooding moves as possible. In each move, a color $c$ is selected and all vertices reachable from a fixed pivot vertex via a monochromatic path are recolored with $c$. In the free variant, the pivot may be chosen anew in every move. Deciding whether a graph can be made monochromatic in at most $k$ moves is NP-complete for both variants, fixed and free. This hardness persists even under strong structural restrictions such as split graphs and trees. The Free Flood-It variant is generally considered more difficult than its fixed-pivot counterpart, as it remains hard on several graph classes where the latter becomes tractable, including co-comparability and AT-free graphs. Cographs, that is, $P_4$-free graphs, are among the few classes on which even Free Flood-It is solvable in polynomial time and therefore serve as our starting point. We consider the ten natural one-vertex extensions of $P_4$ -- referred to as jewels -- and study the complexity of both flooding games on the $1024$ graph classes obtained by forbidding subsets of these graphs as induced subgraphs. Our main contribution is a polynomial-time algorithm for Free Flood-It on graphs that are free of the three jewels bull, gem, and $P_5$, covering $128$ of the $1024$ classes. In addition, we prove that both variants remain NP-complete on thin-spider graphs, which exclude the eight jewels banner, co-banner, chair, gem, house, kite, $P_5$, and $C_5$, thereby establishing hardness for $256$ additional classes. Combined with known algorithms and hardness results, our work determines the complexity of both Flood-It variants for $896$ of the $1024$ considered graph classes.

David Richter, a mathematician at Western Michigan University, recently found himself with a surfeit of ceramic orthogonal polyhedra and, knowing of my own interest in orthogonal polyhedra, generously offloaded two of them to me. They fit nicely in my office together with the paper and crochet orthogonal polyhedra I already had:

The blue one is an orthogonal realization of Boy’s surface, an immersion of the projective plane into three-dimensional space with three-way symmetry and a single triple crossing point. The idea to make an orthogonal version comes from Jean Pierre Petit’s Le Topologicon, where its relation to the usual curved version can maybe be seen more clearly than in my photographs.

The model hides a hidden graph embedding: the uncolored edges form the boundaries of a hemi-dodecahedron, an embedding of the Petersen graph with six pentagonal faces, each adjacent to all five others.

The other ceramic model, colored yellow, green, and red, is an orthogonal realization of the permutohedron or, almost the same thing, the Cayley graph of the four-element symmetric group generated by the three swaps of consecutive elements. Abstractly, it’s the same embedded graph as the paper kirigami model behind it in the family portrait, which I constructed and wrote about in 2009, but what this one loses in orthogonal nonconvexity it makes up for in bilateral symmetry.

Here are a few more views of it:

When viewed top-down their shapes almost look like writing to me. You can see a signature and date in the hollow of the Boy’s surface.

Richter also has a couple of papers on orthogonal polyhedra: “Generic Orthotopes” (arXiv:2210.12012) and “Ehrhart Polynomials of Generic Orthotopes” (arXiv:2309.09026).

(Discuss on Mastodon)

By David Eppstein

My teacher and friend Dimitri Bertsekas passed away earlier this month. I just learned about this over the weekend, and I’m still processing my thoughts.

Dimitri was a hero of mine for so many reasons. I took my first and only class on optimization with him, and I was riveted by his clean presentation of convex analysis and mastery of the overhead projector. He took a liking to me, and I made it a point to find him for a chat whenever I’d visit MIT. He was always generous with his time and excited to exchange ideas, but he wouldn’t hesitate to harshly scold me when I’d present some result new to me that he had in fact written about twenty years earlier.

This was unavoidable because Dimitri did foundational work across mathematical optimization, penning landmark results in stochastic gradient descent, convex optimization, distributed optimization, dynamic programming, and reinforcement learning.

His work in reinforcement learning remains underrated. His collaboration with John Tsitsiklis, compiled in their book Neurodynamic Programming, was the first to show that most reinforcement learning algorithms were effectively approximating dynamic programming. Our contemporary, model-free mindset, rooted in Markov decision processes, derives from these initial insights. As far as actual practice goes, their book is more important to the modern way we implement reinforcement learning than Sutton and Barto’s.

Dimitri was also a passionate mathematical communicator. I own more of his books than any other mathematics researcher, but he wrote more than any other mathematics researcher in my field. Is there too much material? You could make the case! However, that he has definitive texts covering a broad range of optimization theory is remarkable.

In many ways, Dimitri was an original math blogger. He wrote exactly what he wanted to write, and he wrote frequently. He got fed up with publishers getting in the way of his process, so he started his own publishing company, Athena Scientific, shipping stacks of books out of his garage in Belmont, Massachusetts. This allowed him to write countless new editions and revisions of his work, reflecting trends in practice and incorporating new insights and simplified arguments. Though you’ll see plenty of repetition across his volumes, he knew that no book was a final draft. Each volume was a step towards broader understanding.

A decade ago, when he retired from MIT, I wrote a post of appreciation for his scholarly and pedagogical work. I’m going to reprint it here today, as it includes one of my favorite passages in his books about the tension between theory and practice. Right now, in our frenzied agentic era, we’re leaning heavily on only practice and vulgar empiricism to push out as many papers and products as we can before the bubble pops. Is there a role for theory at all anymore?

Dimitri argued that optimization theory is always a mix of qualitative and quantitative. The qualitative helps us understand what we know and don’t know. By gathering feedback from practice and constructing a working narrative, theorists can help engineers develop a language to describe what is possible and what can be improved. Theory provides a narrative scaffolding that helps us understand what to build and what to attend to when things break. Building stories of connections helps us streamline our processes and try things we might not have thought of.

There’s an ebb and flow between the theory and practice. I will revisit this ten years from now and see where the theories land.

Until then, rest in peace, Dimitri. Know you changed the way I think.

The following initially appeared as The Role of Convergence Analysis on June 10, 2016 at the old argmin blog.

This year marks the retirement of Dimitri Bertsekas from MIT. Dimitri is an idol of mine, having literally written the book on every facet of optimization. His seminal works on distributed optimization, dynamic programming, and Lagrangian methods remain the best references available. I had the privilege of taking Dimitri’s convex analysis course in grad school, and he would frequently burst into class beaming because he had stayed up until 2AM the night before simplifying an argument of Rockafellar’s down to elementary calculus.

My last post on Lagrangians was based on Chapter 3 of Dimitri’s Nonlinear Programming Book. Chapter 2 also happens to feature one of my favorite passages about the delicate balance between theory and practice in optimization. One of the trickiest parts about optimization (and a point I intend to repeatedly hammer on this blog) is realizing how many of the theorems are “qualitative” rather than “quantitative.” I wanted to just quote Dimitri’s text in full here, as I don’t think I could write it better. Best wishes to you in retirement!

The Role of Convergence Analysis by Dimitris Bertsekas

The following subsection gives a number of mathematical propositions relating to the convergence properties of gradient methods. The meaning of these propositions is usually quite intuitive but their statement often requires complicated mathematical assumptions. Furthermore, their proof often involves tedious ϵ−δ arguments, so at first sight students may wonder whether “we really have to go through all this.”

When Euclid was faced with a similar question from King Ptolemy of Alexandria, he replied that “there is no royal road to geometry.” In our case, however, the answer is not so simple because we are not dealing with a pure subject such as geometry that may be developed without regard for its practical application. In the eyes of most people, the value of an analysis or algorithm in nonlinear programming is judged primarily by its practical impact in solving various types of problems. It is therefore important to give some thought to the interface between convergence analysis and its practical application. To this end it is useful to consider two extreme viewpoints; most workers in the field find themselves somewhere between the two.

In the first viewpoint, convergence analysis is considered primarily a mathematical subject. The properties of an algorithm are quantified to the extent possible through mathematical statements. General and broadly applicable assertions, and simple and elegant proofs are at a premium here. The rationale is that simple statements and proofs are more readily understood, and general statements apply not only to the problems at hand but also to other problems that are likely to appear in the future. On the negative side, one may remark that simplicity is not always compatible with relevance, and broad applicability is often achieved through assumptions that are hard to verify or appreciate.

The second viewpoint largely rejects the role of mathematical analysis. The rationale here is that the validity and the properties of an algorithm for a given class of problems must be verified through practical experimentation anyway, so if an algorithm looks promising on intuitive grounds, why bother with a convergence analysis. Furthermore, there are a number of important practical questions that are hard to address analytically, such as roundoff error, multiple local minima, and a variety of finite termination and approximation issues. The main criticism of this viewpoint is that mathematical analysis often reveals (and explains) fundamental flaws of algorithms that experimentation may miss. These flaws often point the way to better algorithms or modified algorithms that are tailored to the type of practical problem at hand. Similarly, analysis may be more effective than experimentation in delineating the types of problems for which particular algorithms are well-suited.

Our own mathematical approach is tempered by practical concerns, but we note that the balance between theory and practice in nonlinear programming is particularly delicate, subjective, and problem dependent.

Subscribe now

By Ben Recht

I’ve been getting emails from journalists asking me to comment on the new White House executive order on quantum computing. Alas, I don’t have time for a long response or interviews since I’m at a beautiful science camp in the California mountains, and heading soon to STOC’2026 in Salt Lake City. But I gave anyone who asked me the following statement, which I thought might be of interest to readers of this blog as well.

“I hope that at least some of the new funds made available from this Executive Order will go to basic, curiosity-driven academic research — the kind that led to the idea of quantum computing in the first place, and to the main quantum algorithms and other advances that everything builds on today — and not only to large organizations that have gotten good at capturing federal funds by repeating the requisite buzzwords.”

By Scott

Authors: Ming Yang

Classical simulations of quantum correlations can fail because no low-communication local hidden-variable model exists, or because no single noncontextual hidden state can explain all compatible measurement contexts. This manuscript studies a third regime: genuine global Kochen-Specker contextuality, where local subsystems are noncontextual and the tested multipartite blocks are generalized-Bell-local, but the whole empirical model admits no global noncontextual hidden-variable explanation. We propose a coordination-cost framework in which communication, memory, and local computation are treated as different ways for a classical simulator to maintain a global classical explanation from locally available information. We introduce coordination bits, global contextual covering numbers, scaling laws for task families, and an abstract lifting theorem showing how classical simulation lower bounds for KS-contextual seed families can be transferred to genuinely global-KS models. As worked examples, we analyze a polarization-path Hardy obstruction and postselected KCBS-type tasks.

Authors: Eduardo Yuji Sakabe, Felipe S. Abrahão, Santiago Hernández-Orozco, Ricardo Gudwin, Hector Zenil

The Block Decomposition Method (BDM) was introduced as an alternative to popular lossless compression methods such as LZW for estimating algorithmic complexity from the principles of algorithmic probability and classical information theory. It extends the Coding Theorem Method (CTM) from small objects to larger ones by combining local estimates of algorithmic complexity with a global account of repetition based on Shannon entropy. Here, we introduce a version of BDM in which dependencies between blocks are utilized to reduce the length of the description based on reusable program code in the decomposition of an object, and on conditional descriptions capable of accounting for shared structure between observations. We formalize this allocation of descriptive resources as algorithmic attention. Repeated or related components need not be described independently, and the resulting reduction in description length is governed by the amount of shared algorithmic information. We formulate this extension as a reuse optimization problem, show that exact optimization is NP-hard, derive conditions under which it improves upon independent descriptions, relate the achievable gains to algorithmic mutual information, prove the relationship with the previous BDM version, and provide a roadmap for its implementation using CTM-derived complexity and conditional complexity estimates.

Authors: Avishay Tal, Weiqiang Yuan

We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant $k$-junta testing with high precision can be solved using $\mathrm{poly}(k)$ quantum queries, whereas any classical algorithm requires at least $k^{Ω(\log k)}$ queries. The problem of tolerant $k$-junta testing is as follows: given parameters $(k, ε_1, ε_2)$, with $0\le ε_1<ε_2 \le 1/2$, and black-box access to a Boolean function $f$ (defined on $n$ variables), distinguish whether $f$ is $ε_1$-close to some $k$-junta or $ε_2$-far from every $k$-junta. We show the quantum advantage for a range of parameters close to $1/2$, for example, $ε_1 = 1/2-1/k$ and $ε_2 = 1/2-1/(2k^2)$. The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most $ε_1$ to $k$-juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick $k$ out of $n$ coordinates, and for each fixing of the $k$ coordinates, the $2^{n-k}$ values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to $k$-juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making $k^{o(\log k)}$ queries.

Authors: Chenyuan Jia, Qingqing Peng, Ke Liu, Guanghui Wang, Guiying Yan

The minimum distance problem (MDP) for low-density parity-check (LDPC) codes is a central problem in coding theory and is closely related to the analysis of low-weight codewords and error-floor behavior. Although the unrestricted MDP is computationally intractable, its complexity under degree constraints that commonly occur in LDPC code design has remained less clear. In this paper, we study the MDP for left regular and biregular Tanner graphs. We prove that the problem is $\mathrm{NP}$-complete and $\mathrm{W}[1]$-complete for $J$-left regular Tanner graphs for every fixed $J\geq 3$, and also for $(3,3)$-regular bipartite graphs. We further establish $\mathrm{W}[1]$-completeness for $(J,K)$-regular instances for every fixed $J,K\geq 3$. The reductions are based on a degree-preserving transformation framework consisting of hyperedge decomposition, check node splitting, and controlled variable replication. These transformations transfer hardness between different degree distributions while preserving explicit bijections among nonzero codewords, even covers, and nonempty $(a,0)$-trapping sets. The results delineate the computational limits of exact LDPC code analysis under natural regularity constraints.

Authors: Tianhang Lu, Runtian Ren, Shengcai Liu

This paper studies learning-augmented online weighted vertex cover with advice and a parameter $λ\in (0,1)$. We consider two graph cases: bipartite graphs and general graphs. In both settings, the online algorithm must maintain a feasible vertex cover under irrevocable decisions. We show that these problems admit the same robustness--consistency tradeoffs as learning-augmented ski rental. For the bipartite graph model, we give a randomized algorithm that is $\frac{1}{1-e^{-λ}}$-robust and $\fracλ{1-e^{-λ}}$-consistent. For the general graph model, we give a deterministic algorithm that is $(1+\frac{1}λ)$-robust and $(1+λ)$-consistent. We prove that the tradeoffs above are optimal in both settings. We also validate the proposed algorithms through experiments on synthetic and real-world datasets.

Authors: Liyan Chen, Matthew M. Hong, Yael Tauman Kalai, Zoe Xi

We show that every language in PSPACE decidable by a Turing machine in time $T(n)=n^{O(\log n)}$ admits a doubly efficient interactive proof system: the prover runs in time polynomial in T(n), and the verifier runs in time polynomial in n. This extends the best previously known regime for such proof systems from $T(n)=n^{O(\sqrt{\log n / \log\log n})}$, established by Berger, Goyal, Hong, and Kalai (FOCS 2025), to $T(n)=n^{O(\log n)}$. Beyond improving the range of T, our protocol is substantially simpler than previous doubly efficient proofs for time-bounded PSPACE. Earlier constructions proceed indirectly: they first build batch interactive proofs and then invoke them as a black box to obtain doubly efficient protocols. In contrast, we give a direct construction. This not only simplifies the proof but also points to a more promising route for future improvements.

Authors: Mithil Ramteke

We study exact nonnegative matrix factorization (NMF) of small exact-rank-r matrices via a cone-ray pipeline combining the truncated SVD, the polyhedral cone of nonnegative preimages, the Double Description Method (DDM, via Fukuda's cddlib), and an alternating linear program (alt-LP) for slack minimisation. Under a uniform-support restriction the factorisation constraint Q P^T = I_r reduces to entrywise nonnegativity of an r x r witness matrix M_T = R_T^{-1} (R_K^T)^{-1} for an r-subset pair (T, K) of cone rays; this closed-form witness recovers an exact NMF in microseconds when feasible. We characterise feasibility by ranking r-subsets via geometric near-orthogonality ("obtuseness") and walking the top of each list. A 100-trial Monte Carlo at m=n=10 exposes a clean saturation curve: success 44/32/8, 79/85/58, and 79/87/59 of 100 at top-5/200/400 for r=4,5,6 -- beyond top-200 the failures are structural, not budget-limited. Enlarging m,n at fixed r hurts: at m=n=15 success collapses to 37/7/0/0/0 for r=4..8. On Olivetti faces (400x4096) the DDM step itself times out. Our main contribution is a hybrid that breaks this ceiling: at each pair we first try the closed-form M_T, and when it is infeasible we augment both supports by k=2 maximally angularly-separated rays and solve for mu,nu>=0 by a short slack-LP alternation. On the same m=n=10 Monte Carlo this lifts success from 79/85/58 to 99/95/75 at r=4,5,6, with cone reconstruction error at or near machine precision. We close with the four scaling walls the pipeline faces and concrete next steps.

Authors: Annesha Sen, Shivam Singh, S. P. Tiwari

Mapper is a well-known tool in topological data analysis, which visualizes and summarizes high-dimensional data. However, its output is sensitive to choices of lens functions, cover parameters, and clustering strategies, making evaluation challenging. Most works that have attempted to evaluate the Mapper algorithm have done so visually. In this paper, we review a roadmap for assessing Mapper algorithms along three complementary axes: stability, cluster quality, and topological shape preservation. We analyze Mapper and its variants on synthetic datasets and the UCI Digits dataset. These modes include topological explosion at high resolutions. Our findings indicate that these axes of evaluation are often in tension and that no single Mapper variant performs optimally across all three. This review provides practical guidelines for choosing Mapper variants and identifies open challenges toward a principled Mapper analysis.

Authors: Annesha Sen, Shivam Singh, S. P. Tiwari

Topological Data Analysis uses tools from algebraic topology to study the shape and structure of data. The Mapper algorithm provides a graph-based summary of high-dimensional datasets by combining a filter function, a cover of the filter range, and clustering on the corresponding pullback sets. Several variants of Mapper have been proposed, including Conventional Mapper, F-Mapper, and Shape Fuzzy C-Means Mapper. In this article, we introduce Gustafson-Kessel Fuzzy Mapper Graphs, a geometry-adaptive extension of Shape Fuzzy C-Means Mapper. The proposed method replaces spherical fuzzy covers with ellipsoidal covers induced by the Gustafson-Kessel fuzzy clustering framework, making it more suitable for high-dimensional datasets with anisotropic and non-spherical geometry. We develop a stability framework for the graphs produced by Gustafson-Kessel Mapper and Shape Fuzzy C-Means Mapper. We prove that the membership functions depend smoothly on the fuzzifier, establish a precise condition for the existence of edges, and show that the graph is locally stable under small perturbations of the fuzzifier. We further describe the critical-event structure of graph changes in terms of threshold crossings of the membership functions and show that the graph is constant between consecutive critical events. When the threshold-crossing set is finite, this yields an eventual freezing threshold. Finally, we empirically show that Gustafson-Kessel Mapper can produce more stable graphs than Shape Fuzzy C-Means Mapper on high-dimensional and geometrically complex datasets.

Authors: Michael T. M. Emmerich

We study fixed-cardinality subset selection for the exact integral bi-objective $R_2$ indicator with a uniform continuum of weighted Tchebycheff scalarizing functions. The indicator measures the area under the lower envelope of scalarizing losses over weight space, rather than a finite sample average over weight vectors. For a sorted bi-objective Pareto-front approximation, represented by points ordered by increasing first objective and decreasing second objective, we derive an exact adjacent-neighbor decomposition of this integral objective into boundary terms, unary diagonal corrections, and selected-neighbor transition terms. This yields an exact Bellman dynamic program with $O(kn^2)$ running time for selecting $k$ of $n$ candidate points. We then prove that the transition matrix is Monge. This gives a divide-and-conquer implementation with $O(kn\log n)$ running time and, more strongly, a staircase matrix-search implementation with $O(kn)$ running time under constant-time arithmetic comparisons. The matrix-search proof is presented through a lower-envelope sweep over single-crossing transition functions and includes the triangular feasibility condition $i

Authors: Prashant Gokhale, Mikhail Khodak, Sandeep Silwal

We consider the problem of sequentially approximating functions of each element in a slowly-varying sequence, i.e. one where the magnitude $α_i$ of the difference between the elements at positions $i$ and $i-1$ is small. Recent work on implicit trace estimation shows that when $α_t$ is small, reusing queries to past sequence elements can reduce the overall cost [Dharangutte \& Musco, NeurIPS~2021; Woodruff et al., NeurIPS~2022]. We introduce a framework generalizing this to a variety of linear and nonlinear functions on diverse vector spaces, obtaining novel sequential estimation results for matrix powers, spectral densities, Monte Carlo integration, and a boundary value problem from partial differential equations~(PDEs). Furthermore, we develop a novel algorithm for use with this framework that locally scales the estimation budget with $α_t$, obtaining sharper path-length-style variation bounds of form $\mathcal O(\sum_{i=1}^mα_i)$ on the cost of estimating a sequence of length $m$. This improves upon the previous implicit trace estimation bound of $\mathcal O(m\cdot\max_iα_i)$ [Dharangutte \& Musco, NeurIPS~2021], which is achieved by fixing the query budget using the worst-case $α_i$ and is thus inefficient for stable sequences with rare bursts. Lastly, while all past work assumes a known bound on $α_i$, we show in certain cases how the changes can be estimated on-the-fly with (nearly) no added cost. In summary, our framework makes the sequential approximation toolkit general-purpose and adaptive while improving upon state-of-the-art-guarantees for dynamic trace estimation.

Authors: Arthur Braida, Elie Bermot, Simon Apers

Quantum tunneling is expected to provide a computational speedup in quantum computing, a phenomenon that Adiabatic Quantum Optimization (AQO) aims to leverage. While some academic proofs of concept have been studied, such as the "Hamming weight with a spike" (HWS) problem, the algorithmic gains of this effect remain underexplored. In this work we extend the analysis underlying HWS to more general potentials. In the first half of the work, we establish (discrete) log-concavity of the ground state as a key structural property in this context. We devise a framework for establishing log-concavity of the ground state for a large family of discrete, 1-dimensional Schrödinger operators. The family includes convex potentials, but also certain potentials with local minima. In the convex case, this provides a discrete version of a continuous result by Brascamp and Lieb ('76). We demonstrate the utility of our result by establishing new spectral gap bounds, going beyond related results by Jarret and Jordan ('14) for convex potentials. In the second half of the work, we use our results on log-concavity to extend the perturbative analysis of HWS by Reichardt ('04) to the larger family of potentials with log-concave ground state. As a concrete instantiation, we use our result to extend the HWS analysis from a linear potential (which is exactly solvable) to a quadratic potential (which is no longer solvable). Our result strongly suggests the broader applicability of tunneling to convex potentials with spikes

Authors: Alexander Barvinok

We consider expectations of the type $E\ \exp \left\{\sum_{i=1}^m φ_i \right\}$, where $φ_i: {\Bbb R}^n \longrightarrow {\Bbb C}$ are functions, each depending on a few coordinates of a point in ${\Bbb R}^n$, and the expectation is taken with respect to the standard Gaussian or symmetric exponential probability measures. We prove sufficient conditions, in terms of the Lipschitz constants of $φ_i$ and the combinatorics of their dependencies, for the integral to be separated from 0, and, consequently, to be amenable to a computationally efficient approximation. We discuss applications to computing volumes of bodies and statistics on integer points in polyhedra in ${\Bbb R}^n$.

Authors: Rajesh Jayaram

Multi-vector (MV) embeddings have become a powerful paradigm in neural information retrieval (IR), achieving high retrieval accuracy by representing data with multiple vectors and scoring them via the non-linear Chamfer similarity. Despite their widely perceived superiority over single-vector (SV) embeddings which use inner product similarity, to date there is no formal proof that SV similarities cannot approximate MV similarities with the same representation size. Specifically, we ask the following: for any bounded dataset size $n \leq 2^{poly(m)}$, what is the smallest dimension $D$ so that given any collection of MV embeddings $Q_1,\dots,Q_n,X_1,\dots,X_n \subset \mathbb{R}^d$ containing at most $m$ vectors each, there always exist $q_1,\dots,q_n$, $d_1,\dots,d_n \in \mathbb{R}^{D}$ satisfying $|\langle q_i, d_j \rangle - \texttt{Chamfer}(Q_i,X_j)| \leq ε$ for all $i,j$? Recently, the MUVERA algorithm demonstrated that $D = m^{O(1/ε^2)}$ is possible. If improved to $D = md$, this would imply that MV embeddings are no more expressive than SV embeddings. In this paper, we rule out this scenario. Specifically, we prove the existence of a collection of MV embeddings in $\mathbb{R}^d$, each containing at most $m$ vectors, which require single-vector dimension of $D =(ε^2 m)^{Ω(1/ε)}$ to approximate, establishing a strong separation in representation size between MV and SV embeddings. Our proof leverages the Pattern Matrix Method by constructing a hard instance whose Chamfer similarity matrix encodes the $NAND_k$ boolean function. Our results confirm a long-held belief in the IR community: at a fixed representation size, multi-vector embeddings can express similarities which cannot even be approximately represented by single vector embeddings.

Authors: Nader H. Bshouty

In this paper, we study the problems of abelian group property testing in two models. In the partially specified model (PS-model), the algorithm does not know the group size but can access randomly chosen elements of the group, along with the Cayley table of these elements, which provides the result of the binary operation for every pair of selected elements. In the stronger fully specified model (FS-model), the algorithm knows the size of the group and has access to all its elements and the Cayley table. In property testing of abelian group property, given a finite set $G$ and oracle access to a binary operation $*:G^2\to G$, we aim to distinguish whether $(G,*)$ is an abelian group or is $ε$-far from any abelian group over $G$. Using a novel approach, we present a tester in the PS-model (and consequently in the FS-model) that runs in time $\tilde O(\sqrt{|G|}+1/ε)$, improving upon the Goldreich-Tauber tester, which runs in time $O(|G|/ε)$. Additionally, our tester improves another tester by Goldreich and Tauber that runs in time $O(|G|^2)$ and makes $\tilde O(|G|+1/ε)$ queries. We further extend our result to testing subclasses of abelian groups ${\cal G}$ that are closed under isomorphism. Specifically, if one can decide in time $T$ whether an abelian group of the form $Z_{m_1}\times \cdots\times Z_{m_r}$ belongs to ${\cal G}$, then there exists a tester for ${\cal G}$ that runs in time $T+\tilde O(\sqrt{|G|}+1/ε)$ and makes $O(\sqrt{|G|}+1/ε)$ queries. This result gives testers that run in time $O(\sqrt{|G|}+1/ε)$ for subclasses such as abelian groups of rank at most $k$, abelian $p$-groups, and vector spaces over~$Z_p$.

Authors: David Harvey

We describe several new algorithms for finding all prime numbers up to a given bound $N$, achieving the first ever speedup by a positive power of $\log N$ over the ancient sieve of Eratosthenes. The fastest version, which is not fully rigorous, runs in \[ N (\log \log N)^{1+o(1)} \] bit operations when analysed in the multitape Turing model. This improves on the best existing algorithms due to Pritchard (1981), Atkin--Bernstein (2004) and Sergeev (2016) by a factor of almost $\log N$. We also present a rigorous randomised (Las Vegas) variant that is slower by a factor of $(\log \log N)^{1+o(1)}$, and a rigorous deterministic variant that is slower by a factor of $(\log N)^{1/2+o(1)}$. The new algorithms make heavy use of fast polynomial arithmetic over finite fields, and also involve ideas from the theory of error-correcting codes.

Authors: Sebastiano Vigna

Standard batteries of tests for pseudorandom number generators (such as dieharder, the NIST suite, and TestU01) provide two empirical tests for linearity, the binary rank and linear-complexity tests. Both operate over the field $\mathbf F_2$, and thus detect generators that are linear over $\mathbf F_2$. However, generators can be linear over a larger field, as in the case of congruential generators, single-modulus multiple-recursive recurrences, and of matrix generators such as MIXMAX. We introduce a modular version of the rank and linear-complexity tests, and provide modlin, a Rust program that implements it efficiently for fields of prime size. modlin can detect in minutes statistical bias in all current CERN's ROOT's implementations of the MIXMAX generator, for which no standard statistical test failure has been reported before.

Authors: Weibo Fu, Qian Qin, Guanyang Wang

We prove an inverse-polynomial spectral-gap bound for the lazy swap chain on binary matrices with prescribed row and column sums. This chain is a standard sampler for fixed-margin null models in ecology, statistics, and network analysis, and its rapid mixing for arbitrary feasible margins was conjectured by Kannan, Tetali, and Vempala in 1997. We show that for every feasible set of margins on an $m\times n$ binary matrix, the lazy swap chain has spectral gap at least $$ \binom{m}{2}^{-1}\binom{n}{2}^{-1}, $$ which is tight in the worst case. The proof compares the swap chain with a two-row heat-bath chain, reduces the analysis from arbitrary $m\times n$ matrices to the case of three rows, and proves the resulting three-row inequality by decomposing functions according to the column-count variable and the associated Johnson harmonic sectors. The proof itself was generated by ChatGPT 5.5 Pro. ChatGPT proposed the whole proof strategy, including the comparison with the two-row heat-bath chain, the reduction to the three-row case, and the decomposition of the three-row function space into the count sector and the Johnson harmonic sectors. It also generated all the technical lemmas and initial proofs. The author's role was to pose the problem, guide the search direction, evaluate the AI-generated arguments, rewrite the proof, and take responsibility for the final form and validity of the result.

Authors: Max Klimm, Martin Knaack

We study an online item-allocation problem with budgets and a submodular objective. A set of $m$ agents is known in advance, and each agent $j$ has a known budget. A set of $n$ items arrives over time in a uniformly random order. When item $i$ arrives, its cost $c_{i,j}$ for each agent $j$ is revealed, and the algorithm must irrevocably assign $i$ to an agent without violating any budget constraint. The goal is to maximize a monotone submodular function defined over all possible assignments $[n] \times [m]$. At the time of decision, the algorithm has only oracle access to this submodular function restricted to items seen so far. This model subsumes welfare maximization with submodular valuations, agent-specific item costs, and agent-specific budgets. We measure the performance of an algorithm by its competitive ratio, i.e., the worst-case ratio between the algorithm's expected value and that of the offline optimum, which knows all item costs and the full submodular function in advance. Prior work only considered the case of a single agent and achieved a $1/54.4$-competitive algorithm. We generalize and improve this result to a polynomial-time $α$-competitive algorithm with $α\approx 1/14.85$ for an arbitrary number of agents. We also study the special case in which all item costs and all budgets equal $1$, which yields an online submodular matching problem. Prior work achieved a polynomial $1/9.66$-competitive algorithm for this problem; we improve this to a factor of $1/6.86$. Both our algorithms rely on repeatedly computing $(1 - 1/e)$-approximations of the multilinear extensions of offline variants of the subproblems. If super-polynomial runtime is allowed, these subproblems can be solved optimally, and our competitive ratios improve by this factor.

Authors: Faruk Alpay, Levent Sarioglu

In a tiered cache, eviction is a graph decision: removing one aligned storage block can disconnect downstream demand that never addressed that block directly, so request recency alone cannot price the action. This paper studies aligned eviction as a vertex-separation problem and gives a selection rule whose decisions carry independently checkable service-cut evidence. For every candidate block, it computes the exact weighted downstream demand cut, rejects actions that disconnect protected demand, and selects the minimum-impact admissible eviction. Reclamation is characterized as vertex separation: minimum-location reclamation reduces to node-capacitated flow, while minimum aligned block actions are NP-complete. In two-hop cache networks, one streaming pass evaluates every candidate impact; a matching adversarial construction proves that a history-only victim selector has unbounded one-step damage. The packet-scale implementation combines a seed-indexed exact-cardinality residency structure with collision-aware, 32-bank impact counters. Replay compression makes the result auditable: counter intervals reproduce the stream, exact monoid summaries retain every reported additive statistic, and a counting lower bound quantifies the state required by any exact all-candidate summary. A 144-scenario evaluation processes 582.90 trillion packets (404.86 PiB of simulated payload), validates the coordinate expectations, and exposes a zero-impact extreme-value transition near $Nζ=\log m$. Complete impact vectors, decoded audit samples, telemetry, and logs remain within the ancillary-file budget. Finally, invalidation is monotone replicated state: fair asynchronous delivery converges without coordination, with a diameter bound under synchronous full-edge rounds. The architecture therefore binds capacity reclamation, path continuity, and distributed invalidation to one certifying interface.

Authors: Fabian Spaeh, Themistoklis Haris, Alina Ene, Huy L. Nguyen

We study influence maximization in general stochastic models, the observed cascades model, and the independent cascade (IC) model. For general stochastic models with only black-box sample access, we introduce a low-adaptivity optimization framework that improves sample complexity and running time over Sadeh et al. (2020) and is instrumental to all our results. We further introduce an adaptive algorithm guided by empirical variance, avoiding pessimistic worst-case bounds. Combining our optimization framework with sketching, we obtain the first algorithm with provable guarantees and nearly-linear running time for influence maximization on observed cascades, optimal up to logarithmic factors. For IC, we prove a novel tail bound replacing a factor $n$ with $τ$ (the number of diffusion steps) in sample complexity, improving over prior work when $τ$ is small, as is common due to small-world phenomena. Experiments confirm substantial speedups while maintaining solution quality.

Authors: Valerio Dose, Fabio Furini, Marco Locatelli

The Precedence Constrained Knapsack Problem (PCKP) asks for a maximum-profit subset of items, subject to a knapsack capacity constraint and precedence constraints encoded by a directed acyclic graph. We study the structure of optimal solutions of the Linear Programming (LP) relaxation of the natural Integer Linear Programming formulation of the PCKP. We introduce the notion of macroitem and of feasible sequence of macroitems, which partitions the item set while respecting the precedence structure. We establish that an optimal LP solution is fully characterized by the optimal sequence of macroitems: items are packed in nonincreasing order of the profit-to-weight ratio of their macroitem, with at most one macroitem fractionally included. We further show that the breakpoints of the parametric Lagrangian function of the capacity constraint coincide with the profit-to-weight ratios of the macroitems in the optimal sequence, and provide a complete combinatorial characterization of optimal dual solutions in terms of a feasible flow within each macroitem. Finally, for the special case in which the precedence graph is a forest, we devise an O(n^2) algorithm to compute the optimal sequence, which improves to O(n log n) for in-trees or out-trees, where n denotes the number of items.

Authors: Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Gabriel Le Bouder, Taïssir Marcé, Nils Morawietz

In the standard Freeze-Tag Problem (FTP), an initially awake robot (the source) is in charge of waking up a swarm of sleeping robots by moving towards them, given that all the awake robots can participate in the awakening process. The goal is to minimize the makespan to wake up all robots assuming they move at unit speed. In this paper we introduce the Freeze-Tag-with-Return Problem (FTRP) variant, where the robots must eventually return to their initial positions. In the Euclidean plane with $n$ sleeping robots lying on the unit disk centered at the initial position of the source, we show a non-trivial relationship between FTP and FTRP by proving that the difference between the optimal makespan of both problems never exceeds $1.959$, and is at least $1.732$ in the worst-case. We also present several upper and lower bounds on the optimal makespan. In particular, we show that if the sleeping robots are in convex positions, then the optimal makespan is at most $2 + 2\sqrt{2}$, which is achieved by some instances. From an algorithmic point-of-view, we present single-exponential algorithms for general distance functions. In metric spaces, these algorithms are asymptotically optimal under the ETH, which we show via an NP-hardness reduction on unweighted graphs.

Authors: Syamantak Kumar, Shourya Pandey, Purnamrita Sarkar, Kevin Tian

We study high-dimensional differentially private (DP) covariance estimation in the operator norm, and principal component analysis (PCA), under $k$-row-column sparsity ($k$-RCS) of the covariance matrix. In the non-private setting, it is known that $\mathsf{poly}(k, \log d)$ samples suffice to solve both of these problems. However, the only comparable result known under DP (Wang et al. 2021) requires $Ω(d)$ samples under standard parameterizations of the problem. We investigate when this curse of dimensionality is inherent for sparse covariance estimation tasks under DP. On the upper bound front, we show that a $\mathsf{poly}(k, \log d)$ sample complexity for PCA is possible under DP, if we also posit sparsity of the leading eigenvector. We complement this result with $\mathsf{poly}(d)$ lower bounds under DP for both sparse covariance estimation and PCA, establishing an exponential gap between the private and non-private variants of these problems when $k = \mathsf{polylog}(d)$. To our knowledge, no such separation has previously been demonstrated for any sparse estimation problems in private high-dimensional statistics. Our techniques are flexible enough that they imply stronger lower bounds even for the well-studied problem of standard DP PCA, without sparsity assumptions.

Since I’m a good mood today—at a beautiful science camp with my kids, high in the mountains near Big Bear Lake in California—I thought I’d blog about something positive. Last week, five authors (Chatterjee, Ghosh, Gurjar, Raj, and Thierauf) posted a major paper to the Electronic Colloquium on Computational Complexity, which shows (or anyway, credibly claims to show) that the Bipartite Matching problem is in the complexity class NC. Assuming this stands, it resolves a central problem in parallel algorithms and derandomization that’s been open since the 1980s.

In Bipartite Matching, you’re given a list of n men and n women, you’re told who’s willing to date whom, and your goal is to

1. decide whether it’s possible to pair everyone off with a willing partner, and
2. if they are, actually pair them off.

One of the great early discoveries of combinatorial algorithms, taught in every introductory algorithms course, is that this problem is solvable in time polynomial in n, even though the naïve, brute-force approach would require examining n! possibilities.

(Note that in the bipartite version, we assume that the men and women are all straight. If the men and women can be LGBT, we get the problem of matching in general graphs, which again turns out to be solvable in polynomial time, but now the algorithm is much more sophisticated, and was a major discovery of Edmonds in the 1960s.)

Anyway, the question is whether we can do even better than polynomial time: in particular, can we solve the problem in time polynomial in log(n), given polynomially many parallel processors?

Back in the 1980s, first Karp, Upfal, and Wigderson, and then (via a very different method) Mulmuley, my former PhD adviser Umesh Vazirani, and Umesh’s brother Vijay Vazirani managed to show that the answer is yes, but only if the parallel processors additionally get access to random bits, and only need to succeed with high probability.

The new achievement is to derandomize the Mulmuley-Vazirani-Vazirani algorithm, and show that problems 1 and 2 above are both solvable in deterministic polylogarithmic time with parallel processing (in other words, in the complexity class NC).

No, I don’t understand how it works yet. If anyone does, feel free to explain in the comments! Or ask your favorite AI to generate a summary. If I run out of options, at some point I might actually try reading the paper.

(Note: Thanks to Gil Kalai for some corrections to an earlier version of this post.)

One other announcement: Today is the day of primary elections in NYC! Virtually all of my smartest friends who work on AI governance and safety are extremely excited about the Congressional campaign of Alex Bores—indeed, it would be little exaggeration to say that they consider him the last best hope of humankind. Bores has been a national leader on trying to regulate AI, to the extent that Marc Andreessen’s “Leading the Future” anti-AI-regulation PAC has spent millions of dollars trying to sink his candidacy. Outside of AI, Bores seems like a sane, conventional Democrat, i.e. the kind I like, and much more moderate than his base on Israel (note that his main opponent is also such). Without commenting on Bores’ views on every possible issue, I’ll simply say: if you live in New York’s 12th Congressional District (comprising a huge chunk of central Manhattan), and you care about AI safety, please consider a vote for Bores while there’s still time.

By Scott

On Friday, Midjourney, a generative AI company best known for automatically creating DeviantArt images from text prompts, announced it was pivoting to medicine. Their web copy opens with blunt honesty: “Today we’re gonna announce something a little weird and a little crazy, but also spectacular and filled with hope.” What follows is a cinematic trailer straight out of Ridley Scott’s Alien franchise, depicting Midjourney’s dream of a new whole-body ultrasound scanner that is “as powerful as MRI, and as casual as a trip to the spa.”

Their first scanning spa won’t be available until 2027, so I’m not sure why they decided to announce this on Friday. But it ignited a heated fight between tech boosters and medical practitioners, lighting up my mostly dormant Twitter timeline all weekend. I am embarrassed to confess that it was custom-made to engage me and my niche tastes. I couldn’t look away!

Let’s first be clear: everyone was fighting about vaporware. The actual technology is based on a 2026 Nature Biomedical Engineering paper. That paper, by a Caltech lab, is a nice engineering systems integration project combining a lot of technology that’s been around for decades. There is no fancy AI, and the imaging algorithm is written in Matlab and run on a cheap GPU (an RTX 3070). The paper doesn’t demonstrate any particularly cutting-edge imaging, presenting a few reasonable images of abdominal fat. Instead, the paper promises acceleration, claiming the ability to perform a whole-body scan in about a minute.

Midjourney thus promised something not yet demonstrated:

“In an ideal and near-term future, we take this information and watch how it changes over time. We compare it to the general population, we talk to doctors, nutritionists, coaches, trainers, and AI friends. We become more aware of our health and we improve our lifestyles. We make smarter, more proactive, more frequent decisions. And we live longer, healthier lives, better lives.”

Now, this text may seem clichéd and innocuous, but two communities on Twitter read this paragraph very differently.

On the one side were tech boosters, who seethed with vitriol against the medical establishment. They believe that all information is good, and more information can only improve decisions. They embrace some perverse version of Sutton’s Bitter Lesson that more data fed into more computing can solve all problems.

On the other side were medical doctors, most of whom also seemed to really hate the medical establishment! They’re on Twitter, after all. But they had compelling arguments against indiscriminate scanning.

First, they note that ultrasound is a limited imaging modality, and the new full-body system doesn’t eliminate those limitations. Ultrasound can’t see through bone or air, and has other fundamental limitations with contrast. You can’t fix a fundamentally physics-limited scanner with more frequent scans.1

Second, though conventional wisdom says that early detection improves disease outcomes, we have 75 years of evidence that is far from encouraging. The case has been most illuminating in oncology. Some cancers are untreatable no matter when they are detected. With advances in therapies, some cancers are treatable even if you catch them late. The correlation between early detection and cure is, unfortunately, much lower than cancer researchers had hoped in the 1950s. The medical establishment has tempered its expectations over the last 20 years, but the lay population hasn’t caught up.

Third, frequent scanning means you have to run more tests to follow up on what you see in a scan. This is a nightmare. Imaging is never perfect. Let’s say that you build a technology that is 95% accurate at detecting a disease that afflicts one in a thousand people. A crude probability calculation2 then says that for every hundred scans that come back positive, only 2 of them actually have the disease. What about those other 98 people? They are healthy people who will be subjected to the stress of potentially harmful follow-up tests. Biopsies aren’t fun!

The fourth lesson also comes from oncology. We don’t understand the dynamics of many progressive cancers. Even the best imaging technology still can’t tell the difference between harmful and harmless masses. Some growths look bad and appear to grow over time, but they never cause harm. On imaging, these look the same as tumors that will kill you in six months. Why should we be constantly raising alarms about information that doesn’t lead to actionable, beneficial interventions?

These arguments fell on deaf ears. The tech boosters were furious that the medical conservatives were against more information. They yelled that doctors are terrible at mathematics. They yelled that doctors are gatekeepers preventing people from accessing information that will make them better. They yelled that doctors don’t know innovation if it stares them in the face. One particularly vitriolic person wrote: “You guys thought that Lister and Pasteur both needed to be crushed, and for the most part, you haven’t changed.”

Unsurprisingly to me, the tech boosters didn’t present any scientific arguments. I only saw unfounded assertions about Bayes’ Rule and Blackwell’s theorem, and how “false positives aren’t a problem.” The Midjourney scanner is yet another project in the optimaxxing biohacking space, seeking technological means to wrest control of your body.

What the tech side of the argument came down to was this seemingly anodyne statement in the Midjourney blogpost: “You want as much data as you can get about your health as quickly and as cheaply as possible,” and that you should strive to maximize the “megabytes per second per dollar of information” you capture about yourself. Massive time series data would unlock new diagnostics, overcoming the limitations of single scans. All data is good data, and all data leads to improvement. This assertion is not backed by evidence. It is, as Midjourney wrote, hope.

I side with doctors on this one, though for a reason that they didn’t seem willing to advance. We shouldn’t obsessively overmedicalize ourselves. There is an inherent harm in always seeing yourself as a patient, ailing unless proven healthy. More information can make you sicker.

Subscribe now

By Ben Recht

(All references in this blog post can be found in the main article the post is about which is here.)

Recall that \(R(s,k)  \) is the least \(n\) so that, for all 2-colorings of the edges of \(K_n\), there is either a RED \(s\)-clique or a BLUE \(k\)-clique.

\(R(k,k)\) has been well studied and is often called \(R(k)\).

However, today we are concerned with \(R(s,k)\) \(s\) is fixed and \(k\) goes to infinity.

1) In 1995 Jeong Han Kim showed \(R(3,k)\) is asy \(\Theta(\frac{k^2}{\log k})\). At the workshop In Ramsey Theory: Yesterday, Today, and Tomorrow, Edited by Alexander Soifer, 2011, Joel Spencer gave a great talk titled

80 years of \(R(3,k)\).

The title implies that the problem was open for 80 years, but 40 years is a better estimate.

The general sense I got from both Joel and the audience is that \(R(4,k)\) is a much harder problem.

2) In 2023 there was substantial progress on \(R(4,k)\). Sam Mattheus and Jacques Verstraete showed

\(R(4,k) = \Omega(\frac{k^3}{\log^4 k})\)

Combined with prior results this yields

\( c_1 \frac{k^3}{\log^4 k} \le R(4,k) \le c_2 \frac{k^3}{\log^2 k} \)

The prior lower bound had been \(\Omega(\frac{k^{2.5}}{\log^2 k })\) so this was a big improvement.

3) The following was known for \(R(s,k)\) for fixed \(s\) and asy \(k\):

\( k^{(s+1)/2 + o(1)} \le R(s,k) \le O(k^{s-1}) \)

There were polylog improvements to this which we omit.

Surely improving the lower bound to \(\Omega(k^{s-1+o(1)})\) would be hard.

4) Domagoj Bradac showed the following (posted on May 27, 2026, and pointed to at the beginning of this post):

\(R(s,k) =\Omega(\frac{k^{s-1}}{(\log k)^{2s-4}}).\)

Combining this with the known best upper bounds yields (ignoring constants) 

\( \frac{k^{s-1}}{(\log k)^{2s-4}} \le R(s,k) \le (1+o(1))\frac{k^{s-1}}{(\log k)^{s-2}} \)

So the bounds are now only a polylog apart!

Random Notes.

1) I am not surprised by the results.

2) I am very surprised that the results were obtained.

3a) In 2011 most people thought that \(R(4,k)\) would be hard.

3b) After the progress on \(R(4,k)\) I still thought that \(R(5,k)\) would be hard, though I don't know what others thought.

4) Why such fast progress?

4a) AI? Some was used but not that much. See comment on page 4 of the paper.

4b) More people working on the problem?

4c) More advanced tools developed over time? Surely yes.

5) What other problem that seems like its solution is long in coming will be solved much faster than we think?

By gasarch

Matching is in NC

Matching theory is one of the richest gold mines of ideas and results in mathematics, computer science, and beyond. Recently, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, and Thomas Thierauf proved that bipartite matching is in NC. Namely, there is an algorithm with a polynomial number of processors and polylogarithmic depth that decides whether a bipartite graph has a perfect matching. This problem has long been regarded as a holy grail of complexity theory. Congratulations to Abhranil, Sumanta, Rohit, Roshan, and Thomas.

The authors write in the abstract that “the techniques are based on the polynomial method, inspired by a construction of subspace designs by Guruswami and Kopparty (Combinatorica, 2016).”

(See also this post about matching theory and VVV.)

Remaining open problems are whether there is an algorithm in NC for finding a perfect matching (the search problem), and whether the result extends to finding perfect matching in general (non bipartite) graphs. 

Local Mathematical Events Birthdays

There is a great deal of mathematical activity around (sometimes with conflicting schedules), but not many international visitors.

Last week there was a week-long school (Midrasha) on “Groups, expanders, and codes,” marking Alex Lubotzky’s 70th birthday. (See this post for my after-dinner speech for Alex ten years ago.)

Two weeks ago there was a lovely one-day conference celebrating Yaron Ostrover’s 50th birthday, where I gave a talk on the conjecture. (See this post.)

Noga Alon and I are organizing a session celebrating Micha Perles’ 90th birthday, featuring, besides the two of us, Nati Linial, Ron Adin, and Rom Pinchasi. It will take place on July 6 and will be part of the two-day meeting of the Israel Mathematical Union at Bar-Ilan University on July 5-6. On July 7 there will be our traditional students talk day.

The Israel Academy is devoting an evening to mark Hillel Furstenberg’s 90th birthday. It will take place on July 8.

AI + Math event at TAU

The mathematics department at TAU organized a special day devoted to AI and mathematics, featuring Ronen Eldan (OpenAI and the Weizmann Institute) as the main speaker.

Itai Benjamini organized one of the discussion groups on AI and mathematical research and kindly invited me to participate. It was very interesting.

Yonatan Aumann on the centipede game

Yonatan Aumann gave a beautiful lecture presenting an approach, developed jointly with his father Robert Aumann, for dealing with the centipede game. The occasion was a one-day workshop “Games, Rationality and Society” marking the 20th anniversary of Robert Aumann’s Nobel Prize, which included many other lovely lectures.

Last week, many friends of mine participated in a conference in Paris “Half a Century of Agreeing to Disagree” celebrating the 50th anniversary of Aumann’s celebrated agreement theorem.

Kazhdan’s Hypercontractivity and Groups Seminar

Our Kazhdan’s seminar on hypercontractivity and representation theory is approaching its final weeks. After a few introductory lectures, most of the talks were given by Noam Lifshitz and were devoted to hypercontractivity and group representations.

I gave two lectures in which I summarized some early applications of hypercontractivity in other directions and discussed several open problems. Had we had more time, we could also have discussed additional applications of hypercontractivity to global functions, and I may add some material on this topic to the course webpage. Nati Linial is a dominant participant in the seminar and asked some great questions about representation theory that led to wonderful micro-lectures by David.

Top row: Old friends celebrating Yael and Arnon’s wedding; David taking the chalk to give a one-minute introduction to étale cohomology, at Nati’s request. Middle row: RUNI’s new robot; Eden Ben-Zaken performing at RUNI; bottom row: Shira Tanny lecturing at Yaron Ostrover’s day; Ronen Eldan lecturing about things mathematicians should know about LLMs.

 

 

 

By Gil Kalai

Authors: József Pintér

A graph $G$ is conformable if it admits a proper $(Δ(G)+1)$-coloring in which, among the $Δ(G)+1$ color classes including the empty ones, at most $\sum_{v\in V(G)}(Δ(G)-d_G(v))$ have parity different from that of $|V(G)|$. The complexity of deciding conformability was left open in recent work, and positive results for several graph classes had suggested that the problem might be polynomial-time solvable. We settle the general problem by proving that Conformability is NP-complete. Hardness holds even for connected regular graphs $G$ of odd order with independence number $α(G)=3$ and maximum degree $Δ(G)\ge |V(G)|/2$. In particular, NP-completeness persists when every color class is forced to have the parity of the order. The reduction starts from perfect triangle packing in graphs of clique number three, regularizes the source graph while preserving the relevant triangle packings, and then takes the complement. In the complement, conformable color classes correspond to odd cliques of the regularized graph; $K_4$-freeness restricts these cliques to singletons or triangles, and the number of available colors forces exactly the required number of disjoint triangles.

Authors: Ishay Haviv

A family of permutations of $[n]$ is called setwise distinguishable if for every permutation in the family there exists a subset of $[n]$ whose image under this permutation differs from its image under any other permutation in the family. We prove that there exists a setwise distinguishable family of $2^{(2-o(1)) \cdot n}$ permutations of $[n]$. The result is optimal up to the $o(1)$ term in the exponent and is achieved through an explicit construction. As an application, we obtain nearly tight conditional lower bounds on the kernelization complexity of graph coloring problems parameterized by the vertex-deletion distance to split graphs. This improves a result of Jansen and Kratsch (Inf. Comput., 2013).

Authors: Nagashri Krishnakumar, Harshil Mittal, Jayalal Sarma

The labelled reachability problem for undirected graphs with edges labelled by elements of a monoid $M$ (more generally, groupoids or magmas) captures the classes $\sf{L}$ and $\sf{NL}$. Given a graph $G(V, E)$ labelled by $φ~\colon E \to M$, $s,t \in V$ and an accepting subset $F \subseteq M$, the problem asks to test whether there is a walk $P$ from $s$ to $t$ in $G$ where $φ(P) \in F$. Ramaswamy et al. (2019) studied the variant where the accepting element is part of the input for aperiodic monoids and groups. Motivated by the success in designing space-bounded algorithms for the undirected graph reachability problem, we study the labelled reachability problem when the accepting set is also fixed. This reveals finer complexity bounds and dichotomies for the problem based on the monoid and the accepting set. Previous results imply that the problem is in $\sf{L}$ for any finite accepting subset when $M$ is a group or belongs to $\sf{DA}$. We prove the following (for finite monoids): 1) For any monoid $M$, the problem is in $\sf{L}$ when the accepting element is the identity of $M$. If the accepting element is an idempotent, under suitable constraints, the problem is $\sf{NL}$-hard. 2) For any commutative monoid $M$, the problem is in $\sf{L}$ for all $F \subseteq M$. 3) For any $\mathcal{L}(\mathcal{R})$-commutative union-of-groups (UoG) monoid $M$, the problem is in $\sf{L}$ for all $F\subseteq M$. We show deterministic logspace algorithms for UoG monoids that are neither $\mathcal{L}$-commutative nor $\mathcal{R}$-commutative, under certain constraints. 4) For the monoids $\sf{BA_2}$ and $\sf{U}$, we show a dichotomy: for all $F \subseteq M$, the problem is either $\sf{NL}$-complete or in $\sf{L}$. Our results exploit the connection between Green's relations in the UoG monoids and the properties of the product graph (a graph introduced by Ramaswamy et al. (2019)).

Authors: Michael Epping, Jochen Szangolies

The interface between the quantum and the classical is an intriguing and, at times, hotly contested subject of ongoing research. The quantum regime is characterized by interference, made possible by the superposition principle, while such phenomena are absent in macroscopic, everyday experience. Here, we investigate the link of this absence (or, as we will argue, unobservability) to computational complexity. We show how the assumption that quantum systems cannot solve NP-complete problems efficiently implies that certain formally valid quantum measurements on finite-dimensional systems are unperformable. We study several consequences of this restriction. First, Pauli matrices in an inconveniently transformed basis are a simple example of unobservables. Furthermore, some quantum states are not connected by any physically realizable time evolution. Finally there are quantum states whose coherence cannot be observed, i.e. superpositions of pure quantum states which are indistinguishable from mixtures. We discuss the connection of this phenomenon to the presence of superselection sectors. Our results suggest that the apparent classicality of macroscopic systems may be partly due to limitations on measurements and time evolutions imposed by computational complexity.

Authors: Marcel Jackson

We present a finite semigroup whose pseudovariety has membership problem hard for the class \emph{Difference P}