Theory of Computing Report

Authors: David Miloschewsky, Supartha Podder, Dorian Rudolph

We study the power of quantum witnesses under perfect completeness. We construct a classical oracle relative to which a language lies in $\mathsf{QMA}_1$ but not in $\mathsf{QCMA}$ when the $\mathsf{QCMA}$ verifier is only allowed polynomially many adaptive rounds and exponentially many parallel queries per round. Additionally, we derandomize the permutation-oracle separation of Fefferman and Kimmel, obtaining an in-place oracle separation between $\mathsf{QMA}_1$ and $\mathsf{QCMA}$. Furthermore, we focus on $\mathsf{QCMA}$ and $\mathsf{QMA}$ with an exponentially small gap, where we show a separation assuming the gap is fixed, but not when it may be arbitrarily small. Finally, we derive consequences for approximate ground-state preparation from sparse Hamiltonian oracle access, including a bounded-adaptivity frustration-free variant.

Authors: Kean Chen, Qisheng Wang, Zhicheng Zhang

We consider the problem of quantum channel certification to unitary, where one is given access to an unknown $d$-dimensional channel $\mathcal{E}$, and wants to test whether $\mathcal{E}$ is equal to a target unitary channel or is $\varepsilon$-far from it in the diamond norm. We present optimal quantum algorithms for this problem, settling the query complexities in three access models with increasing power. Specifically, we show that: (i) $Θ(d/\varepsilon^2)$ queries suffice for incoherent access model, matching the lower bound due to Fawzi, Flammarion, Garivier, and Oufkir (COLT 2023). (ii) $Θ(d/\varepsilon)$ queries suffice for coherent access model, matching the lower bound due to Regev and Schiff (ICALP 2008). (iii) $Θ(\sqrt{d}/\varepsilon)$ queries suffice for source-code access model, matching the lower bound due to Jeon and Oh (npj Quantum Inf. 2026). This demonstrates a strict hierarchy of complexities for quantum channel certification to unitary across various access models.

Authors: Farzan Byramji, Daniel M. Kane, Jackson Morris, Anthony Ostuni

We provide a unified method for constructing explicit distributions which are difficult for restricted models of computation to generate. Our constructions are based on a new notion of robust extractors, which are extractors that remain sound even when a small number of points violate the min-entropy constraint. Using such objects, we show that for a broad range of sampling models (e.g., low-depth circuits, small-space sources, etc.), every output of the model has distance $1 - o(1)$ from our target distribution, qualitatively recovering essentially all previously known hardness results. Our work extends that of Viola (SICOMP '14), who developed an earlier unified framework based on traditional extractors to rule out sampling with very small error. As a further application of our technique, we leverage a recent extractor construction of Chattopadhyay, Goodman, and Gurumukhani (ITCS '24) to present the first explicit distribution with distance $1 - o(1)$ from the output of any low-degree $\mathbb{F}_2$-polynomial source. We also describe a potential avenue toward proving a similar hardness result for $\mathsf{AC^0}[\oplus]$ circuits.

Authors: Apurva Mudgal

We prove the Jordan curve theorem by generalizing the sweepline algorithm for trapezoidal decomposition of a polygon. Our proof uses Zorn's lemma (or, equivalently the axiom of choice). Though several proofs have been given for the Jordan curve theorem by various authors, ours is the {\bf first algorithmic proof} of Jordan curve theorem using computational geometry. Further, with some preparation, the proof can be taught as part of an undergraduate discrete mathematics course, where till now the proof of this theorem was considered inaccessible.

Authors: Lucas Meijer, Till Miltzow, Johanna Ockenfels, Miloš Stojaković

In the (Nesting) Bird Box Problem we are given a polygonal domain P and a number k and we want to know if there is a set B of k points inside P such that no two points in B can see each other. The underlying idea is that each point represents a birdhouse and many birds only use a birdhouse if there is no other occupied birdhouse in its vicinity. We say two points a,b see each other if the open segment ab intersects neither the exterior of P nor any vertex of P. We show that the Nesting Bird Box problem is ER-complete. The complexity class ER can be defined by the set of problems that are polynomial time equivalent to finding a solution to the equation $p(x) = 0$, with $x\in R^n$ and $p\in $Z[X_1,...,X_n]$. The proof builds on the techniques developed in the original ER-completeness proof of the Art Gallery problem. However our proof is significantly shorter for two reasons. First, we can use recently developed tools that were not available at the time. Second, we consider polygonal domains with holes instead of simple polygons.

Authors: Tony Zeng

A convex polyhedron is Rupert if a hole can be cut into it (making its genus $1$) such that an identical copy of the polyhedron can pass through the hole. Resolving a conjecture of Jerrard-Wetzel-Yuan, Steininger and Yurkevich recently constructed a convex polyhedron which is not Rupert. We propose a search for the simplest possible non-Rupert polyhedron and provide numerical evidence suggesting that a particular stellated tetrahedron is not Rupert. The computational techniques utilize linear program solvers to compute the largest possible scalings of polygons that can be translated to fit in other polygons. The relative simplicity of the stellated tetrahedron as compared to other polyhedra allows this more rudimentary check to be computationally tractable. In particular, we show that over 88% of a particular encoding of $\text{SO}(3) \times \text{SO}(3)$ equipped with the standard measure does not yield a Rupert passage.

Authors: Alexander Kalinowski

We study detection of collapse in high-dimensional point clouds, where mass concentrates near a lower-dimensional set relative to a non-collapsed geometry. We propose persistent homology-based test statistics under two well-studied filtrations, with cutoffs calibrated under a broad set of non-collapsed reference models. We benchmark power across three alternative collapse mechanisms (linear/spectral, nonlinear-support, and contamination/heterogeneity) and distill the results into a mechanism map guiding the choice of filtration and statistic.

Authors: Ronaldo Garcia, Shmuel, Helman, Dan Reznik

We prove that over a generic Poncelet triangle family, the locus of the circumcenter of an inversive triangle is a conic. Additionally, we prove an earlier conjecture: over generic Poncelet triangles, two unique points exist which maintain constant power with respect to the circumcircle and Euler's circle of the family, respectively.

Authors: Michael T. M. Emmerich

We study exact fixed-cardinality Solow--Polasky diversity subset selection on ordered finite $\ell_1$ sets, with monotone biobjective Pareto fronts and their higher-dimensional staircase analogues as central applications. Solow--Polasky diversity was introduced in biodiversity conservation, whereas the same inverse-matrix expression appears in metric geometry as magnitude: for a finite metric space $(X,d)$ with exponential similarity matrix $Z_{ij}=e^{-q d(x_i,x_j)}$, the quantity $\1^\top Z^{-1}\1$ is the magnitude of the scaled finite metric space $(X,qd)$ whenever the weighting is defined by the inverse matrix. Thus, in this finite exponential-kernel setting, Solow--Polasky diversity and magnitude are mathematically the same object viewed through different motivations. Building on the linear-chain magnitude formula of Leinster and Willerton, we provide a detailed proof of the scaled consecutive-gap identity $ \SP(X)=1+\sum_r \tanh(qg_r/2), $ where the $g_r$ are the gaps between consecutive selected points. We then prove an exact Bellman-recursion theorem for maximizing this value over all subsets of a prescribed cardinality, yielding an $O(kn^2)$ dynamic program for an ordered $n$-point candidate set and subset size $k$. Finally, we prove ordered $\ell_1$ reductions showing that the same algorithm applies to monotone biobjective Pareto-front approximations and, more generally, to finite coordinatewise monotone $\ell_1$ staircases in $\R^d$. These are precisely the ordered $\ell_1$ chains for which the Manhattan metric becomes a line metric along the chosen order, so the one-dimensional dynamic program applies without modification. Keywords: Dynamic Programming, Solow--Polasky Diversity, Complexity Theory, Multiobjective Optimization, Pareto front, Magnitude

Authors: Malory Marin, Rémi Watrigant

While most classical NP-hard graph problems cannot be solved in time $2^{o(n)}$ on general graphs under the Exponential Time Hypothesis (ETH), many exhibit the square-root phenomenon and admit optimal algorithms running in time $2^{O(\sqrt{n})}$ on certain geometric intersection graphs, such as planar graphs or unit disk graphs. In 2018, de Berg et al. developed a general algorithmic framework for such problems on intersection graphs of similarly sized fat objects in $\mathbb{R}^d$, achieving running times of the form $2^{O(n^{1-1/d})}$, along with matching lower bounds under ETH. In this paper, we identify problems that do not exhibit the square-root phenomenon, yet still admit subexponential algorithms on intersection graphs of similarly sized fat objects in $\mathbb{R}^d$, for every fixed dimension $d \geqslant 2$. We introduce the notion of a weak square-root phenomenon: problems that can be solved in time $2^{\tilde{O}(n^{1-1/(d+1)})}$, and for which matching lower bounds hold under ETH. We develop both an algorithmic framework and a corresponding lower bound framework. As concrete examples, we show that the problems 2-Subcoloring and Two Sets Cut-Uncut exhibit this behavior. Our algorithms rely on a new win-win structural theorem, which can be informally stated as follows: every such graph admits a sublinear separator whose removal leaves connected components with sublinear independence number. To facilitate the design of these algorithms, we introduce a new graph parameter, the $α$-modulator number, which generalizes both the independence number and the vertex cover number.

Authors: Steve Hanneke, Alkis Kalavasis, Shay Moran, Grigoris Velegkas

Learning curves are a fundamental primitive in supervised learning, describing how an algorithm's performance improves with more data and providing a quantitative measure of its generalization ability. Formally, a learning curve plots the decay of an algorithm's error for a fixed underlying distribution as a function of the number of training samples. Prior work on revenue-maximizing learning algorithms, starting with the seminal work of Cole and Roughgarden [STOC, 2014], adopts a distribution-free perspective, which parallels the PAC learning framework in learning theory. This approach evaluates performance against the hardest possible sequence of valuation distributions, one for each sample size, effectively defining the upper envelope of learning curves over all possible distributions, thus leading to error bounds that do not capture the shape of the learning curves. In this work we initiate the study of learning curves for revenue maximization and provide a near-complete characterization of their rate of decay in the basic setting of a single item and a single buyer. In the absence of any restriction on the valuation distribution, we show that there exists a Bayes-consistent algorithm, meaning that its learning curve converges to zero for any arbitrary valuation distribution as the number of samples $n \to \infty$. However, this convergence must be arbitrarily slow, even if the optimal revenue is finite. In contrast, if the optimal revenue is achieved by a finite price, then the optimal rate of decay is roughly $1/\sqrt{n}$. Finally, for distributions supported on discrete sets of values, we show that learning curves decay almost exponentially fast, a rate unattainable under the PAC framework.

Authors: Alina Ene, Huy Le Nguyen, Ta Duy Nguyen, Adrian Vladu

We study differentially private approximation algorithms for positive linear programs (LPs with nonnegative coefficients and variables), focusing on the fundamental families of packing, covering, and mixed packing-covering formulations. We focus on the high-sensitivity, constraint-private regime of Hsu-Roth-Roughgarden-Ullman (ICALP 2014), where neighboring instances may differ by an arbitrary single constraint, so one cannot hope to approximately satisfy every constraint under privacy. We give private solvers that return approximate solutions while violating only a controlled number of constraints. Our algorithms improve the prior instance-dependent guarantees, and also yield new data-independent bounds that depend only on the dimension. Our techniques involve a dense multiplicative weights update method developed from a regularized dual viewpoint, which we analyze in a way that exploits structure specific to positive LPs.

Authors: Liam Roditty, Ariel Sapir

We introduce a generalized family of $\left( 2\cdot \left\lfloor \frac{k}{2} \right\rfloor-1, 2\cdot \left\lceil \frac{k}{2} \right\rceil \cdot W_{1} +\max\left\{0,2\cdot\left(\left\lceil\frac{k}{2}\right\rceil-2\right)\right\}\cdot W_{2} \right)$-emulators with $\tilde O \left(n^{1+\frac{1}{k}}\right)$ edges, for any $k\in\mathbb{N}$, where $W_{i}$ is the $i$th heaviest edge on a shortest path between two vertices. Our construction generalizes the $+2W_{1}$-spanner of size $\tilde O\left(n^{\frac{3}{2}}\right)$ and the $+4W_{1}$-emulator of size $\tilde O \left(n^{\frac{4}{3}}\right)$, both by Elkin, Gitlitz and Neiman [DISC'21 and DICO'23]. When $k$ is even, these are $\left(k-1,k\cdot W_{1} + \left(k-4\right)\cdot W_{2}\right)$-emulators and when $k$ is odd, these are $\left(k-2,\left(k+1\right)\cdot W_{1} + \left(k-3\right) \cdot W_{2}\right)$-emulators. Our framework not only expands known constructions for weighted graphs but also yields an improved stretch over state of the art emulators and spanners for unweighted graphs within a specific distance regime. In particular, for all vertex pairs separated by a distance of $δ\leq O\left(3^{k^{2}}\right)$, our construction improves upon the seminal additive $+\tilde O\left(δ^{1-\frac{1}{k}}\right)$-emulator of size $\tilde O\left(n^{1+\frac{1}{2^{k+1}-1}}\right)$ by Thorup and Zwick [SODA'06].

Authors: Hung P. Hoang, Naoto Ohsaka, Rin Saito, Yuma Tamura

In the Independent Set Reconfiguration problem under the Token Addition/Removal rule, given a graph $G$ and two independent sets $I$ and $J$ of $G$, we want to transform $I$ into $J$ by adding and removing vertices, such that all the sets throughout the process are independent sets. Its approximate version called MaxMin Independent Set Reconfiguration aims to maximise the minimum size of the independent sets in the process above. We study the (in)approximability of this problem for general graphs as well as restricted graph classes. Firstly, on general graphs, we obtain a polynomial-time $(n / \log n)$-factor approximation algorithm, complementing the $\mathsf{PSPACE}$-hardness of $n^{Ω(1)}$-factor approximation due to Hirahara and Ohsaka [STOC 2024, ICALP 2024] and the $\mathsf{NP}$-hardness of $n^{1-\varepsilon}$-factor approximation due to Ito, Demaine, Harvey, Papadimitriou, Sideri, Uehara, and Uno [TCS 2011]. Secondly, we present a polynomial-time approximation algorithm for degenerate graphs as well as $\mathsf{FPT}$-approximation schemes for bounded-treewidth graphs and $H$-minor-free graphs. Lastly, we extend the above inapproximability results to bounded-degree graphs, graphs of bandwidth $n^{\frac{1}{2}+Θ(1)}$, and bipartite graphs.

Authors: Ofer Neiman, Alon Spector

Let $G=(V,E)$ be a weighted undirected graph, with $n$ vertices. A distance oracle is a data structure that can quickly answer distance queries, with some stretch factor. A seminal work of \cite{TZ01}, given an integer $k\ge 1$, provides such an oracle with stretch $2k-1$, query time $O(k)$, and size $O(k\cdot n^{1+1/k})$. Furthermore, this oracle can also report a path in $G$ corresponding to the returned distance. In this paper we focus on vertex-labeled graphs, in which each vertex is given a label from a set $L$ of size $\ell$. A {\em vertex-label distance oracle} answers queries of the form $(v,λ)$, where $v\in V$ and $λ\in L$, by reporting (an approximation to) the distance from $v$ to the closest vertex of label $λ$. Following \cite{HLWY11}, it was shown in \cite{C12} that for any integer $k> 1$, there exists a vertex-label distance oracle with stretch $4k-5$, query time $O(k)$, and size $O(k\cdot n\cdot \ell^{1/k})$. This state-of-the-art result suffers from two main drawbacks: The stretch is roughly a factor of 2 larger than in \cite{TZ01}, and it is not path-reporting. We address these concerns in this work, and provide the following results: First, we devise a {\em path-reporting} vertex-label distance oracle, at the cost of a slight increase in stretch and size. For any constant $0<ε<1$, our oracle has stretch $(4k-5)\cdot(1+ε)$, query time $O(k)$, and size $O(n^{1+o(1)}\cdot \ell^{1/k})$. Second, we show how to improve the stretch to the optimal $2k-1$, at the cost of mildly increasing the query time. Specifically, we devise a vertex-label distance oracle with stretch $2k-1$, query time $O(\ell^{1/k}\cdot\log n)$, and size $O(k\cdot n\cdot \ell^{1/k})$. \end{itemize}

Authors: Wen-Han Hsieh, Ya-Chun Liang

We present a learning-augmented online algorithm for the preemptive FIFO buffer management problem, where packets arrive online to a finite-capacity buffer, must be transmitted in FIFO order, and the algorithm may preemptively discard buffered packets to accommodate future arrivals. Our algorithm simultaneously achieves 1-consistency, η-smoothness, and asymptotic \sqrt{3}-robustness, where ηdenotes the prediction error. Specifically, it attains an optimal competitive ratio of 1 under perfect predictions, degrades smoothly as the prediction error increases, and maintains an asymptotic competitive ratio of \sqrt{3} under arbitrarily inaccurate predictions, matching the best-known worst-case guarantee for the classical online problem, established by Englert and Westermann in 2009 [Algorithmica 53(4): 523-548]. A key technical contribution of our work is the introduction of an \emph{output-based prediction error metric}. Because capacity constraints dictate that only a strictly bounded subset of arriving packets is ultimately transmitted, our metric assesses prediction quality over the resulting optimal schedules rather than the raw input sequences, avoiding artificial error penalties. To guarantee robustness, our algorithm dynamically monitors predictions and executes a \emph{buffer-clearing strategy} upon transitioning to a worst-case fallback mechanism. We prove that the competitive loss incurred by this clearing operation is bounded by an additive capacity constant that vanishes asymptotically. Finally, we show that our algorithm provides a generalized framework for learning-augmented buffer management: substituting the fallback module with any β-competitive online algorithm immediately yields asymptotic β-robustness.

Authors: Thomas Konstantinovsky, Gur Yaari

We introduce Flashback, a reversible string decomposition that repeatedly peels the maximal leading and trailing character runs from a sentinel-wrapped input, recording each pair as one bilateral token. Decomposition and reconstruction both run in O(n) time and space. Our central result is a run-pairing theorem: Flashback is equivalent to pairing the first run of the string with the last, the second with the second-to-last, and so on. This gives an exact token count of 1+[r/2] for a string with r maximal runs, and matches a lower bound that holds for any admissible bilateral run-peeling scheme. From the run-pairing theorem the main structural properties follow as corollaries: the irreducible peeling kernel uses at most two symbols; palindromes are precisely the strings whose run-length encoding is symmetric with an odd number of runs; the image of the decomposition admits an explicit finite-state characterisation; and changing one run length rewrites exactly one content token.

Authors: Ronald Deng, Samuel McCauley, Aidin Niaparast, Helia Niaparast, Bennett Ptak, Shirel Quintanilla, Shikha Singh, Nathan Vosburg

Algorithms with predictions is a growing area that aims to leverage machine-learned predictions to design faster beyond-worst-case algorithms. In this paper, we use this framework to design a learned data structure for the incremental strongly connected components (SCC) problem. In this problem, the $n$ vertices of a graph are known a priori and the $m$ directed edges arrive over time. The goal is to efficiently maintain the strongly connected components of the graph after each insert. Our algorithm receives a possibly erroneous prediction of the edge sequence and uses it to precompute partial solutions to support fast inserts. We show that our algorithm achieves nearly optimal bounds with good predictions and its performance smoothly degrades with the prediction error. We also implement our data structure and perform experiments on real datasets. Our empirical results show that the theory is predictive of practical runtime improvements.

Authors: Jaël Champagne Gareau, Daniel Lemire

Converting binary integers to variable-length decimal strings is a fundamental operation in computing. Conventional fast approaches rely on recursive division and small lookup tables. We propose a SIMD-based algorithm that leverages integer multiply-add instructions available on recent AMD and Intel processors. Our method eliminates lookup tables entirely and computes multiple quotients and remainders in parallel. Additionally, we introduce a dual-variant design with dynamic selection that adapts to input characteristics: a branch-heavy variant optimized for homogeneous digit-length distributions and a branch-light variant for heterogeneous datasets. Our single-core algorithm consistently outperforms all competing methods across the full range of integer sizes, running 1.4-2x faster than the closest competitor and 2-4x faster than the C++ standard library function std::to_chars across tested workloads.

My favorite quote about networking came from Jim Kurose.

The Internet works so well because it doesn't have to.

The IP and lower layers of the internet stack make no promises of delivery. Complete failure fulfills the protocol. This allows for simpler and more powerful protocols without the extra complexity needed to guarantee success. TCP aims for delivery basically by restarting the IP communication when it fails, and even TCP can report failure to the layers above.

We can say the same about modern artificial intelligence.

Machine learning works so well because it doesn't have to.

With the softmax function that neural nets use to determine the probability of outputs, neural nets never completely rule out a possibility, always giving it at least some tiny probability. In cases where the complexity is just too difficult, neural nets give several possibilities with nontrivial probabilities, as I described in my recent post, where a machine learning model would generate a uniform distribution to capture the output of a pseudorandom generator. Instead of rigidly forcing the model to give us a specific answer, by looking at distributions we allow the models to make mistakes.

Thus a machine learning model can be correct when it makes probabilistic guesses in situations too complicated to solve directly, which allows it to achieve its best possible performance. Because we allow the models to make mistakes, they have the flexibility to solve complex problems far more frequently.

By Lance Fortnow

The Algorithms and Complexity Group at IDSIA (Lugano) invites applications for a PostDoc position. Topics: Sum of Squares, SDP, Approximation Algorithms.
Terms: 6 months (renewable), ASAP start.
Salary: ~80,000 CHF/year (no teaching, generous travel support).

Website: https://oc.idsia.ch/
Email: monaldo.mastrolilli@supsi.ch

By shacharlovett

Holy crap … yesterday I was elected to the US National Academy of Sciences! If you don’t believe me, click the link and keep scrolling down until you hit the name “Aaronson.” But then continue scrolling to see 144 other inductees, including my IAS postdoctoral classmate Maria Chudnovsky, my longtime friend and colleague Salil Vadhan, and even Janet Yellen. I’m humbled to be in such company.

Years ago, somewhere on this blog, I mused that, if I were ever invited to join NAS, I hoped I’d follow the wisdom of Richard Feynman, who famously resigned his NAS membership, comparing it to an honor society back at his high school that spent most of its time debating who should be a member of the honor society. Feynman was also annoyed at having to pay dues.

But now that I’m actually faced with the choice, it’s like, dude! At my advanced age of 44, I’ve encountered so many people who dislike me or even sneer at me, and so many clubs that won’t have me as a member, that I feel mostly gratitude and warmth toward a fine club like NAS that will have me as a member. Anyway, I’ll certainly try it out to see what it’s like—even Feynman did that!

A few hours after I started getting congratulatory emails, for which I was thankful, someone from UT Austin’s press office asked me how I feel about this “culmination” and “capstone” of my entire research career. I replied, look, I know I’ve slowed down a lot since my nubile twenties, but I still hold out the hope that this isn’t any kind of “capstone”!

In any case, I’m ridiculously grateful to all the friends, family, colleagues, and readers who believed in me and helped me reach wherever this is.

---

Now for a totally different topic, but that will ultimately loop back to the first one:

Last week, I did an Ask Me Anything about quantum computing and blockchain for stacker.news, a forum devoted to bitcoin. Thanks to Will Scoresby for organizing it.

As a longer-term commitment, I also collaborated with my colleagues Dan Boneh, Justin Drake, Sreeram Kannan, Yehuda Lindell, and Dahlia Malkhi, in a panel convened by Coinbase, to put out a detailed position paper about the quantum threat to cryptocurrencies and how best to respond to it. Take a look!

Notably, the situation evolved even while we were writing our position paper—for example, with the major recent papers from Google and Caltech/Oratomic that I blogged about a month ago.

I’d now like to add a few words of my own, not presuming to speak for my fellow Coinbase panelists.

See, some of the most reputable people in quantum hardware and quantum error-correction—people whose judgment I trust more than my own on those topics—are now telling me that a fault-tolerant quantum computer able to break deployed cryptosystems ought to be possible by around 2029.

Maybe they’re overoptimistic. Maybe it will take longer. I dunno. I’m not a timing guy.

But here’s what I do know: the companies racing to scale up fault-tolerant QC, have no plans to slow down in order to “give cybersecurity time to adapt” or whatever. The way they see it, cryptographically relevant QCs will plausibly be built sometime soon: indeed, it’s ultimately unavoidable, even if people’s only interest in QC was to do quantum simulations for materials science and chemistry. So, given that reality, isn’t it better that it be done first by mostly US-based companies in the open, than by (let’s say) Chinese or Russian intelligence in secret? And besides, haven’t there already been years of warnings and meetings about the quantum threat to RSA, Diffie-Hellman, and elliptic curve cryptography? Aren’t many in cybersecurity still in denial about the threat?

Haven’t these slumberers shown that won’t wake up until dramatic achievements in fault-tolerant QC roust them—the way Anthropic’s Mythos model has now jolted even the most ostrich-like about the cybersecurity risks of AI? So, mixing metaphors, mightn’t we just as well rip this Band-Aid off ASAP, rather than giving foreign intelligence agencies extra years to catch up? Indeed, when you think about it that way, isn’t racing to build a cryptographically relevant QC, as quickly as possible, the most ethical, socially responsible thing for an American QC company to do?

Is the above line of reasoning suspiciously self-serving and convenient? Does it remind you of the galaxy-brained arguments that AI company after AI company offered over the last decade for why “really, if you think about it, accelerating toward dangerous superintelligence is the safest course that we could possibly take”? I.e., the arguments that underpinned the current frenzied AI race, which some believe is imperiling all life on earth?

It’s not my place here to answer such questions; I leave all further ethical and geopolitical debate to the comment section! My point here is simply: whether or not anyone likes it, this is how some of the leading QC companies are now thinking about the Shor of Damocles that they genuinely believe now hangs over the Internet.

And I’d say that that makes my own moral duty right now ironically simple and clear: namely, to use my unique soapbox, as the writer of The Internet’s Most Trusted Quantum Computing Blog Since 2005^TM, to sound the alarm.

So, here it is: if quantum computers start breaking cryptography a few years from now, don’t you dare come to this blog and tell me that I failed to warn you. This post is your warning. Please start switching to quantum-resistant encryption, and urge your company or organization or blockchain or standards body to do the same.

Yea, heed my warning, for it comes not from some WordPress-using rando, but from the inventor of BosonSampling and PostBQP and shadow tomography, the Schlumberger Centennial Chair and Founding Director of the Quantum Information Center at the University of Texas at Austin, and (wait for it) new member of the US National Academy of Sciences, that august and distinguished body brought into being by President Abraham Lincoln in 1863.

Because, you know, none of this is about me. It’s only about you. And whether you’ll listen to me.

By Scott

Authors: Tian Bai, Fedor V. Fomin, Petr A. Golovach, Yash Hiren More, Simon Wietheger

Rank aggregation seeks a representative permutation for a collection of rankings and plays a central role in areas such as social choice, information retrieval, and computational biology. Two fundamental aggregation tasks are the center and median problems, which minimize the maximum and the total distance to the input permutations, respectively. While these problems are well understood under Kendall's tau and related distances, their parameterized complexity under the Ulam metric, an edit-distance-based metric on permutations, has remained largely unexplored. In this work, we initiate a systematic study of the parameterized complexity of rank aggregation under the Ulam metric. We consider both the center and median problems, as well as their generalizations to the $k$-center and $k$-median clustering settings, parameterized by the number of centers $k$ and the distance budget $d$ (corresponding to the maximum distance for center variants and the total distance for median variants). Both problems are known to be NP-hard already for $k=1$. We show that the Ulam $k$-center problem remains NP-hard when $d=1$, but is fixed-parameter tractable when parameterized by $k + d$. Our algorithm is based on a novel local-search framework tailored to the non-local nature of Ulam distances. We complement this by proving that no polynomial kernel exists for the $k+d$ parameterization unless NP $\subseteq$ coNP/poly. For the Ulam $k$-median problem parameterized by the total distance $d$, we establish W[1]-hardness and provide an XP algorithm. We also provide a polynomial kernel for the parameter $k + d$, which in turn yields a fixed-parameter tractable algorithm.

Authors: Albert Atserias, Moritz Müller

We prove that the bounded arithmetic theory $S^1_2$ is consistent with EXP $\not\subseteq$ P/poly. More generally, we show that certain separations of $V^1_2$ from a theory $T$ imply the consistency of $T$ with EXP $\not\subseteq$ P/poly. For $T=S^1_2$, Takeuti (1988) established such a separation using a variant of Gödel's consistency statement. Analogous results hold for PSPACE $\not\subseteq$ P/poly but the required separations of theories are yet unknown. Finally, we give magnification results for the hardness of proving almost-everywhere versions of these lower bounds.

Authors: Jakub Jagiełła, Joachim Jelisiejew

We introduce the concise secant varieties, which are, informally speaking, modular partial desingularisations of secant varieties to Segre embeddings. More precisely, they are projective and birational to the abstract secant varieties, yet each of their points corresponds to a concise tensor of appropriate border rank (that is, to a minimal border rank tensor). We discuss implications throughout the theory of tensors, including a characterisation of border rank $\leq r$ tensors as unrestrictions of minimal border rank $r$ tensors (also in the Veronese and Segre-Veronese cases), a characterisation of tensors with cactus rank $\leq r$, concise versions of border apolarity including the fixed point theorem, concise Varieties of Sums of Powers, counting points on the second secant variety, connections to defectivity and identifiability in the Segre case, to the Salmon conjecture etc.

Authors: Yefan Zhi, Yao Lu, Masoud Akbarzadeh

Symmetry is an implicit objective in structural form-finding that often reconciles efficiency and aesthetics. This paper identifies the symmetry of polyhedral diagrams in three-dimensional graphic statics (3DGS) as point groups and formulates them as constraints, enabling the optimization and manipulation of polyhedral diagrams that preserve such symmetry. 3DGS has been an efficient and effective tool for the form-finding of funicular structures. However, when modifying complex diagrams for design exploration or optimization, one can easily break the symmetry of the reciprocal design input, rendering the result undesirable for practical use. To address this problem, this paper investigates symmetry transformations and introduces point groups, an abstract algebra tool commonly used in crystallography to represent the symmetry and equivalence between a network of atoms (points with labels). It then discusses the hierarchy of symmetry in the geometry types of a polyhedral diagram, and proposes the constraint of symmetry through edge lengths. Based on the crystal symmetry search algorithm by spglib and pymatgen, a fast fingerprinting algorithm is developed to identify the point group of a polyhedral diagram and sort equivalent edges into sets. Finally, the paper shows that the necessary and sufficient condition for preserving the point group symmetry is that each set of edges has the same length. This constraint is compatible with the algebraic formulation of 3DGS and effectively preserves symmetry while reducing the dimension of the solution space. The method is implemented in the PolyFrame 2 plug-in for Rhino and Grasshopper.

Authors: Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Johanne M. Vistisen, Sampson Wong

We maintain a $(1+\varepsilon)$-spanner over the disk intersection graph of a dynamic set of disks. We restrict all disks to have their diameter in $[4,Ψ]$ for some fixed and known $Ψ$. The resulting $(1+\varepsilon)$-spanner has size $O(n \varepsilon^{-2} \log Ψ\log (\varepsilon^{-1}))$, where $n$ is the present number of disks. We develop a novel use of persistent data structures to dynamically maintain our $(1+\varepsilon)$-spanner. Our approach requires $O(\varepsilon^{-2} n \log^4 n \log Ψ)$ space and has an $O( \left( \fracΨ{\varepsilon} \right)^2 \log^4 n \log^2 Ψ\log^2 (\varepsilon^{-1}))$ expected amortised update time. For constant $\varepsilon$ and $Ψ$, this spanner has near-linear size, uses near-linear space and has polylogarithmic update time. Furthermore, we observe that for any $\varepsilon < 1$, our spanner also serves as a connectivity data structure. With a slight adaptation of our techniques, this leads to better bounds for dynamically supporting connectivity queries in a disk intersection graph. In particular, we improve the space usage when compared to the dynamic data structure of (Baumann et al., DCG'24), replacing the linear dependency on $Ψ$ by a polylogarithmic dependency. Finally, we generalise our results to $d$-dimensional hypercubes.

Authors: Benjamin Bergougnoux, Vera Chekan, Stefan Kratsch

In this work we contribute to the study of the fine-grained complexity of problems parameterized by multi-clique-width, which was initiated by Fürer [ITCS 2017] and pursued further by Chekan and Kratsch [MFCS 2023]. Multi-clique-width is a parameter defined analogously to clique-width but every vertex is allowed to hold multiple labels simultaneously. This parameter is upper-bounded by both clique-width and treewidth (plus a constant), hence it generalizes both of them without an exponential blow-up. Conversely, graphs of multi-clique-width $k$ have clique-width at most $2^k$, and there exist graphs with clique-width at least $2^{Ω(k)}$. Thus, while the two parameters are functionally equivalent, the fine-grained complexity of problems may differ relative to them. As our first and main result we show that under ETH the Max Cut problem cannot be solved in time $n^{2^{o(k)}} \cdot f(k)$ on graphs of multi-clique-width $k$ for any computable function $f$. For clique-width $k$ an $n^{\mathcal{O}(k)}$ algorithm by Fomin et al. [SIAM J. Comput. 2014] is tight under ETH. This makes Max Cut the first known problem for which the tight running times differ for parameterization by clique-width and multi-clique-width and it contributes to the short list of known lower bounds of form $n^{2^{o(k)}} \cdot f(k)$. As our second contribution we show that Hamiltonian Cycle and Edge Dominating Set can be solved in time $n^{\mathcal{O}(k)}$ on graphs of multi-clique-width $k$ matching the tight running time for clique-width. These results answer three questions left open by Chekan and Kratsch [MFCS 2023].

Authors: Johannes Breitling, Ragnar Groot Koerkamp, Marvin Williams

Priority queues are data structures that maintain a dynamic collection of elements and allow inserting new elements and removing the smallest element. The most widely known and used priority queue is likely the implicit binary heap, even though it is has frequent cache misses and is hard to optimize using e.g. SIMD instructions. We introduce the SimdQuickHeap, a variant of the QuickHeap that was introduced by Navarro and Paredes in 2010. As suggested by the name, the data structure bears some similarity to QuickSort. We modify the data layout of the original QuickHeap to have all \emph{pivots} adjacent in memory, with elements between consecutive pivots stored in dedicated \emph{buckets}. This allows efficient SIMD implementations for both partitioning of buckets and scanning the list of pivots to find the bucket to append newly inserted elements to. The SimdQuickHeap has amortized expected complexity $O(\log n)$ per operation, which improves to $O(\frac 1W\log n)$ in non-degenerate cases, where $W$ is the number of words in a SIMD register. In this case, the I/O-complexity is amortized $O(\frac 1B)$ per push and $O(\frac 1B \log_2 \frac nM)$ per pop. In synthetic benchmarks, the SimdQuickHeap is up to twice as fast as the next-best competitor, including the non-comparison radix heap, and needs around $1.5\log_2 n$ comparisons and $\log_2 n$ nanoseconds per pair of push and pop operations. On graph benchmarks with Dijkstra's shortest path algorithm and Jarnik-Prim's minimum spanning tree algorithm, the SimdQuickHeap is consistently the fastest.

Authors: Jesper Larsson Träff

Parallel scan primitives compute element-wise inclusive or exclusive prefix sums of input vectors contributed by $p$ consecutively ranked processors under an associative, possibly expensive, binary operator $\oplus$. In message-passing systems with bounded, one-ported communication capabilities, at least $\lceil\log_2 p\rceil$ or $\lceil\log_2 (p-1)\rceil$ send-receive communication rounds are required to perform the scans. While there are well-known, simple algorithms for the inclusive scan that solve the problem in $\lceil\log_2 p\rceil$ send-receive communication rounds with $\lceil\log_2 p\rceil$ applications of the $\oplus$ operator, the exclusive scan is different and has been much less addressed. By considering natural invariants for the exclusive prefix sums problem, we present two different algorithms that are efficient in the number of communication rounds and in the number of applications of the $\oplus$ operator. The first algorithm consists of an inclusive scan phase and an exclusive scan phase and trades the number of communication rounds against the number of applications of the $\oplus$ operator. The smallest number of inclusive scan rounds with $q=\lceil\log_2 p\rceil$ rounds in total is $q'\geq q-\log_2(2^q-p+1)$. The other algorithm is a modification of a round-optimal all-reduce algorithm, and the number of additional applications of the $\oplus$ operator is dependent on the number of bits set (popcount of) in $p-1$. Both algorithms are relevant for small(er) input vectors where performance is dominated by the number of communication rounds. For large input vectors, other (pipelined, fixed-degree tree) algorithms must be used.

Authors: Riccardo Dondi, Mohammad Mehdi Hosseinzadeh

This paper addresses the problem of identifying time interval separators in temporal networks. We introduce d-MinIntSep, a new variant of the temporal separator problem, which models failures as time intervals assigned to vertices and aims to block all temporal paths between a source and a target that can be completed within a given deadline d. We prove that the d-MinIntSep problem is NP-hard and hard to approximate within a logarithmic function of the size of the vertex set, assuming P is not equal to NP, and we propose an Integer Linear Programming (ILP) formulation to compute minimum interval separators. This latter method is evaluated on synthetic and real-world temporal networks derived from transportation datasets. The experimental results show that the running time is strongly influenced by the temporal dimension, the imposed deadline, and the density of temporal paths.

Authors: Afrouz Jabal Ameli, Tomohiro Koana, Jesper Nederlof, Shengzhe Wang

The Strongly Connected Steiner Subgraph (SCSS) problem is a well-studied network design problem that asks for a minimum subgraph that strongly connects a given set of terminals. In this paper, we present several new algorithmic and complexity results for SCSS. As our main result, we show that SCSS can be solved in time $17^{\mathrm{tw}} n^{O(1)}$ on directed graphs with $n$ vertices when a tree decomposition of the underlying graph of width $\mathrm{tw}$ is provided. This improves over a natural $\mathrm{tw}^{O(\mathrm{tw})}n^{O(1)}$ time algorithm, and is the first algorithm with this kind of running time for a problem involving strong connectivity. Second, we give an exact exponential-time algorithm that solves SCSS in $2^n n^{O(1)}$ time, improving the known bounds for general directed graphs. Finally, we investigate kernelization with respect to vertex cover. We prove that SCSS does not admit a polynomial kernel when parameterized by the size of a vertex cover, unless the polynomial hierarchy collapses. In contrast, we show that the closely related Strongly Connected Spanning Subgraph problem does admit a polynomial kernel under the same parameterization.

Authors: Georgios Stamoulis

We study the rainbow matching (RM) problem: given an edge-colored graph, find a maximum matching with at most one edge of each color. Rainbow matchings correspond to stable sets in the \emph{augmented} graph $H$ obtained from the line graph by completing each color class into a clique. For a hereditary graph class $\mathcal{X}$, we introduce the parameter $κ_{\mathcal{X}}$ to be the minimum number of colors whose deletion places the \emph{residual} augmented graph in $\mathcal{X}$. We show that this parameter has two complementary flavors. From a polyhedral side, if $\mathcal{X}$ is uniformly rank-$r$ exact, then deleting $k$ colors to obtain a residual augmented graph in $\mathcal{X}$ implies exactness of the Lasserre hierarchy at level $k+r$. This yields, in particular, exactness at level $k+1$ for deletion to perfect, and exactness at level $k+r$ for deletion to $h$-perfect residual graphs of bounded odd-hole rank $r$. Our second result is structural. We show that the right object in this case is the \emph{color-intersection} graph $Γ$ that impacts the topology of the conflict graph $H$ as follows: articulation colors in $Γ$ induce clique-sum decompositions in $H$, so residual obstructions for clique-sum-local hereditary classes $\mathcal{X}$ are embedded in individual blocks. Thus we can test membership of the residual graph in these target classes in a blockwise manner. As a consequence, we give an exact dynamic programming algorithm for computing the deletion parameter when $Γ$ has blocks of bounded size. Finally, once such a deletion set is given, RM can be solved by branching over the deleted color classes and solving residual instances. We also show that computing this parameter is \textbf{NP}-hard already in the chordal targets but it is FPT for classes $\mathcal{X}$ characterized by a set of forbidden induced subgraphs of bounded size.

Authors: Marco Bressan, T-H. Hubert Chan, Qipeng Kuang, Mauro Sozio

In recent years, the problem of computing the frequencies of the induced $k$-vertex subgraphs of a graph, or \emph{$k$-graphlets}, has become central. One approach for this problem is to sample $k$-graphlets randomly. Classic algorithms for $k$-graphlet sampling require loading the entire graph into main memory, making them impractical for massive graphs. To bypass this limitation, Bourreau et al. (NeurIPS 2024) introduced a \emph{streaming} algorithm that through nontrivial techniques makes only $O(\log n)$ passes using $O(n \log n)$ memory. In this work we break their $O(\log n)$-pass bound by giving an algorithm that, for any fixed $c>0$, makes $O(1/c)$ passes using $\tilde O(n^{1+c})$ memory. As a consequence of their lower bound, our algorithm is optimal up to a factor of $\tilde{O}(n^c)$ in the memory usage. We use this sampling algorithm to obtain an efficient method of approximating $k$-graphlet distributions. Experiments on real-world and synthetic graphs show that our algorithm is always at least as good as the one of Bourreau et al., and outperforms it by orders of magnitude on mildly dense graphs.

Authors: Benedikt Peterseim, Milan Lopuhaä-Zwakenberg

Discrete probabilistic programs (DPPs) provide a highly expressive formalism for compactly defining arbitrary finite probabilistic models. This expressivity comes at a price: DPP inference is PSPACE-hard. In this work, we show that DPP inference only takes polynomial time for programs that are 'structurally simple'. More precisely, inference can be performed in polynomial time when the primal graph of each function appearing in the probabilistic program has bounded treewidth, and the inverse acceptance probability is at most exponential in the size of the probabilistic program. Existing algorithms do not achieve this performance guarantee. Our method relies on finding suitable decompositions, algebraisations, of the string diagrams underlying DPPs, employing existing algorithms for tree decompositions. This is independent of the probabilistic setting of DPPs and has direct applications to many problems, such as evaluating queries on relational databases and cybersecurity risk assessment via attack trees.

Authors: Eric Balkanski, Jason Chatzitheodorou, Flore Sentenac

For the classical maximum coverage problem, the greedy algorithm achieves a worst-case $1-1/e$ approximation, which is optimal unless $\text{P} = \text{NP}$. The notion of coverage appears in a wide range of optimization tasks, where empirical evaluations indicate approximation ratios close to $1$ for the greedy algorithm on real data. Random models have provided average-case justifications for the empirical performance of many well-known algorithms, but little is known about the average-case performance of greedy for maximum coverage. We analyze the expected approximation ratio of the greedy algorithm in a random model, which we call the left-regular random model. We first show that, for all parameter settings of this model, the expected approximation ratio of the greedy algorithm improves by a constant over its worst-case $1-1/e$ guarantee. We then identify two simple conditions, either of which ensures that the expected approximation ratio is close to $1$ for sufficiently large graphs. Finally, we show that there is a regime where greedy does not achieve an expected approximation better than $0.94$. To obtain these results, we develop analytical tools, including a novel application of the differential equation method and a connection to maximum matching in Erdős-Rényi graphs, which may be of independent interest for other random models.

Authors: Nishant Shukla

Coherent quantum rollout for sequential decision problems requires a unitary simulator: randomness must live in explicit quantum registers, and basis-state selectors must be mapped to actions reversibly. With branch-dependent valid actions, this mapping is totalized coherent rank-select over an entangled $N$-bit validity mask: return the position of the $r$-th valid bit, or a sentinel if $r$ is out of range. We give the first reversible-circuit complexity analysis of this primitive. For selector width $w = \lceil \log_2(N+1) \rceil$, rank-select admits an $O(Nw)$-gate low-ancilla bounded-span scan, proved gate-optimal in its model, and an $O(N\log w)$-gate low-ancilla blocked construction when long-range gates are available; across all bounded-fan-in layouts, the unconditional gate lower bound is $Ω(N)$. Composing rank-select with reversible transition and predicate-evaluation circuits gives an explicit polynomial-size coherent rollout oracle for finite-horizon planning problems satisfying these primitive assumptions. The resulting oracle satisfies the access model of the best-arm pipeline of Wang et al., yielding $\widetilde{O}(\sqrt{k}/\varepsilon)$ coherent oracle calls against the standard classical $Ω(k/\varepsilon^2)$ arm-pull lower bound. We give a bounded-influence lifting theorem that extends this lower-bound construction from a base configuration to an exponential family of configurations. We instantiate the construction on SIR epidemic intervention, with a stochastic placement-game sanity check, and machine-check the main results in Lean 4. Code and proofs: https://github.com/BinRoot/b01t/tree/main/demos/rollout.

Good news: Email from Knuth. Bad news: It begins “is there a bug in your paper?” The paper in question is “The traveling salesman problem for cubic graphs” (WADS 2003 and JGAA 2007). Of course the bug report is accurate, but fortunately it can be easily patched.

My paper has algorithms for finding a minimum-weight Hamiltonian cycle (when it exists), in an \(n\)-vertex graph of maximum degree three, in time \(O(2^{n/3})\), and for listing all Hamiltonian cycles in time \(O(2^{3n/8})\). Both have since been improved by others. Maciej Liśkiewicz and Martin R. Schuster gave an algorithm for the minimum-weight cycle with time \(O(1.2553^n)\) in their paper “A new upper bound for the traveling salesman problem in cubic graphs” [J. Discrete Algorithms 2014], and Heidi Gebauer gave an algorithm for listing all cycles in time \(O(1.276^n)\) in her paper “Enumerating all Hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs” [Elect. J. Combinatorics 2011]. Despite these improvements, I think it’s interesting enough to examine what the issue was with my paper and how to work around it.

The bug is in the case analysis for the algorithm to list all Hamiltonian cycles. The minimum-weight algorithm includes a case where a triangle is contracted into a single vertex. However, for some reason the cycle-listing algorithm omitted that case, and then later tried to assume there were no triangles, but without a valid justification for this assumption. It’s not impossible that the rest of the analysis goes through without using the assumption of no triangles, but working out the details looks messy.

Both algorithms in the paper work with a more general problem in which, together with an input graph, one is given “forced edges” which are required to be included in any Hamiltonian cycle. This allows certain simplifications in which, for instance, paths through degree-two vertices or paths of multiple forced edges can be compressed into single forced edges. It’s important when listing cycles that the input is a simple graph, not a multigraph, because multigraphs can have as many as \(O(2^{n/2})\) Hamiltonian cycles. So, when this sort of compression produces a forced edge that’s parallel to an unforced edge, the unforced edge can be deleted, and when it produces two parallel forced edges, there can be no Hamiltonian cycle and the algorithm backtracks. After these simplifications, one can assume that the graph is simple and 3-regular rather than merely having maximum degree three, and that no two forced edges are adjacent. But it might still have some triangles.

With that as background, it is indeed possible to eliminate the triangles. Here are the missing cases to do so.

• If a triangle includes a forced edge, then the opposite edge entering the triangle should also become forced. (The paper included a case with the opposite implication, but this direction is needed to preserve the forcing information after the contraction of a triangle, below.) So in the image below, if either of the two thick edges is forced, the other one should be too.

• If there exists a triangle that does not share any of its edges with another triangle, contract it. Hamiltonian cycles in the contracted graph correspond one-for-one with Hamiltonian cycles in the uncontracted graph, and (with no shared edges) this contraction will not create any parallel edges.

• If there exist two triangles that share an edge, then there are two paths through their four vertices that might extend to Hamiltonian cycles. If only one of these two paths is consistent with the forced edges within this subgraph, add the rest of its edges to the forced set; their contraction will eliminate the triangles. Otherwise, make two recursive branches, each with one of the two paths added to the forced set. Each branch eliminates four previously-unforced edges, consistent with the analysis of the other cases in this part of the paper.

As far as I know, another problem from the same paper remains open. The paper constructs a family of cubic graphs that have \(2^{n/3}\) Hamiltonian cycles, but the cycle-listing algorithm proves only that the number of cycles is always \(O(2^{3n/8})\), a bigger number. Gebauer’s paper improves the upper bound, but it still does not match the lower bound. Is \(2^{n/3}\) the maximum number of Hamiltonian cycles in an \(n\)-vertex 3-regular graph?

(Discuss on Mastodon)

By David Eppstein

June 14-18, 2026 Hebrew University, Israel https://iias.huji.ac.il/event/25th-midrasha-mathematicae-groups-expanders-and-codes In the past few years, there has been several exciting developments at the confluence of pure mathematics and theoretical computer science. These include: The refutations of Connes’ embedding problem and the Aldous–Lyons conjecture using tools from group stability, complexity theory and quantum information theory. The construction of good … Continue reading Groups, Expanders and Codes – Celebrating the 70’s birthday of Alex Lubotzky

By shacharlovett

Authors: Nirmit Joshi, Roey Magen, Nathan Srebro, Nikolaos Tsilivis, Gal Vardi

We study learning with Chain-of-Thought (CoT) supervision from multiple thinkers, all of whom provide correct but possibly systematically different solutions, e.g., step-by-step solutions to math problems written by different thinkers, or step-by-step execution traces of different programs solving the same problem. We consider classes that are computationally easy to learn using CoT supervision from a single thinker, but hard to learn with only end-result supervision, i.e., without CoT (Joshi et al. 2025). We establish that, under cryptographic assumptions, learning can be hard from CoT supervision provided by two or a few different thinkers, in passive data-collection settings. On the other hand, we provide a generic computationally efficient active learning algorithm that learns with a small amount of CoT data per thinker that is completely independent of the target accuracy $\varepsilon$, a moderate number of thinkers that scales as $\log \frac{1}{\varepsilon}\log \log \frac{1}{\varepsilon}$, and sufficient passive end-result data that scales as $\frac{1}{\varepsilon}\cdot poly\log\frac{1}{\varepsilon}$.

Authors: Olivier Bournez

What do recurrent neural networks, polynomial ODEs, and discrete polynomial maps each bring to computation, and what do they lack? All three operate over the continuum--real-valued states evolved by real-valued dynamics--even when the target functions are discrete. We study them through primitive recursion. We prove that primitive recursion admits equivalent characterizations in all three frameworks: bounded iteration of a fixed recurrent ReLU network, robust computation by a fixed polynomial ODE, and iteration of a fixed polynomial map with an externally supplied step-size parameter. In each, the time bound is itself primitive recursive, composition emerges from the dynamics rather than as a closure rule, and inputs are raw integer vectors. Every primitive recursive function is first compiled into bounded iteration of a single threshold-affine normal form, then interpreted as a ReLU computation and as a polynomial ODE. The equivalences expose a structural asymmetry: no fixed polynomial map can round uniformly to the nearest integer or realize exact phase selection--operations polynomial ODEs perform robustly via continuous-time flow. Each formalism compensates for a limitation the others lack: the ReLU gate provides exact branching, continuous time provides autonomous rounding and control, and the step-size parameter recovers both at the cost of discretization precision. This opens dynamical characterizations of subrecursive hierarchies and complexity classes by restricting time bounds, polynomial degrees, or discretization resources within one framework. More broadly, these models do not compute by composing subroutines: they shape the trajectory of a dynamical system through clocks, phase selectors, and error correction built into the dynamics. This differs structurally from symbolic programming, and our theorem gives a precise framework to study the difference.

Authors: Petr A. Golovach, Laure Morelle, Daniël Paulusma

An identification of two vertices $u$ and $v$ in a graph replaces them with a new vertex whose neighborhood is the union of the neighborhoods of $u$ and $v$. We study the {\sc ${\cal H}$-Identification} problem, which is to decide whether a given graph $G$ can be transformed (``identified'') to a graph in ${\cal H}$ by applying at most $k$ vertex identifications. We determine the classical and parameterized complexity of this problem for various subclasses ${\cal H}$ of chordal graphs, obtaining an almost complete picture for two parameters: $k$ and $n-k$. We also consider the {\sc Identification} problem, which is to test for two given graphs $G$ and $H$ if $G$ can be identified to $H$. We determine the parameterized complexity of this problem when $H$ is a graph from one of our testbed classes, taking the number of simplicial vertices of $H$ as the parameter.

Authors: Srijan Chakraborty, Samir Datta, Aryan Kusre, Partha Mukhopadhyay, Amit Sinhababu

Understanding the power of space-bounded computation with access to catalytic space has been an important theme in complexity theory over the recent years. One of the key algorithmic results in this area is that bipartite maximum matching can be computed in catalytic logspace with a polynomial-time bound, Agarwala and Mertz (2025). In this paper, we show that we can construct a \emph{maximum matching} in \emph{general graphs} in CL, and, in fact, in CLP. We first show that the size of a \emph{maximum matching} in \emph{general graphs} can be determined in CL. Our algorithm is based on the linear-algebraic algorithm for maximum matching by Geelen (2000). We then show that this algorithm, along with some new ideas, can be used to \emph{find} a maximum matching in general graphs. Using a similar algorithm of Geelen (1999), we also solve the \emph{maximum rank completion problem} in CLP, which was previously known to be solvable in deterministic polynomial time, Geelen. This problem turns out to be equivalent to the \emph{linear matroid intersection} problem (shown by Murota, 1995) which has been shown to be in CLP by Agarwala, Alekseev, and Vinciguerra (2026). Finally, using a PTAS algorithm Bläser, Jindal and Pandey (2018), for approximating the rank in Edmond's problem, we derive a CLP algorithm that can approximate the rank given by any instance of the \emph{Edmond's problem} upto a factor of $(1-\eps)$ for any $\eps\in(0,1)$. An application of this is a CLP bound for approximating the maximum independent matching in the \emph{linear matroid matching} problem.

Authors: Tala Eagling-Vose, Barnaby Martin, Daniël Paulusma, Nicolas Trotignon

We consider the $H$-Induced Minor problem: for a fixed graph~$H$, decide whether a given graph $G$ contains $H$ as an induced minor. While the problem is known to be NP-complete for some trees~$H$ on more than $2^{300}$ vertices, the complexity for small trees remains unresolved. In particular, the case where $H$ is the $7$-vertex tree consisting of a path on five vertices with a pendant vertex attached to the second and fourth vertex was a long-standing open problem. We show that this case is polynomial-time solvable by developing algorithms that detect a sequence of carefully chosen substructures. Complementing this, we prove that detecting some of these substructures individually is NP-hard. We also give polynomial-time algorithms for three cases where $H$ is a graph on five vertices (that is not a tree). In this way, we completed the classification of $H$-Induced Minor for graphs $H$ on five vertices and answered an open problem of Dallard, Dumas, Hilaire and Perez (2025).

Authors: Marius Bozga, Radu Iosif, Florian Zuleger

Series-parallel (SP) graphs are binary edge-labeled graphs with a designated source and target vertex, built using serial and parallel composition. A set of graphs is recognizable if membership depends only on its image under a homomorphism into a finite algebra. For SP-graphs, and more generally, for graphs of bounded tree-width, recognizability coincides with definability in Counting Monadic Second-Order (CMSO) logic. Despite this strong logical characterization, the conciseness and algorithmic effectiveness of syntactic representations of recognizable sets of SP (and bounded-tree-width) graphs remain poorly understood. Building on previously introduced regular grammars for SP-graphs, we show that recognizable sets admit concise and effective syntactic representations. The main contribution is an improved construction of finite recognizer algebras whose size is singly-exponential in the size of a regular grammar, improving upon the previously known double-exponential bound. As a consequence, the problems of intersection and language inclusion for sets represented by regular grammars are shown to be ExpTime-complete, thus improving on a previously known 2ExpTime upper bound.

Authors: Aleksandr Koshkarov, Nadia Tahiri

Comparative analyses of phylogenetic trees typically require identical taxon sets, however, in practice, trees often include distinct but overlapping taxa. Pruning non-shared leaves discards phylogenetic signal, whereas tree completion can preserve both taxa and branch-length information. This work introduces a polynomial-time algorithm for set-wide completion of phylogenetic trees with partial taxon overlap. The proposed method identifies and extracts maximal completion subtrees that frequently appear across the source trees and constructs a weighted majority-rule consensus. Branch lengths are scaled using rates derived from common leaves. Each consensus subtree is inserted at the position that minimizes the quadratic distance error measured against information from the source trees, with candidate positions restricted to the original branches of the target tree. We demonstrate that the algorithm runs in polynomial time and preserves distances among the original taxa, yielding a unique completion that is order-independent with respect to the processing order of target trees. An experimental evaluation on amphibians, mammals, sharks, and squamates shows that the proposed method consistently achieves the lowest distance to the subset reference trees across subsets among all methods, in both topology and branch lengths. An open-source Python implementation of the proposed algorithm and the biological datasets utilized in this study are publicly available at: https://github.com/tahiri-lab/overlap-treeset-completion/.

Authors: Marco Carmosino, Ngu Dang, Tim Jackman

Gate elimination is the primary technique for proving explicit lower bounds against general Boolean circuits, including Li and Yang's state-of-the-art $3.1n - o(n)$ bound for affine dispersers (STOC 2022). Every circuit lower bound is implicitly existential: every circuit that is too small to compute $f$ must err on some input. This raises a natural question: are these lower bounds \emph{constructive}? That is, can we efficiently produce such errors? Chen, Jin, Santhanam, and Williams showed that constructivity plays a central role in many longstanding open problems in complexity theory, and explicitly raised the question of which circuit lower bound techniques can be made constructive (FOCS 2021). We show that a variety of gate elimination arguments yield refuters -- efficient algorithms that, when given a circuit that is too small to compute a function $f$, produce an input on which the circuit errs. Our results range from elementary lower bounds for $XOR$ and the multiplexer to more sophisticated arguments for affine dispersers. Underlying these results is a shift in perspective: gate elimination arguments \emph{are} algorithms. Each step either simplifies the circuit or reveals a violation of some structural or functional property, from which, with a little additional work, explicit counterexamples can be extracted. We further strengthen the $XOR$ result to handle circuits that \emph{match} the lower bound: given any DeMorgan circuit of size $3(n-1)$ that fails to compute $XOR_n$, we can efficiently produce a counterexample. While refuters follow from the gate elimination arguments themselves, this refinement requires a complete characterization of the set of optimal circuits computing $XOR$ -- a requirement rarely met by other explicit functions.

Authors: Arnaud Casteigts, Christian Komusiewicz, Nils Morawietz

Temporal graphs are graphs whose edges are only present at certain points in time. Reachability in these graphs relies on temporal paths, where edges are traversed chronologically. A temporal graph that offers all-pairs reachability is said to be temporally connected (or TC). For temporal graphs that are not TC, a natural question is whether they admit a TC subgraph (a.k.a. closed temporal component) of a given size $k$. This question was one of the earliest in the field, shown to be NP-hard by Bhadra and Ferreira in 2003. We strengthen this result dramatically, showing that deciding if a TC subgraph exists on at least $3$ vertices is already NP-hard in all the standard temporal graph settings (directed/undirected and strict/non-strict through simple and proper reductions). This implies a strong separation between closed temporal components and open temporal components (where temporal paths can travel outside the component), for which inclusion-maximal components can be found in polynomial time. As a by-product, our reductions strengthen a number of existing results and establish new derived results. They imply that the size of the largest TC subgraph cannot be approximated within a factor of $(1-ε)n$ in directed graphs, and within a factor of $(1-ε)\frac{n}{2}$ in undirected graphs. One of the reductions also completes the complexity landscape for TC subgraphs of size exactly $k$ when parameterized by $k$ (answering the missing non-strict case). Finally, on the structural side, our results imply that there exist arbitrarily large TC graphs of constant lifetime without nontrivial TC subgraphs, and we also show that there exist TC graphs of arbitrary girth, both facts being of independent interest.

Authors: Kenta Watanabe

For a smooth irreducible curve $C$, its second gonality $d_2$ is defined to be the minimum integer $d$ such that $C$ admits a linear series $g_d^2$. In this paper, we compute the second gonality of a smooth aCM curve $C$ lying on a smooth quartic surface in $\mathbb{P}^3$, whose Clifford index is computed by a net on $C$.

Authors: Jacobus Conradi, Ivor van der Hoog, Frederikke Uldahl, Eva Rotenberg

The Fréchet distance is a popular distance measure between trajectories or curves in space, or between walks in graphs. We study computing the Fréchet distance between walks in the $d$-dimensional grid graphs, i.e. $\mathbb{Z}^d$ where points share an edge if they differ by one in one coordinate. We give an algorithm, that for two simple paths on $n$ vertices, $(1+\varepsilon)$-approximates the Fréchet distance in time $\widetilde{O}((\frac{n}{\varepsilon})^{2-2/d} +n)$. We complement this by a near-matching fine-grained lower bound: for constant dimensions $d \geq 3$, there is no $O((\varepsilon^{2/d}(\frac{n}{\varepsilon})^{2-2/d})^{1-δ})$ algorithm for any $δ>0$ unless the Orthogonal Vector Hypothesis fails. Thus, our results are tight up to a factor $\varepsilon^{2/d}$ and $\log(n)$-factors. We extend our results to imbalanced lower and upper bounds, where the curves have $n$ and $m$ vertices respectively, and also obtain near-tight bounds. Driemel, Har-Peled and Wenk [DCG'12] studied \emph{realistic assumptions} for curves to speed up Fréchet distance computation. One of these assumptions is $λ$-low density and they can compute a $(1+\varepsilon)$-approximation between $λ$-low dense curves in time $\widetilde{O}( \varepsilon^{-2} λ^2 n^{2(1-1/d)})$. By adapting our lower bound, we show that their algorithm has a tight dependency on $n$ and a tight dependency on $\varepsilon$ as $d$ goes to infinity. A gap remains in terms of $λ$.