Theory of Computing Report

We prove an $\tilde{\Omega}(n^2)$ lower bound for read-once parity branching programs computing an explicit boolean function on $n$ variables. The previous best lower bound was $\tilde{\Omega}(n^{1.5})$. Our lower bound is proved by reducing the problem to a lower bound in algebraic circuit complexity.

Authors: Liyan Chen, Yael Tauman Kalai, Zoe Xi

As AI models continue to develop powerful capabilities, it becomes critical that we are able to verify that their output is aligned with our intentions. A recent line of work focuses on verification via debate, a model of interactive proofs where two competing powerful provers, or AI models, debate each other to convince a weak verifier, or a human, of the correctness of their claim. However, debate assumes that the two AI models possess equal abilities and that one of them is truthful, which may not be realistic. In this work, we show \emph{how to avoid debate}: we initiate the study of \emph{single-prover} interactive proofs for AI safety. Prior results in single-prover interactive proofs do not immediately carry over to the AI safety setting: for example, they do not work when the computation has access to an oracle, such as to human judgment or an external database such as the web. We present doubly-efficient single-prover interactive proofs and arguments for oracle-aided computations (also known as relativizing proofs), in the settings where (1) the computation is robust, in the sense that the output does not change if at most a small fraction of the answers to oracle queries are incorrect, or (2) the oracle is a low-degree polynomial. These results suggest that interactive verification is possible even without debate, under structured or noise-tolerant oracle access.

Authors: Madhumitha Krishnakumar, Marc Roth

Introduced by Lee, Ko, and Shin (VLDB 2020), a hypergraph motif is a connected subhypergraph consisting of three hyperedges whose intersections satisfy a prescribed pattern. Such patterns are represented by Venn diagrams $\mathcal{V}\in\{0,1\}^7$, indicating which of the seven regions determined by three sets must be empty or non-empty. Lee et al. designed and implemented exact and approximate algorithms for counting, in a hypergraph $G$, the motifs specified by $\mathcal{V}$; their algorithms run in worst-case cubic time in the number of hyperedges of $G$. This cubic worst case can occur even for hypergraphs of bounded rank, and already for $2$-uniform hypergraphs, that is, for simple graphs. In this work, we give a complete fine-grained picture of the parameterised complexity of exact hypergraph motif counting with respect to the rank of the input hypergraph. We use $\tilde{O}$ to hide polylogarithmic factors in the input size. First, we show that every Venn diagram $\mathcal{V}$ admits an exact counting algorithm running in FPT-near-quadratic time, \[ f(\mathsf{rank}(G))\cdot \tilde{O}(|E(G)|^2), \] for some computable function $f$. Second, we precisely characterise when this can be improved to FPT-near-linear time. We prove that such an algorithm exists exactly for the degenerate Venn diagrams, namely those that force one of the three hyperedges to be fully contained in another. For all non-degenerate Venn diagrams, we show that no FPT-near-linear-time algorithm exists unless either the Triangle Hypothesis or the Hyperclique Hypothesis fails. Exact hypergraph motif counting is thus always fixed-parameter near-quadratic in the rank, and the degenerate Venn diagrams are precisely the cases admitting fixed-parameter near-linear time.

Authors: Nicolas Gillis, Subhayan Saha, Stefano Sicilia, Arnaud Vandaele

Given a nonnegative matrix $X$, a factorization rank $r$ and a real parameter $p$, entrywise power matrix factorization (EPMF) looks for a low-rank matrix $X_r$ such that $X = |X_r|^{\circ p}$ (exact case) or $X \approx |X_r|^{\circ p}$ (approximate case), where $(\cdot)^{\circ p}$ denotes the component-wise exponent. EPMF includes the modulus model ($p=1$) and component-wise square factorization ($p=2$) as special cases, the latter being closely related to the square root rank. We analyze the computational complexity of the exact decision problem and the Frobenius-norm approximation problem, and establish a complete complexity landscape. In the exact case, we show that EPMF is equivalent to the combinatorial problem of flipping the signs of the entries of a given matrix $X$ to obtain a rank-$r$ matrix, which we refer to as the signing problem. We first show that the signing problem, and hence exact EPMF, is strongly NP-hard, improving a weak NP-hardness result for the square-root-rank of Fawzi et al. (Math. Prog., 2015). We then show that the signing problem can be solved in polynomial-time when $r$ is fixed. Moreover, when the rank $r$ is part of the input, we show that for generic matrices the algorithm is fixed-parameter tractable (FPT) in the parameter $r$; in fact, the running time is linear in the input size $X$. In the approximate case using the Frobenius norm as an error measure, we show that EPMF is NP-hard, already when $r=2$, the smallest nontrivial case.

Authors: Arjan Cornelissen, Nikhil S. Mande, Nithish Raja

We introduce the subcube stifling number, a new combinatorial measure of total Boolean functions. This measure is the largest integer $k$ such that, for every set $S$ of at most $k$ input variables and every assignment $b \in \{0,1\}^S$, there is a fixing of the variables outside $S$ under which the resulting function on the free variables $S$ is the point indicator $\mathbb{I}[x_S=b]$. Equivalently, for every small set of coordinates, the function can isolate any prescribed point of the corresponding Boolean cube by suitably fixing all remaining coordinates. This measure is inspired by the stifling number of Chattopadhyay et al.~(ITCS'23); whereas their measure asks for restrictions realizing every constant function, ours asks for restrictions realizing every point indicator. Our results are as follows. 1) We show that the subcube stifling number gives rise to an approximate-degree composition theorem. In particular, if a Boolean function $f$ has approximate degree $O(\sqrt{μ(f)})$, then for every Boolean function $g$, approximate degree composes tightly. This motivates the study of the subcube stifling number, and in particular the search for functions whose approximate degree is $O(\sqrt{μ(f)})$. 2) We show that a random Boolean function on $n$ input bits has subcube stifling number $Θ(\log(n))$ with high probability. 3) We show that indicators of linear codes over $\mathbb{F}_2$ whose minimum distance and dual distance are both linear have high subcube stifling number. 4) We prove that the functions arising from this linear-code construction do not have approximate degree $O(\sqrt{μ(f)})$; in fact, they have approximate degree $Ω(μ(f))$. The main question left open is whether there exists a Boolean function $f$ with approximate degree $Θ(\sqrt{μ(f)})$. A positive answer would yield new instances of tight approximate-degree composition.

Authors: Yuriy Tarannikov

We study Boolean functions and their Fourier spectrum supports in the context of parity decision trees (PDTs). Recently, H.~Hatami et al.~\cite{HHL+} constructed examples whose Fourier support \(\mathcal S\) satisfies $$ |(\mathcal S+γ_1)\cap(\mathcal S+γ_2)|=O(|\mathcal S|^{5/6}) $$ for all distinct \(γ_1,γ_2\), thereby refuting a natural greedy approach based on finding a single large folding direction. We strengthen this folding estimate by constructing an explicit infinite family of Boolean functions such that $$ |(\mathcal S+γ_1)\cap(\mathcal S+γ_2)|=O(|\mathcal S|^{1/2}) $$ for all distinct \(γ_1,γ_2\). The construction uses a special affine subspace partition, called an APLPS-partition, obtained from full linear spreads. In contrast with the probabilistic construction of \cite{HHL+}, our construction is explicit and has no background spectral components. We also discuss consequences for greedy approaches to PDT construction. Under the <> assumption that the maximum-folding bound is inherited by all restrictions, the usual folding-counting argument cannot yield a PDT upper bound better than \(O(|\mathcal S|^{1/2})\), matching the known general upper bound. However, this inheritance assumption is false in general; hence our result refutes only this <> maximum-folding approach, while a complete refutation of adaptive greedy strategies remains open.

Authors: Sangchul Oh

Random circuit sampling of bitstrings from a Haar-random quantum state is widely believed to be classically intractable, and has therefore been implemented as a primary benchmark for demonstrating quantum advantage. Here, we challenge this premise by proposing an efficient classical frozen-tree sampling algorithm that exploits the conditional scale invariance of Haar-random quantum states [Oh, arXiv:2602.19448]. The frozen-tree sampler draws bitstrings of $n$ qubits in $O(n)$ time per sample. Moreover, its output probability $p_F(x)$ is statistically identical to the probability $p_C(x)$ of a random quantum circuit, since both are independent instances of the same Dirichlet distribution. Consequently, no statistical test acting on samples alone can distinguish the classical frozen-tree sampler from a quantum random circuit. The claimed quantum advantage of random circuit sampling therefore does not withstand scrutiny: its hardness lies not in sampling from the Dirichlet distribution, which is classically efficient, but in identifying a specific circuit realization.

Authors: Tayfun Pay

We study some properties of the parity based bit-counting complexity classes ${\bf B_{|0| \oplus}P}$ and ${\bf B_{|1| \oplus}P}$. We first show that both of these complexity classes are closed under complement and prove that ${\bf B_{|1|\oplus}P}\subseteq {\bf B_{|0|\oplus}P}$. We then prove that ${\bf US}\subseteq {\bf P}^{{\bf B_{|1|\oplus}P}}$ and ${\bf US}\subseteq {\bf P}^{{\bf B_{|0|\oplus}P}}$. We then study the characteristic functions of the parity based bit-counting complexity classes, where the characteristic function of ${\bf B_{|1| \oplus}P}$ outputs the Prouhet-Thue-Morse sequence. We then prove that a finite contiguous block of these sequences yield the parity of the starting number and then prove that ${\bf \oplus P}\subseteq {\bf P}^{{\bf B_{|0|\oplus}P}}$ and ${\bf \oplus P}\subseteq {\bf P}^{{\bf B_{|1|\oplus}P}}$. We then use the parity based bit-counting complexity classes to define various hierarchies and show that they all contain ${\bf PH}$ and are contained in ${\bf CH}$.

Authors: Sang Won Bae, Nicolau Oliver, Evanthia Papadopoulou

Abstract Voronoi diagrams are defined in terms of a given system of planar bisecting curves satisfying some simple combinatorial properties. They offer a unifying framework for a wide range of concrete Voronoi instances on generalized sites and metrics. In this paper, we formulate higher-order abstract color Voronoi diagrams of a set $S$ of $n$ colored abstract sites, simultaneously considering all concrete instances under their umbrella. We prove that the number of vertices in the order-$k$ abstract color Voronoi diagram is at most $4k(n-k)-2n$, and present an iterative construction algorithm. The bound directly applies to a family of $m$ disjoint simple polygons of total complexity $n$. For simple polygons the bound can further improve to $O(\min\{k(n-k),(m-k)^2n\})$. A critical ingredient of our proof is a combinatorial analysis on circular sequences of color permutations derived from the unbounded edges of these diagrams, which is interesting in its own right.

Authors: Timo Brand, Stefan Felsner, Henry Förster, Stephen Kobourov, Anna Lubiw, Yoshio Okamoto, János Pach, Csaba D. Tóth, Géza Tóth, Torsten Ueckerdt, Pavel Valtr

We study the problem of reconfiguring a crossing-free embedding of a graph on a surface, with edges represented as curves, into another crossing-free embedding of the same graph on the same surface with the same fixed vertex positions. In this process, we reroute one edge at a time while maintaining crossing-free intermediate embeddings. This problem was introduced by Ito et al. [TALG 2025], who showed that even if the graph is a matching of two edges, reconfiguration is not always possible in the plane, but is always possible on the torus. For matchings of two or more edges, they gave a necessary and sufficient condition for reconfigurable embeddings in the plane, but not on the torus. Our main result is that for matchings, trees and forests, reconfiguration is always possible on the torus, and consequently, on any orientable surface of genus at least one. In addition, we provide sufficient conditions for reconfiguration on orientable surfaces of genus at least one and in the projective plane. For more general graphs, we show that reconfiguration is not always possible.

Authors: Lukas P. Bachmann, Jiří Fiala, Miriam Münch, Ignaz Rutter, Peter Stumpf, Alexander Wolff

Oriented interval graphs, a recent generalization of interval graphs introduced by Gutowski et al. [GD 2022], are intersection graphs of intervals, each of which is oriented either left or right. Such a representation defines a mixed intersection graph: overlapping intervals with the same orientation define a (directed) arc; nested intervals (irrespective of the orientations of the intervals) and overlapping intervals of opposite orientations define an (undirected) edge. An oriented interval representation of a mixed graph $G$ can be described combinatorially by the combination of (i) an orientation $\varphi \colon V(G) \to \{-1,1\}$ of all intervals, (ii) a clique ordering $σ$, and (iii) a set $E_\mathrm{cont} \subseteq E(G)$ of containment edges, which are represented by nested intervals. The non-trivial dependencies between these three ingredients make the recognition of oriented interval graphs a challenging problem. In this paper, we take steps towards a general recognition algorithm by studying how orientation, clique ordering, and containment edges influence and restrict each other. We characterize the orientations that are consistent with a given set of containment edges as well as the clique orderings that are consistent with a given orientation. Based on these characterizations, we give linear-time algorithms for two constrained versions of the recognition problem where, in addition to the mixed input graph $G$, either the set of containment edges $E_\mathrm{cont}$ or the orientation $\varphi$ is prescribed. This improves a quadratic-time algorithm of Gutowski et al. for the case that all vertices have the same orientation; an assumption that determines both the orientation and the containment edges. In particular, this also solves the recognition problem for oriented proper (or unit) interval graphs.

Authors: Tim Gabriel, Jean-François Remacle, Christophe Geuzaine

We present a method for constructing intrinsic triangulations of closed discrete surfaces, in which edges correspond to shortest geodesic paths and faces decompose into geometric primitives inherited from the underlying mesh. Starting from a watertight input triangulation, the method progressively builds an intrinsic mesh through local optimization operations -- edge swaps, edge splits, edge collapses, and triangle splits -- performed directly on the surface without modifying the original geometry. Element size is controlled via a characteristic length field, and quality is enforced through angle-based criteria derived from intrinsic distances. Geodesic distances are computed exactly using a continuous Dijkstra approach, accelerated by an A* search strategy that reduces computation to roughly $3\%$ of the cost of standard propagation. The framework supports both refinement and coarsening, overcoming a key limitation of prior intrinsic methods based on developable triangles. As a by-product, the intrinsic triangulation provides a natural foundation for direct high-order mesh generation, bypassing the classical pipeline of first constructing a linear mesh and subsequently curving it. The method is validated on the Thingi10K dataset across nearly 5,000 geometrically complex models.

Authors: Vahan Huroyan, Md Rahat-uz-Zaman, Stephen Kobourov

We study 3D point cloud reconstruction from multiple partially observed 2D projections. Given two or more projections of an unknown 3D point cloud, together with cross-view point correspondences and visibility information, our goal is to recover a consistent 3D configuration when different views contain different subsets of points. We propose 3D Multi-Perspective Embedding (3DMPE), an optimization-based, training-free method that reconstructs the 3D point cloud and, in the variable-projection setting, jointly estimates the projection maps. 3DMPE extends Multi-Perspective Simultaneous Embedding to accommodate missing points and incomplete pairwise distance information across views. We consider both fixed-projection and variable-projection settings. Unlike learning-based reconstruction methods that infer shape from raw images and often depend on training data, 3DMPE operates on geometric observations with established correspondences and does not require category-specific training. Experiments on ShapeNet and Pix3D evaluate reconstruction quality using Chamfer Distance, Earth Mover Distance, and RMSE-Optimize-Align (ROA), and examine the effects of initialization, the number of views, point visibility, and several noise regimes, including noisy distances and erroneous correspondences. The results demonstrate that 3DMPE can effectively reconstruct point clouds from partial multi-view geometric observations.

Authors: Chenglong Huang, Tao Lv, Jianing Yang, Chongde Zi, Linsen Chen, Xun Cao

Enhancing perceptual dimensions while miniaturizing imaging systems presents significant challenges for high-dimensional visual sensing. Conventionally, the acquisition of the 5D (x,y,u,v,λ) spectral light field (5D-SLF) data cube relies on bulky and expensive camera arrays, which are impractical for widespread application. Existing single-detector systems are fundamentally limited by a trade-off between the resolutions of different dimensions owing to insufficient coding capabilities. Here we introduce an Aperture-aware Dispersion Light-field Imaging Spectrometer (ADLIS), that targets a synergy between compactness and resolution through aperture-multiplexed modulation, leveraging the inherent spectral-filtering properties of birefringent material. Using only a manufacturing-friendly and cost-effective phase plate made of birefringent quartz crystal, the aperture of the proposed ADLIS enables compact angular-spectral encoding that is highly sensitive to both the incident angle and spectrum of incoming light. In contrast to the viewpoint-separation approach of microlens arrays, ADLIS employs aperture encoding to superimpose all viewpoints onto each sensor pixel. This shifts the design paradigm from spatial division to encoding integration, aiming to achieve full-resolution light field recovery. Thus, we develop the Aperture-aware Dispersion Light-field Imaging (ADLI) framework, which optimizes the aperture design and 5D-SLF reconstruction in an end-to-end (E2E) manner. Trained by simulation data and validated through real-world experiments, our system achieves robust high-performance 5D-SLF imaging while maintaining full spatial resolution.

Authors: Yeganeh Bahoo, Sajad Saeedi, Roni Sherman

This paper introduces an exact $k$-cell decomposition for visibility planning in polygonal environments for agents equipped with $k$-modems, devices that can see through up to $k$ walls. Unlike prior decompositions that may include redundant partition lines, our proposed method ensures that visibility events (appear, disappear, merge, and split) are guaranteed to occur on every line of the decomposition. By eliminating these redundancies, we achieve an $O(n^4)$ complexity , representing a potentially quadratic improvement over the previous best $O(k^2n^4)$ result. This decomposition explicitly identifies the locations of all critical visibility events and extends to polygons with holes. It has practical applications in tasks such as optimal pursuit-evasion under $k$-visibility and agent counting in invisible regions.

Authors: Eunjin Oh, Hyeonjun Shin

In this paper, we study the problem of constructing a $(1/\varepsilon)$-well-separated pair decomposition (WSPD) for a point set of size $n$ in the Massively Parallel Computation (MPC) model, where multiple machines work in parallel and communicate in synchronous rounds. We present an $O(1)$-round MPC algorithm that constructs a $O(1/\varepsilon)$-WSPD of size $(1/\varepsilon)^{O(ddim)}\cdot \tilde O(n)$ for point sets in a metric space of a constant doubling dimension $ddim$, with high probability, using $(1/\varepsilon)^{O(ddim)} \cdot \tilde O(n)$ total space and $O(n^δ)$ space per machine for a constant $δ\in (0,1)$. In the $d$-dimensional Euclidean space, we can improve the size of the WSPD and the total space to $(1/\varepsilon)^{O(d)} n$. This improves the best-known algorithm [FOCS'93] for computing a WSPD which requires $O(\log n)$ rounds and works only in Euclidean spaces. As a consequence, the following problems can be solved in $O(1)$ rounds in the MPC model: computing a $(1+\varepsilon)$-spanner, a $(1-\varepsilon)$-approximation of the diameter, the closest pair, and the $k$-nearest neighbors ($k$-NN). While our $k$-NN algorithm is specific to Euclidean space, the other three problems can be solved in both Euclidean and doubling metric spaces.

Authors: Theresa Pollinger, Masado Ishii, Jens Domke

Recently, omnitrees were introduced as a flexible space partitioning tree that improves upon the benefits of both octrees and k-d trees: Omnitrees' efficient encoding of anisotropic refinements holds particular interest for applications with anisotropic features and high dimensionality. These include, but are not limited to, computer graphics, databases, machine learning, and physics simulations. The present paper defines new operations on the omnitree encoding that extend its capabilities from the existing refinement to also include coarsening and therefore fully adaptive compression. It demonstrates natural integration of omnitrees with wavelets, which conserves moments of the stored function by design. For omnitrees, the wavelet coefficients can be interpreted as local refinement priorities, which can be used to guide the adaptation process. We derive algorithms for coarsening and downsplit that are guided by wavelet coefficients, and show their application to a large dataset of 3D shapes, as well as the continuous-valued density field of a cloud. The comparison to OpenVDB, a widely-used data structure for sparse volumetric data in computer graphics, enables a demonstration of the practical benefits of omnitrees even for moderately anisotropic three-dimensional data. Compared to OpenVDB, objects can be stored using up to 28x less space, and asymptotically show savings that exceed theoretical expectations. Using lossy compression, the cloud dataset can be compressed by $\approx5\times$ compared to OpenVDB, with negligible loss of visual quality. This demonstrates the potential of omnitrees for efficient storage and processing, and motivates further research into their applications in various domains.

Authors: Anna Arutyunova, Irina Fast, Annika Hennes, Carsten Krollmann, Daniel R. Schmidt, Melanie Schmidt

We study the $k$-center clustering problem under demographic fairness constraints, where the point set is partitioned into groups, and the aim is to compute clusters that exhibit a given group proportion. Previous work in this direction assumes that the entire point set already respects the desired proportions or uses relaxed notions of fairness. In this work, we propose a model that facilitates the creation of clusters that exactly match given target ratios, even when the input point set does not. We combine the well-known fair clustering model initiated by Chierichetti, Kumar, Lattanzi, and Vassilvitskii (NeurIPS 2017) with the notion of outliers to obtain a practical combinatorial framework that provides constant-factor approximate solutions for all proportion settings from $1:1$ for two groups to $t_1:t_2:\ldots:t_m$ for $m\geq 2$ groups, where $t_1,\ldots,t_m$ are integers. We implement and evaluate our algorithms, compare different variants, and provide evidence of the practicability of this approach.

Authors: Daniel Gabric, Joe Sawada

We present the first constant-amortized-time algorithms for generating all length-$n$ necklaces and Lyndon words over a $k$-letter alphabet in colexicographic order, for arbitrary $k\geq 2$. Our approach introduces a novel class of words called \emph{quasinecklaces}, which serve as an easily generated superset of necklaces through which all necklaces can be efficiently identified. We derive a formula for the number $Q_k(n)$ of length-$n$ quasinecklaces and show that $Q_k(n)$ is proportional to the number of length-$n$ necklaces, which is the key property needed to achieve constant amortized time. We also apply our results to efficiently generate a well-known de Bruijn sequence and efficiently generate necklaces and Lyndon words subject to a weight constraint.

Authors: Robert Clausecker, Florian Schintke

We present Radsort, a variant of LSD radix sort, sorting data with $\mathcal O(\sqrt n)$ additional space. Radsort is stable, admits a simple implementation and is easy to parallelise. For arrays exceeding a size of around 2 MiB it outperforms a conventional out-of-place LSD radix sort.

Authors: Weiming Feng, Heng Guo, Yichun Yang

We introduce two new models equivalent to ferromagnetic two-spin systems: a weighted subgraph model and a random cluster type model. Using these new connections, we obtain an efficient sampling algorithm and a new randomised algorithm that efficiently approximates the partition function of ferromagnetic two-spin systems in certain parameter regimes. No efficient sampling algorithms are known before in this regime, and our new estimation algorithm runs in near-quadratic time for bounded degree graphs and in polynomial time for general graphs, improving upon the previous algorithm of Guo, Liu, and Lu (2020).

Authors: Jan Eube, Kelin Luo, Heiko Röglin, Sarah Sturm

The Traveling Thief Problem (TTP) combines the Traveling Salesperson Problem with the Knapsack Problem. In this problem, a finite metric space is given, and at each location an item with some profit and weight is placed. An agent seeks to collect a subset of the items. To do so, the agent must decide which items to collect and to determine a cyclic tour visiting the corresponding locations. While collecting an item yields its profit as a reward, the agent's speed decreases as more weight is picked up. The problem involves two competing objectives: maximizing the total profit of the collected items and minimizing the travel time of the tour. While many heuristics and exact algorithms (with a non-polynomial running time) have been developed, no approximation algorithms are known for any variant of the TTP. We aim at computing an $(α_1,α_2)$-approximate Pareto set that, for every solution, contains another solution collecting at least a $\frac{1}{α_1}$ fraction of its profit while requiring at most $α_2$ times its travel time. Our main result is an algorithm that calculates a $(9 + ε,9 + ε)$-approximate Pareto set in polynomial time. We also consider the setting in which the set of items to be collected is given in advance, so that the agent only has to compute a tour through the corresponding locations that minimizes the total travel time. This is the so-called Weighted TSP. For this setting, we present a $(2e + ε)$-approximation algorithm.

Authors: Paola Bonizzoni, Younan Gao, Dominik Köppl, Gregory Kucherov

We revisit the online construction of \emph{smallest suffixient sets} and the online computation of the \emph{longest repeating suffix} (LRS). We give the first compressed-space online construction of smallest suffixient sets, and present two space-time trade-offs for both problems: $O(r\log n+n)$ bits of working space and $O(\log^2 n/\log \log n)$ worst-case time per character, and $O(r\log n+n \log \log n)$ bits of working space and $O((\log n/\log \log n)^2)$ worst-case time per character. Here, $r$ is the number of runs in the Burrows-Wheeler transform of the reverse of $T[1..n]$. In particular, for highly repetitive texts satisfying $r=O(n/\log n)$, the first trade-off uses $O(n)$ bits of working space, while the second uses $O(n\log\log n)$ bits. We also prove that any deterministic online algorithm for computing LRS requires \(Ω(n)\) bits of peak working space in the worst case, even over a constant-size alphabet. Through reductions from online LRS computation, we extend this lower bound to deterministic online algorithms maintaining either an arbitrary smallest suffixient set augmented with the length of the supermaximal right extension represented by each selected position, or the position-only smallest suffixient set obtained by selecting the rightmost occurrence of every such extension. For constructing smallest suffixient sets, our algorithms are the first online solutions using compressed working space, improving the $O(n)$-word space required by previous online constructions. For compressed-space online LRS computation, compared with the algorithm of Prezza and Rosone~[CiE 2020], our bounds improve their $O(\log^2 n)$ amortized time per character by factors of $Θ(\log\log n)$ and $Θ((\log\log n)^2)$, respectively, while also providing worst-case guarantees.

Authors: Cristian Boldrin, Fabio Vandin

We study the problem of k-means clustering on large datasets. The state-of-the-art for the problem is given by coresets-based approaches, which build small weighted summaries of the input and derive approximate solutions with rigorous quality guarantees from them. One of the most popular and advanced approaches to derive coresets for k-means is sensitivity sampling. However, sensitivity sampling requires to compute the importance of each input point with respect to the whole dataset over all possible choices of centers. Since the exact computation of such quantities is unfeasible, current approaches work by approximating the sensitivity values. Nevertheless, the runtime of such approaches is still impractical for large datasets. In this work, we propose to reduce the runtime of sensitivity-based approaches for k-means by leveraging predictions to approximate the importance of input points. We first formally prove that current theoretical results on coresets construction via sensitivity sampling hold for coarser approximations of sensitivities compared to the one required by existing approaches. This implies that even fairly noisy predictors can be leveraged for sensitivity-sampling approaches. We then propose a natural predictor, which applies to the common scenario where clustering is performed (over time) on a sequence of datasets from the same problem. We prove that when the datasets in the sequence come from the same (unknown) distribution, centers resulting in a low error on one dataset can be used as predictions for sensitivity sampling in subsequent datasets, with guarantees on their quality. We perform an extensive experimental evaluation showing that our approach significantly improves, in terms of clustering cost vs runtime, over uniform sampling and state-of-the-art sensitivity sampling approaches when applied to sequences of datasets.

Authors: Daniel Faber, Jan-Henrik Haunert, Petra Mutzel

Regionalization is a fundamental task in spatial analysis that seeks to partition a larger area - such as a country - into smaller regions that are homogeneous with respect to a given attribute. A popular model for regionalization is the p-regions problem, in which regions are formed by grouping the areas of an input planar subdivision. Given the subdivision's adjacency graph G and pairwise dissimilarities between vertices, the goal is to partition G into a fixed number p of connected subgraphs, such as to minimize the sum of dissimilarities over all vertex pairs in the same subgraph. The problem is NP-hard and even small instances are difficult to solve to provable optimality. In this paper, we present the new ILP model ER-S for the p-regions problem, exploiting a connection between the p-regions objective and the k-partitioning problem. Furthermore, we strengthen the known ILP model Tree with a new type of subtour elimination inequality specific to the p-regions problem. Combining ER-S and the strengthened version of Tree yields the model ER-S-Tree, which dominates the state-of-the-art models in polyhedral strength. This theoretical advantage is reflected in its superior performance in our experimental evaluation. In particular, the new models ER-S and ER-S-Tree enable the solution of problem instances for major European countries that were previously intractable.

Authors: Aleksandr Maltsev, Mikhail Remnev, Alexey Kapranov, Ekaterina Krivtsova

This paper presents a parallel QUBO exhaustive search algorithm for dense matrices, based on a prefix-suffix decomposition and Gray code ordering. The algorithm achieves O(1) per-state complexity: for the QUBO objective function computation only one arithmetic operation per state is performed. An adjustable energy components cache size enables placement in the fastest available memory tier. This reduces memory bandwidth requirements to a negligible level and transforms the problem from memory-bound to compute-bound. Our CUDA-based implementation achieves a state-of-the-art evaluation rate of $7.5\times10^{12}$ states per second on a single GPU, setting a new performance benchmark for the full-space-search subclass of exact solvers.

Authors: Paweł Gawrychowski, Adam Górkiewicz, Srinivasa Rao Satti

We consider the 2D RMQ encoding problem: given an $m\times n$ array of $mn$ elements over a total order, encode it such that, for any query rectangle, the position of its maximum element can be reported without accessing the original array. For $m \le n$, it is known how to encode the array in $O(mn \min\{m, \log n\})$ bits with $O(1)$-time queries [Brodal et al., Algorithmica 2012], and also how to obtain an asymptotically optimal encoding consisting of $O(mn \log m)$ bits [Brodal et al., ESA 2013]. However, the latter approach does not prove any guarantee on the query time, and it appears to be inherently sequential: it requires scanning the whole encoding to answer a query. We design a different encoding that uses near-optimal space while allowing for efficient queries. More concretely, for every parameter $κ\in[1, \log\log n]$, our encoding uses $O(κmn(\log m+\log\log n))$ bits and answers 2D RMQ queries in $O(\log^{1/κ}n)$ time.

Authors: Simon Spoorendonk

We present an open, reproducible branch-and-cut (B&C) algorithm for the capacitated profitable tour problem (CPTP) and its open s-t path variant, the capacity-constrained elementary shortest-path problem. The solver re-implements the formulation and cut families of Jepsen et al. (2014) on a fully open mixed-integer programming stack (HiGHS; Huangfu and Hall, 2018), and adds bound-based preprocessing, domain propagation, and reduced-cost variable fixing. We claim no new method; the contribution is twofold. First, an open, reproducible artifact: to our knowledge the first branch-and-cut for this problem class on a fully open stack, with the formulation, every separator, and all benchmark scripts released, so the results below can be rerun and the solver reused and extended as a baseline. Second, a component study on this common modern stack, benchmarked against a dynamic-programming/labelling reference, that decomposes which components pay off and where the running time goes. We find that the capacity-class cuts account for essentially the entire benefit (adding them to a connectivity-only baseline lifts the number of instances solved from 52 to 64 of 76 and shrinks the search tree more than tenfold), while comb and rounded generalized-large-multistar cuts, reduced-cost fixing, and bound-based propagation add nothing measurable. We also report a negative result: the shortest-path-incompatibility (SPI) cut, a variant of the node-precedence inequalities of García (2009), finds no violated inequality on any instance. The solver and all experiments are released as open, reproducible software (Spoorendonk, 2026).

Authors: Anne Driemel, Jan Höckendorff, Ioannis Psarros, Christian Sohler

In this paper, we introduce a new data analysis problem that aims to decompose a set of univariate time series into a small set of $k$ base curves of length at most $l$ such that the sum of Fréchet distances of the time series to a ``Fréchet combination'' of the base curves is minimized. Here, a Fréchet combination allows to combine individually scaled base curves using a $k$-dimensional traversal. We call the problem of finding a set of optimal base curves the Fréchet decomposition problem and we consider two variants: (a) the base curves can be arbitrary curves of bounded length and (b) the curves come from a given finite set of candidate curves. We think of the Fréchet decomposition problem as a Fréchet variant of principal component analysis. For the case of a single base curve we develop a $(1+\varepsilon)$-approximation algorithm for the Fréchet decomposition problem. Additionally we give an exact algorithm for the projection distance problem that asks to compute the distance of one given time series to a given set of $k$ base curves. This allows us to design an exact algorithm for the Fréchet decomposition problem for general $k$ when curves come from a fixed candidate set.

Authors: Ishaq Aden-Ali

We provide an online algorithm with the following guarantee: for any fixed sequence of vectors $v_1,\dots,v_T \in \mathbf{R}^d$ with $\|v_i\|_2\le 1$, the algorithm assigns each arriving vector $v_t$ a random sign $\varepsilon_t$ such that every prefix sum $\sum_{i=1}^t \varepsilon_i v_i $ can be written as the sum of three coupled standard Gaussian vectors. Our algorithm runs in $O(dT)$ time and achieves the optimal prefix discrepancy bound \[ \max_{1 \le t \le T}\left\| \sum_{i=1}^t \varepsilon_i v_i \right\|_\infty = O\left( \sqrt{\log T} \right), \] with high probability. This recovers the optimal bound of Kulkarni, Reis, and Rothvoss, whose algorithm runs in time exponential in $T$ and $d$. The algorithm and main proof were discovered in a GPT-5.5 Pro Extended conversation prompted by the author.

Authors: Yossi Azar, Liad Iluz

In the online Multi-Level Aggregation Problem (MLAP), requests arrive over time and are associated with nodes of a given weighted rooted tree of depth $D$. Each request must eventually be served by performing a service. Serving a request consists of selecting a rooted subtree that contains the request's node, incurring a service cost equal to the total weight of the selected subtree. To reduce service costs, multiple requests may be served simultaneously by selecting a single rooted subtree that spans all of them. In addition, each request is associated with a penalty function that specifies the cost incurred when the request is served at a particular time. The objective is to minimize the total cost, consisting of both service costs and penalty costs. Most previous work on MLAP assumes monotone non-decreasing penalty functions, commonly referred to as delay functions. Only very recent results consider penalty functions that initially decrease and subsequently increase, and even then only for the special cases of depths $D=1$ and $D=2$, namely the Joint Replenishment Problem (JRP). In this work, we extend previous results in two ways. First, we allow arbitrary penalty functions, which may decrease and increase multiple times. Second, we study the general MLAP with arbitrary tree depth $D$ under these arbitrary penalty functions. We present a randomized algorithm that is $O(D \log n \log(nDW))$-competitive, where $W$ is the maximum service window among all penalty functions after normalizing the Lipschitz parameter of each penalty function to 1 and the minimum positive edge weight incident to the root to 1, and $n$ is the number of requests. Our algorithm runs in polynomial time. Moreover, even for $D=1$, the problem admits an $Ω(\log n)$ hardness of approximation for polynomial-time algorithms.

Authors: Guillaume Ducoffe

The Weighted Center} problem takes as its input a graph $G=(V,E)$ together with a profile $π$ such that every vertex $v$ is mapped to some nonnegative multiplicative weight $π(v)$. Its output must be some vertex $c$ minimizing $\max\{π(v)d_G(c,v) : v \in V\}$. The classic Center problem corresponds to the case where $π(v) =1$ for every vertex $v$. In the literature, various almost linear-time algorithms have been proposed for the Center problem on some well-structured classes of graphs. By contrast, similarly efficient algorithms for the Weighted Center problem have been scarce. We investigate how the Gromov hyperbolicity, alone or in combination with other metric and geometric properties on graphs, can be used in the design of exact and approximate almost linear-time algorithms for the Weighted Center problem. In particular, we derive almost optimal algorithms for the following well-studied classes of graphs: chordal graphs, distance-hereditary graphs (both in $\mathcal{O}(m)$ time), dually chordal graphs and chordal bipartite graphs (both in $\mathcal{O}(m\log{n})$ time).

Authors: Haoxin Yang, Pinghui Wang, Zhe Hou, Tian Zhou, Guangmingzi Yang, Zehua Lei, Rundong Li, Yutong Song, Yongyuan Peng, Fangming Dong, Xiaohong Guan

Range counting is a core primitive in geographic information systems. When data is distributed across multiple organizations, conducting range counting raises substantial privacy concerns. Existing privacy-preserving protocols focus on protecting organizations' datasets, but cannot simultaneously achieve efficiency, query privacy, and accuracy on overlapping data. Typical protocols process query range in plaintext for efficient point-in-range evaluation, since query-private designs rely on expensive secure comparisons. Moreover, most works assume non-overlapping datasets across organizations, which leads to huge errors in overlapping scenarios. In this paper, we propose PPRC, the first protocol that jointly satisfies all the privacy, efficiency, and accuracy requirements. PPRC makes two key technical contributions. First, we design the Private Range Predicate (PRP) technique that supports efficient point-in-range evaluation while protecting the query range. PRP reformulates range evaluation as encrypted membership tests, effectively replacing costly secure comparisons with faster secure multiplications. Second, we propose Oblivious Linear Counting (OLC), an aggregation scheme that efficiently and securely aggregates partial results from organizations with overlapping data. OLC involves only lightweight cryptographic operations and ensures that no information is leaked beyond the final range count. We theoretically analyze the accuracy, efficiency, and security of PPRC. Experiments on real-world and synthetic datasets show that PPRC achieves up to 55x smaller errors and 37x speedup compared to baseline protocols.

Authors: Arnav Burudgunte, Paul Valiant, Hongao Wang

We show that trace reconstruction on n-bit strings is possible using a quasipolynomial number of traces, for any retention probability p that is at least inverse polylogarithmic in n.

Authors: Ishani Karmarkar, Liam O'Carroll, Aaron Sidford

We study the fundamental classification problem of computing a separating hyperplane for a binary-labeled dataset of size $n$ with normalized $d$-dimensional features. Letting $Φ\in \mathbb{R}^{n \times d}$ denote the feature matrix and $γ$ the margin of the maximum-margin separating hyperplane, we present a randomized algorithm that solves this problem in $\tilde{O}(γ^{-2/3}\, \operatorname{nnz}(Φ) + γ^{-2(ω+1)/3})$-sequential running time (work), $\tilde{O}(γ^{-2/3})$-parallel (computational) depth, and accesses $Φ$ only through $\tilde{O}(γ^{-2/3})$-matrix-vector queries (matvecs). We also present a second, faster randomized algorithm with a $\tilde{O}(γ^{-2/3}\, \operatorname{nnz}(Φ) + γ^{-2})$-sequential running time that uses $\tilde{O}(γ^{-2/3})$-matvecs to $Φ$, but achieves only $\tilde{O}(γ^{-4/3})$-parallel depth. Both algorithms match the near-optimal deterministic matvec complexity recently established by Kornowski and Shamir [2025], Karmarkar et al. [2026] and achieve improved sequential runtime and parallel depth, albeit at the expense of using randomness.

Authors: Ravi Kumar, Roie Levin, Joseph, Naor, Debmalya Panigrahi

A classic approach to beyond worst-case algorithm design is to impose stochastic assumptions on the input. However, a limiting feature of stochastic analyses is that, by the min-max principle, performance on worst-case distributions mirrors that of randomized algorithms on worst-case inputs. In other words, the same shortcoming of worst-case analysis -- its inability to distinguish "easy" and "hard" instances -- reappears as an inability to distinguish "easy" and "hard" distributions. This raises a natural question: Can we characterize "easy" input distributions with useful beyond worst-case bounds? A canonical example is the stochastic caching problem (Aho et al. 1971). When the page requests are drawn i.i.d. from the uniform distribution, the best achievable competitive ratio is $O(\log k)$, matching the performance of the best randomized algorithm on worst-case instances (Fiat et al. 1991). However, when the input distribution has less entropy, intuition suggests that we should be able to do better by exploiting the information provided by the distribution. We formalize this by defining a new information-theoretic parameter called subset entropy which we use to give a fine-grained characterization of the competitive ratio of stochastic caching, including a new analysis for the well-known LRU algorithm on stochastic inputs. While our technical results are for the caching problem, we believe the broader principle -- parameterizing algorithmic performance by an entropy measure of the input -- is of independent interest and might apply to other online/stochastic optimization problems. Indeed, for problems such as (comparison-based) sorting, online matching, load balancing, etc., the hardest stochastic instances involve high-entropy distributions. We hope our work is a step toward a broader theory of fine-grained algorithmic performance for this class of problems.

Authors: Yupan Liu, Qisheng Wang, Zhan Yu

We investigate the computational complexity of estimating the operator norm distance ${\rm T}_{\infty}(ρ_0,ρ_1)$, defined via the operator norm $\|A\|_{\infty} = σ_{\max}(A)$, given ${\rm poly}(n)$-size state-preparation circuits of $n$-qubit quantum states $ρ_0$ and $ρ_1$. We provide efficient quantum estimators for the operator norm distance whose complexity is independent of the rank (and thus the dimension) of the states: 1. When one state is pure, we establish an optimal quantum estimator using $Θ(1/ε)$ queries to the state-preparation circuits. Consequently, for constant additive error, say $ε=1/5$, our estimator runs in ${\rm poly}(n)$ time. Since the operator norm distance ${\rm T}_{\infty}(|ψ\rangle\!\langleψ|,ρ)$ is exactly half of the trace distance ${\rm T}(|ψ\rangle\!\langleψ|,ρ)$, our result also gives rank-independent query complexity for estimating both quantities, whereas the approaches due to van Apeldoorn, Cornelissen, Gily{é}n, and Nannicini (SODA 2023) and Wang and Zhang (TIT 2024) have query complexity scaling at least linearly with ${\rm rank}(ρ)$, which can be $\exp(n)$ in general. 2. For general quantum states, we also provide a quantum estimator using $\widetilde{O}(1/ε^{3/2})$ queries to the state-preparation circuits, which shows that the corresponding promise problem is ${\sf BQP}$-complete and improves the ${\sf QMA}$ upper bound sketched by Liu and Wang (ESA 2025). Together with an $Ω(1/ε)$ quantum query complexity lower bound, this leaves only square-root room for improvement. The key intuition behind our estimators is that, when one state is pure, the pure state $|ψ\rangle$ has overlap at least $1/2$ with the top unit eigenvector of $|ψ\rangle\!\langleψ|-ρ$, reflecting a structural feature specific to the operator norm distance.

Authors: Marek Eliáš, Fabrizio Grandoni, Adam Polak, Eleonora Vercesi

The Traveling Salesperson Problem (TSP) has long served as a benchmark for evaluating the strength of optimization techniques in the classical theory of algorithms. In recent efforts to apply ML to algorithmic problems, TSP has also become a natural testbed for the development of ML-based techniques. A common approach is to train a neural network to output a heatmap estimating the likelihood of each edge to be part of the optimal tour; however, converting such a heatmap into an actual tour remains a non-trivial and often computationally intensive step. In this work, we propose algorithms for transforming heatmaps into tours with theoretical guarantees linking the achieved approximation ratio to the quality of the provided heatmap. In the spirit of algorithms with predictions, our results can be described as $(1+2\fracη{\mathrm{OPT}})$-approximation algorithms, where $η$ denotes the L1 distance between the prediction (heatmap) and an optimal solution (tour). Since the previous works lack such explicit guarantees, we compare our approach against them experimentally.

I recently read Alan Alda's first memoir Never have your dog stuffed which was pretty good. Hence I began looking for more information about him on the web. I came across a YouTube video  At 89, Alan Alda reveals the seven actors he HATED the most.  Gee, in the book he didn't hate anyone. So I was curious what this was about. This could be interesting. It was not. The title was extremely deceptive. (More than most clickbait?)  Here is the list and what was said about them:

Wayne Rogers (Trapper John on MASH): The YouTube video said Wayne Rogers felt he didn't have a big enough role on MASH. 

Maclean Stevenson (Henry Blake on MASH): Same as Wayne Rogers.

Gary Burghoff (Radar O'Reily on MASH). The YouTube video said that Gary had emotional outbursts on set, or isolated himself. He felt trapped in the role, unable to grow. 

Robert Duvall (Played Frank Burns in the Movie MASH). The YouTube video said that Robert Duvall   had a different take on the role of Frank Burns in the movie than that Alan Alda had for the TV show. Note that this was not the role Alan Alda played. Also note that  Robert  D and Alan A have never met.

Edward Winter (Played Colonel Flagg on MASH): The YouTube video said that Winter was only in  7 of the 251 episodes. 

David Ogden Stiers (Played Charles Winchester on MASH): The YouTube video said that  David did not socialize with the crew.

Larry Linville (Played Frank Burns on MASH): The YouTube video said that Larry L did not like that his role was one-dimensional. 

Quote:

Did Alan Alda hate these actors? Probably not.

Also a common line was 

Alan has always spoken of X in positive terms.

The clickbait worked in that I read it, and indeed, I am blogging about it. But I won't fall for clickbait for another 5 years (the last time I fell for click bait before this was 5 years ago.)

Lesson of the day: do not fall for clickbait. 

Points:

1)  Since it is well known that clickbait is deceptive, does it still work. Well... I fell for it. 

2)  Is this clickbait more deceptive than usual or not?

3) The term clickbait was coined in 2008 by Jay Geiger in a blog post. The word was added to the Oxford English Dictionary in 2016. For more on the word see here.

4) Is the title of this blog  post, Extreme cases of clickbait!, itself clickbait? 

5) Could an AI be trained to classify videos as Clickbait or Not? In general no since one person's clickbait is another person's  HMMM- what is the opposite of clickbait? (Google said  anti-clickbait and honest-headline, neither of which really works.) Perhaps AI could be trained on what (say) Lance thinks is clickbait. 

Request

If you have an extreme example of clickbait, please leave a comment about it. 

By gasarch

Last week in the Washington Post, fitness columnist Gretchen Reynolds wrote about a “new way to treat sprains.” The common, catchy advice of RICE (Rest, Ice, Compression, and Elevation) was out, and new science had come to light: Doctors and scientists now concur with youth sports coaches that you should “walk it off.”

I’m barely being glib. Reynolds quoted research suggesting that reducing inflammation impairs the body’s natural healing mechanisms. By damping inflammation, scientists conjecture you are damping regeneration. This means that anti-inflammatory drugs like ibuprofen are also counterproductive, as they suppress key pathways that aid the healing process. Moreover, resting leads to muscular atrophy and loss of strength in tendons and ligaments. Putting it all together, rest and anti-inflammatory therapies compound to impede healing.

Reynolds cites expert studies on this topic (there are always studies), but to someone immersed in the culture of bro-science, I was surprised this advice was considered new and novel. Since getting a bit too obsessed with strength sports, I have injured myself multiple times, and I have never visited a physical therapist or watched a fitness YouTuber who recommends resting after an injury. Instead, most tell you to move as much as possible and to reduce inflammation only if it’s getting in the way of that movement. If you get injured, they advise you not to panic, to find what motion gets you moving, and to exercise around the limitations brought on by the injury. The place you sprained will be mobility-restricted, but you should access as much range as you can and keep things light, slowly adding work back as you go.

The working model that coaches and PTs share is that weight training and injury recovery are both processes for getting stronger. An injury is just a disadvantaged starting point. In both cases, the way to increase strength is to regularly stress the system with increasingly harder tasks. Every time, you hope to access more range or lift more weight. This is the principle of progressive overload.

Though now the backbone of most sports training and fitness programs, progressive overload originates in physical therapy. The common prescription of “three sets of ten” originates in the practice of physician Thomas DeLorme, who worked to rehab injured soldiers during World War II. His plan to heal, borne out by diligent clinical practice, became the foundation of the modern paradigm for getting stronger.

Though DeLorme’s progressive overload principle worked wonders in patients and athletes alike, standard medical practice unfortunately always needs a stamp of “science” to back it up and make it real. The practice of coaches, trainers, and physical therapists everywhere can’t justify a technique. That’s bro-science. You need some obscure microbiological pathway or a randomized experiment.

The problem is, the science of physiology is much murkier than you might expect. For years, I have been looking for a clean mechanistic description of why bodies adapt to training. Why do we get stronger and faster by progressively working harder at the gym? Reynolds’ column quotes UC Davis Professor Keith Baar applying his research to his own ankle sprain. Baar has long studied the molecular biological pathways that explain why training techniques like progressive overload work and why bodies adapt to stress. He co-authored one of my favorite surveys on adaptation to training, which lays out the myriad biological pathways and how different sports modalities shape them. My main takeaway from the survey is that we still don’t have a clear, comprehensive description of how the body adapts to exercise. The experiments all agree that if you progressively overload, then you get better. There are lots of things you can measure in a body under stress that point to something mechanistic going on. But they can’t pin down a precise mechanism that drives adaptation, and they certainly can’t figure out what an optimal training protocol would look like. In sports medicine, we don’t follow the science. Science follows the practice.

Coming back to inflammation, we can look at the evidence that ibuprofen inhibits muscle growth in strength training. Common gym wisdom is that ibuprofen, those sugar-coated orange pills often consumed like candy by gym addicts, are actually killing your gains. Bros tell you that you have to tough out the delayed onset muscle soreness associated with training. This was also the conclusion conveyed by the scientists quoted in Reynolds’ article.

Well, the science is of course far less certain than the YouTube advice. I could only find one study showing that taking ibuprofen inhibits muscle hypertrophy when strength training. In this study of 31 people aged 18-35, the treatment group took 1.2 grams of ibuprofen every day for eight weeks, and the researchers observed that they had less muscle growth than the control group. 1.2 grams is the maximum recommended over-the-counter dosage! This is a bit extreme. And yet, despite multiple attempts, no study has ever reproduced these results. There’s a fun fight between one of the failed replication teams and the original authors if you’re into those sorts of academic spats.

So who knows, team? It’s possible ibuprofen doesn’t affect training performance at all. I personally wouldn’t recommend eating it like candy. But what do I know? I’m not a scientist.

Subscribe now

By Ben Recht

Authors: Dominic Lowe, M. S. Kim, Roberto Bondesan, Ryu Hayakawa

Topological data analysis (TDA) is a machine learning technique that uses topology to extract patterns from data and has shown the potential to exhibit quantum advantage. A key concept in TDA is persistent homology, which measures the robustness of topological information at different lengthscales. In this paper, we introduce and study the problem of normalized persistence, a practically motivated and easily interpretable version of persistent homology that counts the fraction of holes that persist at different lengthscales. We prove that a variant of normalized persistence is $\mathsf{DQC}_1$-hard and contained in $\mathsf{BQP}$, giving evidence of an exponential quantum speedup for TDA under the standard assumption that $\mathsf{DQC}_1 \not\subseteq \mathsf{BPP}$. These are the first $\mathsf{DQC}_1$-hardness results that are directly applicable to TDA instances. We also find a close connection between normalized persistence and the complexity of estimating spectral quantities in the low-energy subspace of local Hamiltonians. We study a family of such problems, including a low-energy normalized subtrace and spectral density. We show that these are $\mathsf{DQC}_1$-hard for $O(1)$-local Hamiltonians, strengthening previous results that required log-local interactions. We also introduce a variant of $\mathsf{DQC}_1$ with perfect completeness ($\mathsf{SDQC}_1$) to characterize the hardness of problems normalized by an exact kernel. This includes normalized persistence for $O(1)$-local Hamiltonians, which we show is $\mathsf{SDQC}_1$-hard.

Authors: Benjamin Biaggi, Jan Draisma, Fulvio Gesmundo, Aida Maraj, Magdaléna Mišinová

We prove that the symmetry Lie algebra of a parametrized variety can be determined directly from the parametrization, without computing the vanishing ideal of the variety. We derive a practical polynomial-time Monte Carlo algorithm for computing the symmetry Lie algebra of a parametrized variety. We discuss applications to testing the binomiality of the ideal of a parametrized variety after changing coordinates, and test this property on varieties arising from staged tree models and colored Gaussian graphical models. Finally, we discuss symmetries and binomiality after changing coordinates for rational curves and give a characterization of the symmetries of many secant varieties.

Authors: Andrew Krapivin, Benjamin Przybocki, Marijn J. H. Heule

Problems complete for the existential theory of the reals ($\exists \mathbb{R}$) arise throughout discrete geometry. We introduce satisfiability modulo realizability, a SAT-based approach for solving satisfiable instances of $\exists \mathbb{R}$ whose solutions correspond to realizable geometric configurations. Our method encodes an underapproximation of a geometric problem as a SAT instance over abstract order types. Since almost all abstract order types are unrealizable, naive search is infeasible. We guide the search toward realizable order types using diversity-driven sampling, partial realizability feedback, and a novel flippability heuristic that passes only limited information between components. We apply our method to discrete geometry problems and resolve an open problem by showing that the largest set of points avoiding empty convex hexagons and convex heptagons is of size 23.

Authors: Thobias Kvalvik Høivik, Erlend Raa Vågset

Directed Edge Geography and Undirected Edge Geography are classical PSPACE-complete two-player graph games in which players alternately make moves along edges, deleting each one after use; the first player unable to move loses. We prove that both problems are XNLP-hard when parameterized by pathwidth, addressing a question raised by Bodlaender over 30 years ago. On the positive side, we observe that Directed Edge Geography is fixed-parameter tractable when parameterized by treewidth and maximum degree. We also prove that both problems are in XP on simple graphs when parameterized by tree-partition width. These results develop modern lower-bound and decomposition-based algorithmic methods for width-based questions in PSPACE-complete graph games.

Authors: Haitao Wang

Given a polygonal domain $P$ in the plane, the shortest path map with respect to a point $s$, denoted by $SPM(s)$, is the decomposition of $P$ into cells such that shortest paths from $s$ to all points $t$ in the same cell have the same vertex sequence. The shortest path map equivalence decomposition of $P$ is the decomposition of $P$ into cells so that $SPM(s)$ is topologically equivalent for all points $s$ in the same cell. In this paper, we prove new upper bounds on the combinatorial complexities of the $SPM$-equivalence decompositions under various settings, depending on whether $s$ and/or $t$ are restricted to the boundary of $P$. We also propose new algorithms to compute these decompositions. Further, our results lead to new solutions to several other problems, including answering two-point shortest path queries in $P$, and computing geodesic diameter and center of $P$.

Authors: Matthijs Ebbens, Jie Lu, Alexander Munteanu

We revisit random projections for reducing the dimension of high-dimensional polygonal curves. Drawing from the toolbox of randomized linear algebra, we give a considerably simplified proof of the known $O(\varepsilon^{-2}\log(nm))$ bound on the target dimension of a random projection that preserves the continuous Fréchet distance of polygonal curves up to a factor $(1\pm\varepsilon)$. Our proof is based on the concept of sparse oblivious subspace embeddings. While previous techniques were limited to the case of the Fréchet distance, our techniques are fairly general and extend to all possible distance measures that involve the maximum, a sum or an integral over Euclidean distances between pairs of points on both input curves. We define a generalized dissimilarity measure for curves that includes several popular measures such as Fréchet, $q$-DTW, Hausdorff, etc. as special cases and show that the same dimension reduction technique works for this generalized dissimilarity measure. Finally, we apply the same framework for dimension reduction to piecewise linear surfaces, after extending the distance measure suitably to such surfaces.

Authors: Yu Chen, Pavlo Pylyavskyy, Zihan Tan

We study the inverse problem for shortest-path metrics of Okamura-Seymour (OS) instances. Given an OS metric $D$ on a cyclically ordered terminal set $T$, the goal is to find minimum realizations of $D$, where minimum means having the fewest edges among all disk-embedded realizations with the prescribed terminal order. We show that $D$ determines a canonical medial graph template and every minimum realization is the primal graph of an arrangement of this template. Consequently, the underlying embedded graphs of minimum realizations of $D$ can be recovered, and for each such graph one can efficiently compute edge lengths realizing $D$. Our algorithm follows a recent approach of analyzing graph structures, by viewing graphs as paths and their intersections, which we believe is of independent interest.

Authors: Alexandros V. Gerbessiotis

We present two algorithms based on the Newton-Raphson method to calculate the floor of y**(1/m) for natural integer numbers y>2 and m >1. One could use such an algorithm to establish whether y is an integer power of an integer in number theory problems, even though binary search methods are traditionally considered simpler to implement.

Authors: Michael Kaibel, Petra Mutzel

Preprocessing has become an increasingly important part of solving Maximum Cut to optimality, enabling exact solvers to tackle significantly larger instances. This suggests that exact solvers for the more general Maximum k-Cut problem could also benefit from sophisticated preprocessing. However, to the best of our knowledge, no preprocessing techniques that are effective for k > 2 have been published. In this paper, we introduce structured cut sets, a novel data reduction technique for Maximum k-Cut. We provide criteria under which deleting cut sets is optimality-preserving, yielding a decomposition into connected components that can be solved independently and whose solutions can be combined into an optimal solution for the original graph. Furthermore, we extend several preprocessing techniques from Maximum Cut to Maximum k-Cut. To show that our rules are optimality-preserving, we develop a new proof framework based on the addition of weighted graphs. We complement our theoretical results by engineering a preprocessing framework for Maximum k-Cut and show its effectiveness in a computational study. The preprocessed instances are typically significantly smaller. Integrating our preprocessing into an exact solver yields significant speed-ups and enables solving more instances to optimality.

Authors: Krishnan Dehaleesan, Pål Grønås Drange, Fedor V. Fomin, Petr A. Golovach, Laure Morelle

We study the problem of finding a family of diverse minimum edge s-t cuts in a directed weighted graph G. Given integers k and d, the task is to decide whether G contains k minimum s-t cuts C_1, ..., C_k such that for any i,j in [k], the number of edges in the symmetric difference of C_i and C_j is at least d. For d being 1 or 2, the problem corresponds to counting minimum s-t cuts in G, which is #P-complete [Provan and Ball, SICOMP 1983]. The problem is also known to be NP-complete already for k = 3 [de Berg, López Martínez, Spieksma, ISAAC 2024]. Our main result shows that the problem is fixed-parameter tractable (FPT) when parameterized by the combined parameter k + d. The main ingredients of our FPT algorithm build on novel structural properties of diverse minimum s-t cuts and a non-trivial application of the flow-augmentation technique of Kim, Kratsch, Pilipczuk, and Wahlström [JACM 2025].