Theory of Computing Report

As I’ve written before, these past couple years I’ve often felt like the last remaining person in either quantum computing or AI who lacked a stake in some startup company whose valuation is right now shooting into interstellar space. My academic colleagues, including the ones who seemed the most singleminded about quantum oracle separations and other gloriously useless pursuits? One by one, like in a zombie movie, I learn that they too have now launched startups, and invariably raised tens of millions of dollars, for the sorts of ideas we might’ve idly traded at coffee breaks back in the day, before getting back to our real work.

So why didn’t I join this rollicking party? Partly because of a lifelong fear that, the instant my self-worth became tied to how much money I made, I’d need to humble myself before people who bluster and bully and lie and hype and conceal … yet who nevertheless succeed at becoming orders of magnitude richer than me. I’ve been terrified of even starting down that road, of whether I’d still be myself at the end of it.

It’s also partly that I can’t stand failure, or regret, or being wrong. Of course, as an academic researcher I also fail, and regret things, and am wrong constantly—but there it feels tolerable, because normally I can tell myself that it’s all just down to my inborn limitations. After all, if I could’ve solved the major open problem that someone else solved, or written the brilliant book that someone else wrote, then presumably I would’ve done it!

Clearly, though, I could’ve mined bitcoin in 2010. I could’ve gotten an early stake in Amazon or Google. It’s not even like those ideas never crossed my mind. I just … didn’t act on them, for some reason. (But even if I had, I’d probably just be full of regret that I hadn’t done even more.) Thus, my only way to avoid paralyzing regrets, has been to tell myself constantly that I’m not in the forecasting or money-making businesseses in the first place.

It helped that, insofar as I’m shallow or covetous, insofar as I’ve desired things of this world rather than insight or eternal truth, it’s never really been money that I cared about, but just being respected and liked. Elon Musk is the richest man on earth, but also one of the most despised—which isn’t a bargain that I could imagine ever appealing to me.

Plus, when I actually meet billionaires, I don’t find myself envious of their mansions or cars or anything else that they have; I don’t feel like such things would make my life any happier. Maybe I slightly envy their ability to fund the causes they care about, or their professional staffs who relieve them of drudgery, but mostly I envy the way their wealth announces, to whatever extent it does: “I was right when others weren’t.” Again, though, I’ve never trusted the world to cause me to be right about the future valuations of companies or anything similar, so I’ve settled for having been right about PostBQP and algebrization and BosonSampling.

The bottom line is that I made a choice decades ago to forgo trying to get rich, no matter how many of my friends did the same, and to strive instead to discover and tell the truth—to be a professor, a blogger, a jokester, and an “objective” arbiter and commentator. “Then, surely, everyone will like me!” my internal monologue went. “Then, surely, they’ll be grateful for all the free service I’ve rendered them—for decades of blogging, without once so much as asking for a donation or running an ad!”

HAHAHAHAHAHA.

As any regular reader will know, my attempts to be loved as a blogger backfired pretty spectacularly. Or rather: they did lead to thousands of strangers liking me (and I’m grateful for every last one of you), but they also led to probably an order of magnitude more strangers hating me, and congregating on Reddit and Twitter and elsewhere to discuss how badly I suck. And of course, trying to shift that balance by writing what people want to hear, rather than what I actually believe, was never within my realistic option set.

In the startup context, it didn’t matter how carefully I avoided taking a direct stake for or against any of the companies I blogged about. People on Twitter simply assumed that I had a stake—for example, that I must’ve shorted D-Wave or IonQ, or invested in their competitors, or had equity in AI companies. For why else would anyone write what I wrote?

Amusingly, my attackers here typically did have precisely the conflicts-of-interest that they falsely accused me of having, but that was never at issue; only my imaginary conflicts-of-interest were. Even as the Scott-haters greedily filled their pockets (or tried to), I alone needed to keep turning my pockets out to prove that they were still empty.

So then, screw it! In partnership with my brother David Aaronson, who’s long done investing professionally, and on David’s guidance and encouragement, I’m hereby embarking on a new policy.

Namely: when I hear about a brand-new startup that sounds relevant to my interests—in quantum, AI, or anything else—and I like and trust the founders (ideally, because of their previous academic research work), David and I will often make a small seed investment if the founders are open to it. Or, of course, we might become advisors or get involved in some other way.

In fact, David and I are launching BQP Partners—the link goes to our AngelList, where you can read about how to invest with us if you’re interested. (See also whether you can spot any differences between David’s writing style and preoccupations and mine!)

So far, David and I are investing in:

• Oratomic (the new neutral-atom quantum computing startup out of Pasadena started by Dolev Bluvstein, John Preskill, and Hsin-Yuan Huang among others, which I previously blogged about here). See here for their Series A announcement this week.
• A non-quantum startup being cofounded by someone whose scientific work I’ve admired. I’ll write more about this one as soon as I’m able to!

I have little doubt that more potential investments will come our way very soon (some, probably, as a direct result of this post).

Crucially, I can handle my burden of regret—the “why didn’t I do this much earlier, if I was going to do it at all?” question—by telling myself that friends of mine were not founding companies left and right until very recently. I can also tell myself that I’m doing this less as a bet about the future (in which case … what if I’m wrong?), than simply as a way to support brilliant colleagues doing things that I genuinely admire.

When I blog about a company, I’ll always disclose if I have a financial position that presents a clear conflict of interest, so you can judge for yourself whether to listen to me. (Although, if that’s the sort of thing you’d demand, then you probably weren’t listening to me in the first place, were you?)

Having reflected on it a lot these past few months, I’m happy with my new policy and with my and David’s new venture, and I’m curious to see where it goes. I’m at peace with the possibility that we’ll lose our shirts, but I’m even at peace with a more disturbing possibility—that we’ll make millions and then people will scream at me online for being a sellout, a hack, and a shill. Those people, as I’ve learned, were going to scream at me anyway.

By Scott

Authors: Jayakrishnan Madathil, Kitty Meeks, Marc Roth

We study the structural expressivity and the parameterised complexity of counting homomorphisms from small temporal patterns to large temporal graphs. Here, a temporal pattern $P$ consists of a graph together with a partial order on its edges, and a homomorphism from $P$ to a temporal graph must not only preserve edges, but also satisfy the temporal constraints imposed by the partial order of the edge set of the pattern. The main results of this work are three-fold: First, we prove a temporal Lovász-style theorem, stating that two temporal graphs are isomorphic (under a natural definition of temporal isomorphisms) if and only if they have the same number of homomorphisms from all temporal patterns. Second, we introduce a cliquewidth-based measure on temporal patterns, called the temporally order-augmented dual width, the "toadwidth" for short, and show that counting temporal homomorphisms is fixed-parameter tractable for temporal patterns of bounded toadwidth. Third, we provide a parameterised complexity dichotomy with an explicit tractability criterion for counting homomorphisms from totally ordered temporal patterns, classified along their underlying graph structure.

Authors: Hantao Yu

We prove that the minimum edge-outerplanarity of a planar graph can be computed in polynomial time, resolving an open problem of Bentz (2009). The proof was initially produced by GPT~5.5 Pro and then verified and polished manually.

Authors: Madhumita Kundu, Daniel Lokshtanov, Soumi Nandi, Saket Saurabh, Kushal Singanporia

Geometric covering problems ask for a small family of geometric objects whose union covers a given point set. We study the more restrictive \emph{boundary covering} variant, where every point must lie on the boundary of a chosen object. Motivated by the framework of Langerman and Morin\,[Discret.\ Comput.\ Geom., 2005] for hyperspheres, we initiate the study of boundary covering by axis-parallel rectangles. We first consider the \emph{discrete} setting, where rectangles must be selected from a given family. We define \bcdaprfull\ (\bcdaprshort): given a point set \(P\subseteq\mathbb{R}^2\), a family \(\mathcal{R}\) of axis-parallel rectangles, and an integer \(k\), decide whether \(P\) can be covered by the boundaries of at most \(k\) rectangles from \(\mathcal{R}\). We prove that \bcdaprshort\ is \(\mathrm{W}[1]\)-hard parameterized by \(k\). We then study the \emph{continuous} variant, \prbcfull\ (\prbcshort), where rectangles may be placed freely. Given \(P\subseteq\mathbb{R}^2\) and \(k\), the goal is to decide whether \(P\) can be covered by the boundaries of at most \(k\) axis-parallel rectangles. In contrast to the discrete case, we show that \prbcshort\ is fixed-parameter tractable, with running time \(2^{\cO(k\log k)}\cdot n^{\cO(1)}\), where \(n=|P|\). Our algorithm relies on a structural analysis of how \(k\) rectangles interact with the point set, reducing \prbcshort\ to at most \(2^{\cO(k\log k)}\) instances of \ddmtcsp, each solvable in polynomial time. On the hardness side, we prove NP-completeness for boundary covering by axis-aligned \(L\)-shapes and use this reduction to establish NP-completeness of \prbcshort.

Authors: Duen Horng Chau, Donghao Ren, Fred Hohman, Dominik Moritz

While UMAP is widely used for exploring high-dimensional data, typical workflows focus on its lower-dimensional embedding, largely overlooking the rich k-nearest-neighbor (kNN) graph that UMAP constructs internally. This graph encodes the data manifold in its original high-dimensional space, before the distortion that UMAP's 2D projection introduces. We demonstrate the untapped potential of this internal representation, showing how standard graph algorithms applied to this graph enhance data sensemaking: (1) PageRank identifies representative data points, (2) k-core decomposition reveals dense core regions versus sparse periphery, and (3) clustering coefficient detects tight-knit neighborhoods with highly-similar data points. Through quantitative and qualitative evaluation on MNIST and Fashion MNIST, we show that these graph-based analyses are not only practical but also competitive with or complementary to purpose-built methods (e.g., k-medoids for exemplar selection, HDBSCAN for density-based clustering).

Authors: Wei Tang, Hanrui Zhang

Forecast aggregation aims to combine information from multiple Bayesian experts' forecasts into an aggregate forecast. In much of this literature, however, the aggregate forecast is optimized for a particular loss or robustness criterion and need not itself be calibrated with respect to the outcome. We introduce and study expert aggregation, where the goal is instead to aggregate Bayesian experts into a new expert that continues to provide calibrated forecasts. In particular, we consider a setting where each input expert reports calibrated predictions, and the aggregator observes the prior distribution over states, and the input experts, but not the underlying Bayes probabilities of the states. We ask whether one can (i) construct a calibrated output expert that Blackwell refines a target expert and cannot be further Blackwell improved using the available information; and (ii) when a proper loss is specified, compute a nearly loss-optimal expert among all such refinements. We formulate calibrated experts as reduced-form information structures and measure refinement by Blackwell dominance of the induced prediction distributions. We characterize the constructible output experts through observable linear information: the input experts generate a linear system whose row space determines which calibrated output predictions are identifiable, and a new expert is constructible exactly when its predictions lie in the associated observable nonnegative cone. We establish a sharp algorithmic picture. When randomized output experts are allowed, both questions above admit efficient algorithms. In contrast, deterministic output experts are computationally intractable: deciding whether a deterministic calibrated refinement exists is $\mathsf{NP}$-hard, and deterministic proper-loss optimization admits no multiplicative PTAS unless $\mathsf{P}=\mathsf{NP}$.

Authors: Estéban Gabory

A \emph{generalized degenerate string} (GD) is a sequence $T=T_1\dots T_n$ of nonempty finite sets of strings, called \emph{segments}, such that all strings in a segment have the same length. Given a solid pattern $P$, GD string matching asks whether $P$ occurs in $T$. Ascone et al. (WABI 2024) identified this as the main remaining boundary case in the fine-grained complexity of pattern matching on variable strings, between variants with near-linear algorithms and those with SETH-based quadratic lower bounds. We give a $\tilde{\mathcal O}(N\sqrt m)$-time algorithm, where $N$ is the total size of $T$ and $m=|P|$, placing GD matching on the subquadratic side of this boundary. We also study indexing. For elastic-degenerate strings (ED), which drop the equal-width restriction, Gibney (SPIRE 2020) obtained $\mathcal O(nm^2)$ query time after linear preprocessing. We adapt this index to GD strings, obtaining $\mathcal O(nm)$ query time. Conversely, under SETH, we rule out GD indices with polynomial preprocessing and query time $\mathcal O(n^{1-\varepsilon}m^{\mathcal O(1)}+m)$. Under the $k$-Clique conjecture, we further rule out combinatorial GD indices with query time $\mathcal O(n^{\mathcal O(1)}m^{1-\varepsilon}+m)$, and combinatorial ED indices with query time $\mathcal O(n^{\mathcal O(1)}m^{2-\varepsilon})$, matching the quadratic dependence on $m$ in Gibney's upper bound. Finally, under the OMv conjecture, we show that, after polynomial preprocessing of a string set and a pattern, active-prefix queries on a bit vector of length $m$ cannot be answered in $\mathcal O(m^{2-\varepsilon})$ time. Since these queries are the standard bottleneck in ED matching, improving indexed ED queries below $\mathcal O(n^{\mathcal O(1)}m^2)$ would require both non-combinatorial techniques and an approach that avoids using active-prefix queries as the main bottleneck.

Authors: Ripley Becker, Sourav Chakraborty, Debarshi Chanda, A. Pavan, N. V. Vinodchandran

We introduce a streaming model with \emph{catalytic memory}, an auxiliary workspace that must be returned to its initial state at the end of the computation. We show that catalytic space yields dramatic space savings for data stream algorithms. We first study the exact computation of frequency moments in insertion-only data streams. For every $k\ge1$, we give an exact four-pass algorithm for computing $\mathbb{F}_{k}$ using $O(k\log m)$ clean space, where $m$ is the stream length. We also present a $(k+1)$-pass algorithm with the same clean-space complexity that uses a factor of $k$ less catalytic space than the four-pass algorithm. For small moments, we obtain stronger results. In particular, we show that $\mathbb{F}_{2}$ and $\mathbb{F}_{3}$ can be computed exactly in two and three passes, respectively, using only $O(\log m)$ clean space. Additionally, we show that exact $\mathbb{F}_{0}$ computation reduces to computing $\mathbb{F}_{k}$ for a suitably chosen large value of $k$, resulting in an exact four-pass algorithm for $\mathbb{F}_{0}$ using only $O(\log m)$ clean space. We further show how our frequency-moment algorithms can be used to exactly count induced occurrences of any fixed graph $H$ in a graph stream, yielding a four-pass algorithm that uses $O_H(\log n)$ clean space, where $n$ is the number of vertices in the graph. As a special case, we obtain an exact three-pass algorithm for triangle counting using $O(\log n)$ clean space. All of our algorithms are multi-pass. We complement these algorithmic results with a matching limitation showing that catalytic memory does not provide additional power in the single-pass setting. Specifically, we prove that every randomized or deterministic single-pass streaming algorithm using $s$ bits of clean memory and catalytic space can be simulated in the standard streaming model, without catalytic memory, using $O(s)$ space.

Authors: Nicolas Menand, Erik Waingarten

We provide a local computation algorithm to approximate the top eigenvector $x \in \mathbb{R}^n$ of a symmetric matrix $A \in \mathbb{R}^{n \times n}$ with entries between $-1$ and $1$, building on the work of Swartworth and Woodruff [SODA 25] who show how to approximate the eigenvalues up to additive-$\varepsilon n$ error using $\tilde{O}(1/\varepsilon^4)$ queries. Our local computation algorithm has a preprocessing complexity of $\tilde{O}(1/\varepsilon^4)$ and per-coordinate query complexity of $\tilde{O}(1/\varepsilon^2)$ for an additive-$\varepsilon n$ approximation whenever {$|λ_{\min}(A)| = O(λ_{\max}(A))$. When $λ_{\min}(A)$ greatly exceeds $λ_{\max}(A)$, our complexity degrades to at most $\tilde{O}(1/\varepsilon^{6.\overline{6}})$ in preprocessing and $\tilde{O}(1/\varepsilon^{3.\overline{3}})$ per query. Furthermore, we show a lower bound of $Ω(n/\varepsilon^2)$ on the total number of queries needed to output an approximately top eigenvector (implying that the per-coordinate query complexity of $Ω(1/\varepsilon^2)$ is necessary). As an application, we use our algorithm to provide local computation algorithms for the sparsest-cut and max-cut problems in the dense graph model of Goldreich, Goldwasser, Ron [JACM 98]. By accessing the top eigenvectors (of an approximate normalized adjacency), we implement local versions of Cheeger's inequality and Trevisan's algorithm [SICOMP 12] to obtain "square-root-opt" approximations in polynomial time (as opposed to exponential-in-$\text{poly}(1/\varepsilon)$ time which is incurred in Goldreich, Goldwasser, Ron.

Authors: Harrison Grodin, Ethan Chu, Runming Li, Jan Hoffmann, Robert Harper

Amortized analysis can be framed from the physicist's view, amenable to manual verification in dependent type theory using potential functions, and the banker's view, amenable to automated inference in substructural type theory using type-level credit annotations. In this work, we synthesize these perspectives in Calf, a dependent type theory cost verification. From the physicist's view, we present a fracture and gluing theorem that renders every type as containing a fusion of an abstraction function and a potential function. By construction, every program between two such types must preserve abstraction, to facilitate modularity of behavior, and conserve potential, to facilitate modularity of cost. Incorporating the banker's view, we synthetically construct type operators for credits and debits. We then define Giralf, a graded substructural dependent type theory for programming with credits and debits, which is semantically interpreted as a sub-language of Calf. Finally, we adapt an inference algorithm to transform a limited class of Calf programs into Giralf counterparts, automating the cost analysis of common algorithms in Calf.

Authors: Weiming Feng, Xiongxin Yang, Yixiao Yu, Yiyao Zhang

The problem of learning constant-depth circuits holds profound implications for computational learning theory. In a seminal result, by introducing the low-degree algorithm, Linial, Mansour, and Nisan (J. ACM 1993) presented a quasipolynomial-time learner for $\mathsf{AC}^0$ under the uniform distribution. However, obtaining comparable learning guarantees for broader classes of correlated distributions has remained a longstanding challenge. Recently, Chandrasekaran, Gaitonde, Moitra, and Vasilyan (arXiv 2026) extended these guarantees to Gibbs distributions on bounded-degree graphical models with both strong spatial mixing and polynomial growth. In this paper, we give a quasipolynomial-time learner for $\mathsf{AC}^0$ under graphical models that admit efficient local samplers, circumventing the polynomial-growth requirement in prior work. The key ingredient is a new low-degree approximation for Gibbs distributions, established by simulating and suitably truncating the classical Glauber dynamics. As applications, this framework yields learners for two-spin systems, including the hard-core model and Ising model, on arbitrary bounded-degree graphs, in regimes approaching their respective sampling thresholds.

Authors: Christian Coester, Alex Turoczy

The Parking Permit Problem (PPP), first studied by Meyerson, is a classic online problem generalizing the ski rental problem. We re-examine the PPP using the primal-dual scheme, obtaining simple algorithms with superior performance guarantees. Unlike previous work, which relied on reductions that degraded competitive ratios, we work with the problem's structure directly. We also provide near-matching lower bounds. Using the primal-dual framework, we find the PPP's deterministic competitive ratio exactly, and the randomized competitive ratio within an additive constant.

Authors: Arpon Basu, Pravesh K. Kothari, Raghu Meka, Stefan Tudose

We prove that for every Cayley graph $\mathcal{G}$ over any finite abelian group $G$, there is a weighted Cayley graph with $O(\log |G|)$ generators that is a spectral sparsifier for $\mathcal{G}$. This bound is optimal. Applying our bound to the group $G = \mathbb{F}_2^n$, yields, as a corollary, $O(n/\varepsilon^2)$-sized code sparsifiers for $\mathbb{F}_2$-linear codes, improving on the work of Khanna, Putterman and Sudan (SODA'24) who obtained a similar result with an additional $\mathrm{polylog}(n)$ loss. Our proof is strongly inspired by a recent work of Reis and Rothvoss for the construction of $\ell_1$-sparsifiers. Following their work, the abelian Cayley sparsification problem can be reduced to establishing a lower bound for the volume of a certain natural convex body. This volume bound follows from a short, elementary argument that relies on character symmetry.

Authors: Robert P. Streit, Vijay K. Garg

Optimal selections in a decision process are often constrained by prerequisites. However, such prerequisites can encode functional rather than literal dependencies, so a required dependency may be supplied by one or several interacting alternatives. We introduce matroidal prerequisite systems (MPS), a constraint structure where a poset specifies prerequisites while a matroid determines when those prerequisites have been satisfied by its span. This creates an order-sensitive notion of feasibility over words, where feasible words are associated with independent sets, while dependencies may be fulfilled through substitutable functionality. Our main contribution is approximation algorithms for additive maximization and submodular maximization over the feasible words of an MPS. The guarantees are determined by two structural parameters: the maximum matroid rank $Δ$ of a principal ideal in the poset and the maximum matroid connectivity $λ_\mathrm{max}$. These measure the distance an MPS is from encoding a matroid or a poset antimatroid, respectively, both of which are generalized by an MPS. For additive maximization, we obtain efficient deterministic $Δ$- and $(1+λ_\mathrm{max})$-approximation algorithms. By extending these techniques, we obtain efficient deterministic $(2+λ_\mathrm{max})$-approximation and randomized $(Δ^2\cdot(1 - 1/e - δ)^{-1})$-approximation algorithms for all $δ>0$ for submodular maximization. The algorithm design and analysis use the theory of polymatroid greedoids, via cryptomorphism we prove between an MPS and a strong polymatroid greedoid. Finally, an approximation-preserving reduction from densest $k$-subgraph shows it is not possible to efficiently compute a $\min\{Δ,λ_\mathrm{max}\}^{o(1)}$-approximation to additive maximization over the feasible words of an MPS under the Gap Exponential Time Hypothesis.

Authors: Panagiotis Aivasiliotis, Andreas Göbel, Matthias Lanzinger, Marc Roth

The Weisfeiler--Leman (WL) algorithm is one of the most influential heuristics for the graph isomorphism problem. The expressive power of WL has been extensively studied in the contexts of descriptive complexity, logics, graph neural networks, and the theory of homomorphism indistinguishabily. Notably, two graphs are indistinguishable by the $k$-dimensional WL algorithm if and only if they are indistinguishable by homomorphism-counts from graphs of treewidth at most $k$. An intrinsic question is to find a natural version of the WL algorithm for relational structures of higher arity admitting an equivalent characterisation via homomorphism indistinguishability along bounded generalised hypertree width (GHW). Scheidt and Schweikardt solved this for $k=1$ by defining the RCR algorithm and showing indistinguishability from $α$-acyclic structures. In this work, we resolve this for all $k\ge1$: we develop $k$-RCR and show that two structures $\mathcal{A}$ and $\mathcal{B}$ are insdistinguishable by $k$-RCR if and only if they have the same homomorphism-counts from all structures $\mathcal{C}$ of generalised hypertreewidth $\le k$. Moreover, we introduce a ``fractional'' version of $k$-RCR and show that two structures are insdistinguishable by fractional $k$-RCR if and only if they have the same homomorphism-counts from all structures with (a variant of) fractional hypertreewidth at most $k$. Last, we develop $k$-HyperOWL, the first relational WL algorithm operating directly on a relational structure. We show that $k$-HyperOWL is as expressive as $k$-RCR and that, given a structure $\mathcal{A}$, $k$-HyperOWL can compute $t$ iterative refinements in time $O(t|\mathcal{A}|^{k+1})$. Moreover, the colouring produced by $k$-HyperOWL can be used as a constructive preprocessing routine for counting homomorphisms from structures of generalised hypertreewidth $\le k$.

Authors: Ioannis Sigalas, Nikolaos Lazaropoulos, Ioannis Lamprou, Ioannis Vaxevanakis, Vassilis Zissimopoulos

In various domination and coverage problems, certain vertices or edges should not be dominated/covered and are designated as vulnerable. Motivated by this, we define the $k$-Vertex Maximum Domination Ratio with Vulnerable Vertices $(k\textit{-}Max \ \mathit{DRVV})$ problem, which extends the budgeted dominating set problem to include vulnerability constraints. We propose an approximation algorithm based on an unbudgeted variant of $k\textit{-}Max \ \mathit{DRVV}$, termed the Maximum Domination Ratio with Vulnerable Vertices $(\mathit{DRVV})$ problem. For bounded-degree graphs of order $n$, our algorithm provides an $O(k/n)$-approximation for the $k\textit{-}Max \ \mathit{DRVV}$ problem. We introduce the Dominating Set with Vulnerable Vertices $(\mathit{DSV})$ problem, reduce it to the Red-Blue Set Cover problem, and derive a $2\sqrt{|V|\cdot(H(Δ_{N})-\frac{1}{2}})$-approximation algorithm, where $|V|$ is the order of the graph, $Δ_N$ is the maximum degree among non-vulnerable vertices and $H$ is the harmonic function. Finally, we examine the Vertex Cover with Vulnerable Edges $(\mathit{VCVE})$ problem, which can be naturally expressed as a special case of the Red-Blue Set Cover problem. We present a polynomial-time $2$-approximation algorithm for the $VCVE$ problem, achieving the best possible ratio.

Monday’s post highlighted how physical therapy sits at the heart of the tension between populations and individuals in modern scientific medicine. The field addresses one of the core problems people come to their doctors with: musculoskeletal pain or restriction. More often than not, these ailments can’t be treated by simple prescriptions of rest, drugs, or surgery, and primary care physicians don’t have solutions for these problems. So instead, they are often referred to physical therapy, which combines an uncomfortable mix of science and craft that eludes clean, evidence-based evaluation.

I’m a bit of a PT fanatic, and have had the privilege of working with five excellent physical therapists since I got a bit too overly serious about strength and conditioning in my forties. They were all very different, but all of them applied the same core principles. These principles highlight key aspects of what it means for a therapy to be individualized.

Every PT consultation begins with an assessment. Because there are so many moving parts and everything is so interconnected, it’s often hard to identify a single cause of a particular pain or restriction. Weakness in one area is balanced by strength in another. Pain in your foot might be caused by limited mobility in your hip. While everyone’s musculoskeletal system is connected in the same way, we have wide variability in the sizes, shapes, and positioning of our muscles and bones. Once we combine this with the variability of people’s physical interactions with reality, we find there’s no single simple answer for everyone. Each person is a weird biomechanical puzzle, and not every puzzle is particularly easy to solve. However, there is a set of therapeutic principles for making people better.

A therapist will test out the range of the different muscles and joints that could be connected to your symptoms. They try to find how far you can move without pain, which is a mix of qualitative (pain) and quantitative (degrees of rotation). Once they find which specific movements are restricted, they have a general process to fix all of them.

First, the therapist will open the restricted range using some sort of manual therapy. This is done in a single session and might involve stretching, deep-tissue massage, or even cupping (more on that later). Next, they give you exercises to gain control over that newly opened range. This is done between sessions with the homework exercises they assign you. After you can confidently access this new range, you load it, adding strength-bearing exercises to further strengthen the mobility you aim to increase. All of these are progressed over time, adding more intense manual therapy, more difficult exercises, and more weight.

Progression is the core principle, whether you’re treating tennis elbow or a sprained hip (I’ve had both). The difficulty of your physical therapy exercises will gradually increase with each session. It’s sort of obvious when you say it that way, no? This is all there is to the buzzy principle of progressive overload. It works because your body adapts to stress. When you add enough stress, it overcompensates and resists the stress more strongly the next time. Cascading this reaction over a long period in a controlled, thoughtful way leads to a clear and measurable outcome.

The complication is that bodies adapt more slowly than most of us would like. It might take weeks to start to see progress. Because progressive overload is slow, lots of people walk away from physical therapy convinced that their injury would have just gotten better anyway. They might be right, and I can’t argue their concerns away. But that’s why I’ve found it helpful to track progress over time. It might not be the PT prescription that lets me access that extra range or strength, but I feel more in touch with whatever it is that my body is doing. I’ve found that it’s worth targeting something even more ambitious than just “back to normal.” I now aim to come out of physical therapy more capable than I was before my symptoms started.

For many people, PT doesn’t work. I like it, but I might be particularly well suited for it. I love rituals. I love obsessing about niche minutiae. I love tracking and journaling. But recovering from injury and managing pain are not easy. Compliance with physical therapy might be a greater challenge than with other treatments. It’s a much bigger commitment than “take two pills a day with meals.” If you don’t like to spend 30 minutes a day on weird stretches, PT might not work for you. But that doesn’t mean it doesn’t work for someone else.

And this is why physical therapy is so easy to attack on scientific grounds. How do you run a controlled trial on a practice this complex and individualized aimed to treat subjective symptoms like pain? I’ll dig into the impossibility in the next post.

Subscribe now

By Ben Recht

Two editorials in the July issue of the Communications of the Association for Computing Machinery ask about the decay and future of the organization itself.

Jim Larus, editor-in-chief of the CACM, writes Wither ACM? Publish and Perish?

ACM no longer has broad appeal as a professional organization, does not advance many members’ careers, and may not be a valuable affiliation in a more diverse technical world...It is time to recognize that ACM has shifted from functioning as a professional society for the academic computing community to a professional publisher....It is time for ACM members to debate what kind of organization ACM should be and how to remake it into the society they want to belong to!

Vardi writes Whither Computing? starting with the concerns of PhD students whether they made the right choice by going into computer science and ending with a call for ACM to lead the conversation.

A new team will assume the leadership of ACM on July 1, 2026, following the current general election and search for a new chief executive officer. I believe this team will have to grapple with existential questions about the future of computing as a science and a profession...If ACM is about “advancing computing as a science and profession,” then we need to engage in a deep conversation about what this phrase means today for education, research, the profession, and ACM, and about how to truly advance computing as a science and profession.

ACM hasn't served as a true professional society for a long time. Unlike in other fields, ACM doesn't hold annual meetings for the whole community, and shares the spotlight with IEEE-CS, USENIX, AAAI, CRA and others. CRA takes the lead in research and organizes the CS department chairs meetings. ACM has focused on journals, conferences through its SIGS and awards.

This worked well while computing went through tremendous growth from after the financial crisis until a couple of years ago. But now artificial intelligence is making us rethink how we do research, publish and educate. What does it even mean to be a computer scientist in the AI era?

So good luck to incoming president Elisa Bertino and her team. Computing is changing. How will ACM change with it?

By Lance Fortnow

Authors: Tom Altman

We introduce an activation hierarchy consisting of stage machines, stage domains, and stage languages generated by an activation operator. The central result is a Predictor-Impossibility Theorem (PIT), which shows that no effective predictor family can uniformly determine all stage languages of the hierarchy. The proof combines the semantic activation construction with the S-m-n Theorem and Kleene's Recursion Theorem to obtain a self-referential fixed point that yields a contradiction. We then define an aggregate language MIS and establish a slice theorem connecting aggregate inputs to individual stage languages. This provides a bridge from polynomial-time decidability of MIS to the existence of a predictor family. By PIT, the aggregate language is, therefore, not polynomial-time decidable. Under the aggregate growth condition defining valid aggregate objects, MIS is shown to belong to NP. Combining these two results yields MIS in NP-P. The paper is organized so that PIT stands independently as a recursion-theoretic result, while the complexity-theoretic consequences are derived from the aggregate-language framework.

Authors: Jie Wang

The Stochastic-Oracle Turing Machine (SOTM) framework models AI-augmented computation as the interaction of a probabilistic Turing machine with an oracle whose responses are drawn from context-dependent distributions. This paper studies what an SOTM can achieve under two oracle-response schemes: in a cached-response oracle, each distinct query receives one response that is reused on later calls to the same query, while in a fresh-response oracle, each call returns an independent response. In both schemes, the SOTM first computes from its input and internal random source to generate its first query, then proceeds adaptively, computing from its query-response transcript (the record of queries issued and responses received) to generate each subsequent query or produce a final output. Cached responses impose two transcript-based ceilings on achievable performance: a correct-identification ceiling governed by the total variation distance between the transcript distributions induced by the hidden states of the oracle, and an output quality ceiling equal to the expected score of the best output the SOTM can compute from the transcript. Fresh responses can raise these ceilings by allowing repeated calls to accumulate independent evidence toward correct or high-quality outputs. In the binary single-informative-query case, the error probability decreases exponentially in the number of calls to the same query at the Chernoff rate. For output quality, query-count bounds characterize threshold stopping when the score function is incorporated as part of the SOTM, and majority-based amplification bounds characterize the binary candidate-output model when it is not. Together, the results identify how response reuse, transcript information, and access to the score function determine what an SOTM can compute and at what token cost.

Authors: Richard Cleve, Eric Culf, Aviv Taller

It is well known that the quantum value of an XOR nonlocal game, where the winning condition depends only on the XOR of the two players' output bits, may be approximated in polynomial time. We study a variant of the XOR game model, which we call tilted XOR games, where the winning condition can additionally depend on only one of the output bits. We show that this dramatically increases the expressive power: the computational complexity of the problem of approximating the quantum value of tilted XOR games to constant precision is RE-complete. Also, our result extends to succinct versions of tilted XOR games, where the questions can be polynomial-length binary strings, generated by a polynomial-time verifier. For classical strategies, the distinction between XOR games and tilted XOR games is inconsequential. Håstad (J. ACM, 2001) shows that they are both NP-complete to approximate, by using a reduction from linear systems to XOR games. Our approach is to show that this is also quantum-sound, but as a reduction from linear system games to tilted XOR games. Since titled XOR games are a special case of binary games (where each party outputs a single bit), our result implies that binary games are RE-hard to approximate.

Authors: Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Xin Zheng

The parameterized Minimum Monotone Satisfying Assignment ($k$-MMSA) problem asks whether a monotone Boolean circuit admits a satisfying assignment of Hamming weight at most $k$. The MMSA hierarchy is defined by allowing a bounded number of alternations between AND and OR gates in the circuit. While the polynomial-time approximability of the MMSA hierarchy has been studied extensively, much less is known in the parameterized setting. In particular, $k$-MMSA$_2$ is the well-known $k$-SetCover problem, whose parameterized inapproximability lies in the $\text{polylog}(n)$ regime. In contrast, $k$-MMSA$_4$ captures $k$-MinLabel, for which known lower bounds give $\text{poly}(n)$ inapproximability. Sandwiched by $k$-MMSA$_2$ and $k$-MMSA$_4$, the inapproximability of $k$-MMSA$_3$ remained comparatively unexplored. In this paper, we give an FPT-time $O(2^k \log n)$-approximation algorithm for $k$-MMSA$_3$, suggesting that in the fixed-parameter regime, the third level of MMSA remains surprisingly close to the second level. Complementing this algorithm, we also give an FPT-time gap-preserving reduction from $k$-MMSA$_3$ to $k$-MMSA$_2$. Thus, stronger inapproximability for $k$-MMSA$_3$ would imply new hardness for $k$-MMSA$_2$, potentially offering a route around the current barriers for the latter problem. Revisiting Marx's reduction from $k$-MMSA$_t$ to gap $k$-MMSA$_{t+2}$, we also show that $k$-MMSA$_4$ admits no $n^{o(1)}$-factor FPT approximation unless W[2]=FPT, and no $n^{O(1/k)}$-factor approximation running in $n^{o(k)}$ time under ETH. These results separate the parameterized approximability behavior of the third and fourth levels and clarify where stronger inapproximability enters the $k$-MMSA hierarchy.

Authors: Thomas Bläsius, Jean-Pierre von der Heydt, Tobias Kempf, Dennis Kobert, Nikolai Maas

Spherical range queries are a fundamental primitive for working with spatial data. Many spatial data structures have been developed to answer these queries, but choosing the optimal one for a specific application is a difficult task. This is because theoretical worst-case bounds are often overly pessimistic, and existing average-case analyses are rather restricted and hard to compare. We address this problem with two main contributions. First, we present a comprehensive evaluation of state-of-the-art spatial indices across a diverse set of benchmarks. This includes a new benchmark based on graph embeddings alongside multiple real-world datasets from the literature. Our benchmark covers instances scaling up to 10M points and ranging between 2 and 960 dimensions. Second, we introduce the Sorted-Projection Radius KD-tree (SPRK-tree), a high-performance KD-tree variant. The SPRK-tree combines aggressive subtree pruning via radius reduction, sorted projection-based leaf nodes, and careful implementation optimizations. It consistently achieves the fastest query times in almost all benchmarks, and ranks second in the few remaining cases.

Authors: Lenny Liu, Jihan Wang

We give randomized $(5+ε)$-approximation algorithms for both the continuous and discrete Fréchet distances on arbitrary two polygonal curves $τ$ and $σ$ in $\mathbb R^d$ for fixed $d$, with $n$ and $m\le n$ vertices respectively. Our algorithm for continuous Fréchet runs in $\widetilde O_{d,ε}(n m^{8/9})$ time, and our algorithm for discrete Fréchet runs in $\widetilde O_{d,ε}(n m^{4/5})$ time. These bounds improve the recent strongly subquadratic constant-factor approximation algorithms of Cheng, Huang, and Zhang~\cite{cheng2025constant}, which give $(7+ε)$-approximations. The approximation improvement comes from certifying long boundary-to-boundary reachability directly through auxiliary surrogate curves, avoiding an extra conversion back to input subcurves and hence removing one triangle-inequality loss. The running-time improvement comes from a two-scale macro-surrogate search combined with dyadic auxiliary-transfer structures, with the discrete case gaining a faster bound from exact planar reachability in the discrete free-space graph.

Authors: Jean-Daniel Boissonnat, Hana Dal Poz Kourimska, Arijit Ghosh, Mathijs Wintraecken

In 1942, Freudenthal showed that a simplex in Euclidean space can be subdivided such that the quality (well-shapedness of the simplex, quantified in terms of e.g. fatness) of the simplices in the subdivision is lower bounded. This answered a question of Brouwer. Recently, Brunck discussed the same problem for simplices in two-dimensional spaces of constant curvature and provided a closely related construction. In this paper we generalize Brunck's result to arbitrary dimensional spaces of constant curvature by combining Freudenthal's construction and radial projection. We contrast this approach with Brunck's construction.

Authors: Michael Lampis, Yiren Lu

We revisit the complexity of deciding whether a graphical game admits a pure Nash equilibrium (PNE) parameterized by standard measures of the input graph, such as treewidth. The natural dynamic programming algorithm for this problem has parameter dependence $α^{(Δ+1)\text{tw}}$ where $α$ is the maximum number of strategies available to each player, each player's utility depends on at most $Δ$ other players, and the input graph has width $\text{tw}$. Our first contribution is to point out that an algorithm by Thomas and van Leeuwen [Algorithmica 2015] claiming to improve this dependence to $α^{O(\text{tw})}$ is flawed and, more strongly, such an algorithm would imply that FPT=W[1]. We then set out to pinpoint the fine-grained complexity of this problem with respect to standard parameters and show that the natural DP algorithm is not optimal, as the problem can be solved with dependence $α^{\lfloor \frac{2Δ}{3} + 1 \rfloor \text{tw}}$, $α^{\lfloor \fracΔ{2} + 1 \rfloor \text{pw}}$, and $α^{\text{ctw}}$, where $\text{pw}, \text{ctw}$ are the pathwidth and cutwidth of the input respectively. Our main algorithmic tool is a tightening of the relationship between the width of a graph $G$, its maximum degree, and the width of $G^2$, which may be of independent interest. Complementing these results, we show that our algorithms for pathwidth and cutwidth are likely to be optimal, as improving them is equivalent to falsifying the pw-SETH.

Authors: Pachara Sawettamalya, Huacheng Yu

We prove an information-theoretically optimal \emph{gap-majority lemma} in the two-player randomized communication model. For a base function $f: \mathcal{X} \to \{\pm 1\}$, its $n$-fold \emph{gap-majority composition}, denoted $\mathsf{GapMAJ} \circ f^n$, takes $n$ inputs $(X_1, \ldots, X_n)$ and distinguishes whether $f^{+n}(X_1,\ldots,X_n) := f(X_1) + \ldots + f(X_n)$ is at least $0.01\sqrt{n}$ or at most $-0.01\sqrt{n}$. We show that if computing $f$ with success probability $0.501$ requires $I$ bits of information, then computing $\mathsf{GapMAJ} \circ f^n$ with success probability $0.99$ requires $n \cdot (I - O(1))$ bits of information. This result is asymptotically optimal in two aspects: it achieves the correct linear scaling of information cost and the correct constant-constant tradeoff between error rates. This makes $\mathsf{GapMAJ}$, to our knowledge, only the third explicit outer gadget that admits a strong composition theorem in the two-player communication setting, following the identity and XOR gadgets. From an application side, our gap-majority lemma can be viewed as a generic amplification tool that lifts the hardness of deciding $f$ into the hardness of approximating $f^{+n}$. Using this framework, we give a new proof to the communication lower bound of Gap-Hamming and derive a tight streaming lower bound of triangle counting, demonstrating the versatility of the gap-majority lemma.

Authors: Sergei Khargeliia, Danil Sagunov

We study the weighted case of the \textsc{Maximum Acyclic Subgraph (MAS)} problem, where each edge of a given directed graph has a positive weight assigned, and the task is to find a maximum-weight acyclic edge set. The famous and well-studied random ordering lower bound guarantees the existence of an acyclic set that gives at least the half of the total edge weight. The maximum spanning tree (MaxST) guarantee, which is the weight of a maximum-weight acyclic subgraph of the underlying undirected graph of $G$, is another natural lower bound for the weight of an acyclic subgraph. A solution of this weight dominates the random ordering solution on instances where MaxST spans the most of the total edge weight. Our main contribution are two parameterized algorithms that find acyclic subgraphs of total weight larger than the weight of the MaxST of $G$. Both our algorithms find a solution of total weight at least $MaxST(G)+k$, for a given integer $k\ge 0$, or report that it does not exist, and first of our algorithms runs in time $2^{k^{\mathcal{O}(1)}}\cdot \mathcal{I}^{\mathcal{O}(1)}$ and works when all weights are integers; our second algorithm handles rational weights not less than $1$, and its running time is upper-bounded by $n^{k^{\mathcal{O}(1)}}\cdot \mathcal{I}^{\mathcal{O}(1)}$. This positive result is rather surprising since solving \textsc{MAS} above the random ordering lower bound is \classNP-hard in the same rational weights scenario, when $k=1$. Our findings unravel intricate connections between structure of MaxSTs and directed cycles, use perfect graph theorem to tackle rational weights, and raise graph-theoretic questions that are interesting on their own. Of another importance, this is one of the few examples of positive ``above guarantee'' results for a weighted problem on directed graphs, especially for rational weights.

Authors: Alexander M. Dalzell, Jianqiang Li, Yuan Su

The spectral condition number is a widely adopted measure of worst-case cost for quantum linear system solvers. Yet it can significantly overestimate the actual runtime for a typical problem instance. We present two quantum algorithms that produce the normalized solution $|x\rangle$ of linear system $Ax=| b \rangle$ to accuracy $ε$ with complexity independent of the condition number $κ=\lVert A^{-1}\rVert$. We focus on the standard input model where $A$ is accessed through a block encoding and $| b \rangle$ is prepared by a unitary. But we also introduce an affine dilation model that encodes $A$ and $| b \rangle$ jointly, allowing further refinements of the query complexity. Our truncation-based solver makes an optimal number of queries to $| b \rangle$ and $\operatorname{\mathbf{O}}\left(κ_{\mathrm{eff}}\operatorname{polylog}\left(\frac{κ_{\mathrm{eff}}}ε\right)\right)$ queries to $A$. We prove a family of upper bounds on the effective condition number, including $κ_{\mathrm{eff}}\leq\frac{\lVert(A^\dagger A)^{-t/2}|x\rangle\rVert^{1/t}}{ε^{1/t}}$ for positive even integer $t$ and $κ_{\mathrm{eff}}\leq\frac{\lVert A^{-1\dagger}(A^\dagger A)^{-(t-1)/2}|x\rangle\rVert^{1/t}}{ε^{1/t}}$ for positive odd $t$, overcoming the $κ$-barrier. Our filtering-based solver is extremely simple with a favorable runtime prefactor. In particular, the solver has query complexity $6\frac{\lVert A^{-1\dagger}|x\rangle\rVert}ε\ln\left(\frac{1}ε\right)$ to leading order when the solution norm is known. We then present a similarly simple solution norm estimator with the same asymptotic cost up to logarithmic factors. Our quantum linear system solvers thus substantially improve a recent algorithm of Li, enabling faster quantum linear system solving beyond the condition number.

Authors: Sebastian Forster, Yasamin Nazari, Rajath Rao K. N., Antonis Skarlatos

In this paper, we study the $(k,z)$-clustering and $k$-center problems on graphs, where $(k,z)$-clustering generalizes the $k$-median ($z=1$) and $k$-means ($z=2$) problems. We obtain the following main results. Our first contribution is the first deterministic algorithm for $k$-center on graphs that achieves a $(2+\varepsilon)$-approximation in $\tilde{O}(m)$ time. This affirmatively resolves an open problem raised by Abboud, Cohen-Addad, Lee, and Manurangsi [SOSA 2023]. Our techniques also extend to the $k$-center with outliers problem, where up to $t$ points may be discarded. Our second contribution is a randomized algorithm for $(k,z)$-clustering on graphs that achieves an $O(1)$-approximation in $\tilde{O}(m)$ time, which in particular covers $k$-median ($z=1$) and $k$-means ($z=2$). Prior to this work, an $\tilde{O}(m)$-time randomized algorithm was known for $k$-median by Thorup [SIAM J. Comput. 2005], and a recent work of Jiang, Jin, Lou, and Lu [2026] achieves $m^{1+o(1)}$ time for general $z$ via local search. Finally, we design a deterministic algorithm for $(k,z)$-clustering on graphs that achieves an $O(\mathrm{poly}(c))$-approximation in $\tilde{O}(m^{1+1/c})$ time, for a positive parameter $c$. To obtain this result, we use techniques from the Thorup-Zwick distance oracle [JACM 2005]; this technical connection may be of independent interest, considering the wide application of distance oracles in various computational settings. Most of our algorithms are incremental, in the sense that for any given parameter $k$, they return a sequence of centers such that every prefix of length $\ell \leq k$ yields a constant-factor approximate solution to the $\ell$-clustering problem.

Authors: Christian Wallisch, Andrea Benigni, Carsten Hartmann, Leon Kellerhals

Electrical distribution networks are regional, medium- and low-voltage power grids connecting energy sources to individual households and businesses with given power demands. While these networks contain redundant power lines for reliability, they are typically operated in a radial (spanning tree) configuration by opening and closing switches on the lines. The challenge is to find a spanning tree that minimizes the sum of the resistive power losses: The power loss of a line $e$ is its resistance $r(e)$ times the squared current $f(e)^2$ flowing across the line. We study approximation algorithms for this problem, known as Distribution Network Reconfiguration (DNR). We give an $n$-approximation algorithm and, via a new NP-hardness for planar Balanced Connected Partition with a fixed number of parts, show that no $n^{1-\varepsilon}$-approximation is possible even on planar graphs unless P $=$ NP, for any $\varepsilon>0$. Since the approximation hardness holds only if there are many sources, we focus on $k$-DNR with $k$ sources; this is motivated by traditional distribution networks, where oftentimes $k = 1$. For $2$-DNR, we give an approximation lower bound of $Ω(\log^2 n)$ conditioned on P $\neq$ NP. For $1$-DNR, which is equivalent to finding an uncapacitated confluent flow minimizing the squared Euclidean norm, we prove APX-hardness and give an $\mathcal{O}(\sqrt{n})$-approximation for uniform line resistances, answering an open question by Gupta et al. [Math. Program. 2022].

Authors: Amir Nikabadi, Paweł Rzążewski

In this paper, we introduce a framework that aims to unify classes defined by forbidden induced subgraphs or induced minors with classes defined by the existence of certain structured tree decompositions. Let $\mathcal{H}$ be a fixed family of graphs. We define \emph{induced-$\mathcal{H}$-packing treewidth}, a tree-decomposition-based graph parameter that, for each bag, measures the maximum number of pairwise anticomplete induced copies of graphs from $\mathcal{H}$ intersecting that bag. This notion generalizes some previously studied parameters: when $\mathcal{H}=\{P_1\}$, it is equivalent to tree-independence number, and when $\mathcal{H}=\{P_2\}$, it is equivalent to induced matching treewidth. We show that bounded induced-$\mathcal{H}$-packing treewidth yields new algorithmic consequences for a range of choices of $\mathcal{H}$. In particular, we prove the following results for graphs of bounded induced-$\mathcal{H}$-packing treewidth. Our results partially answer and substantially extend a question of Bodlaender, Fomin, and Korhonen [SODA~2026] on the tractability of \textsc{MWIS} for graphs of bounded induced-$\mathcal{H}$-packing treewidth for $\mathcal{H}=\{P_3\}$ and for $\mathcal{H}$ equal to the family of all cycles.

Authors: Greg Bodwin, Aleksey Lopez

We study multiplicative graph spanners in the $f$-degree fault tolerant ($f$-DFT) model, in which the spanner must approximately preserve distances even after any subset of edges of maximum degree $f$ temporarily "fails" and is removed from the graph. We prove that there are $n$-node lower bound graphs for which any $f$-DFT $(2k-1)$-stretch spanner $H$ must have size $$|E(H)| \ge Ω\left( f^{1-1/k} n^{1+1/k}\right).$$ This matches a lower bound that was previously only known to hold conditionally, under the 1963 girth conjecture of Erdős. It also matches the current upper bounds, up to a factor of $\texttt{exp}(k)$. Our proof is an analysis of the so-called Wenger graphs (J. Comb. Theory 1991), via their recent reinterpretation by Szabó and by Conlon (Am. Math. Monthly 2021).

Authors: Ruben Becker, Davide Cenzato, Nicola Prezza, Daniel Puttini

Wheeler automata have recently emerged as a powerful generalization of the Burrows-Wheeler Transform, enabling optimal linear-time pattern matching on compressed labeled graphs -- a task that is otherwise computationally hard. Consequently, when an automaton recognizes a Wheeler language (i.e., it is equivalent to some Wheeler automaton), computing its minimum equivalent Wheeler DFA is a powerful indexing strategy. This problem is particularly relevant in computational pangenomics, where pangenome graphs frequently recognize Wheeler languages. However, constructing the minimum Wheeler DFA for a Wheeler language has remained a computational bottleneck. The problem is known to be PSPACE-hard for nondeterministic inputs. When the input is a DFA, state-of-the-art solutions forced a compromise: they were either fast but limited to acyclic DFAs (Alanko et al., SODA 2020) or capable of handling general topologies but prohibitively slow (D'Agostino et al., TCS 2023). In this work, we bridge this gap with the first algorithm solving the problem for general DFAs in near-optimal, linearithmic output-sensitive time. By matching the efficiency of acyclic-only solutions while retaining full generality, our approach improves upon the previous general solution by at least a quadratic factor. We demonstrate the practical impact of our algorithm on real-world pangenome graphs; our tool achieves a processing throughput of over 10^5 transitions per second on a standard workstation, enabling the construction of a provably optimal pattern matching data structure in such applications.

Authors: Daniel Anker Hermansen

In the Euclidean travelling salesman problem (Euclidean TSP), a salesman must visit $n$ points in Euclidean space, while minimizing the travel distance, according to the Euclidean distance function. In online Euclidean TSP, introduced by Abrahamsen, Bercea, Beretta, Klausen and Kozma [ESA 2024], the points are revealed one at a time, and a time slot must be assigned before the next is revealed. Once a point is assigned to a time slot, it can never be reassigned to another time slot. There are $n$ time slots. Euclidean online TSP is a high-dimensional generalization of online sorting, introduced by Aamand, Abrahamsen, Beretta and Kleist [SODA 2023]. Bertram [ESA 2025] showed an algorithm that achieves a competitive ratio of $O(\sqrt{n})$ in the worst case. In stochastic online Euclidean TSP, the points are sampled uniformly and independently in the unit $d$-cube. Kalavas, Platanos and Tolias [STACS 2026] presented an algorithm achieving a competitive ratio of $O(\log^2 n)$ with high probability for stochastic online Euclidean TSP. We present a simple algorithm that for $d \geq 2$ achieves an expected competitive ratio of $O(1)$, and for $d=1$ achieves an expected competitive ratio of $O(\log n)$, matching the lower bound by Hu [SODA 2026] for $d=1$. The algorithm is deterministic, and the expectation is due to the stochastic input. We also show that in the variant where there are more time slots than points, i.e., $\left\lceil(1 + \varepsilon)n\right\rceil$ time slots and $d=1$, our algorithm achieves an expected competitive ratio of $O\left(1 + \log \varepsilon^{-1}\right)$. We also survey algorithms from the literature. We experimentally evaluate our algorithm, which reveals that in all variants the constant factor hidden asymptotically is small. We also evaluate the algorithms from the literature.

Authors: Debarshi Chanda, Buddha Dev Das, Arijit Ghosh, Gopinath Mishra

We study the problem of estimating the number of edges in an undirected, unweighted graph using sublinear query access. We consider a query model that preserves the structure of Independent Set (IS) queries, but augments their output with a random certificate: given a vertex subset, the oracle returns a uniformly random edge from the induced subgraph if one exists, and returns null otherwise. Using this access, we give a randomized algorithm that outputs a $(1 \pm \varepsilon)$-approximation to the number of edges with constant success probability using $\widetilde{O}(\log^{2} m)$ queries. This implies an exponential separation from both standard IS queries and global random edge-sampling models: estimating the number of edges using standard IS queries require $\widetildeΘ\!\left(\min\left\{\sqrt{m},\, \frac{n}{\sqrt{m}}\right\}\right)$ queries, while direct random edge-sample access requires $\widetildeΘ(\sqrt{m})$ samples. Beyond separation in query complexity, our algorithm is output-sensitive: its query complexity is polylogarithmic in the number of edges in the graph. This aligns with the classical objective in group testing, where one seeks algorithms that are both worst-case optimal and instance-adaptive. Conceptually, our model connects group testing, the decision-versus-counting dichotomy, graph property testing, and the "power of a random certificate", and can be viewed as a structured form of conditional sampling of edges in graphs.

Authors: Donghang Cui, Ronghua Li, Qiangqiang Dai, Guoren Wang

Biplex, as a relaxation of the biclique model, has emerged as an important cohesive subgraph model for bipartite graph analysis. The maximum $k$-biplex search problem aims to identify the $k$-biplex with maximum number of edges and has been widely applied in various real-world applications, including community detection, online recommendation, and fraud detection. However, the problem is NP-hard, and existing exact algorithms remain inefficient on large-scale bipartite graphs with large values of $k$ (e.g., $k\geq 3$). In this paper, we revisit the maximum $k$-biplex search problem from a complementary perspective. We reveal a novel structural duality: finding a maximum $k$-biplex in a bipartite graph is equivalent to finding a minimal $k$-bounded-degree deletion in its complement graph. Based on this observation, we propose a novel deletion-based algorithm for the maximum $k$-biplex search problem. We theoretically prove that the proposed algorithm achieves a worst-case time complexity of $O^*(γ_k^n)$, where $γ_k<2$. Specifically, $γ_1=1.725$, $γ_2=1.856$, and $γ_3=1.928$. To further enhance practical efficiency, we develop several effective upper-bounding techniques and a heuristic strategy for obtaining high-quality initial solutions, which substantially reduce the search space. Extensive experiments on eight real-world bipartite graphs demonstrate the efficiency of our approach, which achieves up to four orders of magnitude speedups over state-of-the-art algorithms.

Authors: Rajat De, Dominik Kempa

Compressed indexing aims to support fundamental string queries in space proportional to compressed input size. For grammar compression, a length-$n$ string $T \in Σ^n$ represented by a grammar of size $|G|$ can support random access in $O(|G|\log^{O(1)} n)$ space and $O(\log^{O(1)} n)$ time, and the same bounds are known for many other queries, including pattern matching, longest common extension, lexicographic predecessor/successor, the Burrows-Wheeler transform, suffix arrays, and suffix trees. Frequency-related queries remain less understood. These include rank queries, which report the number of occurrences of a symbol $c \in Σ$ in a substring $T(b..e]$, and symbol occurrence queries, which ask whether $c$ occurs in $T(b..e]$. No fully general data structure is known for these queries with $O(|G|\log^{O(1)} n)$ space and $O(\log^{O(1)} n)$ query time. We establish new conditional lower bounds for such problems. First, we show that answering rank and symbol occurrence queries on grammar-compressed texts in polylogarithmic time using an $O(|G|\log^{O(1)} n)$-space structure constructible in $O(|G|\log^{O(1)} n)$ time would imply an $O(n^2\log^{O(1)} n)$-time algorithm for Boolean Matrix Multiplication. The proof uses a more general lower bound for efficiently answering a batch of such queries. Second, we extend the exact lower bounds from straight-line programs to LZ78-compressed strings, a weaker compression model. Third, independently, we show that even additive approximations of rank queries on straight-line grammars would imply faster Boolean Matrix Multiplication algorithms. Finally, assuming the Orthogonal Vectors conjecture, we show that other frequency-related problems, including range distinct counting and range mode frequency, also cannot be efficiently supported in compressed space.

Authors: Ragnar Groot Koerkamp, Stefan Hermann, Peter Sanders, Stefan Walzer

A minimal perfect hash function (minimal PHF) is a data structure mapping a static set of $n$ keys to $n$ bins without collisions. Two natural generalizations are minimal $k$-PHFs where $n$ keys are mapped to $n/k$ bins of capacity $k$ each, and (non-minimal) PHFs with load factor $α < 1$ where the number of bins is increased by a factor of $1/α$, resulting in spare capacity. While there has been a recent surge of interest in perfect hashing generally, non-minimal $k$-PHFs have not been systematically studied despite a natural use case of speeding up static hash tables: The idea is that a small cache-resident $k$-PHF maps each key $x$ to a cache-line-sized bin of capacity $k$ where $x$ resides. Ideally, this yields a branchless lookup operation with a single cache miss working at high load factors for positive and negative queries alike. Our main theoretical contribution is to determine tight space lower bounds for $k$-PHFs for all pairs of $α \in (0,1]$ and $k \geq 1$. It turns out that combining $α < 1$ and $k \geq 2$ drastically reduces the space of $k$-PHFs, e.g. for $(k,α) = (16,0.8)$ the space lower bound is $0.027$ bits per key while for $(k,α) = (16,1.0)$ and $(k,α) = (1,0.8)$ the lower bounds are higher by factors of $\approx 8$ and $\approx 32$, respectively. On the practical side, we develop a $k$-PHF based on PtrHash and tune it for use in static hash tables. Empirically, our implementation produces $k$-PHFs of size roughly $50\%$ above the lower bound. A static hash set based on this $k$-PHF is consistently at least as fast as other hash sets for negative and mixed queries. On two of the three tested architectures it achieves up to $1.5\times$ speedup for large $n\geq 30M$ where a $1$-PHF does not fit in cache.

Authors: Julian Aeri, Sebastian Forster, Mara Grilnberger

Graph emulators and hopsets are two fundamental concepts for distance approximation. When the multiplicative stretch is $1+ε$ for arbitrarily small $ε>0$, these structures are known as near-additive emulators and near-exact hopsets, respectively. Prior work showed that there is a remarkable similarity between the constructions and guarantees of these two objects. In their survey on this topic, Elkin and Neiman [Bull. EATCS 130, 2020] explicitly asked whether one can obtain a general reduction between near-additive emulators and near-exact hopsets. Following that, Kogan and Parter [FOCS, 2022] provided a general reduction from hopsets to emulators and spanners. In this paper, we address the reverse direction and show that any construction for a near-additive emulator for undirected unweighted graphs can be leveraged as a black box to construct a hopset for an undirected weighted graph with comparable size, stretch, and a hopbound comparable to the emulator's additive stretch. Specifically, we show that any algorithm that constructs a $(1+ε',β)$-emulator, with $0 \le ε' \le 1$ and $β\ge 1$, of size $S_{\mathcal{A}}(n, ε',β)$, can be used to obtain a $(1+ε, O(\frac{β^2}{ε^2} \ln(\frac{n}ε)))$-hopset of size $O((S_{\mathcal{A}}(n+m\fracβ{ε^2}, \fracε{294},β) \frac{1}ε + n)\ln(\frac{n}ε))$, for any $0 < ε\le 1$. Therefore, our reduction answers the question of Elkin and Neiman [Bull. EATCS 130, 2020] for sparse graphs and further advances the understanding of the formal connection between these two structures. Designing a reduction resulting in a hopset size that does not depend on $m$ remains an intriguing open question.

Authors: Seiei Ando, Yu Yokoi

We study ranking and rank aggregation under the Kendall tau distance, subject to matroid or flag matroid constraints on prefixes of the output ranking. In the matroid case, the top-$k$ prefix is required to form a base of a matroid; in the flag matroid case, several prescribed prefixes are required to form bases of a sequence of matroids linked by quotient relations. This framework contains the previously studied notions of $k$-fairness and block-fairness as special cases, and also captures more general hierarchical and assignment-type lower- and upper-quota constraints. We provide a polynomial-time algorithm for finding, given a single input ranking, a closest feasible ranking under flag matroid prefix constraints. The algorithm is a natural greedy procedure, and its optimality is proved via a Bruhat order argument on the symmetric group. As a consequence, existing approximation frameworks for fair rank aggregation carry over to the matroidal setting. We also prove that rank aggregation with matroid constraints is NP-hard for every fixed number $m\ge 2$ of input rankings, even under partition matroid constraints.

Authors: Benedikt G. Hein, Egon Wanke

A set of vertices $S$ of a directed graph $G$ is geodetic if every vertex of $G$ lies on a shortest path from a vertex of $S$ to a vertex of $S$. A directed graph is geodetic if there is at most one shortest path from every vertex of $G$ to every vertex of $G$. We prove the NP-completeness of the following decision problem. Given a directed acyclic planar geodetic graph $G$ and an integer $k$, does $G$ have a geodetic set with at most $k$ vertices? This implies that the question of whether $G$ has a strong or a monitoring geodetic set with at most $k$ vertices is also NP-complete for directed acyclic planar geodetic graphs. Furthermore, we prove that the number of vertices in a minimum geodetic set and the number of vertices in a minimum edge geodetic set can be computed in linear time for directed acyclic series-parallel graphs.

Authors: Junhao Gan, Xiao Sun, Seeun William Umboh

We consider the parametrized setting of the classical metrical service system (MSS) problem first studied by Bubeck and Rabani (APPROX/RANDOM 2020). In this setting, the adversary is restricted to a set of $m$ distinct request types, known to the algorithm in advance. The goal is to obtain competitive ratio bounds in terms of $m$. In this work, we make significant progress in understanding the landscape of parametrized MSS and resolve several open problems from Bubeck and Rabani. Our first main result is a tight bound for parametrized MSS on weighted stars. Previously, Bubeck and Rabani gave a randomized lower bound of $Ω(m)$ and deterministic upper bound of $O(2^m)$. We show that, surprisingly, a deterministic $O(m)$-competitive algorithm exists, matching the randomized lower bound. Our key insight is an interval covering formulation of MSS on weighted stars which enables an application of the primal-dual method. Our second main contribution is an improved lower bound construction for parametrized MSS on hierarchically separated trees (HSTs). Bubeck and Rabani's construction gave a $ω(1)$ lower bound when $m \geq 6$. Our improved lower bounds are tight for $2$-level HSTs and also rule out $O(1)$-competitive algorithms on HSTs when the parameter $m\geq 4$. We also complement these results by giving a deterministic $O(1)$-competitive algorithm on general metrics when $m=2$ while showing that it is impossible when $m\geq 3$.

Authors: Edith Cohen, Haim Kaplan, Yishay Mansour, Shay Sapir, Uri Stemmer

The Adaptive Data Analysis (ADA) problem formalizes the challenge of preventing false discovery and overfitting when a dataset is repeatedly reused. Formally, our input is a dataset containing $n$ i.i.d. samples from an unknown distribution $\mathcal{P}$ over a domain $\mathcal{X}$, and our goal is to answer a sequence of $k$ adaptively chosen statistical queries with respect to $\mathcal{P}$. The main question is how many queries we can support (i.e., how large $k$ can be), primarily as a function of the number of samples $n$. This question has been intensively studied and is relatively well-understood for randomized mechanisms: there are computationally efficient mechanisms that support $k \approx n^2$ queries, and no computationally efficient mechanism can answer $k \gg n^2$ queries. In this paper, we address a fundamental question: is randomness necessary for ADA? Despite a decade of work on ADA, this question remains open. A folklore observation dating back to the initial works on ADA is that randomness is not necessary when the analyst is computationally bounded. Yet, the necessity of randomness against computationally unbounded analysts has remained elusive. Our main contribution resolves this gap in the information-theoretic Random Oracle model. Perhaps surprisingly, we show that randomness is strictly necessary to answer a non-trivial number of adaptive queries: when the analyst is unbounded, any deterministic mechanism can be forced to fail after just $k = \tilde{O} (n)$ queries.

Authors: Alvin Chiu, David Eppstein, Michael T. Goodrich, Songyu Liu

We show how to visualize a graph, $G=(V,E)$, as a layered drawing, layer-respecting arc diagram, or layer-respecting linear cylindric drawing with a minimum number of edge crossings, where layer-respecting means that layers appear in order on a single line and vertices are grouped by their layers. Even though this problem is NP-hard for general arc diagrams, we show how to create such diagrams with fixed-parameter tractable linear-time algorithms, where the parameter that allows this is the width of a layered graph. Such a layered graph can be obtained from a breadth-first search (BFS), in which case the width is upper bounded by a graph width parameter called the BFS width.

Authors: Mauricio Cari, Martín Muñoz, Cristian Riveros

We study the task of disambiguation of finite state automata, namely, converting an automaton into an equivalent, unambiguous one. We do this by developing a novel and simple algorithmic framework that generalizes the subset construction for determinization, and that satisfies some desirable properties: (1) it preserves the original automaton if it was already unambiguous, (2) it computes the successor states on-the-fly and (3) computes each new state in polynomial time--this last point is crucial as it guarantees that the running time is polynomial in the size of the output automaton. Then, we show how to apply this framework for partial disambiguation: by changing the criterion that builds the new states, we develop algorithms for different levels of ambiguity, namely, finitely ambiguous, and polynomially ambiguous automata. These algorithms also satisfy condition (1) for their respective levels, and also (2) and (3). Finally, we show that the disambiguation framework can easily be extended to other models of automata like weighted automata.

Authors: Afonso S. Bandeira, Ahmed El Alaoui, Almut Rödder

We show fast mixing of Glauber dynamics for certain quadratic Gibbs measures with large external fields. The main ingredient is an overlap condition that allows us to control correlation matrices uniformly over all pinnings, by controlling norms of small submatrices of the interaction matrix. Using stochastic localization, we then obtain a lower bound on the spectral gap and, consequently, polynomial-time mixing of Glauber dynamics. As a direct application, we consider the Sherrington-Kirkpatrick model, whose interaction matrix is a scaled GOE matrix. For this model, we show that for any fixed finite inverse temperature $β$, there exists a strength of external field $θ$, not depending on the size of the system, for which Glauber dynamics mixes in polynomial time (with high probability on the draw of the interaction matrix).

We study one-way quantum communication lower bounds for search problems.Unlike decision problems, search problems can have many valid outputs, which pose a fundamental barrier to standard quantum lower-bound techniques. We overcome this by developing a novel method based on matrix discrepancy, which allows us to bound the output measurements of a quantum protocol jointly. As applications of our method, we establish the first tight quantum lower bounds for two fundamental search problems in some natural parameter regimes: collision finding and triangle finding. For collision finding, we prove a tight \(\Omega(N^{1/4})\) one-way quantum communication lower bound. Previously, the best-known quantum communication lower bound for collision finding was $\Omega(N^{1/12})$ due to Göös and Jain (RANDOM 2022), and no stronger bound was known even under the one-way restriction. For triangle finding in graph streams, we prove a one-pass quantum streaming space lower bound of \(\Omega\left(\sqrt{\Delta_V}\right)\) for graphs with $m$ edges,$\Theta(m)$ triangles, and constant $\Delta_E$, where \(\Delta_V\) and \(\Delta_E\) denote the maximum number of triangles sharing a common vertex and edge, respectively. This constitutes the first nontrivial quantum space lower bound in this regime, matching the classical upper bound of Jayaram and Kallaugher (RANDOM 2021) up to logarithmic factors. Notably, our method also recovers the classical lower bound of Kallaugher and Price (SODA 2017) through an entirely different argument, avoiding their Boolean-Hidden-Matching reduction that breaks down for quantum protocols.

We explore the torus polynomial approximation based approach towards a long-standing question: whether AND can be computed by $CC^0$ circuits - the class of constant-depth polynomial size circuits containing $MOD_m$ gates for some natural number $m$. Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019) introduced torus polynomial approximations as an approach for proving lower bounds against $ACC^0$ - a class containing $CC^0$ where the circuits are also allowed AND, OR and NOT gates. We show how lower bounds for torus polynomials approximating AND can be used to make progress on this question. Using lower bounds on the degree of symmetric torus polynomials approximating AND, proved by Krishan and Vishwanathan (ITCS 2026), we prove size lower bounds for symmetric $CC^0$-circuits computing AND. More precisely, we prove that any depth $h$ symmetric $CC^0$ circuit requires $ 2^{\widetilde{\Omega}(n^{1/O(h)})}$ size to compute $AND$. A key ingredient in our proof is an argument that we can construct symmetric torus polynomials to approximate symmetric $CC^0$ circuits. Our construction exhibits an explicit correspondence between the symmetry of the circuit and that of the polynomial. Using this, we also establish lower bounds for weaker notions of circuit symmetry. Lower bounds for symmetric $CC^0$ circuits were also independently established by Pago (ICALP 2026) using different techniques. In the asymmetric regime, we establish degree upper bounds for depth three circuits of the form $MOD_p \circ MOD_{m} \circ AND_{O(1)}$ where $m=pq$ is a semiprime. This circuit class is a special case of the constant degree hypothesis, introduced by Barrington, Straubing and Th{\'e}rien (Information and Computation, 1990), where $m$ could be an arbitrary composite number. We argue that improved lower bounds for asymmetric torus polynomials approximating AND imply size lower bounds for semiprime $m$ and hence progress on the constant-degree hypothesis.

Authors: Nikola Zubić, Qian Li, Yuyi Wang, Davide Scaramuzza

Modern sequence models are increasingly deployed as agents that interleave token generation with calls to external tools. We give an exact, architecture-level account of when such tool access increases computational expressivity. We model any fixed finite-precision recurrent sequence model, including finite-precision state-space models (SSMs) with $B$ bits of internal state, as a deterministic finite-state controller interacting with an oracle through a finite command/observation interface. Our results form a sharp dichotomy. First, tools that are themselves finite-state add essentially nothing: a product-state simulation internalizes any finite-state bounded-interface oracle with finite memory set $M$ at a cost of only $\log_2 |M| + O(1)$ additional bits, so the augmented system remains finite-state. Second, a single minimal infinite-state tool, namely a tape supporting only local $\mathtt{read}$, $\mathtt{write}$, and $\mathtt{move}$ commands, makes the system Turing complete: for every single-tape Turing machine with state set $Q$ and tape alphabet $Γ$, a controller with $O(\log |Q| + \log |Γ|)$ bits of internal memory simulates it, and we exhibit a concrete exponential separation: $\mathrm{EQ}_n$ requires $2^n$ states without tools but a single constant-size controller with the tape tool. Third, we show that this construction is realized exactly by a natural one-layer finite-precision selective affine SSM controller with binary one-hot hidden states, $\{0,1\}$ transition matrices, and zero biases. Selectivity is essential to the construction. In the supplementary material, we make all constants explicit, prove a logarithmic oracle-assisted universal simulation, where $O(\log B)$ recurrent bits suffice to simulate any $B$-state Turing machine, and prove a matching impossibility result.