Theory of Computing Report

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 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 logarithmic time, given polynomially many parallel processors?

Back in the 1980s, Ketan 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 Mulmuley-Vazirani-Vazirani, and show that problems 1 and 2 above are both solvable in deterministic logarithmic 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.

One other announcement: Tomorrow 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: Domagoj Ševerdija, Jurica Maltar, Nathan Chappel, Domagoj Matijević

Neural combinatorial optimization (NCO) has shown that policies trained by reinforcement can construct strong solutions to NP-hard problems directly from raw instances. What such a policy actually learns, as opposed to what its decoder expresses, remains much less clear. We study this distinction on the vertex-guard Art Gallery Problem, the NP-hard task of choosing polygon vertices from which to observe an entire region. A pointer-network policy is trained from a coverage-aware reward over its own rollouts under the constraint we call geo-free inference: at test time it sees only vertex coordinates, with no visibility computation and no geometric oracle. The policy places guards economically but leaves a tail of under-covered polygons that widens far beyond the training range. To locate the cause, we freeze the trained encoder and read its embeddings with a small single-shot classifier, still geo-free at inference. The classifier closes most of the feasibility gap, in and out of distribution and at up to roughly five times the training range, cutting under-covered polygons by about an order of magnitude at an explicitly reported cost in guard count. We read this as evidence that the reinforcement-trained representation already encodes the geometry required for feasibility, and that residual failures reflect decoder calibration rather than missing knowledge. Probing a frozen encoder thus offers a practical way to ask what a neural combinatorial solver has internalized.

Authors: Dafna K. Matsegora, Stephen M. Watt

We present an iterative algorithm to compute an arc-length parameterized spline interpolating a set of points. This differs from other methods where the computed spline either does not interpolate the original points or the parameterization is not the arc-length of the returned curves. Our method is applicable in any dimension $D \ge 2$, and we illustrate it with numerical results for plane curves.

Authors: Rohit Lohani, Krishnendra Shekhawat

Automated floor plan generation is an important problem in computational architectural design. The goal is to construct a floor plan from user-defined room numbers and door requirements. The user specifies which rooms must share a door and which rooms must not be adjacent. However, these requirements do not determine the exact placement or shape of the rooms. The task is therefore to arrange the rooms in a single floor plan so that all required door connections are satisfied and no rooms overlap. To address this problem, we propose DPLAN (Door Connectivity to Floor Plan Generation), a graph-based prototype that generates floor plans from door and non-adjacency constraints. The framework operates in three stages. First, the user-defined graph is examined and, if disconnected, additional edges are added to connect its components. Second, a bi-connected plane triangulation is constructed to ensure the existence of a floor plan without overlapping rooms or empty spaces. Third, the triangulated graph is transformed into floor plans. For rectangular floor plans (RFPs), separating triangles are removed by modifying edges without adding new vertices, thereby avoiding the creation of extra rooms. For orthogonal floor plans (OFPs), separating triangles are removed by introducing additional vertices, allowing rectilinear room shapes. By enforcing both door and non-adjacency requirements, the framework generates floor plans that satisfy the given constraints. The method is implemented in Python and includes a prototype for interactive constraint specification and floor plan visualization. Currently, the framework supports rectangular plot boundaries. Future work includes support for non-rectangular plots, dimension-based scaling, and circulation modeling.

Authors: Patrizio Frosini, Ulderico Fugacci, Nicola Quercioli, Francesca Tombari

This new book is intended as a first elementary introduction to Topological Data Analysis for mathematics students seeking a rigorous account of the foundations of persistent homology, as well as for computer scientists interested in its theoretical underpinnings. The exposition is as self-contained as possible: all the required background is recalled when needed, and only a few standard results are cited without proof. One section of the book, devoted to monodromy in biparameter persistence (Section 4.4), requires more advanced knowledge of algebraic topology. Persistent homology can be introduced from different perspectives, reflecting the variety of mathematical languages that have shaped its development over the years. Some approaches emphasize the algebraic foundations of the theory, while others highlight its topological essence. In this book, we adopt the latter viewpoint - the one that historically marked the birth of the subject - because we believe it offers both conceptual clarity and pedagogical effectiveness, making it particularly suitable for undergraduate and early graduate students. This book differs from existing introductory texts in several respects. First, it adopts a functional viewpoint: rather than representing data as finite (pseudo-)metric spaces, it treats them as functions encoding the information to be analyzed. This interpretative framework allows data to be viewed as measurable objects and highlights the role of observers and their equivariances in the analysis process. Second, this perspective provides a natural bridge between Topological Data Analysis and machine learning through the theory of Group Equivariant Non-Expansive Operators (GENEOs), which offers a mathematically grounded framework for incorporating symmetries and invariances into learning systems.

Authors: Neeraj Mohan Sushma, Aditya Nagarsekar, Cabrel Teguemne Fokam, Robin Schiewer, Amit Kumar Pal, Anand Subramoney, David Kappel

Modern deep neural network architectures are trained via backpropagation, which requires errors to be sequentially propagated through all layers before parameters can be updated. This introduces two limitations: locking, where layer-wise updates are strictly interdependent and cannot proceed in parallel, and the weight transport problem, which requires symmetric forward and backward pathways for exact gradient computation. These constraints restrict parallelism, increase memory and communication overhead, and pose challenges for scalable learning. In this work, we propose Hierarchical Block-Local Learning (HBLL), a framework that decomposes deep neural networks into hierarchically linked blocks trained using local learning objectives derived from variational principles, eliminating the need for full end-to-end backpropagation while maintaining effective information propagation across the network. HBLL is the first algorithm that is able to train deep neural networks in $\mathcal{O}(\log N)$ parallel time complexity, where $N$ is the number of network layers. We show that HBLL implicitly defines a family of subnetworks corresponding to different hierarchical paths, enabling flexible inference with different effective numbers of layers. We evaluate HBLL on a set of challenging vision and language modeling tasks, achieving competitive performance. We also extend HBLL to recurrent sequence architectures, applying to settings that otherwise rely on backpropagation through time.

Authors: Martin Olsen

We consider the stacking problem where items are temporarily stored in stacks in a stacking area. The stacks are working as Last In First Out (LIFO) data structures. The objective is to avoid {\em shifts} or {\em restows} that occur when an item has to leave the stacking area earlier than an item above it. We present a simple online algorithm for the problem where we pick a stack for an incoming item without any information on future items. We present a sufficient condition for the algorithm to avoid shifts expressed as an inequality involving the dimension of the stacking area, the number of load/unload points and the maximum number of items present at the same time. The condition is relatively tight in the sense that we can find instances requiring shifts for {\em any} algorithm (including offline algorithms) with small modifications of the condition. Our results indicate that our algorithm is useful if the number of load/unload points is relatively small compared to the number of items.

Authors: Zhidan Li, Siyu Liu, Kuan Yang

The anti-ferromagnetic multi-state Potts model, a generalization of the Ising model, is one of the most fundamental models in statistical physics. It was conjectured by Kotecký (Phys.~Rev.~B, 1985) that the model undergoes a phase transition from a disordered phase at infinite temperature to an ordered phase at sufficiently low temperature on lattices. Such phase transitions are believed to play an important role in computational complexity theory and remain closely connected to the problem of approximating the partition function of the system. For proper three-coloring models (corresponding to the zero-temperature), torpid mixing of a family of local-update Markov chains on lattices was established by Galvin, Kahn, Randall and Sorkin (SIDMA, 2015), coinciding with the presence of phase coexistence following shown by Feldheim and Spinka (J.~Eur.~Math.~Soc., 2019). In this work, we study approximating the partition function of the anti-ferromagnetic multi-state Potts model at low temperature on random regular bipartite graphs, which are with high probability good bipartite expanders. On the negative side, we generalize the result by Geisler, Kang, Sarantis and Wdowinski (arXiv, 2026) for anti-ferromagnetic Ising models to show that when the temperature is sufficiently low relative to the degree of the underlying graph, the celebrated single-site Glauber dynamics has exponentially slow mixing time. On the positive side, we design a deterministic algorithm that yields an approximation to the partition function of the model via the framework of abstract polymer models as Jenssen, Keevash and Perkins (SICOMP, 2020), Liao, Lin, Lu and Mao (Theor.~Comput.~Sci., 2022), Galanis, Goldberg and Stewart (TOCT, 2021) and Geisler, Kang, Sarantis and Wdowinski (arXiv, 2026).

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^{\Omega(\log k)}$ queries. The problem of tolerant $k$-junta testing is as follows: given parameters $(k, \epsilon_1, \epsilon_2)$, with $0\le \epsilon_1<\epsilon_2 \le 1/2$, and black-box access to a Boolean function $f$ (defined on $n$ variables), distinguish whether $f$ is $\epsilon_1$-close to some $k$-junta or $\epsilon_2$-far from every $k$-junta. We show the quantum advantage for a range of parameters close to $1/2$, for example, $\epsilon_1 = 1/2-1/k$ and $\epsilon_2 = 1/2-1/(2k^2)$. (As such, the problem is more naturally captured using the notion of correlation with closest $k$-junta.) 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 $\epsilon_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.

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.

In 2024, at the same time as I was being called a genocide apologist, Zionist baby killer, etc. etc., I was also being hounded by my right-wing, pro-Israel readers, who demanded of me: knowing what you know, understanding what you understand, how could you possibly vote for Kamala Harris? How could you donate to Kamala’s campaign, urge your readers to vote for her, when she (like most Democrats) is obviously beholden to young left-wing activists, and young left-wing activists’ central unifying cause has become the death of “Zionists” like yourself and your children? Can’t you see that, even if Trump is a raging, lying, bullying, incoherent monster, at least he’s our monster?

This view, I confess, gave me more pause than “just accept that the liberation of the world’s oppressed requires Israel’s annihilation and hence the death of much of your family,” which my far-left critics considered their most persuasive argument. And yet I also rejected, with extreme prejudice, the right-wingers’ constant invitations to join their MAGA brigade. I replied: I’ll simply continue being a moderate Enlightenment liberal, transported here in a block of ice from the 1990s, even if I’m the last such on earth, even if I’m condemned by everyone on either side for it.

Why? Because, I said at the time, while I’m honest enough to admit when a rampaging T-Rex happens to do something that aligns with my interests—when, e.g., it chases away some velociraptors ready to slice me open, or cracks down on antisemitic fanatics trying to dominate the universities where I spend my life—still, I’ll never delude myself into imagining the T-Rex my ally. I understand that it would just as soon devour me. If the monster goes after my enemies not because of liberal principles or recognizable moral emotions, but just raw self-interest and ego gratification, then what happens the instant its perceived self-interest changes?

It gives me no pleasure that this week Trump proved my instincts here 3,000% correct, by fully capitulating to the Islamic Republic of Iran, far more so than Barack Obama ever did, or than President Kamala Harris ever would have. Trump has now abandoned both the Iranian and the Israeli peoples to suffer and die at the hands of the IRGC, as he abandoned the Ukrainians and the Venezuelans before them, as Neville Chamberlain abandoned Czechoslovakia. All because of the price of gas and the midterm elections.

On the most charitable reading, Trump gambled that taking out Ayatollah Khamenei would lead to a cowed and compliant puppet regime, as basically happened in Venezuela, with no need for a ground invasion or arming the Iranian resistance. His gamble predictably failed, because (alas) the Iranian government actually believes in something—horrifying and medieval though it is. Trump was unable to process that fact, because he’s never believed in anything beyond himself, and he wrongly assumes that everyone else is the same.

With the $300 billion and control over the Strait of Hormuz, I expect that Iran will rebuild its military and proxies to stronger than they were before Trump’s idiotically mismanaged war. I expect that Iran will then launch attacks against Israel that make October 7 look like the Little League—and that, when it does so, a large fraction of the Western world will ecstatically cheer, as it did on October 7 itself. Netanyahu is a fool for expecting otherwise from Trump, a man who’s betrayed everyone who’s ever trusted him outside possibly his immediate family.

I salute those Israelis who will choose to stay and fight even after their abandonment and betrayal, in the spirit of the Bar-Kochba revolt and other desperate battles of Jewish history. Despite the existential danger that Israel will soon be in, facing a victorious and emboldened Iran essentially alone, I also see it as possible that Western countries will rapidly become even more dangerous for Jews than Israel. If that happens, I’ll be grateful that Israel still exists, that it considers itself unbound by America’s surrender, and that I’ll be able to seek refuge there, as was the idea when Israel was founded.

At the same time, I wouldn’t begrudge any Israelis who moved to the US, or Switzerland, or whatever other country will take them. As in the 1930s and at countless other points in Jewish history, the priority now is physical survival, wherever that turns out to be possible.

With hindsight, I spent the first half of my life in a strange interregnum, wherein Jewish history seemed to have finally ended. Now, fueled by fading memory of the Holocaust and by the greatest lie-amplification technologies the world has ever seen, the history I learned as a child has come roaring back. Jews, as they have for millennia, look out on a world of murderous enemies and fickle friends. It’s just the restoration of a norm.

Incredibly, abandoning both the Iranian and Israeli peoples to the Revolutionary Guard might not have been the most shortsighted or catastrophic thing Trump did in the last couple weeks. Another candidate would have to be Trump’s attempt to destroy Anthropic (and as collateral damage, American AI development more generally), transparently to punish Anthropic for the crime of having any principles that it was willing to put ahead of obedience to Trump and Pete Hegseth. Specifically, the White House forced Anthropic to pull Fable, its new flagship model (and the “safe” version of Mythos), off the market just a few days after customers had started using it, by subjecting it to export controls that it knew were impossible to enforce. Even the many foreign nationals who work at Anthropic are no longer allowed to use their own model (!). A plausible consequence is that those foreign nationals will stop working at American AI companies altogether, and will move to China or whichever other country rolls out the red carpet for them.

For AI accelerationists, you’d think that this would be a worst-case scenario: a direct government crackdown on AI that goes beyond anything the AI safetyists had proposed, and that indeed would’ve sounded like fantasy even a year ago. And yet many of the accelerationists are gleeful. Why? Because Anthropic, in supporting reasonable AI regulations, had made itself the accelerationists’ enemy. So, the accelerationists’ attitude now is quintessentially Trumpian: “Haha, Anthropic, you say you like regulation? Then take that!” Never mind that whatever dangerous behavior can be elicited from Fable, can almost certainly be elicited as well from GPT 5.5 Pro, and yet there’s no talk of any similar crackdown against OpenAI. Sam Altman, after all, donated $1 million to Trump’s inaugural fund. No one finds it remarkable anymore, in Trump’s destroyed and recreated United States, that your rights depend entirely on your standing with the Don.

And so, just like the question of whether Trump would side with the isolationists or with the hawks who wanted to liberate Iran, was resolved by his worst-of-all-worlds choice to surrender to Iran, so too the question of whether Trump would hit the brakes on the race to dangerous AI, or accelerate in order to beat China, has been resolved by his worst-of-all-worlds choice to lose the race to China. I.e., we’re still in full race mode, but we’re also going to do whatever we can to lose the race—by, for example, letting NVIDIA sell its chips to China, and now, scaring away our top researchers and punishing our AI firms with capricious and arbitrary crackdowns.

It’s disconcerting to reflect that, while the prognosis of the world is arguably the worst it’s ever been in my lifetime, my own life is pleasant. Intellectually I know that the Titanic has already hit the iceberg, but the band is still playing and I’m still being served delicious food.

Last week I visited Paris and the French countryside with my wife and kids. In addition to sightseeing, I spoke at a workshop celebrating 50 years of Aumann’s Agreement Theorem (where I got to meet the 96-year-old Aumann), and gave a quantum computing talk at the Sorbonne. Next week I’m going with my family to a science camp in California, then to STOC in Salt Lake City, where I’ll accept the Trevisan Prize and give an after-dinner speech, then to Epsilon Camp where I’ll again teach theoretical computer science to 11- and 12-year-olds.

Like I said, life is good here on the Titanic, if you ignore the rapidly rising seawater at your feet.

By Scott

Authors: Benjamin Carleton, Michael C. Chavrimootoo, Lane A. Hemaspaandra, David E. Narváez, Conor Taliancich, Melissa Welsh

Ambiguity-bounded versions of $\mathrm{NP}$, denoted $\mathrm{UP}_{\leq f(n)}$, bound by $f(n)$ the number of accepting paths the nondeterministic polynomial-time Turing machine can have on inputs of length $n$. Such classes range from Valiant's completely unambiguous ($f(n)=1$) class $\mathrm{UP}$ to $\mathrm{NP}$ itself, where there is no bound or, equivalently, there is the toothless exponential bound ($f(n) = 2^{n^{O(1)}}$). This paper seeks to understand which of these classes stand and fall together as to whether they equal deterministic polynomial time. Informally put, what ranges of ambiguities have linked fates? That is, for which pairs of nondecreasing functions, $(f_1 ,f_2)$, satisfying $(\forall n)[f_1(n) \leq f_2(n)]$, does it hold that $\mathrm{P} = \mathrm{UP}_{\leq f_1(n)} \implies \mathrm{P} = \mathrm{UP}_{\leq f_2(n)}$. More particularly, for which pairs does that hold robustly, i.e., it holds in the real world and every relativized world? And for which pairs does that implication fail to hold robustly, i.e., there is an oracle $A$ such that $\mathrm{P}^A = \mathrm{UP}_{\leq f_1(n)}^A \subsetneq \mathrm{UP}_{\leq f_2(n)}^A$? The only previously known positive result is Watanabe's 1988 result that $ \mathrm{P} = \mathrm{UP}_{\leq 1} \implies (\forall k \geq 1)[\mathrm{P} = \mathrm{UP}_{\leq k}]$, which even holds robustly. His result, though lovely, applies only to constant-bounded ambiguities. As our positive result, we present a new class of cases (Theorem 3.8) that apply (and even robustly apply) at greater ambiguity levels. To give our class of cases, we leverage two approaches: a novel path-poisoning approach that works even on superconstant ambiguities (Theorem 3.5) and a new application of the power of padding (Theorems 3.3/3.4). As negative results, we show that for essentially all other cases, no linkage holds robustly.

Authors: David Brander, Jens Gravesen, Marc Isern

An elastic space curve is a critical point of the bending energy subject to appropriate constraints. An analytic representation, equivalent to the spherical pendulum equation, leads to an 11-parameter description of the space of 3D elastic curve segments. We give a numerically stable method for recovering the 11 parameters from a given elastic curve segment. Using this, we give a fast and stable method to approximate an arbitrary space curve segment by a 3D elastica. Applications include interactive design with exact elastic curves and CAD surface rationalization for robotic hot-blade cutting.

Authors: Md Sakir Ahmed, Kumaresh Sarmah, Hemen Dutta

A widely held intuition in deep learning is that stochastic gradient descent (SGD) implicitly favors flat minima and that flat minima generalize better, but standard Euclidean measures of flatness such as the trace or maximum eigenvalue of the loss Hessian are not invariant under reparametrizations that preserve the network function, which undermines the theoretical foundations of this narrative. In this study we resolve this issue by grounding flatness in the Riemannian geometry of the statistical manifold induced by the Fisher Information Matrix (FIM). We define Riemannian sharpness mathematically and prove that it is invariant under smooth, function-preserving reparametrizations, which directly addresses the critique of Dinh et al. in the paper ``Sharp minima can generalize for deep nets''.We note that this invariance is a property of the true FIM; the diagonal empirical estimator used in practice (and in all experiments below) inherits invariance only approximately, and exact invariance under arbitrary reparametrizations would require structured estimators such as K-FAC. We formalize the gradient noise of mini-batch SGD as having a covariance structure proportional to the FIM, derive the stationary distribution of the resulting stochastic differential equation, and then show that the probability mass is exponentially concentrated at Riemannian-flat minima. A PAC-Bayes generalization bound controlled explicitly by SR formally links this geometric bias to test performance. Our experiments on MNIST and CIFAR-10 confirm that SR reliably tracks generalization in ways that Euclidean sharpness does not, and that its scaling with $η/B$ matches the theoretical predictions. Together these results provide a rigorous, reparametrization-invariant account of why flat minima generalize.

Authors: Yossi Bokor Bleile, Emanuele Cortinovis, Herbert Edelsbrunner, Shota Uka

Tree-like structures appear in many areas of science, and their shapes can help understand the underlying processes they drive or that give rise to them. By thinking of these structures as geometric graphs in $\mathbb{R}^3$, we gain access to tools from computational geometry and topology to study them. In this paper, we adopt the theory of quadratic forms to measure the directional spread of geometric graphs, and we introduce the hexplot model -- equipped with a metric derived from the Fisher metric on the standard triangle -- to visualize, measure, and collect statistics.

Authors: Ruoxuan Yang, Chuan Li

Skeletonization of tubular structures from 3D imaging is essential for tasks such as morphometric analysis, transport or flow simulation, and procedural planning in domains including vascular networks, plant root systems, and neural connectomes. However, automatic skeleton extraction often introduces topological artifacts, such as erroneous connections between nearby branches and fragmented centerlines caused by noise or missing data. Correcting these artifacts manually can be time-consuming and error-prone, especially when precise interaction is required. We present a semi-automatic correction method that reconstructs a plausible centerline connection from minimal user input. Given a user-selected source and target point, our method traces a path by combining (i) component-wise minimum spanning trees for stable local propagation and (ii) a filtered 3D Delaunay edge graph for bridging gaps and handling ambiguous junctions. Candidate steps are ranked using a score that accounts for direction continuity, spatial proximity, component consistency, and target-directed progress. The output is an ordered polyline (or edge sequence) that can be used as a suggested correction and integrated into downstream skeleton post-processing workflows. We implement the system in C++ with an interactive viewer based on Libigl and demonstrate representative qualitative results on brain vessel datasets, including correction of typical "crossing" and "dotted" artifacts. While our current validation is qualitative, the method is lightweight and serves as a practical building block toward more comprehensive interactive correction pipelines in biomedical imaging and related domains.

Authors: Robert Ganian, Mathis Rocton

Twin-width is a graph parameter that has become central to explaining the fixed-parameter tractability of first-order model checking across many graph classes. Despite its algorithmic importance, computing twin-width remains poorly understood: even recognizing graphs of twin-width at most four is NP-hard, and no fixed-parameter approximations parameterized by twin-width itself are known. A recent approach towards breaking this barrier focuses on first developing fixed-parameter algorithms for computing or approximating twin-width under parameterizations distinct from twin-width. Our first result establishes that approximating twin-width is fixed-parameter tractable when parameterized by treedepth, thereby breaking the long-standing barrier that all previous tractable parameterizations were based on deletion distance. The proof proceeds via oriented twin-width, yielding the first constructive evidence that this variant may be easier to handle algorithmically. As our second main result, we show that computing twin-width exactly is fixed-parameter tractable with respect to vertex integrity. This constitutes the first non-trivial parameterized algorithm for computing optimal contraction sequences.