Theory of Computing Report

Authors: Abdulrahman Al-Fakih, Nabil Sariah, Ardiansyah Koeshidayatullah, Sherif Hanafy, SanLinn I. Kaka

Reservoir geomodeling is central to subsurface characterization, but it remains challenging because conditioning data are sparse, geological heterogeneity is strong, and conventional geostatistical workflows often struggle to capture nonlinear relationships between facies and petrophysical properties. This study evaluates the robustness and transferability of Pix2Geomodel on a different and more complex reservoir dataset with reduced vertical support. The new case includes a heterogeneous reservoir-quality classification and only 54 retained layers, providing a stricter test of whether Pix2Pix-based image-to-image translation can preserve facies-property relationships under constrained data conditions. Facies, porosity, permeability, and clay volume (VCL) were extracted from a reference reservoir model, exported as aligned two-dimensional slices, augmented using consistent geometric transformations, and assembled into paired image datasets. Six bidirectional tasks were evaluated: facies to porosity, facies to permeability, facies to VCL, porosity to facies, permeability to facies, and VCL to facies. The Pix2Pix model, consisting of a U-Net generator and PatchGAN discriminator, was evaluated using image-based metrics, visual comparison, and variogram-based spatial-continuity validation. Results show that the model preserves the dominant geological architecture and main spatial-continuity trends. Facies to porosity achieved the highest pixel accuracy and frequency-weighted intersection over union of 0.9326 and 0.8807, while VCL to facies achieved the highest mean pixel accuracy and mean intersection over union of 0.8506 and 0.7049. These findings show that Pix2Geomodel can transfer beyond its original case study as a practical framework for rapid bidirectional facies-property translation in complex reservoir modeling.

Authors: Abdulrahman Al-Fakih, Nabil Sariah, Ardiansyah Koeshidayatullah, Sherif Hanafy, SanLinn I. Kaka

Reservoir geomodeling is central to subsurface characterization, but it remains challenging because conditioning data are sparse, geological heterogeneity is strong, and conventional geostatistical workflows often struggle to capture nonlinear relationships between facies and petrophysical properties. This study evaluates the robustness and transferability of Pix2Geomodel on a different and more complex reservoir dataset with reduced vertical support. The new case includes a heterogeneous reservoir-quality classification and only 54 retained layers, providing a stricter test of whether Pix2Pix-based image-to-image translation can preserve facies-property relationships under constrained data conditions. Facies, porosity, permeability, and clay volume (VCL) were extracted from a reference reservoir model, exported as aligned two-dimensional slices, augmented using consistent geometric transformations, and assembled into paired image datasets. Six bidirectional tasks were evaluated: facies to porosity, facies to permeability, facies to VCL, porosity to facies, permeability to facies, and VCL to facies. The Pix2Pix model, consisting of a U-Net generator and PatchGAN discriminator, was evaluated using image-based metrics, visual comparison, and variogram-based spatial-continuity validation. Results show that the model preserves the dominant geological architecture and main spatial-continuity trends. Facies to porosity achieved the highest pixel accuracy and frequency-weighted intersection over union of 0.9326 and 0.8807, while VCL to facies achieved the highest mean pixel accuracy and mean intersection over union of 0.8506 and 0.7049. These findings show that Pix2Geomodel can transfer beyond its original case study as a practical framework for rapid bidirectional facies-property translation in complex reservoir modeling.

Wednesday, May 06 2026, 00:00

On the Induced Norms of Matrices and Grothendieck problems

Authors: Lan V. Truong, M. H. Duong

We study the induced matrix norm $\|\bA\|_{q \to r}$, whose exact value has been known only in a few classical cases. Determining this norm has long been regarded as difficult due to the highly non-convex nature of its variational definition. Existing works offer numerical estimates or analytic bounds but no exact formula. In this paper we present a purely analytic framework that determines $\|\bA\|_{q \to r}$ exactly for all $q, r \ge 1$ for several classes of important matrices. For these matrices, using a direct connection between the induced norms and Grothendieck problems, our results also simultaneously provide exact values for the later.

Authors: Lan V. Truong, M. H. Duong

We study the induced matrix norm $\|\bA\|_{q \to r}$, whose exact value has been known only in a few classical cases. Determining this norm has long been regarded as difficult due to the highly non-convex nature of its variational definition. Existing works offer numerical estimates or analytic bounds but no exact formula. In this paper we present a purely analytic framework that determines $\|\bA\|_{q \to r}$ exactly for all $q, r \ge 1$ for several classes of important matrices. For these matrices, using a direct connection between the induced norms and Grothendieck problems, our results also simultaneously provide exact values for the later.

Wednesday, May 06 2026, 00:00

A Critical Comment on 'Entropy Computing: A Paradigm for Optimization in Open Photonic Systems'

Authors: Ali Hamed Moosavian, Bahram Abedi Ravan

In this article, we take a close look at Entropy Quantum Computing (EQC), a computational paradigm developed by Quantum Computing Inc. (QCi), which deviates from mainstream quantum computing by embracing rather than battling environmental noise and decoherence arXiv:2407.04512 . In their words this approach purports EQC as an open quantum system that turns "entropy into super-power fuels of its computing engine". We show that some of the claims in the main article can be made more rigorous, and yet these are still not good enough to beat state of the art classical algorithms on conventional classical computers. Note that these conclusions reflect the technology's current early stage of development and are not meant to discourage its pursuit. Continued rigorous exploration is necessary to fully assess the long-term viability and potential advantages of this distinct computational approach.

Authors: Ali Hamed Moosavian, Bahram Abedi Ravan

In this article, we take a close look at Entropy Quantum Computing (EQC), a computational paradigm developed by Quantum Computing Inc. (QCi), which deviates from mainstream quantum computing by embracing rather than battling environmental noise and decoherence arXiv:2407.04512 . In their words this approach purports EQC as an open quantum system that turns "entropy into super-power fuels of its computing engine". We show that some of the claims in the main article can be made more rigorous, and yet these are still not good enough to beat state of the art classical algorithms on conventional classical computers. Note that these conclusions reflect the technology's current early stage of development and are not meant to discourage its pursuit. Continued rigorous exploration is necessary to fully assess the long-term viability and potential advantages of this distinct computational approach.

Wednesday, May 06 2026, 00:00

Optimal Union Probability Interval Is NP-Hard

Authors: Petteri Kaski, Heikki Mannila, Chandra Kanta Mohapatra

A problem dating back to Boole [Laws of Thought, Walton & Maberly,1854] is what can be computed about the probability of a finite union of events when given as input the probabilities of intersections of some of the events. The modern geometric study of the problem can be traced back to Hailperin [Amer. Math. Monthly 2 (1965) 343--359] who phrased the problem in the language of linear programming and generalized it to logical formulas of the events other than disjunction, heralding a substantial body of work in probabilistic logic [Nilsson, Artif.\ Intell.\ 28 (1986) 71--87], including the probabilistic satisfiability problem of Georgakopoulos, Kavvadis, and Papadimitriou [J.Complexity 4 (1988) 1--11], as well as fundamental connections to the geometry of metrics via cut and correlation polytopes [Deza and Laurent, Geometry of Cuts and Metrics, Springer, 1997] and to the study of marginal polytopes in graphical models of machine learning [Wainwright and Jordan, Found.\ Trends Mach.\ Learn. 1 (2008) 1--305]. This paper (i) describes the pertinent geometry of Boole's problem via coordinate projections of an elementary polytope arising essentially from Hailperin's linear program on the atoms of a Venn diagram, and (ii) shows that computing the optimal interval for the union probability is NP-hard, resolving an apparent gap in the literature highlighted by Pitowsky [Math.\ Programming 50 (1991) 395--414] and Boros et al. [Math.\ Oper.\ Res. 39 (2014) 1311--1329 and 51 (2026) 134--148].

Authors: Petteri Kaski, Heikki Mannila, Chandra Kanta Mohapatra

A problem dating back to Boole [Laws of Thought, Walton & Maberly,1854] is what can be computed about the probability of a finite union of events when given as input the probabilities of intersections of some of the events. The modern geometric study of the problem can be traced back to Hailperin [Amer. Math. Monthly 2 (1965) 343--359] who phrased the problem in the language of linear programming and generalized it to logical formulas of the events other than disjunction, heralding a substantial body of work in probabilistic logic [Nilsson, Artif.\ Intell.\ 28 (1986) 71--87], including the probabilistic satisfiability problem of Georgakopoulos, Kavvadis, and Papadimitriou [J.Complexity 4 (1988) 1--11], as well as fundamental connections to the geometry of metrics via cut and correlation polytopes [Deza and Laurent, Geometry of Cuts and Metrics, Springer, 1997] and to the study of marginal polytopes in graphical models of machine learning [Wainwright and Jordan, Found.\ Trends Mach.\ Learn. 1 (2008) 1--305]. This paper (i) describes the pertinent geometry of Boole's problem via coordinate projections of an elementary polytope arising essentially from Hailperin's linear program on the atoms of a Venn diagram, and (ii) shows that computing the optimal interval for the union probability is NP-hard, resolving an apparent gap in the literature highlighted by Pitowsky [Math.\ Programming 50 (1991) 395--414] and Boros et al. [Math.\ Oper.\ Res. 39 (2014) 1311--1329 and 51 (2026) 134--148].

Wednesday, May 06 2026, 00:00

Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time

Authors: John M. Hitchcock

Lutz (1987) introduced resource-bounded category and showed the circuit size class SIZE($\frac{2^n}{n}$) is meager within ESPACE. Li (2024) established that the symmetric alternation class $S^E_2$ contains problems requiring circuits of size $\frac{2^n}{n}$. In this note, we extend resource-bounded category to $S^E_2$ by defining meagerness relative to single-valued $FS^P_2$ strategies in the Banach-Mazur game. We show that Li's $FS^P_2$ algorithm for the Range Avoidance problem yields a winning strategy, proving that SIZE($\frac{2^n}{n}$) is meager in $S^E_2$. Consequently, languages requiring exponential-size circuits are comeager in $S^E_2$: they are typical with respect to resource-bounded category.

Authors: John M. Hitchcock

Lutz (1987) introduced resource-bounded category and showed the circuit size class SIZE($\frac{2^n}{n}$) is meager within ESPACE. Li (2024) established that the symmetric alternation class $S^E_2$ contains problems requiring circuits of size $\frac{2^n}{n}$. In this note, we extend resource-bounded category to $S^E_2$ by defining meagerness relative to single-valued $FS^P_2$ strategies in the Banach-Mazur game. We show that Li's $FS^P_2$ algorithm for the Range Avoidance problem yields a winning strategy, proving that SIZE($\frac{2^n}{n}$) is meager in $S^E_2$. Consequently, languages requiring exponential-size circuits are comeager in $S^E_2$: they are typical with respect to resource-bounded category.

Wednesday, May 06 2026, 00:00

Computing Planar Convex Hulls with a Promise

Authors: Sepideh Aghamolaei, Kevin Buchin, Timothy M. Chan, Jacobus Conradi, Ivor Van der Hoog, Vahideh Keikha, Jeff M. Phillips, Benjamin Raichel

Computing the convex hull of a planar $n$-point set $P$ is one of the most fundamental problems in computational geometry. It has an $Ω(n \log n)$ lower bound in the algebraic computation tree model, and many convex hull algorithms match this bound. Classical results show that, under special input assumptions, sub-$O(n \log n)$ algorithms are possible. For instance, when the points are given in lexicographic or angular order, the convex hull can be computed in linear time. Even under the weaker assumption that the sequence of points corresponds to the ordered vertices of a simple polygonal chain, linear-time algorithms exist. This naturally raises the question: can the convex hull of a point set be computed in sub-$O(n \log n)$ time under weaker input assumptions? We answer this positively. Under the promise that the input sequence contains the convex hull as a subsequence, we give a deterministic $O(n \sqrt{\log n})$-time algorithm to compute the convex hull of $P$. With randomisation, we achieve expected running time $O(n \log^{\varepsilon} n)$ for any constant $\varepsilon > 0$. We find this surprising, as points not on the convex hull may behave adversarially toward our convex hull construction algorithm. Yet the promise that \emph{only} the hull points are sorted suffices for $o(n \log n)$-time algorithms. Finally, we show that this promise is tight: if it is even slightly broken, i.e., allowing just one hull point to appear out of order, we prove an adversarial $Ω(n \log n)$-time lower bound. Consequently, the promise cannot be verified with fewer than $Ω(n \log n)$ comparisons. This also negatively resolves an open problem of Löffler and Raichel, who conjectured sub-$O(n \log n)$-time algorithms for computing the convex hull of a supersequence containing the hull as a subsequence.

Authors: Sepideh Aghamolaei, Kevin Buchin, Timothy M. Chan, Jacobus Conradi, Ivor Van der Hoog, Vahideh Keikha, Jeff M. Phillips, Benjamin Raichel

Computing the convex hull of a planar $n$-point set $P$ is one of the most fundamental problems in computational geometry. It has an $Ω(n \log n)$ lower bound in the algebraic computation tree model, and many convex hull algorithms match this bound. Classical results show that, under special input assumptions, sub-$O(n \log n)$ algorithms are possible. For instance, when the points are given in lexicographic or angular order, the convex hull can be computed in linear time. Even under the weaker assumption that the sequence of points corresponds to the ordered vertices of a simple polygonal chain, linear-time algorithms exist. This naturally raises the question: can the convex hull of a point set be computed in sub-$O(n \log n)$ time under weaker input assumptions? We answer this positively. Under the promise that the input sequence contains the convex hull as a subsequence, we give a deterministic $O(n \sqrt{\log n})$-time algorithm to compute the convex hull of $P$. With randomisation, we achieve expected running time $O(n \log^{\varepsilon} n)$ for any constant $\varepsilon > 0$. We find this surprising, as points not on the convex hull may behave adversarially toward our convex hull construction algorithm. Yet the promise that \emph{only} the hull points are sorted suffices for $o(n \log n)$-time algorithms. Finally, we show that this promise is tight: if it is even slightly broken, i.e., allowing just one hull point to appear out of order, we prove an adversarial $Ω(n \log n)$-time lower bound. Consequently, the promise cannot be verified with fewer than $Ω(n \log n)$ comparisons. This also negatively resolves an open problem of Löffler and Raichel, who conjectured sub-$O(n \log n)$-time algorithms for computing the convex hull of a supersequence containing the hull as a subsequence.

Wednesday, May 06 2026, 00:00

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases

Authors: Sanjeev Khanna, Aaron Putterman, Junkai Song

We study the parallel (adaptive) complexity of the classic problem of finding a basis in an $n$-element matroid, given access via an \emph{independence oracle}. In this model, the algorithm may submit polynomially many independence queries in each round, and the central question is: how many rounds are necessary and sufficient to find a basis? Karp, Upfal, and Wigderson (FOCS~1985, JCSS~1988; hereafter KUW) initiated this study, showing that $O(\sqrt{n})$ adaptive rounds suffice for any matroid, and that $\widetildeΩ(n^{1/3})$ rounds are necessary even for partition matroids. This left a substantial gap that persisted for nearly four decades, until Khanna, Putterman, and Song (FOCS~2025; hereafter KPS) achieved $\widetilde O(n^{7/15})$ rounds, the first improvement since~KUW. In this work, we make another conceptual advance beyond KPS, giving a new algorithm that finds a matroid basis in $\widetilde O(n^{3/7})$ rounds. We develop a structural and algorithmic framework that brings a new lens to the analysis of random circuits, moving from reasoning about individual elements to understanding how dependencies span multiple elements simultaneously.

Authors: Sanjeev Khanna, Aaron Putterman, Junkai Song

We study the parallel (adaptive) complexity of the classic problem of finding a basis in an $n$-element matroid, given access via an \emph{independence oracle}. In this model, the algorithm may submit polynomially many independence queries in each round, and the central question is: how many rounds are necessary and sufficient to find a basis? Karp, Upfal, and Wigderson (FOCS~1985, JCSS~1988; hereafter KUW) initiated this study, showing that $O(\sqrt{n})$ adaptive rounds suffice for any matroid, and that $\widetildeΩ(n^{1/3})$ rounds are necessary even for partition matroids. This left a substantial gap that persisted for nearly four decades, until Khanna, Putterman, and Song (FOCS~2025; hereafter KPS) achieved $\widetilde O(n^{7/15})$ rounds, the first improvement since~KUW. In this work, we make another conceptual advance beyond KPS, giving a new algorithm that finds a matroid basis in $\widetilde O(n^{3/7})$ rounds. We develop a structural and algorithmic framework that brings a new lens to the analysis of random circuits, moving from reasoning about individual elements to understanding how dependencies span multiple elements simultaneously.

Wednesday, May 06 2026, 00:00

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs

Authors: David Gamarnik, Miklós Z. Rácz, Gabe Schoenbach

We study the problem of efficiently finding large common induced subgraphs of two independent Erdős--Rényi random graphs $G_1, G_2 \sim \mathbb{G}(n,1/2)$. Recently, Chatterjee and Diaconis showed that the largest common induced subgraph of $G_1$ and $G_2$ has size $(4-o(1))\log_2 n$ with high probability. We first show that a simple greedy online algorithm finds a common induced subgraph of $G_1$ and $G_2$ of size $(2-o(1)) \log_2 n$ with high probability. Our main result shows that no online algorithm can find a common induced subgraph of $G_1$ and $G_2$ of size at least $(2+\varepsilon) \log_2 n$ with probability bounded away from $0$ as $n \to \infty$. Together, these results provide evidence that this problem exhibits a computation-to-optimization gap. To prove the impossibility result, we show that the solution space of the problem exhibits a version of the (multi) overlap gap property (OGP), and utilize an interpolation argument recently developed by Gamarnik, Kizildağ, and Warnke that connects OGP and online algorithms.

Authors: David Gamarnik, Miklós Z. Rácz, Gabe Schoenbach

We study the problem of efficiently finding large common induced subgraphs of two independent Erdős--Rényi random graphs $G_1, G_2 \sim \mathbb{G}(n,1/2)$. Recently, Chatterjee and Diaconis showed that the largest common induced subgraph of $G_1$ and $G_2$ has size $(4-o(1))\log_2 n$ with high probability. We first show that a simple greedy online algorithm finds a common induced subgraph of $G_1$ and $G_2$ of size $(2-o(1)) \log_2 n$ with high probability. Our main result shows that no online algorithm can find a common induced subgraph of $G_1$ and $G_2$ of size at least $(2+\varepsilon) \log_2 n$ with probability bounded away from $0$ as $n \to \infty$. Together, these results provide evidence that this problem exhibits a computation-to-optimization gap. To prove the impossibility result, we show that the solution space of the problem exhibits a version of the (multi) overlap gap property (OGP), and utilize an interpolation argument recently developed by Gamarnik, Kizildağ, and Warnke that connects OGP and online algorithms.

Wednesday, May 06 2026, 00:00

The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth

Authors: Hans L. Bodlaender, Maher Mallem

In this paper, we study the parameterized complexity of several variants of scheduling with precedence constraints between jobs. Namely, we consider the single machine setting with delay values on top of the precedence constraints. Such scheduling problems are related to several decades-old problems with open parameterized complexity status, notably Shuffle Product and Directed Bandwidth. We obtain XNLP-completeness results for both problems, and derive implications to scheduling with minimum (resp. maximum) delays parameterized by the width of the directed acyclic graph giving the precedence constraints, and/or by the maximum delay value in the input. Regarding Directed Bandwidth, we also settle the case of trees by showing XNLP-completeness parameterized by the target value. Beyond these results, we believe that Shuffle Product is an unusual and promising addition to the list of XNLP-complete problems.

Authors: Hans L. Bodlaender, Maher Mallem

In this paper, we study the parameterized complexity of several variants of scheduling with precedence constraints between jobs. Namely, we consider the single machine setting with delay values on top of the precedence constraints. Such scheduling problems are related to several decades-old problems with open parameterized complexity status, notably Shuffle Product and Directed Bandwidth. We obtain XNLP-completeness results for both problems, and derive implications to scheduling with minimum (resp. maximum) delays parameterized by the width of the directed acyclic graph giving the precedence constraints, and/or by the maximum delay value in the input. Regarding Directed Bandwidth, we also settle the case of trees by showing XNLP-completeness parameterized by the target value. Beyond these results, we believe that Shuffle Product is an unusual and promising addition to the list of XNLP-complete problems.

Wednesday, May 06 2026, 00:00

Quantum Multi-Level Estimation of Functionals of Discrete Distributions

Authors: Kean Chen, Minbo Gao, Tongyang Li, Qisheng Wang, Xinzhao Wang

We propose a quantum multi-level estimation framework for a functional $\sum_{i=1}^n f(p_i)$ of a discrete distribution $(p_i)_{i=1}^n$. We partition the values $p_i$ into logarithmically many intervals whose length decays exponentially. For each interval, we perform non-destructive singular value discrimination to isolate the relevant $p_i$, enabling adaptive estimation of the partial sum over this interval. Unlike previous variable-time approaches, our method avoids high control overhead and requires only constant extra ancilla qubits. As an application, we present efficient quantum estimators for the $q$-Tsallis entropy of discrete distributions. Specifically: (i) For $q > 1$, we obtain a near-optimal quantum algorithm with query complexity $\tildeΘ(1/\varepsilon^{\max\{1/(2(q-1)), 1\}})$, improving the prior best $O(1/\varepsilon^{1+1/(q-1)})$ due to Liu and Wang (SODA 2025; IEEE Trans. Inf. Theory 2026). (ii) For $0 < q < 1$, we obtain a quantum algorithm with query complexity $\tilde{O}(n^{1/q-1/2}/\varepsilon^{1/q})$, exhibiting a quantum speedup over the near-optimal classical estimators due to Jiao, Venkat, Han, and Weissman (IEEE Trans. Inf. Theory 2017). Our results achieve, to our knowledge, the first near-optimal quantum estimators for parameterized $q$-entropy for non-integer $q$.

Authors: Kean Chen, Minbo Gao, Tongyang Li, Qisheng Wang, Xinzhao Wang

We propose a quantum multi-level estimation framework for a functional $\sum_{i=1}^n f(p_i)$ of a discrete distribution $(p_i)_{i=1}^n$. We partition the values $p_i$ into logarithmically many intervals whose length decays exponentially. For each interval, we perform non-destructive singular value discrimination to isolate the relevant $p_i$, enabling adaptive estimation of the partial sum over this interval. Unlike previous variable-time approaches, our method avoids high control overhead and requires only constant extra ancilla qubits. As an application, we present efficient quantum estimators for the $q$-Tsallis entropy of discrete distributions. Specifically: (i) For $q > 1$, we obtain a near-optimal quantum algorithm with query complexity $\tildeΘ(1/\varepsilon^{\max\{1/(2(q-1)), 1\}})$, improving the prior best $O(1/\varepsilon^{1+1/(q-1)})$ due to Liu and Wang (SODA 2025; IEEE Trans. Inf. Theory 2026). (ii) For $0 < q < 1$, we obtain a quantum algorithm with query complexity $\tilde{O}(n^{1/q-1/2}/\varepsilon^{1/q})$, exhibiting a quantum speedup over the near-optimal classical estimators due to Jiao, Venkat, Han, and Weissman (IEEE Trans. Inf. Theory 2017). Our results achieve, to our knowledge, the first near-optimal quantum estimators for parameterized $q$-entropy for non-integer $q$.

Wednesday, May 06 2026, 00:00

Exact and Approximate Algorithms for Polytree Learning

Authors: Juha Harviainen, Frank Sommer, Manuel Sorge

Polytrees are a subclass of Bayesian networks that seek to capture the conditional dependencies between a set of $n$ variables as a directed forest and are motivated by their more efficient inference and improved interpretability. Since the problem of learning the best polytree is NP-hard, we study which restrictions make it more tractable by considering for example in-degree bounds, properties of score functions measuring the quality of a polytree, and approximation algorithms. We devise an algorithm that finds the optimal polytree in time $O((2+ε)^n)$ for arbitrarily small $ε> 0$ and any constant in-degree bound $k$, improving over the fastest previously known algorithm of time complexity $O(3^n)$. We further give polynomial-time algorithms for finding a polytree whose score is within a factor of $k$ from the optimal one for arbitrary scores and a factor of $2$ for additive ones. Many of the results are complemented by (nearly) tight lower bounds for either the time complexity or the approximation factors.

Authors: Juha Harviainen, Frank Sommer, Manuel Sorge

Polytrees are a subclass of Bayesian networks that seek to capture the conditional dependencies between a set of $n$ variables as a directed forest and are motivated by their more efficient inference and improved interpretability. Since the problem of learning the best polytree is NP-hard, we study which restrictions make it more tractable by considering for example in-degree bounds, properties of score functions measuring the quality of a polytree, and approximation algorithms. We devise an algorithm that finds the optimal polytree in time $O((2+ε)^n)$ for arbitrarily small $ε> 0$ and any constant in-degree bound $k$, improving over the fastest previously known algorithm of time complexity $O(3^n)$. We further give polynomial-time algorithms for finding a polytree whose score is within a factor of $k$ from the optimal one for arbitrary scores and a factor of $2$ for additive ones. Many of the results are complemented by (nearly) tight lower bounds for either the time complexity or the approximation factors.

Wednesday, May 06 2026, 00:00

On Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds in the MPC Model

Authors: Andrzej Lingas

We study the possibility of designing $N^{o(1)}$-round protocols for problems of substantially super-linear polynomial-time (sequential) complexity in the model of Massively Parallel Computation, where $N$ is the input size. We show that if the machines are not equipped with relatively large local memory and their number does not exceed $N$, then the exponent of the average time complexity of the local computation performed by a machine in a round (in terms of local memory size) in such protocols must be larger than the exponent of the time complexity of the given problem.

Authors: Andrzej Lingas

We study the possibility of designing $N^{o(1)}$-round protocols for problems of substantially super-linear polynomial-time (sequential) complexity in the model of Massively Parallel Computation, where $N$ is the input size. We show that if the machines are not equipped with relatively large local memory and their number does not exceed $N$, then the exponent of the average time complexity of the local computation performed by a machine in a round (in terms of local memory size) in such protocols must be larger than the exponent of the time complexity of the given problem.

Wednesday, May 06 2026, 00:00

Visibility Queries in Simple Polygons

Authors: Sujoy Bhore, Chih-Hung Liu, Anurag Murty Naredla, Yakov Nekrich, Eunjin Oh, André van Renssen, Frank Staals, Haitao Wang, Jie Xue

Given a simple polygon $P$ with $n$ vertices, we consider the problem of constructing a data structure for visibility queries: for any query point $q \in P$, compute the visibility polygon of $q$ in $P$. To obtain $O(\log n + k)$ query time, where $k$ is the size of the visibility polygon of $q$, the previous best result requires $O(n^3)$ space. In this paper, we propose a new data structure that uses $O(n^{2+ε})$ space, for any $ε> 0$, while achieving the same query time. If only $O(n^2)$ space is available, the best known result provides $O(\log^2 n + k)$ query time. We improve this to $O(\log n \log \log n + k)$ time. When restricted to $o(n^2)$ space, the only previously known approach, aside from the $O(n)$-time algorithm that computes the visibility polygon without preprocessing, is an $O(n)$-space data structure that supports $O(k \log n)$-time queries. We construct a data structure using $O(n \log n)$ space that answers visibility queries in $O(n^{1/2+ε} + k)$ time. In addition, for the special case in which $q$ lies on the boundary of $P$, we build a data structure of $O(n \log n)$ space supporting $O(\log^2 n + k)$ query time; alternatively, we achieve $O(\log n + k)$ query time using $O(n^{1+ε})$ space. To achieve our results, we propose a new method for decomposing simple polygons, which may be of independent interest.

Authors: Sujoy Bhore, Chih-Hung Liu, Anurag Murty Naredla, Yakov Nekrich, Eunjin Oh, André van Renssen, Frank Staals, Haitao Wang, Jie Xue

Given a simple polygon $P$ with $n$ vertices, we consider the problem of constructing a data structure for visibility queries: for any query point $q \in P$, compute the visibility polygon of $q$ in $P$. To obtain $O(\log n + k)$ query time, where $k$ is the size of the visibility polygon of $q$, the previous best result requires $O(n^3)$ space. In this paper, we propose a new data structure that uses $O(n^{2+ε})$ space, for any $ε> 0$, while achieving the same query time. If only $O(n^2)$ space is available, the best known result provides $O(\log^2 n + k)$ query time. We improve this to $O(\log n \log \log n + k)$ time. When restricted to $o(n^2)$ space, the only previously known approach, aside from the $O(n)$-time algorithm that computes the visibility polygon without preprocessing, is an $O(n)$-space data structure that supports $O(k \log n)$-time queries. We construct a data structure using $O(n \log n)$ space that answers visibility queries in $O(n^{1/2+ε} + k)$ time. In addition, for the special case in which $q$ lies on the boundary of $P$, we build a data structure of $O(n \log n)$ space supporting $O(\log^2 n + k)$ query time; alternatively, we achieve $O(\log n + k)$ query time using $O(n^{1+ε})$ space. To achieve our results, we propose a new method for decomposing simple polygons, which may be of independent interest.

Wednesday, May 06 2026, 00:00

Deterministic Sparse FFT via Keyed Multi-View Gating with $O(\sqrt{N} \log k)$ Expected Time

Authors: Aaron R. Flouro, Shawn P. Chadwick

We introduce a deterministic sparse Fourier transform framework based on a keyed multi-view gating mechanism that leverages 2-of-3 Chinese Remainder Theorem (CRT) agreement to reduce candidate frequency pairs from $O(k^2)$ to $Θ(k)$ under sparse-regime assumptions. Unlike prior approaches that rely on randomized bucketization for candidate formation, the proposed method provides deterministic structure with probabilistic guarantees arising only from assumptions on frequency placement and independence of affine hashing across views. The algorithm is realized through a peeling-based recovery procedure that extracts frequencies directly from singleton bins without explicit pair enumeration. A recursive self-reduction eliminates the $O(\sqrt{N} \log N)$ preprocessing floor, yielding $O(\sqrt{N} \log k)$ expected identification time while maintaining an $O(N \log N)$ worst-case bound via deterministic dense-FFT fallback. A multi-view verification framework combining Parseval energy consistency and bin-wise residual checks ensures bounded failure probability and no false negatives under correct verification. This establishes a framework combining deterministic candidate reduction, sublinear expected complexity, and worst-case safety guarantees within a CRT-based sparse FFT architecture.

Authors: Aaron R. Flouro, Shawn P. Chadwick

We introduce a deterministic sparse Fourier transform framework based on a keyed multi-view gating mechanism that leverages 2-of-3 Chinese Remainder Theorem (CRT) agreement to reduce candidate frequency pairs from $O(k^2)$ to $Θ(k)$ under sparse-regime assumptions. Unlike prior approaches that rely on randomized bucketization for candidate formation, the proposed method provides deterministic structure with probabilistic guarantees arising only from assumptions on frequency placement and independence of affine hashing across views. The algorithm is realized through a peeling-based recovery procedure that extracts frequencies directly from singleton bins without explicit pair enumeration. A recursive self-reduction eliminates the $O(\sqrt{N} \log N)$ preprocessing floor, yielding $O(\sqrt{N} \log k)$ expected identification time while maintaining an $O(N \log N)$ worst-case bound via deterministic dense-FFT fallback. A multi-view verification framework combining Parseval energy consistency and bin-wise residual checks ensures bounded failure probability and no false negatives under correct verification. This establishes a framework combining deterministic candidate reduction, sublinear expected complexity, and worst-case safety guarantees within a CRT-based sparse FFT architecture.

Wednesday, May 06 2026, 00:00

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth

Authors: Vikrant Ashvinkumar, Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak

We present parallel algorithms for computing single-source reachability and shortest paths on directed $n$-vertex $m$-edge graphs using near-linear $\tilde{O}(m)$ work and $o(\sqrt{n})$ depth whenever $m\ge n^{1+o(1)}$. At the extreme of $m=Ω(n^{2})$, our reachability and shortest path algorithms have depth only $n^{0.136}$ and $n^{0.25+o(1)}$, respectively. The state-of-the-art parallel algorithms with near-linear work for both problems require $Ω(\sqrt{n})$ depth in all density regimes.

Authors: Vikrant Ashvinkumar, Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak

We present parallel algorithms for computing single-source reachability and shortest paths on directed $n$-vertex $m$-edge graphs using near-linear $\tilde{O}(m)$ work and $o(\sqrt{n})$ depth whenever $m\ge n^{1+o(1)}$. At the extreme of $m=Ω(n^{2})$, our reachability and shortest path algorithms have depth only $n^{0.136}$ and $n^{0.25+o(1)}$, respectively. The state-of-the-art parallel algorithms with near-linear work for both problems require $Ω(\sqrt{n})$ depth in all density regimes.

Wednesday, May 06 2026, 00:00

On Computing Total Variation Distance Between Mixtures of Product Distributions

Authors: Weiming Feng, Yucheng Fu, Minji Yang, Anqi Zhang

We study the problem of approximating the total variation distance between two mixtures of product distributions over an $n$-dimensional discrete domain. Given two mixtures $\mathbb{P}$ and $\mathbb{Q}$ with $k_1$ and $k_2$ product distributions over $[q]^n$, respectively, we give a randomized algorithm that approximates $d_{\mathrm{TV}}\left({\mathbb{P}},{\mathbb{Q}}\right)$ within a multiplicative error of $(1\pm \varepsilon)$ in time $\mathrm{poly}((nq)^{k_1+k_2},1/\varepsilon)$. We also study the special case of mixtures of Boolean subcubes over $\{0,1\}^n$. For this class, we give a deterministic algorithm that exactly computes the total variation distance in time $\mathrm{poly}(n,2^{O(k_1+k_2)})$, and show that exact computation is $\#\mathsf{P}$-hard when $k_1+k_2=Θ(n)$.

Authors: Weiming Feng, Yucheng Fu, Minji Yang, Anqi Zhang

We study the problem of approximating the total variation distance between two mixtures of product distributions over an $n$-dimensional discrete domain. Given two mixtures $\mathbb{P}$ and $\mathbb{Q}$ with $k_1$ and $k_2$ product distributions over $[q]^n$, respectively, we give a randomized algorithm that approximates $d_{\mathrm{TV}}\left({\mathbb{P}},{\mathbb{Q}}\right)$ within a multiplicative error of $(1\pm \varepsilon)$ in time $\mathrm{poly}((nq)^{k_1+k_2},1/\varepsilon)$. We also study the special case of mixtures of Boolean subcubes over $\{0,1\}^n$. For this class, we give a deterministic algorithm that exactly computes the total variation distance in time $\mathrm{poly}(n,2^{O(k_1+k_2)})$, and show that exact computation is $\#\mathsf{P}$-hard when $k_1+k_2=Θ(n)$.

Wednesday, May 06 2026, 00:00

Potential Hessian Ascent III: Sampling the Sherrington--Kirkpatrick Model at Beta < 1/2

Authors: Ewan Davies, Holden Lee, Juspreet Singh Sandhu, Jonathan Shi

We give a polynomial-time algorithm to sample from the Gibbs measure of the Sherrington--Kirkpatrick model with negligible total-variation distance (TVD) error up to inverse temperature $β< 1/2$. Prior work obtained TVD error guarantees only up to $β\approx 0.295$, while results covering the entire replica-symmetric regime $β< 1$ gave guarantees only in Wasserstein distance. Our approach demonstrates that the same potential Hessian ascent previously developed for optimization also functions as a sampling algorithm by implementing algorithmic stochastic localization at high temperature. By estimating the covariance of the tilted Gibbs distribution via Gaussian integration by parts, overlap concentration, and precise cavity estimates, we show that a Hessian-ascent process achieves an $O(1)$ Wasserstein error guarantee for finite-time localization, improving on the previous $o(n)$. A careful comparison of stochastic localization with the Hessian ascent process and a free probability argument controlling the diagonal sub-algebra of the Hessian improves this to $O(1)$ in KL divergence. We then use Jarzynski's equality with rejection sampling, along with a restricted log-Sobolev inequality on the time-$T$ localized distribution, to refine the error to $o(1)$ in TVD up to a constant time $T$ and to complete the sampling with Glauber dynamics.

Authors: Ewan Davies, Holden Lee, Juspreet Singh Sandhu, Jonathan Shi

We give a polynomial-time algorithm to sample from the Gibbs measure of the Sherrington--Kirkpatrick model with negligible total-variation distance (TVD) error up to inverse temperature $β< 1/2$. Prior work obtained TVD error guarantees only up to $β\approx 0.295$, while results covering the entire replica-symmetric regime $β< 1$ gave guarantees only in Wasserstein distance. Our approach demonstrates that the same potential Hessian ascent previously developed for optimization also functions as a sampling algorithm by implementing algorithmic stochastic localization at high temperature. By estimating the covariance of the tilted Gibbs distribution via Gaussian integration by parts, overlap concentration, and precise cavity estimates, we show that a Hessian-ascent process achieves an $O(1)$ Wasserstein error guarantee for finite-time localization, improving on the previous $o(n)$. A careful comparison of stochastic localization with the Hessian ascent process and a free probability argument controlling the diagonal sub-algebra of the Hessian improves this to $O(1)$ in KL divergence. We then use Jarzynski's equality with rejection sampling, along with a restricted log-Sobolev inequality on the time-$T$ localized distribution, to refine the error to $o(1)$ in TVD up to a constant time $T$ and to complete the sampling with Glauber dynamics.

Wednesday, May 06 2026, 00:00

Counting Small Balanced (p,q)-bicliques in Signed Bipartite Graphs

Authors: Mekala Kiran, Apurba Das, Suman Banerjee, Tathagata Ray

Two disjoint sets of entities and their relationship can be modelled as a bipartite graph. Real-life examples include drug-target interaction in biological networks, user-item relationships in e-commerce networks, etc. Motif-based analysis is essential for understanding the structure of large-scale networks, and bipartite graphs are no exception. In contrast to unsigned graphs, motif analysis in signed bipartite graphs has received limited attention. The smallest non-trivial motif in a signed bipartite graph is a balanced (2,2)-biclique, often called a balanced butterfly, which captures only local patterns and cannot reveal higher-order relationships. Bipartite motifs have been studied in the literature in the context of signed bipartite graphs, such as maximal biclique, bitruss, and so on. None of these works addresses bipartite motifs with fixed-sized vertex sets, which are often relevant in practical situations. In this work, we study the balanced (p,q)-biclique counting problem for small values of p and q. As a baseline, we first adapt and extend the state-of-the-art BCList++ algorithm for unsigned bipartite graphs to incorporate edge signs, which we call SBCList++. We then propose two efficient algorithms: BBWC, a wedge-centric approach that enforces balance constraints during enumeration, and BBVP, a vertex-based pruning approach that directly enumerates feasible vertex sets. Extensive experiments on large real-world datasets demonstrate that the vertex-based pruning algorithm, BBVP, significantly outperforms the baseline, achieving an average speedup of 636$\times$ over SBCList++ (where p=q=3).

Authors: Mekala Kiran, Apurba Das, Suman Banerjee, Tathagata Ray

Two disjoint sets of entities and their relationship can be modelled as a bipartite graph. Real-life examples include drug-target interaction in biological networks, user-item relationships in e-commerce networks, etc. Motif-based analysis is essential for understanding the structure of large-scale networks, and bipartite graphs are no exception. In contrast to unsigned graphs, motif analysis in signed bipartite graphs has received limited attention. The smallest non-trivial motif in a signed bipartite graph is a balanced (2,2)-biclique, often called a balanced butterfly, which captures only local patterns and cannot reveal higher-order relationships. Bipartite motifs have been studied in the literature in the context of signed bipartite graphs, such as maximal biclique, bitruss, and so on. None of these works addresses bipartite motifs with fixed-sized vertex sets, which are often relevant in practical situations. In this work, we study the balanced (p,q)-biclique counting problem for small values of p and q. As a baseline, we first adapt and extend the state-of-the-art BCList++ algorithm for unsigned bipartite graphs to incorporate edge signs, which we call SBCList++. We then propose two efficient algorithms: BBWC, a wedge-centric approach that enforces balance constraints during enumeration, and BBVP, a vertex-based pruning approach that directly enumerates feasible vertex sets. Extensive experiments on large real-world datasets demonstrate that the vertex-based pruning algorithm, BBVP, significantly outperforms the baseline, achieving an average speedup of 636$\times$ over SBCList++ (where p=q=3).

Wednesday, May 06 2026, 00:00

An Optimal Algorithm for Cardinality-Constrained Diameter Partitioning

Authors: Chao Xu, Mingdong Yang

Cardinality-constrained diameter partitioning asks for a partition of $n$ items into two classes of prescribed sizes that minimizes the larger of the two class diameters. We give an $O(n^2)$ algorithm and a matching $Ω(n^2)$ lower bound if we can only query the weight between two elements. The algorithm computes the optimum for every cardinality simultaneously, improving Avis's $O(n^2\log n)$. The reduction is to a bottleneck 2-coloring problem on the maximum spanning tree, solved by a standard tree DP. For a single cardinality with Euclidean weights, we obtain a subquadratic time algorithm in any fixed dimension.

Authors: Chao Xu, Mingdong Yang

Cardinality-constrained diameter partitioning asks for a partition of $n$ items into two classes of prescribed sizes that minimizes the larger of the two class diameters. We give an $O(n^2)$ algorithm and a matching $Ω(n^2)$ lower bound if we can only query the weight between two elements. The algorithm computes the optimum for every cardinality simultaneously, improving Avis's $O(n^2\log n)$. The reduction is to a bottleneck 2-coloring problem on the maximum spanning tree, solved by a standard tree DP. For a single cardinality with Euclidean weights, we obtain a subquadratic time algorithm in any fixed dimension.

Wednesday, May 06 2026, 00:00

Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch

Authors: Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo

Embedding-based representations in Euclidean space $\mathbb{R}^d$ are a cornerstone of modern machine learning, where a major goal is to use the \emph{smallest dimension} that faithfully captures data relations. In this work, we prove sharp dimension--accuracy tradeoffs and identify a fundamental information-theoretic limitation: unless the embedding dimension $d$ is chosen close to the ground-truth dimension $D$, accuracy undergoes a sudden collapse. Our main result shows that this phenomenon arises even in standard contrastive learning settings, where supervision is limited to a set of $m$ anchor--positive--negative triplets $(i,j,k)$ encoding distance comparisons $\mathrm{dist}(i,j) < \mathrm{dist}(i,k)$. Specifically, given triplets realizable by an unknown ground-truth embedding in $D$ dimensions, we prove that there exists constant $c < 1$, such that \emph{every embedding of dimension at most $cD$ violates half of the triplets}, yielding accuracy as low as a trivial one-dimensional solution that ignores the input. We complement our information-theoretic bounds with strong computational hardness results: under the Unique Games Conjecture, even if the given triplets are nearly realizable in $D=1$ dimension, no polynomial-time algorithm -- \textit{regardless of its dimension} -- can achieve accuracy above the trivial $50\%$ baseline.

Authors: Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo

Embedding-based representations in Euclidean space $\mathbb{R}^d$ are a cornerstone of modern machine learning, where a major goal is to use the \emph{smallest dimension} that faithfully captures data relations. In this work, we prove sharp dimension--accuracy tradeoffs and identify a fundamental information-theoretic limitation: unless the embedding dimension $d$ is chosen close to the ground-truth dimension $D$, accuracy undergoes a sudden collapse. Our main result shows that this phenomenon arises even in standard contrastive learning settings, where supervision is limited to a set of $m$ anchor--positive--negative triplets $(i,j,k)$ encoding distance comparisons $\mathrm{dist}(i,j) < \mathrm{dist}(i,k)$. Specifically, given triplets realizable by an unknown ground-truth embedding in $D$ dimensions, we prove that there exists constant $c < 1$, such that \emph{every embedding of dimension at most $cD$ violates half of the triplets}, yielding accuracy as low as a trivial one-dimensional solution that ignores the input. We complement our information-theoretic bounds with strong computational hardness results: under the Unique Games Conjecture, even if the given triplets are nearly realizable in $D=1$ dimension, no polynomial-time algorithm -- \textit{regardless of its dimension} -- can achieve accuracy above the trivial $50\%$ baseline.

Wednesday, May 06 2026, 00:00

Dynamic Detours

Authors: Daniel Dadush, Michał Pilipczuk, Amadeus Reinald, Marek Sokołowski, Michał Włodarczyk

Fix a parameter $k\in \mathbf{N}$. We give dynamic data structures that for a fully dynamic undirected graph $G$, updated over time by edge insertions and edge deletions, can answer the following queries: - Long $(u,v)$-path: Given $u,v\in V(G)$, is there a path from $u$ to $v$ of length at least $k$? - Long $(u,v)$-detour: Given $u,v\in V(G)$, is there a path from $u$ to $v$ of length at least $\text{dist}_G(u,v)+k$? - Even/odd $(u,v)$-path: Given $u,v\in V(G)$, is there a path from $u$ to $v$ of even/odd length? The amortized time of executing an update or answering a query is $2^{O(k^3)} \log n + O(\log^2 n \log^2 \log n)$ in the first two cases, and $O(\log^2 n \log^2 \log n)$ in the last, where $n$ is the number of vertices of $G$. The first result is in sharp contrast with known conditional lower bounds for reporting paths of length at most $k$. Specifically, there is no data structure supporting queries about $(u,v)$-paths of length at most two in time $n^{o(1)}$ unless the Triangle Conjecture fails. Our main technical contribution is a mechanism of "delayed edge insertion" that works locally on the level of biconnected components.

Authors: Daniel Dadush, Michał Pilipczuk, Amadeus Reinald, Marek Sokołowski, Michał Włodarczyk

Fix a parameter $k\in \mathbf{N}$. We give dynamic data structures that for a fully dynamic undirected graph $G$, updated over time by edge insertions and edge deletions, can answer the following queries: - Long $(u,v)$-path: Given $u,v\in V(G)$, is there a path from $u$ to $v$ of length at least $k$? - Long $(u,v)$-detour: Given $u,v\in V(G)$, is there a path from $u$ to $v$ of length at least $\text{dist}_G(u,v)+k$? - Even/odd $(u,v)$-path: Given $u,v\in V(G)$, is there a path from $u$ to $v$ of even/odd length? The amortized time of executing an update or answering a query is $2^{O(k^3)} \log n + O(\log^2 n \log^2 \log n)$ in the first two cases, and $O(\log^2 n \log^2 \log n)$ in the last, where $n$ is the number of vertices of $G$. The first result is in sharp contrast with known conditional lower bounds for reporting paths of length at most $k$. Specifically, there is no data structure supporting queries about $(u,v)$-paths of length at most two in time $n^{o(1)}$ unless the Triangle Conjecture fails. Our main technical contribution is a mechanism of "delayed edge insertion" that works locally on the level of biconnected components.

Wednesday, May 06 2026, 00:00

A Poisson Process for Submodular Maximization

Authors: Amit Ganz Rozenman, Ariel Kulik, Roy Schwartz, Mohit Singh

We study the problem of maximizing a monotone submodular function subject to a matroid independence constraint. For more than a decade, a rich body of work has studied this problem. Initially, a tight approximation of $ (1-\frac{1}{e})$ was given using the continuous greedy algorithm [Calinescu-Chekuri-Pal-Vondr{á}k STOC`2008] and later non-oblivious local search techniques were able to match this tight approximation guarantee [Filmus-Ward FOCS`2012] and [Buchbinder-Feldman FOCS`2024]. We propose a new and remarkably simple approach to this problem that is based on a stochastic Poisson process. Our approach matches the tight $ (1-\frac{1}{e})$ approximation guarantee and it differs from the known two techniques since it does not require discretization or rounding while performing very few single element swaps. We also present applications of our approach and obtain fast algorithms for submodular welfare maximization, and for the general and separable assignment problems.

Authors: Amit Ganz Rozenman, Ariel Kulik, Roy Schwartz, Mohit Singh

We study the problem of maximizing a monotone submodular function subject to a matroid independence constraint. For more than a decade, a rich body of work has studied this problem. Initially, a tight approximation of $ (1-\frac{1}{e})$ was given using the continuous greedy algorithm [Calinescu-Chekuri-Pal-Vondr{á}k STOC`2008] and later non-oblivious local search techniques were able to match this tight approximation guarantee [Filmus-Ward FOCS`2012] and [Buchbinder-Feldman FOCS`2024]. We propose a new and remarkably simple approach to this problem that is based on a stochastic Poisson process. Our approach matches the tight $ (1-\frac{1}{e})$ approximation guarantee and it differs from the known two techniques since it does not require discretization or rounding while performing very few single element swaps. We also present applications of our approach and obtain fast algorithms for submodular welfare maximization, and for the general and separable assignment problems.

Wednesday, May 06 2026, 00:00

The Complexity of Stoquastic Sparse Hamiltonians

Authors: Alex B. Grilo, Marios Rozos

Despite having an unnatural definition, $\mathsf{StoqMA}$ plays a central role in Hamiltonian complexity, e.g., in the classification theorem of the complexity of Hamiltonians by Cubitt and Montanaro (SICOMP 2016). Moreover, it lies between the two randomized extensions of $\mathsf{NP}$, $\mathsf{MA}$ and $\mathsf{AM}$. Therefore, understanding the exact power of $\mathsf{StoqMA}$ (and hopefully collapsing it with more natural complexity classes) is of great interest for different reasons. In this work, we take a step further in understanding this complexity class by showing that the Stoquastic Sparse Hamiltonians problem ($\mathsf{StoqSH}$) is in $\mathsf{StoqMA}$. Since Stoquastic Local Hamiltonians are $\mathsf{StoqMA}$-hard, this implies that $\mathsf{StoqSH}$ is $\mathsf{StoqMA}$-complete. We complement this result by showing that the separable version of $\mathsf{StoqSH}$ is $\mathsf{StoqMA}(2)$-complete, where $\mathsf{StoqMA}(2)$ is the version of $\mathsf{StoqMA}$ that receives two unentangled proofs.

Authors: Alex B. Grilo, Marios Rozos

Despite having an unnatural definition, $\mathsf{StoqMA}$ plays a central role in Hamiltonian complexity, e.g., in the classification theorem of the complexity of Hamiltonians by Cubitt and Montanaro (SICOMP 2016). Moreover, it lies between the two randomized extensions of $\mathsf{NP}$, $\mathsf{MA}$ and $\mathsf{AM}$. Therefore, understanding the exact power of $\mathsf{StoqMA}$ (and hopefully collapsing it with more natural complexity classes) is of great interest for different reasons. In this work, we take a step further in understanding this complexity class by showing that the Stoquastic Sparse Hamiltonians problem ($\mathsf{StoqSH}$) is in $\mathsf{StoqMA}$. Since Stoquastic Local Hamiltonians are $\mathsf{StoqMA}$-hard, this implies that $\mathsf{StoqSH}$ is $\mathsf{StoqMA}$-complete. We complement this result by showing that the separable version of $\mathsf{StoqSH}$ is $\mathsf{StoqMA}(2)$-complete, where $\mathsf{StoqMA}(2)$ is the version of $\mathsf{StoqMA}$ that receives two unentangled proofs.

Tuesday, May 05 2026, 00:00

Exponential speedups in fault-tolerant processing of quantum experiments

Authors: Ishaan Kannan, Harald Putterman, Jordan Cotler

Quantum information processing has the potential to substantially enhance how we learn from physical experiments, but coupling a quantum processor to an experimental sample introduces noise that can exponentially degrade learning even when the processor itself is fault-tolerant. In this work, we show that fault tolerance can nevertheless be leveraged to recover exponential speedups by embedding the unknown system into an arbitrarily high-distance quantum code with only constant error overhead and running a fault-tolerant learning algorithm. Using this $\textit{quantum uploading}$ procedure, we prove that both classical shadow tomography and the estimation of cubic observables can be performed exponentially faster than by any adaptive strategy that does not immediately upload the state into encoded memory. These separations hold even when the uploading stage is substantially noisier than the bare experimental interface. To prove them, we introduce the Heisenberg learning tree method, a flexible tool for obtaining learning lower bounds when the limited resource is not quantum replicas but an experimentally motivated constraint such as noise. We numerically illustrate the speedups in an astronomical imaging application, where quantum processing of individual uploaded photons locates an exoplanet obscured by a bright star using orders of magnitude fewer shots than unencoded baselines. Our results establish fault-tolerant quantum computation as a valuable tool for learning from quantum experiments.

Authors: Ishaan Kannan, Harald Putterman, Jordan Cotler

Quantum information processing has the potential to substantially enhance how we learn from physical experiments, but coupling a quantum processor to an experimental sample introduces noise that can exponentially degrade learning even when the processor itself is fault-tolerant. In this work, we show that fault tolerance can nevertheless be leveraged to recover exponential speedups by embedding the unknown system into an arbitrarily high-distance quantum code with only constant error overhead and running a fault-tolerant learning algorithm. Using this $\textit{quantum uploading}$ procedure, we prove that both classical shadow tomography and the estimation of cubic observables can be performed exponentially faster than by any adaptive strategy that does not immediately upload the state into encoded memory. These separations hold even when the uploading stage is substantially noisier than the bare experimental interface. To prove them, we introduce the Heisenberg learning tree method, a flexible tool for obtaining learning lower bounds when the limited resource is not quantum replicas but an experimentally motivated constraint such as noise. We numerically illustrate the speedups in an astronomical imaging application, where quantum processing of individual uploaded photons locates an exoplanet obscured by a bright star using orders of magnitude fewer shots than unencoded baselines. Our results establish fault-tolerant quantum computation as a valuable tool for learning from quantum experiments.

Tuesday, May 05 2026, 00:00

The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions

Authors: Gorgi Pavlov

We introduce the Banach-Butterfly Invariant (BBT), an influence-adaptive Banach geometry on the Walsh-Hadamard butterfly factorization. For a Boolean function $f:\{-1,+1\}^n\to\{-1,+1\}$ with coordinate influences $\mathrm{Inf}_\ell(f)$, BBT assigns exponent $p_\ell = 1+\mathrm{Inf}_\ell(f)$ to butterfly layer $\ell$, yielding the contraction invariant $μ(f)=\prod_\ell 2^{-\mathrm{Inf}_\ell/(1+\mathrm{Inf}_\ell)}$. We prove a Jensen lower bound $\log_2μ(f) \ge -I(f)/(1+I(f)/n)$ and that $μ$ is strictly Schur-convex in the influence vector (modulo permutation), giving scaling classes $μ\sim 2^{-n/2}$ (parity), $2^{-Θ(\sqrt{n})}$ (majority), $2^{-1/2}$ (dictators). $\log_2μ$ is rational but not polynomial in the Fourier coefficients while $μ$ is algebraic, and $μ$ separates functions with identical total influence (122 pairs at $n=3$). Using the certified $n \le 4$ ternary Walsh-threshold universe from a companion synthesis manuscript as a finite testbed, we compute exact MILP minimum-support certificates for all 65,536 Boolean functions at $n=4$ (mean 6.42, max 9, all-odd by a parity argument) and on 10,000 of the 616,126 NPN-canonical representatives we enumerate at $n=5$ (matching OEIS A000370). Conditional Spearman $ρ(μ,|\mathrm{supp}|)$ at fixed total influence is $+0.571$ in the largest stratum at $n=4$ but reverses to $-0.38$ at $n=5$ under both function-uniform and NPN-canonical sampling: $μ$ is a valid Schur-convex concentration invariant, not a universal monotone predictor of minimum support across $n$. A companion application paper validates a real-valued WHT activation-energy proxy inspired by this theory on five pretrained LLMs at W2A16, cutting wikitext-2 perplexity by 15-58% versus vanilla auto-round; the transfer from Boolean theory to the real-valued proxy is qualitative, not formal.

Authors: Gorgi Pavlov

We introduce the Banach-Butterfly Invariant (BBT), an influence-adaptive Banach geometry on the Walsh-Hadamard butterfly factorization. For a Boolean function $f:\{-1,+1\}^n\to\{-1,+1\}$ with coordinate influences $\mathrm{Inf}_\ell(f)$, BBT assigns exponent $p_\ell = 1+\mathrm{Inf}_\ell(f)$ to butterfly layer $\ell$, yielding the contraction invariant $μ(f)=\prod_\ell 2^{-\mathrm{Inf}_\ell/(1+\mathrm{Inf}_\ell)}$. We prove a Jensen lower bound $\log_2μ(f) \ge -I(f)/(1+I(f)/n)$ and that $μ$ is strictly Schur-convex in the influence vector (modulo permutation), giving scaling classes $μ\sim 2^{-n/2}$ (parity), $2^{-Θ(\sqrt{n})}$ (majority), $2^{-1/2}$ (dictators). $\log_2μ$ is rational but not polynomial in the Fourier coefficients while $μ$ is algebraic, and $μ$ separates functions with identical total influence (122 pairs at $n=3$). Using the certified $n \le 4$ ternary Walsh-threshold universe from a companion synthesis manuscript as a finite testbed, we compute exact MILP minimum-support certificates for all 65,536 Boolean functions at $n=4$ (mean 6.42, max 9, all-odd by a parity argument) and on 10,000 of the 616,126 NPN-canonical representatives we enumerate at $n=5$ (matching OEIS A000370). Conditional Spearman $ρ(μ,|\mathrm{supp}|)$ at fixed total influence is $+0.571$ in the largest stratum at $n=4$ but reverses to $-0.38$ at $n=5$ under both function-uniform and NPN-canonical sampling: $μ$ is a valid Schur-convex concentration invariant, not a universal monotone predictor of minimum support across $n$. A companion application paper validates a real-valued WHT activation-energy proxy inspired by this theory on five pretrained LLMs at W2A16, cutting wikitext-2 perplexity by 15-58% versus vanilla auto-round; the transfer from Boolean theory to the real-valued proxy is qualitative, not formal.

Tuesday, May 05 2026, 00:00

Lower Bounds for Approximate Sign Rank

Authors: Riju Bindu, Hamed Hatami, Hasti Karimi, Robert Robere

We prove new upper and lower bounds on $ε$-approximate sign-rank, a relaxation of sign-rank introduced by Chornomaz, Moran, and Waknine (STOC 2025). We show that every $m \times n$ sign matrix with approximate sign-rank $d$ contains a monochromatic rectangle of size $d^{-O(d)}m \times d^{-O(d^2)}n$, paralleling classical results for exact sign-rank. As an application, we establish a lower bound of $Ω(\sqrt{d/\log d})$ on the $ε$-approximate sign-rank of large-margin $d$-dimensional half-spaces. Prior to our work, the only general lower bound technique known for approximate sign-rank yielded bounds of strength $ε^{-1} - 1$, which are constant for fixed $ε$. A key ingredient is a new geometric theorem on hyperplane avoidance: for any set of $n$ points in general position in $\mathbb{R}^d$, there exist $d$ subsets, each of size $d^{-O(d)} n$, such that no hyperplane simultaneously splits all of them. The proof combines the Forster-Barthe isotropic position theorem with the Bourgain-Tzafriri restricted invertibility principle. We also study the relationship between approximate sign-rank and VC dimension. We prove a lower bound on approximate sign-rank in terms of VC dimension, and exhibit concept classes of VC dimension $2$ with large approximate sign-rank. Finally, we study the approximate sign-rank of the $2^m \times 2^m$ Hadamard matrix $H_m$. The sign-rank of $H_m$ is known to be $Ω(\sqrt{2^m})$ by Forster's classic theorem. Contrasting this, we adapt an argument of Alman and Williams to show that the approximate sign-rank of $H_m$ is at most $m^{O(\sqrt{m} \log(1/ε))}$, and hence the Hadamard matrix does not witness polynomial-strength lower bounds for approximate sign-rank. Using our VC dimension bound, we prove that the approximate sign-rank of $H_m$ is at least $Ω_ε(m)$.

Authors: Riju Bindu, Hamed Hatami, Hasti Karimi, Robert Robere

We prove new upper and lower bounds on $ε$-approximate sign-rank, a relaxation of sign-rank introduced by Chornomaz, Moran, and Waknine (STOC 2025). We show that every $m \times n$ sign matrix with approximate sign-rank $d$ contains a monochromatic rectangle of size $d^{-O(d)}m \times d^{-O(d^2)}n$, paralleling classical results for exact sign-rank. As an application, we establish a lower bound of $Ω(\sqrt{d/\log d})$ on the $ε$-approximate sign-rank of large-margin $d$-dimensional half-spaces. Prior to our work, the only general lower bound technique known for approximate sign-rank yielded bounds of strength $ε^{-1} - 1$, which are constant for fixed $ε$. A key ingredient is a new geometric theorem on hyperplane avoidance: for any set of $n$ points in general position in $\mathbb{R}^d$, there exist $d$ subsets, each of size $d^{-O(d)} n$, such that no hyperplane simultaneously splits all of them. The proof combines the Forster-Barthe isotropic position theorem with the Bourgain-Tzafriri restricted invertibility principle. We also study the relationship between approximate sign-rank and VC dimension. We prove a lower bound on approximate sign-rank in terms of VC dimension, and exhibit concept classes of VC dimension $2$ with large approximate sign-rank. Finally, we study the approximate sign-rank of the $2^m \times 2^m$ Hadamard matrix $H_m$. The sign-rank of $H_m$ is known to be $Ω(\sqrt{2^m})$ by Forster's classic theorem. Contrasting this, we adapt an argument of Alman and Williams to show that the approximate sign-rank of $H_m$ is at most $m^{O(\sqrt{m} \log(1/ε))}$, and hence the Hadamard matrix does not witness polynomial-strength lower bounds for approximate sign-rank. Using our VC dimension bound, we prove that the approximate sign-rank of $H_m$ is at least $Ω_ε(m)$.

Tuesday, May 05 2026, 00:00

On Sampling Lower Bounds for Polynomials

Authors: Mohammad Mahdi Khodabandeh, Igor Shinkar

In this work, we continue the line of research on the complexity of distributions (Viola, Journal of Computing 2012), and study samplers defined by low degree polynomials. An $n$-tuple $P = (P_1,\dots, P_n)$ of functions $P_i \colon \mathbb{F}_2^m \to \mathbb{F}_2$ defines a distribution over $\{0,1\}^n$ in the natural way: draw $X$ uniformly at random from $\mathbb{F}_2^m$ and output $(P_1(X),\dots, P_n(X)) \in \{0,1\}^n$. We show that when $P$ is defined by polynomials of degree $d$, the total variation distance of $P$ from the product distribution $\mathrm{Ber}(1/3)^{\otimes n}$ is $1-o_n(1)$, where $o_n(1)$ is a vanishing function of $n$ for any constant degree $d$. For small values of $d$, we show the following concrete bounds. (i) For $d=1$ we have $\|P-\mathrm{Ber}(1/3)^{\otimes n}\|_{TV} \geq 1-\exp(-Ω(n))$. (ii) For $d=2$ we have $\|P-\mathrm{Ber}(1/3)^{\otimes n}\|_{TV} \geq 1-\exp(-Ω(\log(n)/\log\log(n)))$. (iii) For $d=3$ we have $\|P-\mathrm{Ber}(1/3)^{\otimes n}\|_{TV} \geq 1-\exp(-Ω(\sqrt{\log\log(n)}))$. Our results extend the recent lower bound results for sampling distributions, which have mostly focused on local samplers, small depth decision trees, and small depth circuits. As part of our proof, we establish the following result, that may be of independent interest: for any degree-$d$ polynomial $P\colon\mathbb{F}_2^m \to \mathbb{F}_2$ it holds that $\Pr_X[P(X) = 1]$ is bounded away from $1/3$ by some absolute constant $δ= δ_d>0$. Although the statement may seem obvious, we are not aware of an elementary proof of this. The proof techniques rely on the structural results for low degree polynomials, saying that any biased polynomial of degree $d$ can be written as a function of a small number of polynomials of degree $d-1$.

Authors: Mohammad Mahdi Khodabandeh, Igor Shinkar

In this work, we continue the line of research on the complexity of distributions (Viola, Journal of Computing 2012), and study samplers defined by low degree polynomials. An $n$-tuple $P = (P_1,\dots, P_n)$ of functions $P_i \colon \mathbb{F}_2^m \to \mathbb{F}_2$ defines a distribution over $\{0,1\}^n$ in the natural way: draw $X$ uniformly at random from $\mathbb{F}_2^m$ and output $(P_1(X),\dots, P_n(X)) \in \{0,1\}^n$. We show that when $P$ is defined by polynomials of degree $d$, the total variation distance of $P$ from the product distribution $\mathrm{Ber}(1/3)^{\otimes n}$ is $1-o_n(1)$, where $o_n(1)$ is a vanishing function of $n$ for any constant degree $d$. For small values of $d$, we show the following concrete bounds. (i) For $d=1$ we have $\|P-\mathrm{Ber}(1/3)^{\otimes n}\|_{TV} \geq 1-\exp(-Ω(n))$. (ii) For $d=2$ we have $\|P-\mathrm{Ber}(1/3)^{\otimes n}\|_{TV} \geq 1-\exp(-Ω(\log(n)/\log\log(n)))$. (iii) For $d=3$ we have $\|P-\mathrm{Ber}(1/3)^{\otimes n}\|_{TV} \geq 1-\exp(-Ω(\sqrt{\log\log(n)}))$. Our results extend the recent lower bound results for sampling distributions, which have mostly focused on local samplers, small depth decision trees, and small depth circuits. As part of our proof, we establish the following result, that may be of independent interest: for any degree-$d$ polynomial $P\colon\mathbb{F}_2^m \to \mathbb{F}_2$ it holds that $\Pr_X[P(X) = 1]$ is bounded away from $1/3$ by some absolute constant $δ= δ_d>0$. Although the statement may seem obvious, we are not aware of an elementary proof of this. The proof techniques rely on the structural results for low degree polynomials, saying that any biased polynomial of degree $d$ can be written as a function of a small number of polynomials of degree $d-1$.

Tuesday, May 05 2026, 00:00

Implicit Minimal Surfaces for Bijective Correspondences

Authors: Etienne Corman, Yousuf Soliman, Robin Magnet, Mark Gillespie

We introduce an implicit representation of continuous, bijective, orientation-preserving maps between genus zero surfaces with or without boundary. The distortion of these maps can easily be minimized by optimizing the Ginzburg-Landau functional - a ubiquitous model in physics and differential geometry - leading to a simple algorithm for computing bijective correspondences using only standard tools of the tangent vector field toolbox. The method avoids combinatorial mesh modifications and does not require barrier functions to enforce bijectivity making it more robust to noise and simpler to implement. Moreover, the algorithm does not assume a bijective initialization and can untangle non-bijective correspondences generated by computationally cheaper methods such as functional maps. It supports the use of both landmark points and landmark curves to guide the correspondence. The key idea is that a bijection between surfaces defines a two-dimensional mapping surface sitting inside the four-dimensional product space of the two inputs, and this mapping surface can be stored implicitly as the zero set of a complex section - essentially a complex function defined on the product space. Now the distortion of the map can be optimized by minimizing the area of this mapping surface, which amounts to minimizing the Ginzburg-Landau functional of the complex section. We demonstrate the practical benefits of our method by comparing to state-of-the-art correspondence algorithms and show that our implicit representation offers improved stability and naturally supports constraints that are difficult to enforce with explicit map representations.

Authors: Etienne Corman, Yousuf Soliman, Robin Magnet, Mark Gillespie

We introduce an implicit representation of continuous, bijective, orientation-preserving maps between genus zero surfaces with or without boundary. The distortion of these maps can easily be minimized by optimizing the Ginzburg-Landau functional - a ubiquitous model in physics and differential geometry - leading to a simple algorithm for computing bijective correspondences using only standard tools of the tangent vector field toolbox. The method avoids combinatorial mesh modifications and does not require barrier functions to enforce bijectivity making it more robust to noise and simpler to implement. Moreover, the algorithm does not assume a bijective initialization and can untangle non-bijective correspondences generated by computationally cheaper methods such as functional maps. It supports the use of both landmark points and landmark curves to guide the correspondence. The key idea is that a bijection between surfaces defines a two-dimensional mapping surface sitting inside the four-dimensional product space of the two inputs, and this mapping surface can be stored implicitly as the zero set of a complex section - essentially a complex function defined on the product space. Now the distortion of the map can be optimized by minimizing the area of this mapping surface, which amounts to minimizing the Ginzburg-Landau functional of the complex section. We demonstrate the practical benefits of our method by comparing to state-of-the-art correspondence algorithms and show that our implicit representation offers improved stability and naturally supports constraints that are difficult to enforce with explicit map representations.

Tuesday, May 05 2026, 00:00

Manifold k-NN: Accelerated k-NN Queries for Manifold Point Clouds

Authors: Pengfei Wang, Qinghao Guo, Haisen Zhao, Shiqing Xin, Shuangmin Chen, Changhe Tu, Wenping Wang

k-nearest neighbor (k-NN) search is a fundamental primitive in geometry processing and computer graphics. While spatial partitioning structures such as kd-trees are standard, they are often manifold-blind, failing to exploit the intrinsic low-dimensional structure of points sampled from 2-manifolds. Recent advances in dynamic programming-based nearest neighbor search (DP-NNS) leverage incrementally constructed Voronoi diagrams to accelerate queries, where each site p maintains a list of successors that progressively refine its Voronoi cell. However, DP-NNS is restricted to single nearest neighbor (k=1) searches, precluding their adoption in applications that require local neighborhood statistics. In this paper, we generalize the DP-NNS framework to support arbitrary k-NN queries for manifold-aligned data. Our approach is founded on the geometric observation that if p_i is the nearest neighbor of a query q in P, then the second nearest neighbor of q must reside either within the prefix set P_{1:i-1} = {p_1, \dots, p_{i-1}} or within p_i's successor list. By recursively extending this principle, we introduce Manifold k-NN, a recursive algorithmic scheme that significantly outperforms conventional kd-trees for manifold-aligned data. Our method achieves a 1\times--10\times speedup in volume-to-surface query scenarios and inherently supports dynamic prefix queries -- enabling k-NN searches within any subset P_{1:m} (m \leq n) with zero overhead. Furthermore, we extend the framework to support point deletion via local Delaunay updates, providing a complete suite of dynamic operations for point set modification. Comprehensive experiments on diverse geometric datasets demonstrate the efficiency and broad applicability of our approach for modern graphics pipelines. Source code is available at github.com/sssomeone/manifold-knn.

Authors: Pengfei Wang, Qinghao Guo, Haisen Zhao, Shiqing Xin, Shuangmin Chen, Changhe Tu, Wenping Wang

k-nearest neighbor (k-NN) search is a fundamental primitive in geometry processing and computer graphics. While spatial partitioning structures such as kd-trees are standard, they are often manifold-blind, failing to exploit the intrinsic low-dimensional structure of points sampled from 2-manifolds. Recent advances in dynamic programming-based nearest neighbor search (DP-NNS) leverage incrementally constructed Voronoi diagrams to accelerate queries, where each site p maintains a list of successors that progressively refine its Voronoi cell. However, DP-NNS is restricted to single nearest neighbor (k=1) searches, precluding their adoption in applications that require local neighborhood statistics. In this paper, we generalize the DP-NNS framework to support arbitrary k-NN queries for manifold-aligned data. Our approach is founded on the geometric observation that if p_i is the nearest neighbor of a query q in P, then the second nearest neighbor of q must reside either within the prefix set P_{1:i-1} = {p_1, \dots, p_{i-1}} or within p_i's successor list. By recursively extending this principle, we introduce Manifold k-NN, a recursive algorithmic scheme that significantly outperforms conventional kd-trees for manifold-aligned data. Our method achieves a 1\times--10\times speedup in volume-to-surface query scenarios and inherently supports dynamic prefix queries -- enabling k-NN searches within any subset P_{1:m} (m \leq n) with zero overhead. Furthermore, we extend the framework to support point deletion via local Delaunay updates, providing a complete suite of dynamic operations for point set modification. Comprehensive experiments on diverse geometric datasets demonstrate the efficiency and broad applicability of our approach for modern graphics pipelines. Source code is available at https://github.com/sssomeone/manifold-knn.

Tuesday, May 05 2026, 00:00

A greedy maximal sweepline algorithm for a Jordan curve

Authors: Apurva Mudgal

We give a greedy sweepline algorithm for a Jordan curve and prove that it is maximal in the sense of [1]. Our proof uses Kőnig's lemma.

Authors: Apurva Mudgal

We give a greedy sweepline algorithm for a Jordan curve and prove that it is maximal in the sense of [1]. Our proof uses Kőnig's lemma.

Tuesday, May 05 2026, 00:00

Witness Set: A Visibility Problem in $NP\cap XP$

Authors: Satyabrata Jana, Debabrata Pal, Bodhayan Roy, Sasanka Roy

We study the Witness Set problem, a natural dual to the classical Art Gallery problem. In the Witness Set problem, we are given a polygon $P$ and an integer $k$ as input, and the objective is to determine whether $P$ has a witness set of size at least $k$. A point set $X$ in $P$ is called a witness set if every point in $P$ is visible from at most one point in $X$. For simple polygons, we show that Witness Set lies in both $NP$ and $XP$. This stands in sharp contrast to its dual, the Art Gallery problem, which was recently shown to be $\exists \mathbb{R}$-complete by Abrahamsen et al. and is therefore neither in $NP$ nor admits a polynomial-size discretization unless $NP=\exists \mathbb{R}$. In contrast, we prove that Witness Set for simple polygons admits a finite discretization of size $n^{f(k)}$ for some function $f$. For comparison, even for simple polygons, Efrat and Har-Peled gave an algorithm for Art Gallery running in time $n^{O(k)}$ using tools from real algebraic geometry, and it appears difficult to obtain such algorithms without this machinery. On the other hand, our approach for Witness Set is purely combinatorial and relies on discretization, leading to an $n^{f(k)}$-time algorithm. Although Amit et al. claimed more than fifteen years ago that Witness Set is $NP$-hard, no proof or reference was provided. We show that the discrete version of the Witness Set problem - where the witness set must be chosen from a given finite point set $Q$ (instead of allowing witnesses to be chosen anywhere in the polygon), referred to as Discrete Witness Set - is $NP$-complete, even when the input is restricted to rectilinear polygons with holes. However, for simple polygons, Discrete Witness Set admits a polynomial-time algorithm by Das et al. Thus, it remains an open question whether the Witness Set problem is $NP$-hard.

Authors: Satyabrata Jana, Debabrata Pal, Bodhayan Roy, Sasanka Roy

We study the Witness Set problem, a natural dual to the classical Art Gallery problem. In the Witness Set problem, we are given a polygon $P$ and an integer $k$ as input, and the objective is to determine whether $P$ has a witness set of size at least $k$. A point set $X$ in $P$ is called a witness set if every point in $P$ is visible from at most one point in $X$. For simple polygons, we show that Witness Set lies in both $NP$ and $XP$. This stands in sharp contrast to its dual, the Art Gallery problem, which was recently shown to be $\exists \mathbb{R}$-complete by Abrahamsen et al. and is therefore neither in $NP$ nor admits a polynomial-size discretization unless $NP=\exists \mathbb{R}$. In contrast, we prove that Witness Set for simple polygons admits a finite discretization of size $n^{f(k)}$ for some function $f$. For comparison, even for simple polygons, Efrat and Har-Peled gave an algorithm for Art Gallery running in time $n^{O(k)}$ using tools from real algebraic geometry, and it appears difficult to obtain such algorithms without this machinery. On the other hand, our approach for Witness Set is purely combinatorial and relies on discretization, leading to an $n^{f(k)}$-time algorithm. Although Amit et al. claimed more than fifteen years ago that Witness Set is $NP$-hard, no proof or reference was provided. We show that the discrete version of the Witness Set problem - where the witness set must be chosen from a given finite point set $Q$ (instead of allowing witnesses to be chosen anywhere in the polygon), referred to as Discrete Witness Set - is $NP$-complete, even when the input is restricted to rectilinear polygons with holes. However, for simple polygons, Discrete Witness Set admits a polynomial-time algorithm by Das et al. Thus, it remains an open question whether the Witness Set problem is $NP$-hard.

Tuesday, May 05 2026, 00:00

Spherical Geometrical Bases of Spherical Origami

Authors: Takashi Yoshino

This paper establishes a rigorous geometrical framework for spherical origami, origami using spherical sheets based on spherical geometry. Two settings are treated: origami restricted to the unit sphere ($\mathbb{S}^2$), and three-dimensional folding of spherical sheets in space. For origami on $\mathbb{S}^2$, the definitions of Euclidean origami are systematically extended to the spherical setting, and all seven Huzita--Justin axioms are shown to admit explicit equations in spherical geometry. For three-dimensional folding, equidistant curves are introduced as fold curves, replacing geodesics and enabling a richer family of folds. The framework is validated by successfully constructing computer graphics of spherical origami birds, demonstrating both the theoretical completeness and practical utility of the proposed approach.

Authors: Takashi Yoshino

This paper establishes a rigorous geometrical framework for spherical origami, origami using spherical sheets based on spherical geometry. Two settings are treated: origami restricted to the unit sphere ($\mathbb{S}^2$), and three-dimensional folding of spherical sheets in space. For origami on $\mathbb{S}^2$, the definitions of Euclidean origami are systematically extended to the spherical setting, and all seven Huzita--Justin axioms are shown to admit explicit equations in spherical geometry. For three-dimensional folding, equidistant curves are introduced as fold curves, replacing geodesics and enabling a richer family of folds. The framework is validated by successfully constructing computer graphics of spherical origami birds, demonstrating both the theoretical completeness and practical utility of the proposed approach.

Tuesday, May 05 2026, 00:00

Solution independence and self-referential instances

Authors: Guangyan Zhou, Bin Wang, Jianxin Wang, Ke Xu

In this paper, we investigate the hitting set problem and demonstrate that solution independence is the crucial property underlying the construction of self-referential instances. As a special case of the hitting set problem, the vertex cover problem lacks the solution independence property. This distinction accounts for its ability to evade exhaustive search, as correlations among candidate solutions can be leveraged to compress the overall search space. In contrast, the dominating set problem on hypergraphs, which is also a special case of the hitting set problem, satisfies the solution independence property, thereby enabling the construction of self-referential instances. Moreover, we prove that these self-referential instances possess an irreducible property, implying that any algorithm for solving such instances must process nearly the entire graph to yield a correct solution.

Authors: Guangyan Zhou, Bin Wang, Jianxin Wang, Ke Xu

In this paper, we investigate the hitting set problem and demonstrate that solution independence is the crucial property underlying the construction of self-referential instances. As a special case of the hitting set problem, the vertex cover problem lacks the solution independence property. This distinction accounts for its ability to evade exhaustive search, as correlations among candidate solutions can be leveraged to compress the overall search space. In contrast, the dominating set problem on hypergraphs, which is also a special case of the hitting set problem, satisfies the solution independence property, thereby enabling the construction of self-referential instances. Moreover, we prove that these self-referential instances possess an irreducible property, implying that any algorithm for solving such instances must process nearly the entire graph to yield a correct solution.

Tuesday, May 05 2026, 00:00

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs

Authors: Guillaume Ducoffe

A vertex in a graph is called central if it minimizes its maximum distance to the other vertices. The radius of a graph $G$ is the largest distance between a central vertex and the other vertices, and it is denoted by $rad(G)$. In the center problem, we are asked to find a central vertex. We study the fine-grained complexity of the center problem on graphs with small Gromov hyperbolicity. Roughly, the Gromov hyperbolicity of a graph represents how close, locally, it is to a tree, from a metric point of view. It has applications in the design of approximation algorithms. In particular, there is a linear-time algorithm that for every $δ$-hyperbolic graph $G$ outputs some vertex at distance at most $rad(G) + 5δ$ to the other vertices [Chepoi et al, SoCG'08]. However, a linear-time algorithm for computing a central vertex is known only for $0$-hyperbolic graphs, whereas its existence was ruled out for $2$-hyperbolic graphs under the Hitting Set Conjecture of [Abboud et al, SODA'16]. Our main contribution in the paper is a linear-time algorithm for computing a central vertex in the class of $\frac 1 2$-hyperbolic graphs. Furthermore, we rule out the existence of such an algorithm for $1$-hyperbolic graphs, under the Hitting Set Conjecture, thus completely settling all the cases left open.

Authors: Guillaume Ducoffe

A vertex in a graph is called central if it minimizes its maximum distance to the other vertices. The radius of a graph $G$ is the largest distance between a central vertex and the other vertices, and it is denoted by $rad(G)$. In the center problem, we are asked to find a central vertex. We study the fine-grained complexity of the center problem on graphs with small Gromov hyperbolicity. Roughly, the Gromov hyperbolicity of a graph represents how close, locally, it is to a tree, from a metric point of view. It has applications in the design of approximation algorithms. In particular, there is a linear-time algorithm that for every $δ$-hyperbolic graph $G$ outputs some vertex at distance at most $rad(G) + 5δ$ to the other vertices [Chepoi et al, SoCG'08]. However, a linear-time algorithm for computing a central vertex is known only for $0$-hyperbolic graphs, whereas its existence was ruled out for $2$-hyperbolic graphs under the Hitting Set Conjecture of [Abboud et al, SODA'16]. Our main contribution in the paper is a linear-time algorithm for computing a central vertex in the class of $\frac 1 2$-hyperbolic graphs. Furthermore, we rule out the existence of such an algorithm for $1$-hyperbolic graphs, under the Hitting Set Conjecture, thus completely settling all the cases left open.

Tuesday, May 05 2026, 00:00

Faster Mixing for Triangulations via Transport Flows

Authors: Vedat Levi Alev, Daniel Frishberg, Mihalis Sarantis, Prasad Tetali

We prove an $\widetilde O(n^2)$ bound for the \emph{relaxation time} and the \emph{log-Sobolev time} (inverse log-Sobolev constant) of the classical triangulation flip chain on a convex $(n+2)$-gon, implying a mixing time of $\widetilde O(n^2)$. The previous state of the art for the mixing time of this chain, due to Eppstein and Frishberg, was $\widetilde O(n^3)$, while the best known lower bound on the mixing time, due to Molloy, Reed, and Steiger, is $Ω(n^{3/2})$. Our relaxation time bound makes significant progress towards Aldous' conjectured bound of $Θ(n^{3/2})$ for the relaxation time. We improve upon the analysis of Eppstein and Frishberg by further developing the framework of \emph{transport flows} introduced in the work of Chen et al. In this light, our results can be seen as a more efficient way of using combinatorial decompositions to obtain functional inequalities for Markov chains. We hope our ideas will find other applications in the future.

Authors: Vedat Levi Alev, Daniel Frishberg, Mihalis Sarantis, Prasad Tetali

We prove an $\widetilde O(n^2)$ bound for the \emph{relaxation time} and the \emph{log-Sobolev time} (inverse log-Sobolev constant) of the classical triangulation flip chain on a convex $(n+2)$-gon, implying a mixing time of $\widetilde O(n^2)$. The previous state of the art for the mixing time of this chain, due to Eppstein and Frishberg, was $\widetilde O(n^3)$, while the best known lower bound on the mixing time, due to Molloy, Reed, and Steiger, is $Ω(n^{3/2})$. Our relaxation time bound makes significant progress towards Aldous' conjectured bound of $Θ(n^{3/2})$ for the relaxation time. We improve upon the analysis of Eppstein and Frishberg by further developing the framework of \emph{transport flows} introduced in the work of Chen et al. In this light, our results can be seen as a more efficient way of using combinatorial decompositions to obtain functional inequalities for Markov chains. We hope our ideas will find other applications in the future.

Tuesday, May 05 2026, 00:00

Ranking with Partitioning

Authors: Samuel Boardman

Given an undirected graph representing similarities between a set of items and an additive measure evaluating the items, we treat the position of a special subset of items in an ordinal ranking through a collection of combinatorial optimization problems in which items may be combined if they are similar. The objective for these problems is to either maximize or minimize the absolute or relative rank of the special subset, with a meta-goal of assessing the robustness of the rank, even in the presence of a well-defined criterion. We classify the computational complexity of all four problems, mostly finding worst-case hardness, then find exact and approximate solutions to special cases and variants of the problems. These structured cases are inspired by several real-world examples and may be used to assess commonly cited facts across disparate domains, as we demonstrate for sources of greenhouse gas emissions that contribute to climate change.

Authors: Samuel Boardman

Given an undirected graph representing similarities between a set of items and an additive measure evaluating the items, we treat the position of a special subset of items in an ordinal ranking through a collection of combinatorial optimization problems in which items may be combined if they are similar. The objective for these problems is to either maximize or minimize the absolute or relative rank of the special subset, with a meta-goal of assessing the robustness of the rank, even in the presence of a well-defined criterion. We classify the computational complexity of all four problems, mostly finding worst-case hardness, then find exact and approximate solutions to special cases and variants of the problems. These structured cases are inspired by several real-world examples and may be used to assess commonly cited facts across disparate domains, as we demonstrate for sources of greenhouse gas emissions that contribute to climate change.

Tuesday, May 05 2026, 00:00

A Polynomial Kernel for Vertex Deletion to the Scattered Class of Proper Interval Graph and Trees

Authors: Ashwin Jacob, Arpit Kumar, Diptapriyo Majumdar

Vertex deletion to hereditary graph class is well-studied in parameterized complexity. Vertex deletion to the scattered graph classes has gained attention in recent years. In this paper, we consider (Proper-Interval, Tree)-Vertex Deletion, the input to which is an undirected graph $G = (V, E)$ and an integer $k$. The goal is to pick a set $X \subseteq V(G)$ of at most $k$ vertices such that $G - X$ is a simple graph and every connected component of $G - X$ is a proper interval graph or a tree. When parameterized by the solution size $k$, (Proper-Interval, Tree)-Vertex Deletion has been proved to be fixed-parameter tractable by Jacob et al. [JCSS-2023, FCT-2021]. In this paper, we consider this problem from the perspective of polynomial kernelization. We provide a first nontrivial polynomial kernel for (Proper-Interval, Tree)-Vertex Deletion, with $O(k^{33})$ vertices.

Authors: Ashwin Jacob, Arpit Kumar, Diptapriyo Majumdar

Vertex deletion to hereditary graph class is well-studied in parameterized complexity. Vertex deletion to the scattered graph classes has gained attention in recent years. In this paper, we consider (Proper-Interval, Tree)-Vertex Deletion, the input to which is an undirected graph $G = (V, E)$ and an integer $k$. The goal is to pick a set $X \subseteq V(G)$ of at most $k$ vertices such that $G - X$ is a simple graph and every connected component of $G - X$ is a proper interval graph or a tree. When parameterized by the solution size $k$, (Proper-Interval, Tree)-Vertex Deletion has been proved to be fixed-parameter tractable by Jacob et al. [JCSS-2023, FCT-2021]. In this paper, we consider this problem from the perspective of polynomial kernelization. We provide a first nontrivial polynomial kernel for (Proper-Interval, Tree)-Vertex Deletion, with $O(k^{33})$ vertices.

Tuesday, May 05 2026, 00:00

On the power of standard DFS and BFS

Authors: Binh-Minh Bui-Xuan, Michel Habib, Fabien de Montgolfier, Renaud Torfs

It is well-known since the seventies of last century that Depth First Search (DFS) can be used to compute strongly connected components [RE. Tarjan. SIAM Journal on Computing, 1972] and Breadth First Search (BFS) can be used to compute distance in graphs [GY. Handler. Transportation Science, 1973]. We furthermore demonstrate that these standard graph searches are powerful enough to recognize and certify several well-structured graph classes. Specifically, we provide a single DFS approach for recognizing and certifying trivially perfect graphs that is significantly simpler than previous methods using [FPM. Chu. Information Processing Letters, 2008]. We further show that a single BFS can recognize split graphs and bipartite chain graphs, and we improve upon the triple LexBFS algorithm for proper interval graphs [DG. Corneil. Discrete Applied Mathematics, 2004] by proposing a two consecutive BFS recognition scheme. These results are underpinned by characterizations using vertex orderings that avoid specific patterns [L. Feuilloley, M. Habib. SIAM Journal on Discrete Mathematics, 2021]. Finally, we provide a structural study of connected proper interval graphs, proving that their characterizations via special orderings are unique up to reversal and the permutation of true twins.

Authors: Binh-Minh Bui-Xuan, Michel Habib, Fabien de Montgolfier, Renaud Torfs

It is well-known since the seventies of last century that Depth First Search (DFS) can be used to compute strongly connected components [RE. Tarjan. SIAM Journal on Computing, 1972] and Breadth First Search (BFS) can be used to compute distance in graphs [GY. Handler. Transportation Science, 1973]. We furthermore demonstrate that these standard graph searches are powerful enough to recognize and certify several well-structured graph classes. Specifically, we provide a single DFS approach for recognizing and certifying trivially perfect graphs that is significantly simpler than previous methods using [FPM. Chu. Information Processing Letters, 2008]. We further show that a single BFS can recognize split graphs and bipartite chain graphs, and we improve upon the triple LexBFS algorithm for proper interval graphs [DG. Corneil. Discrete Applied Mathematics, 2004] by proposing a two consecutive BFS recognition scheme. These results are underpinned by characterizations using vertex orderings that avoid specific patterns [L. Feuilloley, M. Habib. SIAM Journal on Discrete Mathematics, 2021]. Finally, we provide a structural study of connected proper interval graphs, proving that their characterizations via special orderings are unique up to reversal and the permutation of true twins.

Tuesday, May 05 2026, 00:00

Many Hamiltonians Are Sparsifiable

Authors: Arpon Basu, Joshua Brakensiek, Aaron Putterman

We study the problem of Hamiltonian sparsification: given a parameter $\varepsilon \in (0,1)$ and an $n$-qubit Hamiltonian $H$ which is the sum of $r$-local positive semi-definite (PSD) terms $H_1, \dots H_m$, our goal is to compute a sparse set $L \subseteq [m]$, along with weights $w: L \rightarrow \mathbb{R}_{\geq 0}$ such that for every state $|ψ\rangle\in \mathbb{C}^{2^n}$, $$ \sum_{i \in L} w(i) \langle ψ| H_i | ψ\rangle \in (1 \pm ε) \sum_{i = 1}^m \langle ψ| H_i | ψ\rangle $$. When the set $L$ is significantly smaller than $m$, this reduces the number of terms in the underlying system, while still ensuring that the behavior of the system is essentially unchanged. We show that many Hamiltonians indeed are sparsifiable to a number of terms much smaller than $n^r$, including: (a) Hamiltonians where each term is an $r$-local Pauli string, (b) Hamiltonians where each term is an $r$-local random operator of rank $R$, for $R \geq 2^{r-1}+1$, and (c) Hamiltonians where each term is an arbitrary $r$-local operator of rank $\geq 2^r -1$ (a.k.a. Quantum SAT). Taken together, our results show that the sparsifiability of Hamiltonians is a robust phenomenon, contrary to prevailing belief (see for instance, Aharonov-Zhou ITCS 2019, QIP 2019). Our results find applications, for instance, to better (semi-)streaming algorithms for quantum Max-Cut, answering a question left open by Kallaugher and Parekh (FOCS 2022). In fact, our results even codify that quantum systems are often easier to sparsify than their classical counterparts.

Authors: Arpon Basu, Joshua Brakensiek, Aaron Putterman

We study the problem of Hamiltonian sparsification: given a parameter $\varepsilon \in (0,1)$ and an $n$-qubit Hamiltonian $H$ which is the sum of $r$-local positive semi-definite (PSD) terms $H_1, \dots H_m$, our goal is to compute a sparse set $L \subseteq [m]$, along with weights $w: L \rightarrow \mathbb{R}_{\geq 0}$ such that for every state $|ψ\rangle\in \mathbb{C}^{2^n}$, $$ \sum_{i \in L} w(i) \langle ψ| H_i | ψ\rangle \in (1 \pm ε) \sum_{i = 1}^m \langle ψ| H_i | ψ\rangle $$. When the set $L$ is significantly smaller than $m$, this reduces the number of terms in the underlying system, while still ensuring that the behavior of the system is essentially unchanged. We show that many Hamiltonians indeed are sparsifiable to a number of terms much smaller than $n^r$, including: (a) Hamiltonians where each term is an $r$-local Pauli string, (b) Hamiltonians where each term is an $r$-local random operator of rank $R$, for $R \geq 2^{r-1}+1$, and (c) Hamiltonians where each term is an arbitrary $r$-local operator of rank $\geq 2^r -1$ (a.k.a. Quantum SAT). Taken together, our results show that the sparsifiability of Hamiltonians is a robust phenomenon, contrary to prevailing belief (see for instance, Aharonov-Zhou ITCS 2019, QIP 2019). Our results find applications, for instance, to better (semi-)streaming algorithms for quantum Max-Cut, answering a question left open by Kallaugher and Parekh (FOCS 2022). In fact, our results even codify that quantum systems are often easier to sparsify than their classical counterparts.

Tuesday, May 05 2026, 00:00

Undirected Replacement Paths: Dual Fault Reduces to Single Source

Authors: Jakob Nogler, Virginia Vassilevska Williams

Given a graph and two fixed vertices $s$ and $t$, the Replacement Path Problem (RP) is to compute for every edge $e$, the distance between $s$ and $t$ when $e$ is removed. There are two natural extensions to RP: (1) Single Source Replacement Paths (SSRP): Given a graph $G$ and a source node $s$, compute for every vertex $v$ and every edge $e$ the $s$-$v$ distance in $G \setminus \{e\}$. That is, we do not fix the target anymore. (2) $2$-Fault Replacement Paths (2-FRP): Given a graph $G$ and two nodes $s$ and $t$, compute for every pair of edges $e, e'$ the $s$-$t$ distance in $G \setminus \{e, e'\}$. That is, we consider two failures instead of one. Previously, there was no known reduction between SSRP and 2-FRP. It seemed plausible that 2-FRP would be computationally harder because there are no settings where 2-FRP admits a faster algorithm than SSRP. In directed unweighted graphs there is a provable gap in complexity, and in undirected graphs many of the known 2-FRP algorithms in a variety of settings are much slower than those for SSRP in the same setting. The main contribution of this paper is a tight reduction from undirected $2$-FRP to undirected SSRP, showing that contrary to prior intuition, 2-FRP is not harder than SSRP. As our reduction is weight-preserving, we obtain the first algorithms for $2$-FRP that match the best-known runtimes for SSRP: (1) $\tilde{O}(M n^ω)$ for weights in $[1, M]$ [GVW19], improving upon $O(Mn^{2.87})$ [CZ24]; (2) $n^3/2^{Ω(\sqrt{\log n})}$ for weights in $[1, \text{poly}(n)]$ [GVW19], improving over the previous $n^3\text{polylog}(n)$ running time [VWWX22]; (3) $\tilde{O}(mn^{1/2}+n^{2})$ combinatorial time for unweighted graphs [CC19], and more generally for rational weights in $[1, 2]$ [CM20], improving upon $\tilde{O}(n^{3-1/18})$ [CZ24]. We complement these upper bounds with tight lower bounds under fine-grained hypotheses.

Authors: Jakob Nogler, Virginia Vassilevska Williams

Given a graph and two fixed vertices $s$ and $t$, the Replacement Path Problem (RP) is to compute for every edge $e$, the distance between $s$ and $t$ when $e$ is removed. There are two natural extensions to RP: (1) Single Source Replacement Paths (SSRP): Given a graph $G$ and a source node $s$, compute for every vertex $v$ and every edge $e$ the $s$-$v$ distance in $G \setminus \{e\}$. That is, we do not fix the target anymore. (2) $2$-Fault Replacement Paths (2-FRP): Given a graph $G$ and two nodes $s$ and $t$, compute for every pair of edges $e, e'$ the $s$-$t$ distance in $G \setminus \{e, e'\}$. That is, we consider two failures instead of one. Previously, there was no known reduction between SSRP and 2-FRP. It seemed plausible that 2-FRP would be computationally harder because there are no settings where 2-FRP admits a faster algorithm than SSRP. In directed unweighted graphs there is a provable gap in complexity, and in undirected graphs many of the known 2-FRP algorithms in a variety of settings are much slower than those for SSRP in the same setting. The main contribution of this paper is a tight reduction from undirected $2$-FRP to undirected SSRP, showing that contrary to prior intuition, 2-FRP is not harder than SSRP. As our reduction is weight-preserving, we obtain the first algorithms for $2$-FRP that match the best-known runtimes for SSRP: (1) $\tilde{O}(M n^ω)$ for weights in $[1, M]$ [GVW19], improving upon $O(Mn^{2.87})$ [CZ24]; (2) $n^3/2^{Ω(\sqrt{\log n})}$ for weights in $[1, \text{poly}(n)]$ [GVW19], improving over the previous $n^3\text{polylog}(n)$ running time [VWWX22]; (3) $\tilde{O}(mn^{1/2}+n^{2})$ combinatorial time for unweighted graphs [CC19], and more generally for rational weights in $[1, 2]$ [CM20], improving upon $\tilde{O}(n^{3-1/18})$ [CZ24]. We complement these upper bounds with tight lower bounds under fine-grained hypotheses.

Tuesday, May 05 2026, 00:00

Fast Monte-Carlo

Authors: Irene Aldridge

This paper proposes an eigenvalue-based small-sample approximation of the celebrated Markov Chain Monte Carlo that delivers an invariant steady-state distribution that is consistent with traditional Monte Carlo methods. The proposed eigenvalue-based methodology reduces the number of paths required for Monte Carlo from as many as 1,000,000 to as few as 10 (depending on the simulation time horizon $T$), and delivers comparable, distributionally robust results, as measured by the Wasserstein distance. The proposed methodology also produces a significant variance reduction in the steady-state distribution.

Authors: Irene Aldridge

This paper proposes an eigenvalue-based small-sample approximation of the celebrated Markov Chain Monte Carlo that delivers an invariant steady-state distribution that is consistent with traditional Monte Carlo methods. The proposed eigenvalue-based methodology reduces the number of paths required for Monte Carlo from as many as 1,000,000 to as few as 10 (depending on the simulation time horizon $T$), and delivers comparable, distributionally robust results, as measured by the Wasserstein distance. The proposed methodology also produces a significant variance reduction in the steady-state distribution.

Tuesday, May 05 2026, 00:00

U-HNSW: An Efficient Graph-based Solution to ANNS Under Universal Lp Metrics

Authors: Huayi Wang, Jingfan Meng, Jun Xu

Approximate nearest neighbor search under universal L_p metrics (ANNS-U-L_p) is an important and challenging research problem, as it requires answering queries under all possible p (0

Authors: Huayi Wang, Jingfan Meng, Jun Xu

Approximate nearest neighbor search under universal L_p metrics (ANNS-U-L_p) is an important and challenging research problem, as it requires answering queries under all possible p (0

Tuesday, May 05 2026, 00:00

Randomized $k$-server in polynomial time

Authors: Christian Coester, Romain Cosson

We study the design of computationally efficient randomized algorithms for the $k$-server problem. Existing randomized algorithms with the best known competitive ratios are, on the one hand, inherently implicit and, on the other hand, employ a rounding scheme that maintains a distribution over exponentially many configurations. In this work, we introduce a derandomization framework that transforms any randomized $k$-server algorithm on a hierarchically separated tree into one that uses only $O(\log k)$ random bits for request sequences of arbitrary length; hence maintaining a distribution over only polynomially many server configurations. Leveraging this black-box derandomization, we obtain the first polynomial-time randomized $k$-server algorithm on arbitrary $n$-point metrics with a polylogarithmic competitive ratio. Our results also have implications for the advice complexity of the $k$-server problem.

Authors: Christian Coester, Romain Cosson

We study the design of computationally efficient randomized algorithms for the $k$-server problem. Existing randomized algorithms with the best known competitive ratios are, on the one hand, inherently implicit and, on the other hand, employ a rounding scheme that maintains a distribution over exponentially many configurations. In this work, we introduce a derandomization framework that transforms any randomized $k$-server algorithm on a hierarchically separated tree into one that uses only $O(\log k)$ random bits for request sequences of arbitrary length; hence maintaining a distribution over only polynomially many server configurations. Leveraging this black-box derandomization, we obtain the first polynomial-time randomized $k$-server algorithm on arbitrary $n$-point metrics with a polylogarithmic competitive ratio. Our results also have implications for the advice complexity of the $k$-server problem.

Tuesday, May 05 2026, 00:00

A Unified Approach to Minimizing Symmetric Submodular Functions

Authors: Satoru Iwata, Haruto Konno

Symmetric submodular function minimization admits purely combinatorial algorithms using special orderings of the ground set. Extending the minimum-cut algorithm of Nagamochi and Ibaraki (1992), Queyranne (1998) showed that the maximum adjacency ordering yields a pendent pair, which can be used to find a nontrivial minimizer. Nagamochi (2010) later introduced the minimum degree ordering, which yields a flat pair and leads to the identification of extreme sets. Despite the apparent similarity between these two algorithms, their connection remained unclear. In this paper, we introduce yet another ordering called minimum capacity ordering, and extend it to a one-parameter family of orderings, called $α$-orderings, that unifies these two previously known orderings. We prove a general inequality for $α$-orderings, and our framework recovers the known pendent-pair and flat-pair results as special cases, corresponding to $α= -1$ and $α= 1$, respectively. For each $α\in [-1, 1]$, the last two elements of an $α$-ordering form a contractible pair, i.e., a pair whose contraction preserves the existence of a nontrivial minimizer, which leads to a contraction algorithm that finds a nontrivial minimizer of a symmetric submodular function in $O(n^3)$ oracle calls, where $n$ is the cardinality of the ground set. In addition, we discuss the ranges of $α$ that ensure $α$-ordering to obtain these special pairs.

Authors: Satoru Iwata, Haruto Konno

Symmetric submodular function minimization admits purely combinatorial algorithms using special orderings of the ground set. Extending the minimum-cut algorithm of Nagamochi and Ibaraki (1992), Queyranne (1998) showed that the maximum adjacency ordering yields a pendent pair, which can be used to find a nontrivial minimizer. Nagamochi (2010) later introduced the minimum degree ordering, which yields a flat pair and leads to the identification of extreme sets. Despite the apparent similarity between these two algorithms, their connection remained unclear. In this paper, we introduce yet another ordering called minimum capacity ordering, and extend it to a one-parameter family of orderings, called $α$-orderings, that unifies these two previously known orderings. We prove a general inequality for $α$-orderings, and our framework recovers the known pendent-pair and flat-pair results as special cases, corresponding to $α= -1$ and $α= 1$, respectively. For each $α\in [-1, 1]$, the last two elements of an $α$-ordering form a contractible pair, i.e., a pair whose contraction preserves the existence of a nontrivial minimizer, which leads to a contraction algorithm that finds a nontrivial minimizer of a symmetric submodular function in $O(n^3)$ oracle calls, where $n$ is the cardinality of the ground set. In addition, we discuss the ranges of $α$ that ensure $α$-ordering to obtain these special pairs.

Tuesday, May 05 2026, 00:00

New Bounds for Kernel Sums via Fast Spherical Embeddings

Authors: Tal Wagner

We study query time bounds for the fundamental problem of estimating the kernel mean $\frac1{|X|}\sum_{x\in X}\mathbf{k}(x,y)$ of a query $y$ in a finite dataset $X\subset\mathbb{R}^d$ up to a prescribed additive error $\varepsilon$. The best known bounds for the Gaussian kernel are $O(d/\varepsilon^2)$, $\widetilde O(d+1/\varepsilon^4)$, and $\widetilde O(d+Δ^2/\varepsilon^2)$, where $Δ$ is the diameter of a region containing the points. We prove the new bound $\tilde O(d+\varepsilonΔ^2+1/\varepsilon^3)$, which improves over the previous ones in regimes with small error $\varepsilon$ and intermediate diameter $Δ$. At the center of our proof is a new fast spherical embedding theorem in the sense introduced by Bartal, Recht and Schulman (2011), which limits the embedded data diameter while preserving local Euclidean distances and avoiding ``distance collapse'' at larger scales. This fast embedding theorem may be of independent interest.

Authors: Tal Wagner

We study query time bounds for the fundamental problem of estimating the kernel mean $\frac1{|X|}\sum_{x\in X}\mathbf{k}(x,y)$ of a query $y$ in a finite dataset $X\subset\mathbb{R}^d$ up to a prescribed additive error $\varepsilon$. The best known bounds for the Gaussian kernel are $O(d/\varepsilon^2)$, $\widetilde O(d+1/\varepsilon^4)$, and $\widetilde O(d+Δ^2/\varepsilon^2)$, where $Δ$ is the diameter of a region containing the points. We prove the new bound $\tilde O(d+\varepsilonΔ^2+1/\varepsilon^3)$, which improves over the previous ones in regimes with small error $\varepsilon$ and intermediate diameter $Δ$. At the center of our proof is a new fast spherical embedding theorem in the sense introduced by Bartal, Recht and Schulman (2011), which limits the embedded data diameter while preserving local Euclidean distances and avoiding ``distance collapse'' at larger scales. This fast embedding theorem may be of independent interest.

Tuesday, May 05 2026, 00:00

Imperial Research Fellowships at Imperial College London (apply by June 15, 2026)

from CCI: jobs

Four‑year fellowship at Imperial College London for early‑career researchers. Open across CS. Sponsorship available for outstanding Theory of Computing candidates. Full freedom to define and drive an independent research agenda, with no obligatory teaching; salary + research budget (~£45k), strong potential towards permanence. (Departmental deadline 22 June.) Website: www.imperial.ac.uk/research-and-innovation/research-office/funder-information/research-fellowships/irf/ Email: iddo.tzameret@gmail.com

Four‑year fellowship at Imperial College London for early‑career researchers. Open across CS. Sponsorship available for outstanding Theory of Computing candidates. Full freedom to define and drive an independent research agenda, with no obligatory teaching; salary + research budget (~£45k), strong potential towards permanence. (Departmental deadline 22 June.)

Website: https://www.imperial.ac.uk/research-and-innovation/research-office/funder-information/research-fellowships/irf/
Email: iddo.tzameret@gmail.com

By shacharlovett

Monday, May 04 2026, 21:54

TR26-068 | Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time | John Hitchcock

from ECCC Papers

Lutz (1987) introduced resource-bounded category and showed the circuit size class SIZE($\frac{2^n}{n}$) is meager within ESPACE. Li (2024) established that the symmetric alternation class $S^E_2$ contains problems requiring circuits of size $\frac{2^n}{n}$. In this note, we extend resource-bounded category to $S^E_2$ by defining meagerness relative to single-valued $FS^P_2$ strategies in the Banach-Mazur game. We show that Li’s $FS^P_2$ algorithm for the Range Avoidance problem yields a winning strategy, proving that $SIZE(\frac{2^n}{n})$ is meager in $S^E_2$. Consequently, languages requiring exponential-size circuits are comeager in $S^E_2$: they are typical with respect to resource-bounded category.

Monday, May 04 2026, 18:51

Termination of Real Linear Loops

Authors: Eike Neumann, Margret Tembo

We study the problem of deciding universal termination of linear and affine loops over the reals in the bit-model of real computation. We show that both problems are as close to decidable as one can expect them to be: there exist sound partial algorithms that halt on all problem instances whose answer is robust under all sufficiently small perturbations. We further show that in each case the set of non-robust problem instances has Lebesgue measure zero.

Authors: Eike Neumann, Margret Tembo

We study the problem of deciding universal termination of linear and affine loops over the reals in the bit-model of real computation. We show that both problems are as close to decidable as one can expect them to be: there exist sound partial algorithms that halt on all problem instances whose answer is robust under all sufficiently small perturbations. We further show that in each case the set of non-robust problem instances has Lebesgue measure zero.

Monday, May 04 2026, 00:00

On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank