Theory of Computing Report

Authors: Yun-Tak Oh, Dongsoo Lee, Jungyoul Park, Kyung Chul Jeong, Panjin Kim

This work identifies a necessary condition for any variational quantum approach to reach the exact ground state. Briefly, the norms of the projections of the input and the ground state onto each group module must match, implying that module weights of the solution state have to be known in advance in order to reach the exact ground state. An exemplary case is provided by matchgate circuits applied to problems whose solutions are classical bit strings, since all computational basis states share the same module-wise weights. Combined with the known classical simulability of quantum circuits for which observables lie in a small linear subspace, this implies that certain problems admit a classical surrogate for exact solution with each step taking $O(n^5)$ time. The Maximum Cut problem serves as an illustrative example.

Authors: Yun-Tak Oh, Dongsoo Lee, Jungyoul Park, Kyung Chul Jeong, Panjin Kim

This work identifies a necessary condition for any variational quantum approach to reach the exact ground state. Briefly, the norms of the projections of the input and the ground state onto each group module must match, implying that module weights of the solution state have to be known in advance in order to reach the exact ground state. An exemplary case is provided by matchgate circuits applied to problems whose solutions are classical bit strings, since all computational basis states share the same module-wise weights. Combined with the known classical simulability of quantum circuits for which observables lie in a small linear subspace, this implies that certain problems admit a classical surrogate for exact solution with each step taking $O(n^5)$ time. The Maximum Cut problem serves as an illustrative example.

Thursday, April 16 2026, 00:00

On the Decidability of Verification under Release/Acquire

Authors: Giovanna Kobus Conrado, Andreas Pavlogiannis

The verification of concurrent programs under weak-memory models is a burgeoning effort, owing to the increasing adoption of weak memory in concurrent software and hardware. Release/Acquire has become the standard model for high-performance concurrent programming, adopted by common mainstream languages and computer architectures. In a surprising result, Abdulla et al. (PLDI'19) proved that reachability in this model is undecidable when programs have access to atomic Read-Modify-Write (RMW) operations. Moreover, undecidability holds even for executions with just 4 contexts, and is thus immune to underapproximations based on bounded context switching. The canonical, RMW-free case was left as a challenging question, proving a non-primitive recursive lower bound as a first step, and has remained open for the past seven years. In this paper, we settle the above open question by proving that reachability is undecidable even in the RMW-free fragment of Release/Acquire, thereby characterizing the simplest set of communication primitives that gives rise to undecidability. Moreover, we prove that bounding both the number of context switches and the number of RMWs recovers decidability, thus fully characterizing the boundary of decidability along the dimensions of RMW-bounding and context-bounding.

Authors: Giovanna Kobus Conrado, Andreas Pavlogiannis

The verification of concurrent programs under weak-memory models is a burgeoning effort, owing to the increasing adoption of weak memory in concurrent software and hardware. Release/Acquire has become the standard model for high-performance concurrent programming, adopted by common mainstream languages and computer architectures. In a surprising result, Abdulla et al. (PLDI'19) proved that reachability in this model is undecidable when programs have access to atomic Read-Modify-Write (RMW) operations. Moreover, undecidability holds even for executions with just 4 contexts, and is thus immune to underapproximations based on bounded context switching. The canonical, RMW-free case was left as a challenging question, proving a non-primitive recursive lower bound as a first step, and has remained open for the past seven years. In this paper, we settle the above open question by proving that reachability is undecidable even in the RMW-free fragment of Release/Acquire, thereby characterizing the simplest set of communication primitives that gives rise to undecidability. Moreover, we prove that bounding both the number of context switches and the number of RMWs recovers decidability, thus fully characterizing the boundary of decidability along the dimensions of RMW-bounding and context-bounding.

Thursday, April 16 2026, 00:00

Fast Time-Varying Contiguous Cartograms Using Integral Images

Authors: Vladimir Molchanov, Hennes Rave, Lars Linsen

Cartograms are a technique for visually representing geographically distributed statistical data, where values of a numerical attribute are mapped to the size of geographic regions. Contiguous cartograms preserve the adjacencies of the original regions during the mapping. To be useful, contiguous cartograms also require approximate preservation of shapes and relative positions. Due to these desirable properties, contiguous cartograms are among the most popular ones. Most methods for constructing contiguous cartograms exploit a deformation of the original map. Aiming at the preservation of geographical properties, existing approaches are often algorithmically cumbersome and computationally intensive. We propose a novel deformation technique for computing time-varying contiguous cartograms based on integral images evaluated for a series of discrete density distributions. The density textures represent the given dynamic statistical data. The iterative application of the proposed mapping smoothly transforms the domain to gradually equalize the temporal density, i.e., region areas grow or shrink following their evolutionary statistical data. Global shape preservation at each time step is controlled by a single parameter that can be interactively adjusted by the user. Our efficient GPU implementation of the proposed algorithm is significantly faster than existing state-of-the-art methods while achieving comparable quality for cartographic accuracy, shape preservation, and topological error. We investigate strategies for transitioning between adjacent time steps and discuss the parameter choice. Our approach applies to comparative cartograms' morphing and interactive cartogram exploration.

Authors: Vladimir Molchanov, Hennes Rave, Lars Linsen

Cartograms are a technique for visually representing geographically distributed statistical data, where values of a numerical attribute are mapped to the size of geographic regions. Contiguous cartograms preserve the adjacencies of the original regions during the mapping. To be useful, contiguous cartograms also require approximate preservation of shapes and relative positions. Due to these desirable properties, contiguous cartograms are among the most popular ones. Most methods for constructing contiguous cartograms exploit a deformation of the original map. Aiming at the preservation of geographical properties, existing approaches are often algorithmically cumbersome and computationally intensive. We propose a novel deformation technique for computing time-varying contiguous cartograms based on integral images evaluated for a series of discrete density distributions. The density textures represent the given dynamic statistical data. The iterative application of the proposed mapping smoothly transforms the domain to gradually equalize the temporal density, i.e., region areas grow or shrink following their evolutionary statistical data. Global shape preservation at each time step is controlled by a single parameter that can be interactively adjusted by the user. Our efficient GPU implementation of the proposed algorithm is significantly faster than existing state-of-the-art methods while achieving comparable quality for cartographic accuracy, shape preservation, and topological error. We investigate strategies for transitioning between adjacent time steps and discuss the parameter choice. Our approach applies to comparative cartograms' morphing and interactive cartogram exploration.

Thursday, April 16 2026, 00:00

NP-Hardness and a PTAS for the Pinwheel Problem

Authors: Robert Kleinberg, Ahan Mishra

In the pinwheel problem, one is given an $m$-tuple of positive integers $(a_1, \ldots, a_m)$ and asked whether the integers can be partitioned into $m$ color classes $C_1,\ldots,C_m$ such that every interval of length $a_i$ has non-empty intersection with $C_i$, for $i = 1, 2, \ldots, m$. It was a long-standing open question whether the pinwheel problem is NP-hard. We affirm a prediction of Holte et al. (1989) by demonstrating, for the first time, NP-hardness of the pinwheel problem. This enables us to prove NP-hardness for a host of other problems considered in the literature: pinwheel covering, bamboo garden trimming, windows scheduling, recurrent scheduling, and the constant gap problem. On the positive side, we develop a PTAS for an approximate version of the pinwheel problem. Previously, the best approximation factor known to be achievable in polynomial time was $\frac{9}{7}$.

Authors: Robert Kleinberg, Ahan Mishra

In the pinwheel problem, one is given an $m$-tuple of positive integers $(a_1, \ldots, a_m)$ and asked whether the integers can be partitioned into $m$ color classes $C_1,\ldots,C_m$ such that every interval of length $a_i$ has non-empty intersection with $C_i$, for $i = 1, 2, \ldots, m$. It was a long-standing open question whether the pinwheel problem is NP-hard. We affirm a prediction of Holte et al. (1989) by demonstrating, for the first time, NP-hardness of the pinwheel problem. This enables us to prove NP-hardness for a host of other problems considered in the literature: pinwheel covering, bamboo garden trimming, windows scheduling, recurrent scheduling, and the constant gap problem. On the positive side, we develop a PTAS for an approximate version of the pinwheel problem. Previously, the best approximation factor known to be achievable in polynomial time was $\frac{9}{7}$.

Thursday, April 16 2026, 00:00

Parallel Algorithms for Group Isomorphism via Code Equivalence

Authors: Michael Levet

In this paper, we exhibit $\textsf{AC}^{3}$ isomorphism tests for coprime extensions $H \ltimes N$ where $H$ is elementary Abelian and $N$ is Abelian; and groups where $\text{Rad}(G) = Z(G)$ is elementary Abelian and $G = \text{Soc}^{*}(G)$. The fact that isomorphism testing for these families is in $\textsf{P}$ was established respectively by Qiao, Sarma, and Tang (STACS 2011), and Grochow and Qiao (CCC 2014, SIAM J. Comput. 2017). The polynomial-time isomorphism tests for both of these families crucially leveraged small (size $O(\log |G|)$) instances of Linear Code Equivalence (Babai, SODA 2011). Here, we combine Luks' group-theoretic method for Graph Isomorphism (FOCS 1980, J. Comput. Syst. Sci. 1982) with the fact that $G$ is given by its multiplication table, to implement the corresponding instances of Linear Code Equivalence in $\textsf{AC}^{3}$. As a byproduct of our work, we show that isomorphism testing of arbitrary central-radical groups is decidable using $\textsf{AC}$ circuits of depth $O(\log^3 n)$ and size $n^{O(\log \log n)}$. This improves upon the previous bound of $n^{O(\log \log n)}$-time due to Grochow and Qiao (ibid.).

Authors: Michael Levet

In this paper, we exhibit $\textsf{AC}^{3}$ isomorphism tests for coprime extensions $H \ltimes N$ where $H$ is elementary Abelian and $N$ is Abelian; and groups where $\text{Rad}(G) = Z(G)$ is elementary Abelian and $G = \text{Soc}^{*}(G)$. The fact that isomorphism testing for these families is in $\textsf{P}$ was established respectively by Qiao, Sarma, and Tang (STACS 2011), and Grochow and Qiao (CCC 2014, SIAM J. Comput. 2017). The polynomial-time isomorphism tests for both of these families crucially leveraged small (size $O(\log |G|)$) instances of Linear Code Equivalence (Babai, SODA 2011). Here, we combine Luks' group-theoretic method for Graph Isomorphism (FOCS 1980, J. Comput. Syst. Sci. 1982) with the fact that $G$ is given by its multiplication table, to implement the corresponding instances of Linear Code Equivalence in $\textsf{AC}^{3}$. As a byproduct of our work, we show that isomorphism testing of arbitrary central-radical groups is decidable using $\textsf{AC}$ circuits of depth $O(\log^3 n)$ and size $n^{O(\log \log n)}$. This improves upon the previous bound of $n^{O(\log \log n)}$-time due to Grochow and Qiao (ibid.).

Thursday, April 16 2026, 00:00

Max Cut with Small-Dimensional SDP Solutions

Authors: Hsien-Chih Chang, Suprovat Ghoshal, Euiwoong Lee

We study the Max-Cut semidefinite programming (SDP) relaxation in the regime where a near-optimal solution admits a low-dimensional realization. While the Goemans--Williamson hyperplane rounding achieves the worst-case optimal approximation ratio $α_{GW}\approx 0.87856$, it is natural to ask whether one can beat $α_{GW}$ when the SDP solution lives in $\mathbb{R}^d$ for a small dimension $d$. We answer this in the affirmative for every fixed $d$: there is a polynomial-time rounding algorithm that, given a $d$-dimensional feasible solution to the standard Max-Cut SDP strengthened with triangle inequalities, produces a cut of expected value at least $(α_{GW}+2^{-O(d)})$ times the SDP value. Our improvement is driven by a new geometric anti-concentration lemma for signs of low-dimensional Gaussian projections.

Authors: Hsien-Chih Chang, Suprovat Ghoshal, Euiwoong Lee

We study the Max-Cut semidefinite programming (SDP) relaxation in the regime where a near-optimal solution admits a low-dimensional realization. While the Goemans--Williamson hyperplane rounding achieves the worst-case optimal approximation ratio $α_{GW}\approx 0.87856$, it is natural to ask whether one can beat $α_{GW}$ when the SDP solution lives in $\mathbb{R}^d$ for a small dimension $d$. We answer this in the affirmative for every fixed $d$: there is a polynomial-time rounding algorithm that, given a $d$-dimensional feasible solution to the standard Max-Cut SDP strengthened with triangle inequalities, produces a cut of expected value at least $(α_{GW}+2^{-O(d)})$ times the SDP value. Our improvement is driven by a new geometric anti-concentration lemma for signs of low-dimensional Gaussian projections.

Thursday, April 16 2026, 00:00

Block-Based Pathfinding: A Minecraft System for Visualizing Graph Algorithms

Authors: Luca-Stefan Pirvu, Bogdan-Alexandru Maciuca, Andrei-Ciprian Rabu, Adrian-Marius Dumitran

Graph theory is a cornerstone of Computer Science education, yet entry-level students often struggle to map abstract node-edge relationships to practical applications. This paper presents the design and architecture of a Minecraft-based educational tool specifically built to visualize graph traversal and shortest-path algorithms. We propose a three-layer system: (1) a Grid Traversal module where terrain types (e.g., soul sand, ice) represent edge weights, allowing for the gamified study of shortest path algorithms; (2) a "Sky Graph" module for interactive 3D manipulation of both directed and undirected graphs; and (3) lessons and quizzes available through books. The system grounds its design in Constructionist learning theory, transitioning students from passive observers to active protagonists who physically manipulate algorithmic behavior. We additionally present a planned empirical evaluation using NASA-TLX and in-game telemetry to validate the system's pedagogical efficacy.

Authors: Luca-Stefan Pirvu, Bogdan-Alexandru Maciuca, Andrei-Ciprian Rabu, Adrian-Marius Dumitran

Graph theory is a cornerstone of Computer Science education, yet entry-level students often struggle to map abstract node-edge relationships to practical applications. This paper presents the design and architecture of a Minecraft-based educational tool specifically built to visualize graph traversal and shortest-path algorithms. We propose a three-layer system: (1) a Grid Traversal module where terrain types (e.g., soul sand, ice) represent edge weights, allowing for the gamified study of shortest path algorithms; (2) a "Sky Graph" module for interactive 3D manipulation of both directed and undirected graphs; and (3) lessons and quizzes available through books. The system grounds its design in Constructionist learning theory, transitioning students from passive observers to active protagonists who physically manipulate algorithmic behavior. We additionally present a planned empirical evaluation using NASA-TLX and in-game telemetry to validate the system's pedagogical efficacy.

Thursday, April 16 2026, 00:00

Fully Dynamic Maintenance of Loop Nesting Forests in Reducible Flow Graphs

Authors: Gregory Morse, Tamás Kozsik

Loop nesting forests (LNFs) are a fundamental abstraction for reasoning about control-flow structure, enabling applications such as compiler optimizations, program analysis, and dominator computation. While efficient static algorithms for constructing LNFs are well understood, maintaining them under dynamic graph updates has remained largely unexplored due to the lack of efficient dynamic depth-first search (DFS) maintenance. In this paper, we present the first fully dynamic algorithm for maintaining loop nesting forests in reducible control-flow graphs. Our approach leverages recent advances in dynamic DFS maintenance to incrementally update loop structure under edge insertions and deletions. We show that updates can be confined to local regions of the depth-first spanning tree, avoiding global recomputation. We provide formal invariants, correctness arguments, and complexity analysis, and demonstrate how the maintained LNF enables efficient derivation of dominance information. Our results establish LNFs as a practical dynamic abstraction for modern compiler and analysis pipelines.

Authors: Gregory Morse, Tamás Kozsik

Loop nesting forests (LNFs) are a fundamental abstraction for reasoning about control-flow structure, enabling applications such as compiler optimizations, program analysis, and dominator computation. While efficient static algorithms for constructing LNFs are well understood, maintaining them under dynamic graph updates has remained largely unexplored due to the lack of efficient dynamic depth-first search (DFS) maintenance. In this paper, we present the first fully dynamic algorithm for maintaining loop nesting forests in reducible control-flow graphs. Our approach leverages recent advances in dynamic DFS maintenance to incrementally update loop structure under edge insertions and deletions. We show that updates can be confined to local regions of the depth-first spanning tree, avoiding global recomputation. We provide formal invariants, correctness arguments, and complexity analysis, and demonstrate how the maintained LNF enables efficient derivation of dominance information. Our results establish LNFs as a practical dynamic abstraction for modern compiler and analysis pipelines.

Thursday, April 16 2026, 00:00

Lawler-Moore Speedups via Additive Combinatorics

Authors: Karl Bringmann, Danny Hermelin, Tomohiro Koana, Dvir Shabtay

The Lawler-Moore dynamic programming framework is a classical tool in scheduling on parallel machines. It applies when the objective is regular, i.e. monotone in job completion times, and each machine follows a fixed priority order such as Smith's Rule or Jackson's Rule. For the basic objectives $Pm||\sum w_jC_j$, $Pm||L_{\max}$, and $Pm||\sum w_jU_j$, it gives running times $O(P^{m-1}n)$, $O(P^{m-1}n)$, and $O(P^mn)$, respectively, where $P$ is the total processing time. Recent SETH-based lower bounds indicate that the dependence on $P$ is essentially optimal, but they do not rule out improved dependence on the maximum processing time $p_{\max}$. We give the first major speedup of the Lawler-Moore recurrence. Our main ingredients are a new state-pruning method and a swapping argument based on an additive-combinatorial lemma. We prove that, whenever this swap does not increase the objective value, there exists an optimal schedule in which, for every prefix of jobs, the load difference between any two machines is at most $4p_{\max}^2$. This lets us prune redundant states throughout the dynamic program, replacing the dependence on $P$ by a dependence on $p_{\max}^2$. We show that the swap is non-increasing for all three objectives above. Hence $Pm||\sum w_jC_j$ and $Pm||L_{\max}$ admit algorithms with running time $O(p_{\max}^{2m-2}n)$, while $Pm||\sum w_jU_j$ can be solved in time $O(p_{\max}^{2m-2}Pn)\le O(p_{\max}^{2m-1}n^2)$. These bounds strictly improve the original Lawler-Moore runtimes whenever $p_{\max}=o(\sqrt{P})$. In particular, for $Pm||\sum w_jC_j$ and $Pm||L_{\max}$, we obtain the first near-linear-time algorithms when processing times are polylogarithmic in $n$.

Authors: Karl Bringmann, Danny Hermelin, Tomohiro Koana, Dvir Shabtay

The Lawler-Moore dynamic programming framework is a classical tool in scheduling on parallel machines. It applies when the objective is regular, i.e. monotone in job completion times, and each machine follows a fixed priority order such as Smith's Rule or Jackson's Rule. For the basic objectives $Pm||\sum w_jC_j$, $Pm||L_{\max}$, and $Pm||\sum w_jU_j$, it gives running times $O(P^{m-1}n)$, $O(P^{m-1}n)$, and $O(P^mn)$, respectively, where $P$ is the total processing time. Recent SETH-based lower bounds indicate that the dependence on $P$ is essentially optimal, but they do not rule out improved dependence on the maximum processing time $p_{\max}$. We give the first major speedup of the Lawler-Moore recurrence. Our main ingredients are a new state-pruning method and a swapping argument based on an additive-combinatorial lemma. We prove that, whenever this swap does not increase the objective value, there exists an optimal schedule in which, for every prefix of jobs, the load difference between any two machines is at most $4p_{\max}^2$. This lets us prune redundant states throughout the dynamic program, replacing the dependence on $P$ by a dependence on $p_{\max}^2$. We show that the swap is non-increasing for all three objectives above. Hence $Pm||\sum w_jC_j$ and $Pm||L_{\max}$ admit algorithms with running time $O(p_{\max}^{2m-2}n)$, while $Pm||\sum w_jU_j$ can be solved in time $O(p_{\max}^{2m-2}Pn)\le O(p_{\max}^{2m-1}n^2)$. These bounds strictly improve the original Lawler-Moore runtimes whenever $p_{\max}=o(\sqrt{P})$. In particular, for $Pm||\sum w_jC_j$ and $Pm||L_{\max}$, we obtain the first near-linear-time algorithms when processing times are polylogarithmic in $n$.

Thursday, April 16 2026, 00:00

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model

Authors: Yuichi Yoshida

We study property testing of directed acyclicity in the unidirectional bounded-degree oracle model, where a query to a vertex reveals its outgoing neighbors. We prove that there exist absolute constants $d_0\in\mathbb{N}$ and $\varepsilon>0$ such that for every constant $d\ge d_0$, any one-sided $\varepsilon$-tester for acyclicity on $n$-vertex digraphs of maximum outdegree at most $d$ requires $\widetildeΩ(n^{2/3})$ queries. This improves the previous $\widetildeΩ(n^{5/9})$ lower bound for one-sided testing of acyclicity in the same model. We also prove that, under the same degree assumption, any two-sided $\varepsilon$-tester requires $Ω(\sqrt n)$ queries, improving the previous $Ω(n^{1/3})$ lower bound. We further prove an $Ω(n)$ lower bound for tolerant testing for some absolute constant outdegree bound $d$ by reduction from bounded-degree $3$-colorability.

Authors: Yuichi Yoshida

We study property testing of directed acyclicity in the unidirectional bounded-degree oracle model, where a query to a vertex reveals its outgoing neighbors. We prove that there exist absolute constants $d_0\in\mathbb{N}$ and $\varepsilon>0$ such that for every constant $d\ge d_0$, any one-sided $\varepsilon$-tester for acyclicity on $n$-vertex digraphs of maximum outdegree at most $d$ requires $\widetildeΩ(n^{2/3})$ queries. This improves the previous $\widetildeΩ(n^{5/9})$ lower bound for one-sided testing of acyclicity in the same model. We also prove that, under the same degree assumption, any two-sided $\varepsilon$-tester requires $Ω(\sqrt n)$ queries, improving the previous $Ω(n^{1/3})$ lower bound. We further prove an $Ω(n)$ lower bound for tolerant testing for some absolute constant outdegree bound $d$ by reduction from bounded-degree $3$-colorability.

Thursday, April 16 2026, 00:00

Linear-Time Exact Computation of Influence Spread on Bounded-Pathwidth Graphs

Authors: Kengo Nakamura, Masaaki Nishino

Given a network and a set of vertices called seeds to initially inject information, influence spread is the expected number of vertices that eventually receive the information under a certain stochastic model of information propagation. Under the commonly used independent cascade model, influence spread is equivalent to the expected number of vertices reachable from the seeds on a directed uncertain graph, and the exact evaluation of influence spread offers many applications, e.g., influence maximization. Although its evaluation is a \#P-hard task, there is an algorithm that can precisely compute the influence spread in $O(mnω_p^2\cdot 2^{ω_p^2})$ time, where $ω_p$ is the pathwidth of the graph. We improve this by developing an algorithm that computes the influence spread in $O((m+n)ω_p^2\cdot 2^{ω_p^2})$ time. This is achieved by identifying the similarities in the repetitive computations in the existing algorithm and sharing them to reduce computation. Although similar refinements have been considered for the probability computation on undirected uncertain graphs, a greater number of similarities must be leveraged for directed graphs to achieve linear time complexity.

Authors: Kengo Nakamura, Masaaki Nishino

Given a network and a set of vertices called seeds to initially inject information, influence spread is the expected number of vertices that eventually receive the information under a certain stochastic model of information propagation. Under the commonly used independent cascade model, influence spread is equivalent to the expected number of vertices reachable from the seeds on a directed uncertain graph, and the exact evaluation of influence spread offers many applications, e.g., influence maximization. Although its evaluation is a \#P-hard task, there is an algorithm that can precisely compute the influence spread in $O(mnω_p^2\cdot 2^{ω_p^2})$ time, where $ω_p$ is the pathwidth of the graph. We improve this by developing an algorithm that computes the influence spread in $O((m+n)ω_p^2\cdot 2^{ω_p^2})$ time. This is achieved by identifying the similarities in the repetitive computations in the existing algorithm and sharing them to reduce computation. Although similar refinements have been considered for the probability computation on undirected uncertain graphs, a greater number of similarities must be leveraged for directed graphs to achieve linear time complexity.

Thursday, April 16 2026, 00:00

Online TCP Acknowledgment under General Delays

Authors: Sujoy Bhore, Michał Pawłowski, Seeun William Umboh

In a seminal work, Dooly, Goldman, and Scott (STOC 1998; JACM 2001) introduced the classic Online TCP Acknowledgment problem. In this problem, a sequence of $n$ packets arrives over time, and the objective is to minimize both the number of acknowledgments sent and the total delay experienced by the packets. They showed that a greedy algorithm -- acknowledge when the delay of pending packets equals the acknowledgment cost -- is $2$-competitive. Online TCP Acknowledgment is the canonical online problem with delay, capturing the fundamental tradeoff between reducing service cost through batching and the delay incurred by pending requests. Prior work has largely focused on different types of service costs, e.g., Joint Replenishment. However, to the best of our knowledge, beyond the work of Albers and Bals (SODA 2003), which studies maximum delay and closely related objectives, not much is known for more general delay cost models. In this work, we study the Online TCP Acknowledgment under two new generalized delay costs that we call batch-oblivious and batch-aware. In the former, the delay cost is a function of the vector of packet delays. We show that the classic greedy approach is also $2$-competitive for continuous submodular functions and $\ell_p$ norms. In the batch-aware model, each batch incurs a delay cost that is a function $f$ of the vector of delays incurred by its packets. When the overall delay cost is the maximum of the batch delay costs, we show that the greedy approach is also $2$-competitive. Our main technical contribution is for the batch-aware setting, where the overall delay cost is the sum of the batch delay costs. We show that the greedy approach is $Ω(n)$-competitive and that the deterministic competitive ratio is $Θ(\log n)$. Remarkably, our algorithm only requires the bare minimum assumption that $f$ is monotone.

Authors: Sujoy Bhore, Michał Pawłowski, Seeun William Umboh

In a seminal work, Dooly, Goldman, and Scott (STOC 1998; JACM 2001) introduced the classic Online TCP Acknowledgment problem. In this problem, a sequence of $n$ packets arrives over time, and the objective is to minimize both the number of acknowledgments sent and the total delay experienced by the packets. They showed that a greedy algorithm -- acknowledge when the delay of pending packets equals the acknowledgment cost -- is $2$-competitive. Online TCP Acknowledgment is the canonical online problem with delay, capturing the fundamental tradeoff between reducing service cost through batching and the delay incurred by pending requests. Prior work has largely focused on different types of service costs, e.g., Joint Replenishment. However, to the best of our knowledge, beyond the work of Albers and Bals (SODA 2003), which studies maximum delay and closely related objectives, not much is known for more general delay cost models. In this work, we study the Online TCP Acknowledgment under two new generalized delay costs that we call batch-oblivious and batch-aware. In the former, the delay cost is a function of the vector of packet delays. We show that the classic greedy approach is also $2$-competitive for continuous submodular functions and $\ell_p$ norms. In the batch-aware model, each batch incurs a delay cost that is a function $f$ of the vector of delays incurred by its packets. When the overall delay cost is the maximum of the batch delay costs, we show that the greedy approach is also $2$-competitive. Our main technical contribution is for the batch-aware setting, where the overall delay cost is the sum of the batch delay costs. We show that the greedy approach is $Ω(n)$-competitive and that the deterministic competitive ratio is $Θ(\log n)$. Remarkably, our algorithm only requires the bare minimum assumption that $f$ is monotone.

Thursday, April 16 2026, 00:00

Near-Optimal Constructive Bounds for $\ell_2$ Prefix Discrepancy and Steinitz Problems via Affine Spectral Independence

Authors: Kunal Dutta, Agastya Vibhuti Jha, Haotian Jiang

A classical result of Steinitz from 1913 \cite{Ste13}, answering an earlier question of Riemann and Lévy (e.g., \cite{Lev05}), states that for any norm $\|\cdot\|$ in $\mathbb{R}^d$ and any set of vectors $v_1, \cdots, v_n \in \R^d$ satisfying $\sum_{i=1}^n v_i = 0$, there exists an ordering $π: [n] \rightarrow [n]$ such that every partial sum along this order is bounded by $O(d)$, i.e., $\big\| \sum_{i=1}^t v_{π(i)} \big\| \leq O(d)$ for all $t \in [n]$. Steinitz's bound is tight up to constants in general, but for the $\ell_2$ norm $\|\cdot\|_2$, it has been conjectured that the best bound is $O(\sqrt{d})$. Almost a century later, a breakthrough work of Banaszczyk \cite{Ban12} gave a bound of $O(\sqrt{d} + \sqrt{\log n})$ for the $\ell_2$ Steinitz problem, matching the conjecture under the mild assumption that $d \geq Ω(\log n)$. Banaszczyk's result is non-constructive, and the previous best algorithmic bound was $O(\sqrt{d \log n})$, due to Bansal and Garg \cite{BG17}. In this work, we give an efficient algorithm that matches the conjectured $O(\sqrt{d})$ bound for the $\ell_2$ Steinitz problem under the slightly worse, yet still polylogarithmic, condition of $d \geq Ω(\log^7 n)$. As in prior work, our result extends to the harder problem of $\ell_2$ prefix discrepancy. We employ the framework of obtaining the desired ordering via a discrete Brownian motion, guided by a semidefinite program (SDP). To obtain our results, we use the new technique of ``Decoupling via Affine Spectral Independence'', proposed by Bansal and Jiang \cite{BJ26} to achieve substantial progress on the Beck-Fiala and Komlós conjectures, together with a ``Global Interval Tree'' data structure that simultaneously controls the deviations for all prefixes.

Authors: Kunal Dutta, Agastya Vibhuti Jha, Haotian Jiang

A classical result of Steinitz from 1913 \cite{Ste13}, answering an earlier question of Riemann and Lévy (e.g., \cite{Lev05}), states that for any norm $\|\cdot\|$ in $\mathbb{R}^d$ and any set of vectors $v_1, \cdots, v_n \in \R^d$ satisfying $\sum_{i=1}^n v_i = 0$, there exists an ordering $π: [n] \rightarrow [n]$ such that every partial sum along this order is bounded by $O(d)$, i.e., $\big\| \sum_{i=1}^t v_{π(i)} \big\| \leq O(d)$ for all $t \in [n]$. Steinitz's bound is tight up to constants in general, but for the $\ell_2$ norm $\|\cdot\|_2$, it has been conjectured that the best bound is $O(\sqrt{d})$. Almost a century later, a breakthrough work of Banaszczyk \cite{Ban12} gave a bound of $O(\sqrt{d} + \sqrt{\log n})$ for the $\ell_2$ Steinitz problem, matching the conjecture under the mild assumption that $d \geq Ω(\log n)$. Banaszczyk's result is non-constructive, and the previous best algorithmic bound was $O(\sqrt{d \log n})$, due to Bansal and Garg \cite{BG17}. In this work, we give an efficient algorithm that matches the conjectured $O(\sqrt{d})$ bound for the $\ell_2$ Steinitz problem under the slightly worse, yet still polylogarithmic, condition of $d \geq Ω(\log^7 n)$. As in prior work, our result extends to the harder problem of $\ell_2$ prefix discrepancy. We employ the framework of obtaining the desired ordering via a discrete Brownian motion, guided by a semidefinite program (SDP). To obtain our results, we use the new technique of ``Decoupling via Affine Spectral Independence'', proposed by Bansal and Jiang \cite{BJ26} to achieve substantial progress on the Beck-Fiala and Komlós conjectures, together with a ``Global Interval Tree'' data structure that simultaneously controls the deviations for all prefixes.

Thursday, April 16 2026, 00:00

Encodings for Range Minimum Queries over Bounded Alphabets

Authors: Seungbum Jo, Srinivasa Rao Satti

Range minimum queries (RMQs) are fundamental operations with widespread applications in database management, text indexing and computational biology. While many space-efficient data structures have been designed for RMQs on arrays with arbitrary elements, there has not been any results developed for the case when the alphabet size is small, which is the case in many practical scenarios where RMQ structures are used. In this paper, we investigate the encoding complexity of RMQs on arrays over bounded alphabet. We consider both one-dimensional (1D) and two-dimensional (2D) arrays. For the 1D case, we present a near-optimal space encoding. For constant-sized alphabets, this also supports the queries in constant time. For the 2D case, we systematically analyze the 1-sided, 2-sided, 3-sided and 4-sided queries and derive lower bounds for encoding space, and also matching upper bounds that support efficient queries in most cases. Our results demonstrate that, even with the bounded alphabet restriction, the space requirements remain close to those for the general alphabet case.

Authors: Seungbum Jo, Srinivasa Rao Satti

Range minimum queries (RMQs) are fundamental operations with widespread applications in database management, text indexing and computational biology. While many space-efficient data structures have been designed for RMQs on arrays with arbitrary elements, there has not been any results developed for the case when the alphabet size is small, which is the case in many practical scenarios where RMQ structures are used. In this paper, we investigate the encoding complexity of RMQs on arrays over bounded alphabet. We consider both one-dimensional (1D) and two-dimensional (2D) arrays. For the 1D case, we present a near-optimal space encoding. For constant-sized alphabets, this also supports the queries in constant time. For the 2D case, we systematically analyze the 1-sided, 2-sided, 3-sided and 4-sided queries and derive lower bounds for encoding space, and also matching upper bounds that support efficient queries in most cases. Our results demonstrate that, even with the bounded alphabet restriction, the space requirements remain close to those for the general alphabet case.

Thursday, April 16 2026, 00:00

Linkage

from David Eppstein

Congratulations to Ken Clarkson and the rest of the newly-named SIAM Fellows ($\mathbb{M}$)!

Congratulations to Ken Clarkson and the rest of the newly-named SIAM Fellows ($\mathbb{M}$)!
Richard Elwes on Numberphile talking about big numbers ($\mathbb{M}$). The twist: these ones are from many centuries ago, from Jain mathematicians. They got at least as far as tetration.
How wireless origami cushioning could improve logistics ($\mathbb{M}$), by providing shipping damage alerts in real time.
The long-predicted cleveref apocalypse is upon me ($\mathbb{M}$). For the most part it works to just replace
```
\usepackage[capitalize,nameinlink]{cleveref}
```
by
```
\usepackage{zref-clever}
\zcsetup{cap}
\let\cref\zcref
```
I have been using an “observation” theorem type, and for this I need to tell zref-clever what to call them:
```
\zcRefTypeSetup{observation}{Name-sg=Observation,Name-pl=Observations}
```
If you want to have different theorem types share the same numbers, things get more complicated. I haven’t needed that yet, but there’s guidance in Section 10.2 of the zref-clever user manual.
After a long-ish quiet period, quite a few new solutions to the no-three-in-line problem have been discovered this year ($\mathbb{M}$).
A medieval woman teaches geometry to a group of students ($\mathbb{M}$). From an early 14th-century manuscript of Euclid’s Elements. Sadly, most online sources make the sexist inference that a woman couldn’t possibly have been a geometry teacher then, and therefore that she must instead be a “personification of geometry”.
Deterministic primality testing for limited bit width ($\mathbb{M}$). Precomputing a small set of good bases gives a fast derandomization of the Miller–Rabin primality test.
The Music of the Spheres ($\mathbb{M}$), sequence from the Saturday Morning Breakfast Cereal comic strip, coauthored by Terry Tao, on what mathematicians do and the unreasonable effectiveness of mathematics, as illustrated through the sphere packing problem.
Alison Martin folds a single sheet of paper into an umbilic torus (see also).
Cathedral building geometry basics: how to find the center of a circle with compass and straightedge ($\mathbb{M}$). It might not come as a surprise that people who repair stonework on old cathedrals with handheld chisels and hand-poured molten lead (the rest of the content on this YouTube channel) might also prefer to make their architectural drawings and templates by hand instead of with a CAD system.
Tariq asks: What do people recommend for publication quality plots of mathematical functions?
Many sequences in OEIS come from various real-world applications. Jeremy Kun looks for the opposite: open-source code that has applied OEIS sequences in unusual ways ($\mathbb{M}$). These include music synthesis, pen tool size settings, and geocaching.
Through a new Wikipedia article I learn that Uruguay has a museum devoted to origami ($\mathbb{M}$), claimed to be the only one in the Americas.
Cats on a lintel ($\mathbb{M}$):

By David Eppstein

Wednesday, April 15 2026, 17:17

Reticulating Splines

from Ben Recht

The long legacy of simulation-based control.

This is a live blog of Lecture 9 of my graduate seminar “Feedback, Learning, and Adaptation.” A table of contents is here.

As I mentioned Monday, one of the big paradigms in modern robotics and control is the “sim2real” pipeline. People invest in complex computer simulators to test their robotic policies. The simulators have detailed dynamic and kinematic models of the robot and how it moves in contact with varied terrain and obstacles. The hope is that by burning through infinite GPU credits to troubleshoot every possibility in simulation, they can deploy code to their actual robot and need no troubleshooting once it’s unleashed in the real world.

While the young folks like to make this paradigm sound like a novel new research program, all of optimal control rests on the sim2real pipeline. Think about the core problem of optimal control: the linear quadratic regulator. This problem looks for a control sequence that minimizes a quadratic cost subject to the world evolving according to a linear dynamical system. Control theorists banged their heads against this problem for decades, and we are now taught the beautiful dynamic programming derivations that reduce this problem to solving a compact equation. However, we can also solve it using gradient descent. The gradient computation amounts to simulating the system with the current control policy, computing the sensitivity of the cost trajectory to each control decision, and then adding this information up to compute the gradient.

The lovely thing about gradient descent is that it gives you a solution technique for general optimal control problems with nonquadratic costs or nonlinear dynamics. You evaluate your policy under the current control, run a dynamical system backward in time to compute how sensitive the trajectory was to your control decisions, and then add up the contributions of each time point to get the full gradient. Arthur Bryson invented this method to compute gradients of general optimal control problems in 1962. Today, we call his algorithm backpropagation. This simulation-based gradient method provides incremental improvement of policies for any differentiable dynamical model and any differentiable cost function.

Now, if your simulation isn’t differentiable, maybe you’ll use a different sort of policy optimization method to solve your optimal control problem. However, reinforcement learning for robotics is still optimal control. RL for robotics minimizes a designed cost function subject to dynamics. The modern departure is that no one bothers to write down the equations of motion anymore. They just assume the simulator will compute them.

This belief pushes a lot of work onto the simulator. GPU cycles are sadly neither free nor abundant. It would be nice to minimize the simulation time and cost required to find a good control policy. It would be particularly nice because many people would like to have a simulator on board the actual robot to compute policies with methods like model predictive control. This begs the question of how accurate your simulation needs to be.

Unfortunately, no one knows. We all think that if you can act quickly enough with enough control authority, then a really simple model should work. But it’s impossible to quantify “enough” in that sentence. You have to try things out because dynamical processes are always surprising.

While it feels like increasing the fidelity of a simulator to the minute details of physical law always improves performance, this is not remotely the case. In class on Monday, Spencer Schutz presented a paper on autonomous driving showing a simple, inaccurate kinematic model with a low sampling rate performed just as well as a more accurate dynamic model. Anyone who’s spent time with dynamic models knows that very high-dimensional complex systems often look simple when you have limited controllability and observability. This is the basis of thermodynamics, where infinitely many bodies colliding collectively produce fairly boring dissipative behavior. Many complex-looking circuits have the input-output behavior of resistors.

On the other side of the coin, safe execution demands identification of subtle aspects of input-output relationships. You can have two dynamical systems with nearly identical behavior perform completely differently once in a closed loop circuit. You can also have systems with completely different behavior look the same in closed loop. I worked through a few examples of this phenomenon in a blog post a couple of years ago. Your model needs to be perfect in exactly the right places. But it’s usually impossible to know those places in advance.

To make matters worse, you can’t really identify the parameters of a robot in open loop. An expensive robot is always going to be running with its low-level controllers on both for its safety and yours. The actual parameters of closed-loop systems can’t be identified.1 So you’re stuck with guesses in your simulator, and you have to hope that your plausible parameters are good enough for your sim2real application.

The most popular solution to this identification problem is domain adaptation. Since you can only find a range of parameters that describe reality, you build a control policy that works for randomly sampled parameters. By constantly sampling different parameters in each run, you build a policy that performs well on average across all possible parameters.

Finding controllers that work for the average model isn’t new. Indeed, this is just a variant of optimal control called dual control, which has seen bursts of interest since the 1960s. Dual control is literally the problem of minimizing an expected control performance over a distribution of parameters. Like dual control, domain adaptation needs a good prior model for how the environment “samples” parameters. But you can also just YOLO and hope that as long as you include all the edge cases, you’ll never crash. That’s the machine learning mindset, after all.

But what does it mean to sample the coefficient of friction of a surface? What’s the right distribution of coefficients of friction? This is again a tricky question.

One approach to modeling the distribution of parameters is to add an element of adversarial behavior to the system. We can adapt the simulations to find hard parameter settings and train more on those. We can have the simulator learn to trip up the robot. Rather than minimizing expected cost, we are working to minimize a worst-case cost, where the supremum is over a distribution of parameters or disturbances. The dual control people were really into this sort of minimax robustness in the 60s. But practice in aerospace applications ultimately pushed the community to robust control.

But people hate robust control because it gives them conservative policies. Computer scientists love to hack and ship. Look how productive they’ve been! You only need to write a few tests and make sure your simulator passes those. No bugs detected, LGTM! What could go wrong, right?

Is that last paragraph about coding agents? It might be.

But regardless, robust control pointed out that unmodeled uncertainties are everywhere, and they can be out there to bite you if you’re not careful. For its entire history, robust control advocates have been haranguing people about the limits of simulators. They note a couple of significant problems: first, training on a simulator often means fitting to quirks of the simulator that don’t appear in the real world. This is a major danger, even in linear systems. Second, many apparent parametric robustness properties of optimal controllers break down under scrutiny.

In class, I introduced the structured singular value to motivate this issue. The structured singular value showed that when you had a system with many inputs and outputs, and you only considered independent perturbations, you’d convince yourself that a system was stable when it was not remotely stable. Guaranteeing stable behavior required understanding the dependencies between different errors. But how you test stability in simulation is not clear.

We are thus left considering a strategy beyond sim2real: sim2real2sim2real. Or sim2real2sim2real2sim2real. You deploy the system and find out what didn’t work in reality. And then you go back to your simulator, add a few thousand lines of code to account for the mistake, and try again. The software state of mind is that we can always patch mistakes. You can have an all-hands, blameless post-mortem and say it won’t happen again. This drives the old control theorists mad, but it’s been great working so far, so why change course?

Subscribe now

1

In case you haven’t encountered this before, suppose you are trying to model a closed-loop system x[t+1] = Ax[t]+ Bu[t], u[t]= Kx[t]. Then for an arbitrary matrix E_B,

A+BK = (A -E_BK)+(B+E_B) K

Hence, you can only identify a subspace of possible dynamical systems describing your data.

By Ben Recht

Wednesday, April 15 2026, 14:12

PhD student at University of Salzburg (apply by May 6, 2026)

from CCI: jobs

The University of Salzburg is currently seeking a Predoctoral University Assistant (“PhD student”) in the Big Data Algorithms Group headed by Sebastian Forster. The goal is to develop graph algorithms for solving clustering, distance, flow, or cut problems that are as well-suited as possible to dynamic, parallel, or distributed computing models. Please consult the linked […]

The University of Salzburg is currently seeking a Predoctoral University Assistant (“PhD student”) in the Big Data Algorithms Group headed by Sebastian Forster. The goal is to develop graph algorithms for solving clustering, distance, flow, or cut problems that are as well-suited as possible to dynamic, parallel, or distributed computing models. Please consult the linked website for details.

Website: https://karriere.plus.ac.at/en/jobs/6e6aa798-0429-01e8-cabb-69c12151a2bd
Email: forster@cs.sbg.ac.at

By shacharlovett

Wednesday, April 15 2026, 09:24

A complexity phase transition at the EPR Hamiltonian

Authors: Kunal Marwaha, James Sud

We study the computational complexity of 2-local Hamiltonian problems generated by a positive-weight symmetric interaction term, encompassing many canonical problems in statistical mechanics and optimization. We show these problems belong to one of three complexity phases: QMA-complete, StoqMA-complete, and reducible to a new problem we call EPR*. The phases are physically interpretable, corresponding to the energy level ordering of the local term. The EPR* problem is a simple generalization of the EPR problem of King. Inspired by empirically efficient algorithms for EPR, we conjecture that EPR* is in BPP. If true, this would complete the complexity classification of these problems, and imply EPR* is the transition point between easy and hard local Hamiltonians. Our proofs rely on perturbative gadgets. One simple gadget, when recursed, induces a renormalization-group-like flow on the space of local interaction terms. This gives the correct complexity picture, but does not run in polynomial time. To overcome this, we design a gadget based on a large spin chain, which we analyze via the Jordan-Wigner transformation.

Authors: Kunal Marwaha, James Sud

We study the computational complexity of 2-local Hamiltonian problems generated by a positive-weight symmetric interaction term, encompassing many canonical problems in statistical mechanics and optimization. We show these problems belong to one of three complexity phases: QMA-complete, StoqMA-complete, and reducible to a new problem we call EPR*. The phases are physically interpretable, corresponding to the energy level ordering of the local term. The EPR* problem is a simple generalization of the EPR problem of King. Inspired by empirically efficient algorithms for EPR, we conjecture that EPR* is in BPP. If true, this would complete the complexity classification of these problems, and imply EPR* is the transition point between easy and hard local Hamiltonians. Our proofs rely on perturbative gadgets. One simple gadget, when recursed, induces a renormalization-group-like flow on the space of local interaction terms. This gives the correct complexity picture, but does not run in polynomial time. To overcome this, we design a gadget based on a large spin chain, which we analyze via the Jordan-Wigner transformation.

Wednesday, April 15 2026, 00:00

Symmetric subrank and its border analogue

Authors: Benjamin Biaggi, Jan Draisma, Koen de Nooij, Immanuel van Santen

The symmetric subrank of homogeneous polynomial is the largest number of terms in a diagonal form to which it can be specialized by a (typically non-invertible) linear variable substitution. Building on earlier work by Derksen-Makam-Zuiddam and Biaggi-Chang-Draisma-Rupniewski for ordinary tensors, we determine the asymptotic behavior of symmetric subrank and symmetric border subrank of degree-d forms as the number of variables tends to infinity. Furthermore, by using results from geometric invariant theory we show that for cubic (resp. quartic) forms the symmetric subrank and symmetric border subrank coincide if the latter is at most three (resp. two).

Authors: Benjamin Biaggi, Jan Draisma, Koen de Nooij, Immanuel van Santen

The symmetric subrank of homogeneous polynomial is the largest number of terms in a diagonal form to which it can be specialized by a (typically non-invertible) linear variable substitution. Building on earlier work by Derksen-Makam-Zuiddam and Biaggi-Chang-Draisma-Rupniewski for ordinary tensors, we determine the asymptotic behavior of symmetric subrank and symmetric border subrank of degree-d forms as the number of variables tends to infinity. Furthermore, by using results from geometric invariant theory we show that for cubic (resp. quartic) forms the symmetric subrank and symmetric border subrank coincide if the latter is at most three (resp. two).

Wednesday, April 15 2026, 00:00

From Witness-Space Sharpness To Family-Pointwise Exactness For The Solvability Complexity Index

Authors: Christopher Sorg

We study how exact Solvability Complexity Index (SCI) statements should be formulated for families of computational problems rather than for single problems. While the equality $\operatorname{SCI}_G (\mathcal P)=k$ is unambiguous for an individual computational problem $\mathcal P$, the family setting requires one to distinguish family-pointwise exactness, witness-space sharpness, and worst-case exactness. We formalize this trichotomy, prove that witness-space sharpness coincides with worst-case exactness but is, in general, strictly weaker than family-pointwise exactness, and show that certain Koopman-operator classification results are sharp only in this worst-case sense. We then establish two positive upgrade theorems: an abstract pullback principle and a concrete finite-query criterion guaranteeing that witness-space sharpness upgrades to family-pointwise exactness. Next, we introduce a decoder-regular finite-query transport preorder on SCI computational problems, prove that it is a preorder, derive a transport-saturation sufficient criterion extending the principal-source package, and show that the associated transport degrees need not form a lattice in full generality. We analyze the natural decoder classes $\mathscr R_{\mathrm{cont}}$ and $\mathscr R_{\mathrm{Bor}}$: on the full class the corresponding quotients are not upper semilattices, while on the nondegenerate subclass the preorder is upward and downward directed. Finally, we exhibit two natural positive families realizing the principal transport mechanism: exact integration on compact intervals and a fixed-window spectral decision family obtained by block-diagonal stabilization.

Authors: Christopher Sorg

We study how exact Solvability Complexity Index (SCI) statements should be formulated for families of computational problems rather than for single problems. While the equality $\operatorname{SCI}_G (\mathcal P)=k$ is unambiguous for an individual computational problem $\mathcal P$, the family setting requires one to distinguish family-pointwise exactness, witness-space sharpness, and worst-case exactness. We formalize this trichotomy, prove that witness-space sharpness coincides with worst-case exactness but is, in general, strictly weaker than family-pointwise exactness, and show that certain Koopman-operator classification results are sharp only in this worst-case sense. We then establish two positive upgrade theorems: an abstract pullback principle and a concrete finite-query criterion guaranteeing that witness-space sharpness upgrades to family-pointwise exactness. Next, we introduce a decoder-regular finite-query transport preorder on SCI computational problems, prove that it is a preorder, derive a transport-saturation sufficient criterion extending the principal-source package, and show that the associated transport degrees need not form a lattice in full generality. We analyze the natural decoder classes $\mathscr R_{\mathrm{cont}}$ and $\mathscr R_{\mathrm{Bor}}$: on the full class the corresponding quotients are not upper semilattices, while on the nondegenerate subclass the preorder is upward and downward directed. Finally, we exhibit two natural positive families realizing the principal transport mechanism: exact integration on compact intervals and a fixed-window spectral decision family obtained by block-diagonal stabilization.

Wednesday, April 15 2026, 00:00

A Relativizing MIP for BQP

Authors: Scott Aaronson, Anand Natarajan, Avishay Tal, Agi Villanyi

Complexity class containments involving interactive proof classes are famously nonrelativizing: although $\mathsf{IP} = \mathsf{PSPACE}$, Fortnow and Sipser showed that that there exists an oracle relative to which $\mathsf{coNP} \not\subseteq \mathsf{IP}$. In contrast, the question of whether the containment $\mathsf{BQP} \subseteq \mathsf{IP}$ is relativizing remains wide open. In this work we make progress towards resolving this question by showing that the containment $\mathsf{BQP} \subseteq \mathsf{MIP}$ holds with respect to any classical oracle. We obtain this result by constructing, for any classical oracle $O$, a $\mathsf{PCP}$ proof system for $\mathsf{BQP}^{O}$ where the verifier makes polynomially many classical queries to an exponentially-long proof, and to the oracle $O$. Our construction is inspired by the state synthesis algorithm of Grover and Rudolph, and serves as a complement to the "exponential PCP" constructed by Aharonov, Arad, and Vidick, which achieves similar parameters but which is based on different ideas and does not relativize. We propose relativization as a proxy for prover efficiency, and hope that progress towards an $\mathsf{IP}$ for $\mathsf{BQP}$ in the oracle world will lead to a non-cryptographic interactive protocol for proving any quantum computation to a classical skeptic in the unrelativized world, which is a longstanding open problem in quantum complexity theory.

Authors: Scott Aaronson, Anand Natarajan, Avishay Tal, Agi Villanyi

Complexity class containments involving interactive proof classes are famously nonrelativizing: although $\mathsf{IP} = \mathsf{PSPACE}$, Fortnow and Sipser showed that that there exists an oracle relative to which $\mathsf{coNP} \not\subseteq \mathsf{IP}$. In contrast, the question of whether the containment $\mathsf{BQP} \subseteq \mathsf{IP}$ is relativizing remains wide open. In this work we make progress towards resolving this question by showing that the containment $\mathsf{BQP} \subseteq \mathsf{MIP}$ holds with respect to any classical oracle. We obtain this result by constructing, for any classical oracle $O$, a $\mathsf{PCP}$ proof system for $\mathsf{BQP}^{O}$ where the verifier makes polynomially many classical queries to an exponentially-long proof, and to the oracle $O$. Our construction is inspired by the state synthesis algorithm of Grover and Rudolph, and serves as a complement to the "exponential PCP" constructed by Aharonov, Arad, and Vidick, which achieves similar parameters but which is based on different ideas and does not relativize. We propose relativization as a proxy for prover efficiency, and hope that progress towards an $\mathsf{IP}$ for $\mathsf{BQP}$ in the oracle world will lead to a non-cryptographic interactive protocol for proving any quantum computation to a classical skeptic in the unrelativized world, which is a longstanding open problem in quantum complexity theory.

Wednesday, April 15 2026, 00:00

Topology Understanding of B-Spline Surface/Surface Intersection with Mapper

Authors: Chenming Gao, Hongwei Lin, Gengchen Li

In the realm of computer-aided design (CAD) software, the intersection of B-spline surfaces stands as a fundamental operation. Despite the extensive history of surface intersection algorithms, the challenge of handling complex intersection topologies persists. While subdivision algorithms have demonstrated strong robustness in computing surface/surface intersection and are capable of addressing singular cases, determining the topology of the intersection obtained through these methods is a key factor for calculating correct intersection, and remains a difficult issue. To address this challenge, we propose a Mapper-based method for determining the topology of the intersection between two B-spline surfaces. Our algorithm is designed to efficiently handle various common and complex intersection topologies. Experimental results verify the robustness and topological correctness of this method.

Authors: Chenming Gao, Hongwei Lin, Gengchen Li

In the realm of computer-aided design (CAD) software, the intersection of B-spline surfaces stands as a fundamental operation. Despite the extensive history of surface intersection algorithms, the challenge of handling complex intersection topologies persists. While subdivision algorithms have demonstrated strong robustness in computing surface/surface intersection and are capable of addressing singular cases, determining the topology of the intersection obtained through these methods is a key factor for calculating correct intersection, and remains a difficult issue. To address this challenge, we propose a Mapper-based method for determining the topology of the intersection between two B-spline surfaces. Our algorithm is designed to efficiently handle various common and complex intersection topologies. Experimental results verify the robustness and topological correctness of this method.

Wednesday, April 15 2026, 00:00

The Parameterized Complexity of Vertex-Coloring Edge-Weighting

Authors: Shubhada Aute, Fahad Panolan, Geevarghese Philip

Motivated by the landmark resolution of the 1-2-3 Conjecture, we initiate the study of the parameterized complexity of the Vertex-Coloring {0,1}-Edge-Weighting problem and its generalization, Vertex-Coloring Pre-edge-Weighting, under various structural parameters. The base problem, Vertex-Coloring {0,1}-Edge-Weighting, asks whether we can assign a weight from {0,1} to each edge of a graph. The goal is to ensure that for every pair of adjacent vertices, the sums of their incident edge weights are distinct. In the Vertex-Coloring Pre-edge-Weighting variant, we are given a graph where a subset of edges is already assigned fixed weights from {0,1}. The goal is to determine if this partial weighting can be extended to all remaining edges such that the final, complete assignment satisfies the proper vertex coloring property. While the existence of such weightings is well-understood for specific graph classes, their algorithmic complexity under structural parameterization has remained unexplored. We prove both hardness and tractability for the problem, across a hierarchy of structural parameters. We show that both the base problem and the Pre-edge-Weighting variant are W[1]-hard when parameterized by the size of a feedback vertex set of the input graph. On the positive side, we establish that the base problem and a restricted Pre-edge-Weighting variant where the pre-assigned weights are all 1, become FPT when parameterized by the size of a vertex cover of the input graph. Further, we show that both the base problem and the Pre-edge-Weighting variant have XP algorithms when parameterized by the treewidth of the input graph.

Authors: Shubhada Aute, Fahad Panolan, Geevarghese Philip

Motivated by the landmark resolution of the 1-2-3 Conjecture, we initiate the study of the parameterized complexity of the Vertex-Coloring {0,1}-Edge-Weighting problem and its generalization, Vertex-Coloring Pre-edge-Weighting, under various structural parameters. The base problem, Vertex-Coloring {0,1}-Edge-Weighting, asks whether we can assign a weight from {0,1} to each edge of a graph. The goal is to ensure that for every pair of adjacent vertices, the sums of their incident edge weights are distinct. In the Vertex-Coloring Pre-edge-Weighting variant, we are given a graph where a subset of edges is already assigned fixed weights from {0,1}. The goal is to determine if this partial weighting can be extended to all remaining edges such that the final, complete assignment satisfies the proper vertex coloring property. While the existence of such weightings is well-understood for specific graph classes, their algorithmic complexity under structural parameterization has remained unexplored. We prove both hardness and tractability for the problem, across a hierarchy of structural parameters. We show that both the base problem and the Pre-edge-Weighting variant are W[1]-hard when parameterized by the size of a feedback vertex set of the input graph. On the positive side, we establish that the base problem and a restricted Pre-edge-Weighting variant where the pre-assigned weights are all 1, become FPT when parameterized by the size of a vertex cover of the input graph. Further, we show that both the base problem and the Pre-edge-Weighting variant have XP algorithms when parameterized by the treewidth of the input graph.

Wednesday, April 15 2026, 00:00

Dequantizing Short-Path Quantum Algorithms

Authors: François Le Gall, Suguru Tamaki

The short-path quantum algorithm introduced by Hastings (Quantum 2018, 2019) is a variant of adiabatic quantum algorithms that enables an easier worst-case analysis by avoiding the need to control the spectral gap along a long adiabatic path. Dalzell, Pancotti, Campbell, and Brandão (STOC 2023) recently revisited this framework and obtained a clear analysis of the complexity of the short-path algorithm for several classes of constraint satisfaction problems (MAX-$k$-CSPs), leading to quantum algorithms with complexity $2^{(1-c)n/2}$ for some constant $c>0$. This suggested a super-quadratic quantum advantage over classical algorithms. In this work, we identify an explicit classical mechanism underlying a substantial part of this line of work, and show that it leads to clean dequantizations. As a consequence, we obtain classical algorithms that run in time $2^{(1-c')n}$, for some constant $c'>c$, for the same classes of constraint satisfaction problems. This shows that current short-path quantum algorithms for these problems do not achieve a super-quadratic advantage. On the positive side, our results provide a new ``quantum-inspired'' approach to designing classical algorithms for important classes of constraint satisfaction problems.

Authors: François Le Gall, Suguru Tamaki

The short-path quantum algorithm introduced by Hastings (Quantum 2018, 2019) is a variant of adiabatic quantum algorithms that enables an easier worst-case analysis by avoiding the need to control the spectral gap along a long adiabatic path. Dalzell, Pancotti, Campbell, and Brandão (STOC 2023) recently revisited this framework and obtained a clear analysis of the complexity of the short-path algorithm for several classes of constraint satisfaction problems (MAX-$k$-CSPs), leading to quantum algorithms with complexity $2^{(1-c)n/2}$ for some constant $c>0$. This suggested a super-quadratic quantum advantage over classical algorithms. In this work, we identify an explicit classical mechanism underlying a substantial part of this line of work, and show that it leads to clean dequantizations. As a consequence, we obtain classical algorithms that run in time $2^{(1-c')n}$, for some constant $c'>c$, for the same classes of constraint satisfaction problems. This shows that current short-path quantum algorithms for these problems do not achieve a super-quadratic advantage. On the positive side, our results provide a new ``quantum-inspired'' approach to designing classical algorithms for important classes of constraint satisfaction problems.

Wednesday, April 15 2026, 00:00

Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs

Authors: Bence Deák, Péter Madarasi

The family of $(k,\ell)$-sparse graphs, introduced by Lorea, plays a central role in combinatorial optimization and has a wide range of applications, particularly in rigidity theory. A key algorithmic problem is to decide whether a given graph is $(k,\ell)$-sparse and, if not, to produce a vertex set certifying the failure of sparsity. While pebble game algorithms have long yielded $O(n^2)$-time recognition throughout the classical range $0 \leq \ell < 2k$, and $O(n^3)$-time algorithms in the extended range $2k \leq \ell < 3k$, substantially faster bounds were previously known only in a few special cases. We present new recognition algorithms for the parameter ranges $0 \le \ell \le k$, $k < \ell < 2k$, and $2k \leq \ell < 3k$. Our approach combines bounded-indegree orientations, reductions to rooted arc-connectivity, augmenting-path techniques, and a divide-and-conquer method based on centroid decomposition. This yields the first subquadratic, and in fact near-linear-time, recognition algorithms throughout the classical range when instantiated with the fastest currently available subroutines. Under purely combinatorial implementations, the running times become $O(n\sqrt n)$ for $0 \leq \ell \leq k$ and $O(n\sqrt{n\log n})$ for $k< \ell <2k$. For $2k \leq \ell < 3k$, we obtain an $O(n^2)$-time algorithm when $\ell \leq 2k+1$ and an $O(n^2\log n)$-time algorithm otherwise. In each case, the algorithm can also return an explicit violating set certifying that the input graph is not $(k,\ell)$-sparse.

Authors: Bence Deák, Péter Madarasi

The family of $(k,\ell)$-sparse graphs, introduced by Lorea, plays a central role in combinatorial optimization and has a wide range of applications, particularly in rigidity theory. A key algorithmic problem is to decide whether a given graph is $(k,\ell)$-sparse and, if not, to produce a vertex set certifying the failure of sparsity. While pebble game algorithms have long yielded $O(n^2)$-time recognition throughout the classical range $0 \leq \ell < 2k$, and $O(n^3)$-time algorithms in the extended range $2k \leq \ell < 3k$, substantially faster bounds were previously known only in a few special cases. We present new recognition algorithms for the parameter ranges $0 \le \ell \le k$, $k < \ell < 2k$, and $2k \leq \ell < 3k$. Our approach combines bounded-indegree orientations, reductions to rooted arc-connectivity, augmenting-path techniques, and a divide-and-conquer method based on centroid decomposition. This yields the first subquadratic, and in fact near-linear-time, recognition algorithms throughout the classical range when instantiated with the fastest currently available subroutines. Under purely combinatorial implementations, the running times become $O(n\sqrt n)$ for $0 \leq \ell \leq k$ and $O(n\sqrt{n\log n})$ for $k< \ell <2k$. For $2k \leq \ell < 3k$, we obtain an $O(n^2)$-time algorithm when $\ell \leq 2k+1$ and an $O(n^2\log n)$-time algorithm otherwise. In each case, the algorithm can also return an explicit violating set certifying that the input graph is not $(k,\ell)$-sparse.

Wednesday, April 15 2026, 00:00

Efficiency of Proportional Mechanisms in Online Auto-Bidding Advertising

Authors: Nguyen Kim Thang

The rise of automated bidding strategies in online advertising presents new challenges in designing and analyzing efficient auction mechanisms. In this paper, we focus on proportional mechanisms within the context of auto-bidding and study the efficiency of pure Nash equilibria, specifically the price of anarchy (PoA), under the liquid welfare objective. We first establish a tight PoA bound of 2 for the standard proportional mechanism. Next, we introduce a modified version with an alternative payment scheme that achieves a PoA bound of $1 + \frac{O(1)}{n-1}$ where $n \geq 2$ denotes the number of bidding agents. This improvement surpasses the existing PoA barrier of 2 and approaches full efficiency as the number of agents increases. Our methodology leverages duality and the Karush-Kuhn-Tucker (KKT) conditions from linear and convex programming. Despite its conceptual simplicity, our approach proves powerful and may offer broader applications for establishing PoA bounds.

Authors: Nguyen Kim Thang

The rise of automated bidding strategies in online advertising presents new challenges in designing and analyzing efficient auction mechanisms. In this paper, we focus on proportional mechanisms within the context of auto-bidding and study the efficiency of pure Nash equilibria, specifically the price of anarchy (PoA), under the liquid welfare objective. We first establish a tight PoA bound of 2 for the standard proportional mechanism. Next, we introduce a modified version with an alternative payment scheme that achieves a PoA bound of $1 + \frac{O(1)}{n-1}$ where $n \geq 2$ denotes the number of bidding agents. This improvement surpasses the existing PoA barrier of 2 and approaches full efficiency as the number of agents increases. Our methodology leverages duality and the Karush-Kuhn-Tucker (KKT) conditions from linear and convex programming. Despite its conceptual simplicity, our approach proves powerful and may offer broader applications for establishing PoA bounds.

Wednesday, April 15 2026, 00:00

Longest Common Extension of a Dynamic String in Parallel Constant Time

Authors: Daniel Albert

A longest common extension (LCE) query on a string computes the length of the longest common suffix or prefix at two given positions. A dynamic LCE algorithm maintains a data structure that allows efficient LCE queries on a string that can change via character insertions and deletions. A dynamic parallel constant-time algorithm is presented that can maintain LCE queries on a common CRCW PRAM with $\mathcal{O}(n^ε)$ work, for any $ε> 0$. The algorithm maintains a string synchronizing sets hierarchy, which it uses to answer substring equality queries, which it in turn uses to answer LCE queries. To achieve constant runtime, the algorithm allows parts of its information to become outdated by up to $\log n \log^* n$ updates. It answers queries by combining this slightly outdated information with a list of the recent changes. Two applications of this dynamic LCE algorithm are shown. Firstly, a dynamic parallel constant-time algorithm can maintain membership in a Dyck language $D_k, k > 0$ with $\mathcal{O}(n^ε)$ work for any $ε> 0$. Secondly, a dynamic parallel constant-time algorithm can maintain squares with $\mathcal{O}(n^ε)$ work for any $ε> 0$.

Authors: Daniel Albert

A longest common extension (LCE) query on a string computes the length of the longest common suffix or prefix at two given positions. A dynamic LCE algorithm maintains a data structure that allows efficient LCE queries on a string that can change via character insertions and deletions. A dynamic parallel constant-time algorithm is presented that can maintain LCE queries on a common CRCW PRAM with $\mathcal{O}(n^ε)$ work, for any $ε> 0$. The algorithm maintains a string synchronizing sets hierarchy, which it uses to answer substring equality queries, which it in turn uses to answer LCE queries. To achieve constant runtime, the algorithm allows parts of its information to become outdated by up to $\log n \log^* n$ updates. It answers queries by combining this slightly outdated information with a list of the recent changes. Two applications of this dynamic LCE algorithm are shown. Firstly, a dynamic parallel constant-time algorithm can maintain membership in a Dyck language $D_k, k > 0$ with $\mathcal{O}(n^ε)$ work for any $ε> 0$. Secondly, a dynamic parallel constant-time algorithm can maintain squares with $\mathcal{O}(n^ε)$ work for any $ε> 0$.

Wednesday, April 15 2026, 00:00

Sorting under Partial Information with Optimal Preprocessing Time via Unified Bound Heaps

Authors: Daniel Rutschmann

In 1972, Fredman proposes the problem of sorting under partial information: preprocess a directed acyclic graph $G$ with vertex set $X$ so that you can sort $X$ in $O(\log e(G))$ time, where $e(G)$ is the number of sorted orders compatible with $G$. Cardinal, Fiorini, Joret, Jungers and Munro [STOC'10] show that you can preprocess $G$ in $O(n^{2.5})$ time and then sort $X$ in $O(\log e(G) + n)$ time and $O(\log e(G))$ comparisons. Recent work of van der Hoog and Rutschmann [FOCS'24] implies an algorithm with $O(n^ω)$ preprocessing time where $ω< 2.372$ and $O(\log e(G))$ sorting time. Haeupler, Hladík, Iacono, Rozhoň, Tarjan and Tětek [SODA'25] achieve an overall running time of $O(\log e(G) + m)$. In this paper, we achieve tight bounds for this problem: $O(m)$ preprocessing time and $O(\log e(G))$ sorting time. As a key ingredient, we design a new fast heap data structure that might be of independent theoretical interest.

Authors: Daniel Rutschmann

In 1972, Fredman proposes the problem of sorting under partial information: preprocess a directed acyclic graph $G$ with vertex set $X$ so that you can sort $X$ in $O(\log e(G))$ time, where $e(G)$ is the number of sorted orders compatible with $G$. Cardinal, Fiorini, Joret, Jungers and Munro [STOC'10] show that you can preprocess $G$ in $O(n^{2.5})$ time and then sort $X$ in $O(\log e(G) + n)$ time and $O(\log e(G))$ comparisons. Recent work of van der Hoog and Rutschmann [FOCS'24] implies an algorithm with $O(n^ω)$ preprocessing time where $ω< 2.372$ and $O(\log e(G))$ sorting time. Haeupler, Hladík, Iacono, Rozhoň, Tarjan and Tětek [SODA'25] achieve an overall running time of $O(\log e(G) + m)$. In this paper, we achieve tight bounds for this problem: $O(m)$ preprocessing time and $O(\log e(G))$ sorting time. As a key ingredient, we design a new fast heap data structure that might be of independent theoretical interest.

Wednesday, April 15 2026, 00:00

Robust Graph Isomorphism, Quadratic Assignment and VC Dimension

Authors: Anatole Dahan, Martin Grohe, Daniel Neuen, Tomáš Novotný

We present an additive $\varepsilon n^{2}$-approximation algorithm for the Graph Edit Distance problem (GED) on graphs of VC dimension $d$ running in time $n^{O(d/\varepsilon^{2})}$. In particular, this recovers a previous result by Arora, Frieze, and Kaplan [Math. Program. 2002] who gave an $\varepsilon n^{2}$-approximation running in time $n^{O(\log n/\varepsilon^{2})}$. Similar to the work of Arora et al., we extend our results to arbitrary Quadratic Assignment problems (QAPs) by introducing a notion of VC dimension for QAP instances, and giving an $\varepsilon n^{2}$-approximation for QAPs with bounded weights running in time $n^{O(\varepsilon^{-2}(d + \log\varepsilon^{-1}))}$. As a particularly interesting special case, we further study the problem $\varepsilon$-$\mathsf{GI}$, which entails determining if two graphs $G,H$ over $n$ vertices are isomorphic, when promised that if they are not, their graph edit distance is at least $\varepsilon n^{2}$. We show that the standard Weisfeiler--Leman algorithm of dimension $O(\varepsilon^{-1}d\log(\varepsilon^{-1}))$ solves this problem on graphs of VC dimension $d$. We also show that dimension $O(\varepsilon^{-1}\log n)$ suffices on arbitrary $n$-vertex graphs, while $k$-WL fails on instances at distance $Ω(n^{2}/k)$.

Authors: Anatole Dahan, Martin Grohe, Daniel Neuen, Tomáš Novotný

We present an additive $\varepsilon n^{2}$-approximation algorithm for the Graph Edit Distance problem (GED) on graphs of VC dimension $d$ running in time $n^{O(d/\varepsilon^{2})}$. In particular, this recovers a previous result by Arora, Frieze, and Kaplan [Math. Program. 2002] who gave an $\varepsilon n^{2}$-approximation running in time $n^{O(\log n/\varepsilon^{2})}$. Similar to the work of Arora et al., we extend our results to arbitrary Quadratic Assignment problems (QAPs) by introducing a notion of VC dimension for QAP instances, and giving an $\varepsilon n^{2}$-approximation for QAPs with bounded weights running in time $n^{O(\varepsilon^{-2}(d + \log\varepsilon^{-1}))}$. As a particularly interesting special case, we further study the problem $\varepsilon$-$\mathsf{GI}$, which entails determining if two graphs $G,H$ over $n$ vertices are isomorphic, when promised that if they are not, their graph edit distance is at least $\varepsilon n^{2}$. We show that the standard Weisfeiler--Leman algorithm of dimension $O(\varepsilon^{-1}d\log(\varepsilon^{-1}))$ solves this problem on graphs of VC dimension $d$. We also show that dimension $O(\varepsilon^{-1}\log n)$ suffices on arbitrary $n$-vertex graphs, while $k$-WL fails on instances at distance $Ω(n^{2}/k)$.

Wednesday, April 15 2026, 00:00

Submodular Max-Min Allocation under Identical Valuations

Authors: Kimon Boehmer

In the problem of Submodular Max-Min Allocation, we are given a set of items, a set of players, and monotone submodular valuation functions that represent the satisfaction of a player with a certain subset of items. The goal is to find an allocation of the items to the players that maximizes the lowest satisfaction among all players. We study this problem in the special case where all players have the same valuation function. We devise a greedy algorithm which gives a $0.4$-approximation, improving the previously best factor of $\frac{10}{27} \approx 0.37$ by Uziahu and Feige. Furthermore, we study the integrality gap of the \emph{configuration LP} when players have identical valuations. By constructing a variable assignment to the dual from a primal integral solution, we give the first constant upper bound on the integrality gap for submodular valuations. Generalizing the result to the case where players' allocations must be independent in $k$ given matroids, we derive a $\mathcal{O}(k)$-estimation algorithm for max-min allocation subject to $k$ matroid constraints under identical valuations.

Authors: Kimon Boehmer

In the problem of Submodular Max-Min Allocation, we are given a set of items, a set of players, and monotone submodular valuation functions that represent the satisfaction of a player with a certain subset of items. The goal is to find an allocation of the items to the players that maximizes the lowest satisfaction among all players. We study this problem in the special case where all players have the same valuation function. We devise a greedy algorithm which gives a $0.4$-approximation, improving the previously best factor of $\frac{10}{27} \approx 0.37$ by Uziahu and Feige. Furthermore, we study the integrality gap of the \emph{configuration LP} when players have identical valuations. By constructing a variable assignment to the dual from a primal integral solution, we give the first constant upper bound on the integrality gap for submodular valuations. Generalizing the result to the case where players' allocations must be independent in $k$ given matroids, we derive a $\mathcal{O}(k)$-estimation algorithm for max-min allocation subject to $k$ matroid constraints under identical valuations.

Wednesday, April 15 2026, 00:00

Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs

Authors: Gregory Morse, Tamás Kozsik

We study the problem of maintaining a breadth-first spanning tree and the induced BFS ordering in a directed graph under edge updates. While semi-dynamic algorithms are known, maintaining the spanning tree, level information, and numbering together in the fully dynamic setting is less developed. This preprint presents a framework for fully dynamic BFS in directed graphs together with supporting data structures for maintaining the BFS tree, single-source shortest paths, and single-source reachability under both insertions and deletions.

Authors: Gregory Morse, Tamás Kozsik

We study the problem of maintaining a breadth-first spanning tree and the induced BFS ordering in a directed graph under edge updates. While semi-dynamic algorithms are known, maintaining the spanning tree, level information, and numbering together in the fully dynamic setting is less developed. This preprint presents a framework for fully dynamic BFS in directed graphs together with supporting data structures for maintaining the BFS tree, single-source shortest paths, and single-source reachability under both insertions and deletions.

Wednesday, April 15 2026, 00:00

A Residual-Shell-Based Lower Bound for Ollivier-Ricci Curvature

Authors: Xiang Gu, Huichun Zhang, Jian Sun

Ollivier-Ricci curvature (ORC), defined via the Wasserstein distance that captures rich geometric information, has received growing attention in both theory and applications. However, the high computational cost of Wasserstein distance evaluation has significantly limited the broader practical use of ORC. To alleviate this issue, previous work introduced a computationally efficient lower bound as a proxy for ORC based on 1-hop random walks, but this approach empirically exhibits large gaps from the exact ORC. In this paper, we establish a substantially tighter lower bound for ORC than the existing lower bound, while retaining much lower computational cost than exact ORC computation, with practical speedups of tens of times. Moreover, our bound is not restricted to 1-hop random walks, but also applies to k-hop random walks (k > 1). Experiments on several fundamental graph structures demonstrate the effectiveness of our bound in terms of both approximation accuracy and computational efficiency.

Authors: Xiang Gu, Huichun Zhang, Jian Sun

Ollivier-Ricci curvature (ORC), defined via the Wasserstein distance that captures rich geometric information, has received growing attention in both theory and applications. However, the high computational cost of Wasserstein distance evaluation has significantly limited the broader practical use of ORC. To alleviate this issue, previous work introduced a computationally efficient lower bound as a proxy for ORC based on 1-hop random walks, but this approach empirically exhibits large gaps from the exact ORC. In this paper, we establish a substantially tighter lower bound for ORC than the existing lower bound, while retaining much lower computational cost than exact ORC computation, with practical speedups of tens of times. Moreover, our bound is not restricted to 1-hop random walks, but also applies to k-hop random walks (k > 1). Experiments on several fundamental graph structures demonstrate the effectiveness of our bound in terms of both approximation accuracy and computational efficiency.

Wednesday, April 15 2026, 00:00

Phylogenetic Inference under the Balanced Minimum Evolution Criterion via Semidefinite Programming

Authors: P. Skums

In this study, we investigate the application of Semidefinite Programming (SDP) to phylogenetics. SDP is a powerful optimization framework that seeks to optimize a linear objective function over the cone of positive semidefinite matrices. As a convex optimization problem, SDP generalizes linear programming and provides tight relaxations for many combinatorial optimization problems. However, despite its many applications, SDP remains largely unused in computational biology. We argue that SDP relaxations are particularly well suited for phylogenetic inference. As a proof of concept, we focus on the Balanced Minimum Evolution (BME) problem, a widely used model in distance-based phylogenetics. We propose an algorithm combining an SDP relaxation with a rounding scheme that iteratively converts relaxed solutions into valid tree topologies. Experiments on simulated and empirical datasets show that the method enables accurate phylogenetic reconstruction. The approach is sufficiently general to be extendable to other phylogenetic problems.

Authors: P. Skums

In this study, we investigate the application of Semidefinite Programming (SDP) to phylogenetics. SDP is a powerful optimization framework that seeks to optimize a linear objective function over the cone of positive semidefinite matrices. As a convex optimization problem, SDP generalizes linear programming and provides tight relaxations for many combinatorial optimization problems. However, despite its many applications, SDP remains largely unused in computational biology. We argue that SDP relaxations are particularly well suited for phylogenetic inference. As a proof of concept, we focus on the Balanced Minimum Evolution (BME) problem, a widely used model in distance-based phylogenetics. We propose an algorithm combining an SDP relaxation with a rounding scheme that iteratively converts relaxed solutions into valid tree topologies. Experiments on simulated and empirical datasets show that the method enables accurate phylogenetic reconstruction. The approach is sufficiently general to be extendable to other phylogenetic problems.

Wednesday, April 15 2026, 00:00

Constant-Factor Approximation for the Uniform Decision Tree

Authors: Michał Szyfelbein

We resolve a long-standing open question, about the existence of a constant-factor approximation algorithm for the average-case \textsc{Decision Tree} problem with uniform probability distribution over the hypotheses. We answer the question in the affirmative by providing a simple polynomial-time algorithm with approximation ratio of $\frac{2}{1-\sqrt{(e+1)/(2e)}}+ε<11.57$. This improves upon the currently best-known, greedy algorithm which achieves $O(\log n/{\log\log n})$-approximation. The first key ingredient in our analysis is the usage of a decomposition technique known from problems related to \textsc{Hierarchical Clustering} [SODA '17, WALCOM '26], which allows us to decompose the optimal decision tree into a series of objects called separating subfamilies. The second crucial idea is to reduce the subproblem of finding a \textsc{Separating Subfamily} to an instance of the \textsc{Maximum Coverage} problem. To do so, we analyze the properties of cutting cliques into small pieces, which represent pairs of hypotheses to be separated. This allows us to obtain a good approximation for the \textsc{Separating Subfamily} problem, which then enables the design of the approximation algorithm for the original problem.

Authors: Michał Szyfelbein

We resolve a long-standing open question, about the existence of a constant-factor approximation algorithm for the average-case \textsc{Decision Tree} problem with uniform probability distribution over the hypotheses. We answer the question in the affirmative by providing a simple polynomial-time algorithm with approximation ratio of $\frac{2}{1-\sqrt{(e+1)/(2e)}}+ε<11.57$. This improves upon the currently best-known, greedy algorithm which achieves $O(\log n/{\log\log n})$-approximation. The first key ingredient in our analysis is the usage of a decomposition technique known from problems related to \textsc{Hierarchical Clustering} [SODA '17, WALCOM '26], which allows us to decompose the optimal decision tree into a series of objects called separating subfamilies. The second crucial idea is to reduce the subproblem of finding a \textsc{Separating Subfamily} to an instance of the \textsc{Maximum Coverage} problem. To do so, we analyze the properties of cutting cliques into small pieces, which represent pairs of hypotheses to be separated. This allows us to obtain a good approximation for the \textsc{Separating Subfamily} problem, which then enables the design of the approximation algorithm for the original problem.

Wednesday, April 15 2026, 00:00

Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity

Authors: Vishesh Jain, Clayton Mizgerd, Eric Vigoda

Sampling graph colorings via local Markov chains is a central problem in approximate counting and Markov chain Monte Carlo (MCMC). We address the problem of sampling a random $k$-coloring of a graph with maximum degree $Δ$. The simplest algorithmic approach is to establish rapid mixing of the single-site update chain known as the Metropolis Glauber dynamics, which at each step chooses a random vertex $v$ and proposes a random color $c$, recoloring $v$ to $c$ if the resulting coloring remains proper. It is a long-standing open problem to prove that the Glauber dynamics has polynomial mixing time on all graphs whenever $k\geqΔ+2$. We prove that for every $δ>0$ and all $Δ\geq Δ_0(δ)$, if $k\ge (1+δ)Δ$ then the Glauber dynamics has optimal mixing time of $O_δ(|V| \log |V|)$ on any graph of girth $\geq 11$ and maximum degree $Δ$. Our approach builds on a non-Markovian coupling introduced by Hayes and Vigoda (2003) for the large-degree regime $Δ=Ω(\log n)$, in which updates at time $t$ may depend on and modify proposed updates at future times. A complete analysis of this framework requires resolving substantial technical obstacles that remain in the original argument, and extending it to the constant-degree regime introduces further difficulties, since non-Markovian updates may fail with constant probability. We overcome these obstacles by developing and analyzing a refined local non-Markovian coupling, and by establishing new local-uniformity results for the Metropolis dynamics, extending prior results for the heat-bath chain due to Hayes (2013). Together, these ingredients provide a complete analysis of the non-Markovian coupling framework in the large-degree regime, while simultaneously strengthening it substantially to obtain optimal mixing all the way down to the constant-degree setting.

Authors: Vishesh Jain, Clayton Mizgerd, Eric Vigoda

Sampling graph colorings via local Markov chains is a central problem in approximate counting and Markov chain Monte Carlo (MCMC). We address the problem of sampling a random $k$-coloring of a graph with maximum degree $Δ$. The simplest algorithmic approach is to establish rapid mixing of the single-site update chain known as the Metropolis Glauber dynamics, which at each step chooses a random vertex $v$ and proposes a random color $c$, recoloring $v$ to $c$ if the resulting coloring remains proper. It is a long-standing open problem to prove that the Glauber dynamics has polynomial mixing time on all graphs whenever $k\geqΔ+2$. We prove that for every $δ>0$ and all $Δ\geq Δ_0(δ)$, if $k\ge (1+δ)Δ$ then the Glauber dynamics has optimal mixing time of $O_δ(|V| \log |V|)$ on any graph of girth $\geq 11$ and maximum degree $Δ$. Our approach builds on a non-Markovian coupling introduced by Hayes and Vigoda (2003) for the large-degree regime $Δ=Ω(\log n)$, in which updates at time $t$ may depend on and modify proposed updates at future times. A complete analysis of this framework requires resolving substantial technical obstacles that remain in the original argument, and extending it to the constant-degree regime introduces further difficulties, since non-Markovian updates may fail with constant probability. We overcome these obstacles by developing and analyzing a refined local non-Markovian coupling, and by establishing new local-uniformity results for the Metropolis dynamics, extending prior results for the heat-bath chain due to Hayes (2013). Together, these ingredients provide a complete analysis of the non-Markovian coupling framework in the large-degree regime, while simultaneously strengthening it substantially to obtain optimal mixing all the way down to the constant-degree setting.

Wednesday, April 15 2026, 00:00

The Distributional Tail of Worst-Case Quickselect

Authors: Witold Płecha

We study the almost surely finite random variable $S$ defined by the distributional fixed-point equation \[ S \stackrel{d}{=} 1 + \max\{US', (1-U)S''\}, \qquad U \sim \mathrm{Unif}(0,1), \] where $S'$ and $S''$ are independent copies of $S$, independent of $U$. This random variable arises as the almost sure limit of the normalized worst-case number of key comparisons used by classical Quickselect with uniformly chosen pivots in the model of Devroye. Our first contribution concerns the right tail of $S$. We prove explicit one-sided bounds for the rate function $-\log \mathbb{P}(S>t)$ and, in particular, identify its first-order asymptotic growth: \[ -\log \mathbb{P}(S>t) = t \log t + O(t \log \log t), \qquad t \to \infty. \] The argument combines a binary-search-tree embedding and a one-level second-moment method with a moment-generating-function comparison inspired by ideas of Alsmeyer and Dyszewski for the nonhomogeneous smoothing transform. As a byproduct, we obtain an explicit pointwise Chernoff majorant for the tail. Our second contribution is a distribution-function scheme for deriving explicit upper bounds on $\mathbb{E}[S]$. Starting from the fixed-point equation at the level of the distribution function, we construct an order-preserving lower iteration and a conservative mesh discretization suited to computer-assisted upper bounds on the mean. We illustrate the latter numerically in floating-point arithmetic, but do not pursue a certified numerical proof here.

Authors: Witold Płecha

We study the almost surely finite random variable $S$ defined by the distributional fixed-point equation \[ S \stackrel{d}{=} 1 + \max\{US', (1-U)S''\}, \qquad U \sim \mathrm{Unif}(0,1), \] where $S'$ and $S''$ are independent copies of $S$, independent of $U$. This random variable arises as the almost sure limit of the normalized worst-case number of key comparisons used by classical Quickselect with uniformly chosen pivots in the model of Devroye. Our first contribution concerns the right tail of $S$. We prove explicit one-sided bounds for the rate function $-\log \mathbb{P}(S>t)$ and, in particular, identify its first-order asymptotic growth: \[ -\log \mathbb{P}(S>t) = t \log t + O(t \log \log t), \qquad t \to \infty. \] The argument combines a binary-search-tree embedding and a one-level second-moment method with a moment-generating-function comparison inspired by ideas of Alsmeyer and Dyszewski for the nonhomogeneous smoothing transform. As a byproduct, we obtain an explicit pointwise Chernoff majorant for the tail. Our second contribution is a distribution-function scheme for deriving explicit upper bounds on $\mathbb{E}[S]$. Starting from the fixed-point equation at the level of the distribution function, we construct an order-preserving lower iteration and a conservative mesh discretization suited to computer-assisted upper bounds on the mean. We illustrate the latter numerically in floating-point arithmetic, but do not pursue a certified numerical proof here.

Wednesday, April 15 2026, 00:00

TCS+ talk: Wednesday, April 22 — Yichuan Wang, UC Berkeley

from TCS+ Seminar Series

The next TCS+ talk will take place this coming Wednesday, April 22th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Yichuan Wang from UC Berkeley will speak about “Superquadratic Lower Bounds for Depth-2 Linear Threshold Circuits” (abstract below). You can reserve a spot as an individual or a […]

The next TCS+ talk will take place this coming Wednesday, April 22th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Yichuan Wang from UC Berkeley will speak about “Superquadratic Lower Bounds for Depth-2 Linear Threshold Circuits” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: Proving lower bounds against depth-2 linear threshold circuits (a.k.a. THR ◦ THR) is one of the frontier questions in complexity theory. Despite tremendous effort, our best lower bounds for THR ◦ THR only hold for sub-quadratic number of gates, which was proven a decade ago by Tamaki (ECCC TR16) and Alman, Chan, and Williams (FOCS 2016) for a hard function in E^NP.

In this work, we prove that there is a function f in E^NP that requires $n^{2.5-\varepsilon}$ -size THR ◦ THR circuits for any $\varepsilon > 0$ . We obtain our new results by designing a new non-trivial algorithm for estimating the acceptance probability of an XOR of two $n^{2.5-\varepsilon}$ -size THR ◦ THR circuits, and apply Williams’ algorithmic method to obtain the desired lower bound.

By plustcs

Tuesday, April 14 2026, 20:32

Guest Post from Peter Brass, Former NSF Theory Director, on the NSF budget.

from Computational Complexity

Guest post from Peter Brass, Former NSF Theory director (though not affiliated with the NSF now) on the White House NSF budget for FY 2027.

---------------------------------------------

Dear Colleagues

A week ago the White House released the NSF budget request for FY 2027( here) so I want to provide you an update. As always, this is just my interpretation, I am not connected to the NSF any more

The general news is bad, we get a replay of FY 2026 (FY 2026 is October 2025 to September 2026)
For context: the NSF enacted budget in FY 2023 was $9.5B. The CISE budget was $0.9B. Budgets start with a request by the White House, and then get negotiated with Congress.
A year ago, the White House made a FY 2026 budget request of $3.9B, which was a ~60% cut from the previous level. After negotiation with Congress, the enacted budget became $8.7B
However, a long period of FY 2025 were funded by continuing resolutions, and continuing resolutions are based on the White House budget request, so for the first half of FY 2025 the 60% cut was in effect, and awards only now pick up. In addition, there was the government shutdown, and the removal of NSF from the Eisenhower Ave building in Alexandria, so processing will be delayed.
The cancellation of awards, although it caused a huge media echo, had a very small impact outside the EDU and SBE directorates, about 2% of awards were affected, and perhaps 1/3 of them were restored.
The FY 2027 budget request asks for $4.8B, but subtracting $0.9B reserved for a new antarctic research vessel, the request is the same $3.9B. We hope that Congress will again restore much, but clearly the White House continues not supportive of basic research. The proposed cuts for NSF are a larger percentage than for NASA, NIH, NIST, or the DoE Research. The request reduces the CISE budget from $0.9B to $0.3B.
The NSF projects a slight decrease in the number of proposals, and a huge decrease in the funding rate, across all research proposals a decline from 18% to 7%. The average award size and award duration are projected to increase slightly, giving much fewer people a bit more resources.
So far NSF has not done any hiring since the start of the current administration, and although Congress restored much of the research funding, it did not restore the cuts in the staffing level. Rotators continue to end their rotation, and are not replaced, the current plan seems to discontinue the concept of a rotator entirely. With the reduction is program staff, the remaining program directors are overworked, and are put in charge of programs where they have no previous connection to the research community, without time to establish the connection. The programs themselves remain unchanged, as they are governed by the solicitations, but the people managing the programs can give less time to the individual program. And the money available depends on the outcome of the budget process.
That is the current situation, or at least the plan of the White House; we will see what Congress makes of it.
TO DO: tell your congress member that you thank for their previous support of basic research at the NSF, and hope they continue it.

By gasarch

Guest post from Peter Brass, Former NSF Theory director (though not affiliated with the NSF now) on the White House NSF budget for FY 2027.

---------------------------------------------

Dear Colleagues

A week ago the White House released the NSF budget request for FY 2027( here) so I want to provide you an update. As always, this is just my interpretation, I am not connected to the NSF any more

The general news is bad, we get a replay of FY 2026 (FY 2026 is October 2025 to September 2026)

For context: the NSF enacted budget in FY 2023 was $9.5B. The CISE budget was $0.9B. Budgets start with a request by the White House, and then get negotiated with Congress.

A year ago, the White House made a FY 2026 budget request of $3.9B, which was a ~60% cut from the previous level. After negotiation with Congress, the enacted budget became $8.7B

However, a long period of FY 2025 were funded by continuing resolutions, and continuing resolutions are based on the White House budget request, so for the first half of FY 2025 the 60% cut was in effect, and awards only now pick up. In addition, there was the government shutdown, and the removal of NSF from the Eisenhower Ave building in Alexandria, so processing will be delayed.

The cancellation of awards, although it caused a huge media echo, had a very small impact outside the EDU and SBE directorates, about 2% of awards were affected, and perhaps 1/3 of them were restored.

The FY 2027 budget request asks for $4.8B, but subtracting $0.9B reserved for a new antarctic research vessel, the request is the same $3.9B. We hope that Congress will again restore much, but clearly the White House continues not supportive of basic research. The proposed cuts for NSF are a larger percentage than for NASA, NIH, NIST, or the DoE Research. The request reduces the CISE budget from $0.9B to $0.3B.

The NSF projects a slight decrease in the number of proposals, and a huge decrease in the funding rate, across all research proposals a decline from 18% to 7%. The average award size and award duration are projected to increase slightly, giving much fewer people a bit more resources.

So far NSF has not done any hiring since the start of the current administration, and although Congress restored much of the research funding, it did not restore the cuts in the staffing level. Rotators continue to end their rotation, and are not replaced, the current plan seems to discontinue the concept of a rotator entirely.

With the reduction is program staff, the remaining program directors are overworked, and are put in charge of programs where they have no previous connection to the research community, without time to establish the connection. The programs themselves remain unchanged, as they are governed by the solicitations, but the people managing the programs can give less time to the individual program. And the money available depends on the outcome of the budget process.

That is the current situation, or at least the plan of the White House; we will see what Congress makes of it.

TO DO: tell your congress member that you thank for their previous support of basic research at the NSF, and hope they continue it.

By gasarch

Tuesday, April 14 2026, 19:45

Complexity Theory meets Ordinary Differential Equations

Authors: Adalbert Fono, Noah Wedlich, Holger Boche, Gitta Kutyniok

This contribution investigates the computational complexity of simulating linear ordinary differential equations (ODEs) on digital computers. We provide an exact characterization of the complexity blowup for a class of ODEs of arbitrary order based on their algebraic properties, extending previous characterization of first order ODEs. Complexity blowup indeed arises in most ODEs (except for certain degenerate cases) and means that there exists a low complexity input signal, which can be generated on a Turing machine in polynomial time, leading to a corresponding high complexity output signal of the system in the sense that the computation time for determining an approximation up to $n$ significant digits grows faster than any polynomial in $n$. Similarly, we derive an analogous blowup criterion for a subclass of first-order systems of linear ODEs. Finally, we discuss the implications for the simulation of analog systems governed by ODEs and exemplarily apply our framework to a simple model of neuronal dynamics$-$the leaky integrate-and-fire neuron$-$heavily employed in neuroscience.

Authors: Adalbert Fono, Noah Wedlich, Holger Boche, Gitta Kutyniok

This contribution investigates the computational complexity of simulating linear ordinary differential equations (ODEs) on digital computers. We provide an exact characterization of the complexity blowup for a class of ODEs of arbitrary order based on their algebraic properties, extending previous characterization of first order ODEs. Complexity blowup indeed arises in most ODEs (except for certain degenerate cases) and means that there exists a low complexity input signal, which can be generated on a Turing machine in polynomial time, leading to a corresponding high complexity output signal of the system in the sense that the computation time for determining an approximation up to $n$ significant digits grows faster than any polynomial in $n$. Similarly, we derive an analogous blowup criterion for a subclass of first-order systems of linear ODEs. Finally, we discuss the implications for the simulation of analog systems governed by ODEs and exemplarily apply our framework to a simple model of neuronal dynamics$-$the leaky integrate-and-fire neuron$-$heavily employed in neuroscience.

Tuesday, April 14 2026, 00:00

The Borsuk number of a graph

Authors: José Cáceres, Delia Garijo, Alberto Márquez, Rodrigo I. Silveira

The Borsuk problem asks for the smallest number of subsets with strictly smaller diameters into which any bounded set in the $d$-dimensional space can be decomposed. It is a classical problem in combinatorial geometry that has been subject of much attention over the years, and research on variants of the problem continues nowadays in a plethora of directions. In this work, we propose a formulation of the problem in the context of graphs. Depending on how the graph is partitioned, we consider two different settings dealing either with the usual notion of diameter in abstract graphs, or with the diameter in the context of continuous graphs, where all points along the edges, instead of only the vertices, must be taken into account when computing distances. We present complexity results, exact computations and upper bounds on the parameters associated to the problem.

Authors: José Cáceres, Delia Garijo, Alberto Márquez, Rodrigo I. Silveira

The Borsuk problem asks for the smallest number of subsets with strictly smaller diameters into which any bounded set in the $d$-dimensional space can be decomposed. It is a classical problem in combinatorial geometry that has been subject of much attention over the years, and research on variants of the problem continues nowadays in a plethora of directions. In this work, we propose a formulation of the problem in the context of graphs. Depending on how the graph is partitioned, we consider two different settings dealing either with the usual notion of diameter in abstract graphs, or with the diameter in the context of continuous graphs, where all points along the edges, instead of only the vertices, must be taken into account when computing distances. We present complexity results, exact computations and upper bounds on the parameters associated to the problem.

Tuesday, April 14 2026, 00:00

Any 3D Scene is Worth 1K Tokens: 3D-Grounded Representation for Scene Generation at Scale

Authors: Dongxu Wei, Qi Xu, Zhiqi Li, Hangning Zhou, Cong Qiu, Hailong Qin, Mu Yang, Zhaopeng Cui, Peidong Liu

3D scene generation has long been dominated by 2D multi-view or video diffusion models. This is due not only to the lack of scene-level 3D latent representation, but also to the fact that most scene-level 3D visual data exists in the form of multi-view images or videos, which are naturally compatible with 2D diffusion architectures. Typically, these 2D-based approaches degrade 3D spatial extrapolation to 2D temporal extension, which introduces two fundamental issues: (i) representing 3D scenes via 2D views leads to significant representation redundancy, and (ii) latent space rooted in 2D inherently limits the spatial consistency of the generated 3D scenes. In this paper, we propose, for the first time, to perform 3D scene generation directly within an implicit 3D latent space to address these limitations. First, we repurpose frozen 2D representation encoders to construct our 3D Representation Autoencoder (3DRAE), which grounds view-coupled 2D semantic representations into a view-decoupled 3D latent representation. This enables representing 3D scenes observed from arbitrary numbers of views--at any resolution and aspect ratio--with fixed complexity and rich semantics. Then we introduce 3D Diffusion Transformer (3DDiT), which performs diffusion modeling in this 3D latent space, achieving remarkably efficient and spatially consistent 3D scene generation while supporting diverse conditioning configurations. Moreover, since our approach directly generates a 3D scene representation, it can be decoded to images and optional point maps along arbitrary camera trajectories without requiring per-trajectory diffusion sampling pass, which is common in 2D-based approaches.

Authors: Dongxu Wei, Qi Xu, Zhiqi Li, Hangning Zhou, Cong Qiu, Hailong Qin, Mu Yang, Zhaopeng Cui, Peidong Liu

3D scene generation has long been dominated by 2D multi-view or video diffusion models. This is due not only to the lack of scene-level 3D latent representation, but also to the fact that most scene-level 3D visual data exists in the form of multi-view images or videos, which are naturally compatible with 2D diffusion architectures. Typically, these 2D-based approaches degrade 3D spatial extrapolation to 2D temporal extension, which introduces two fundamental issues: (i) representing 3D scenes via 2D views leads to significant representation redundancy, and (ii) latent space rooted in 2D inherently limits the spatial consistency of the generated 3D scenes. In this paper, we propose, for the first time, to perform 3D scene generation directly within an implicit 3D latent space to address these limitations. First, we repurpose frozen 2D representation encoders to construct our 3D Representation Autoencoder (3DRAE), which grounds view-coupled 2D semantic representations into a view-decoupled 3D latent representation. This enables representing 3D scenes observed from arbitrary numbers of views--at any resolution and aspect ratio--with fixed complexity and rich semantics. Then we introduce 3D Diffusion Transformer (3DDiT), which performs diffusion modeling in this 3D latent space, achieving remarkably efficient and spatially consistent 3D scene generation while supporting diverse conditioning configurations. Moreover, since our approach directly generates a 3D scene representation, it can be decoded to images and optional point maps along arbitrary camera trajectories without requiring per-trajectory diffusion sampling pass, which is common in 2D-based approaches.

Tuesday, April 14 2026, 00:00

A Ray Intersection Algorithm for Fast Growth Distance Computation Between Convex Sets

Authors: Akshay Thirugnanam, Koushil Sreenath

In this paper, we discuss an efficient algorithm for computing the growth distance between two compact convex sets with representable support functions. The growth distance between two sets is the minimum scaling factor such that the sets intersect when scaled about some center points. Unlike the minimum distance between sets, the growth distance provides a unified measure for set intersection and separation. We first reduce the growth distance problem to an equivalent ray intersection problem on the Minkowski difference set. Then, we propose an algorithm to solve the ray intersection problem by iteratively constructing inner and outer polyhedral approximations of the Minkowski difference set. We show that our algorithm satisfies several key properties, such as primal and dual feasibility and monotone convergence. We provide extensive benchmark results for our algorithm and show that our open-source implementation achieves state-of-the-art performance across a wide variety of convex sets. Finally, we demonstrate robotics applications of our algorithm in motion planning and rigid-body simulation.

Authors: Akshay Thirugnanam, Koushil Sreenath

In this paper, we discuss an efficient algorithm for computing the growth distance between two compact convex sets with representable support functions. The growth distance between two sets is the minimum scaling factor such that the sets intersect when scaled about some center points. Unlike the minimum distance between sets, the growth distance provides a unified measure for set intersection and separation. We first reduce the growth distance problem to an equivalent ray intersection problem on the Minkowski difference set. Then, we propose an algorithm to solve the ray intersection problem by iteratively constructing inner and outer polyhedral approximations of the Minkowski difference set. We show that our algorithm satisfies several key properties, such as primal and dual feasibility and monotone convergence. We provide extensive benchmark results for our algorithm and show that our open-source implementation achieves state-of-the-art performance across a wide variety of convex sets. Finally, we demonstrate robotics applications of our algorithm in motion planning and rigid-body simulation.

Tuesday, April 14 2026, 00:00

Topo-ADV: Generating Topology-Driven Imperceptible Adversarial Point Clouds

Authors: Gayathry Chandramana Krishnan Nampoothiry, Raghuram Venkatapuram, Anirban Ghosh, Ayan Dutta

Deep neural networks for 3D point cloud understanding have achieved remarkable success in object classification and recognition, yet recent work shows that these models remain highly vulnerable to adversarial perturbations. Existing 3D attacks predominantly manipulate geometric properties such as point locations, curvature, or surface structure, implicitly assuming that preserving global shape fidelity preserves semantic content. In this work, we challenge this assumption and introduce the first topology-driven adversarial attack for point cloud deep learning. Our key insight is that the homological structure of a 3D object constitutes a previously unexplored vulnerability surface. We propose Topo-ADV, an end-to-end differentiable framework that incorporates persistent homology as an explicit optimization objective, enabling gradient-based manipulation of topological features during adversarial example generation. By embedding persistence diagrams through differentiable topological representations, our method jointly optimizes (i) a topology divergence loss that alters persistence, (ii) a misclassification objective, and (iii) geometric imperceptibility constraints that preserve visual plausibility. Experiments demonstrate that subtle topology-driven perturbations consistently achieve up to 100% attack success rates on benchmark datasets such as ModelNet40, ShapeNet Part, and ScanObjectNN using PointNet and DGCNN classifiers, while remaining geometrically indistinguishable from the original point clouds, beating state-of-the-art methods on various perceptibility metrics.

Authors: Gayathry Chandramana Krishnan Nampoothiry, Raghuram Venkatapuram, Anirban Ghosh, Ayan Dutta

Deep neural networks for 3D point cloud understanding have achieved remarkable success in object classification and recognition, yet recent work shows that these models remain highly vulnerable to adversarial perturbations. Existing 3D attacks predominantly manipulate geometric properties such as point locations, curvature, or surface structure, implicitly assuming that preserving global shape fidelity preserves semantic content. In this work, we challenge this assumption and introduce the first topology-driven adversarial attack for point cloud deep learning. Our key insight is that the homological structure of a 3D object constitutes a previously unexplored vulnerability surface. We propose Topo-ADV, an end-to-end differentiable framework that incorporates persistent homology as an explicit optimization objective, enabling gradient-based manipulation of topological features during adversarial example generation. By embedding persistence diagrams through differentiable topological representations, our method jointly optimizes (i) a topology divergence loss that alters persistence, (ii) a misclassification objective, and (iii) geometric imperceptibility constraints that preserve visual plausibility. Experiments demonstrate that subtle topology-driven perturbations consistently achieve up to 100% attack success rates on benchmark datasets such as ModelNet40, ShapeNet Part, and ScanObjectNN using PointNet and DGCNN classifiers, while remaining geometrically indistinguishable from the original point clouds, beating state-of-the-art methods on various perceptibility metrics.

Tuesday, April 14 2026, 00:00

Differentially Private Verification of Distribution Properties

Authors: Elbert Du, Cynthia Dwork, Pranay Tankala, Linjun Zhang

A recent line of work initiated by Chiesa and Gur and further developed by Herman and Rothblum investigates the sample and communication complexity of verifying properties of distributions with the assistance of a powerful, knowledgeable, but untrusted prover. In this work, we initiate the study of differentially private (DP) distribution property testing. After all, if we do not trust the prover to help us with verification, why should we trust it with our sensitive sample? We map a landscape of DP prover-aided proofs of properties of distributions. In the non-private case it is known that one-round (two message) private-coin protocols can have substantially lower complexity than public-coin AM protocols, but in the private case, the possibility for improvement depends on the parameter regime and privacy model. Drawing on connections to replicability and techniques for amplification, we show: (1) There exists a reduction from any one-round $(\varepsilon,δ)$-DP private-coin interactive proof to a one-round public-coin DP interactive proof with the same privacy parameters, for the parameter regime $\varepsilon=O(1/\sqrt{n})$ and $δ=O(1/n^{5/2})$, and with the same sample and communication complexities. (2) If the verifier's message in the private-coin interactive proof is $O(1/\sqrt{\log n})$ locally DP -- a far more relaxed privacy parameter regime in a different model -- then applying one additional transformation again yields a one-round public-coin protocol with the same privacy bound and the same sample and computational complexities. (3) However, when the privacy guarantee is very relaxed ($\varepsilon\inΩ(\log n)$), private coins indeed reduce complexity. We also obtain a Merlin-Arthur (one-message) proof for privately testing whether samples are drawn from a product distribution, and prove that its sample complexity is optimal.

Authors: Elbert Du, Cynthia Dwork, Pranay Tankala, Linjun Zhang

A recent line of work initiated by Chiesa and Gur and further developed by Herman and Rothblum investigates the sample and communication complexity of verifying properties of distributions with the assistance of a powerful, knowledgeable, but untrusted prover. In this work, we initiate the study of differentially private (DP) distribution property testing. After all, if we do not trust the prover to help us with verification, why should we trust it with our sensitive sample? We map a landscape of DP prover-aided proofs of properties of distributions. In the non-private case it is known that one-round (two message) private-coin protocols can have substantially lower complexity than public-coin AM protocols, but in the private case, the possibility for improvement depends on the parameter regime and privacy model. Drawing on connections to replicability and techniques for amplification, we show: (1) There exists a reduction from any one-round $(\varepsilon,δ)$-DP private-coin interactive proof to a one-round public-coin DP interactive proof with the same privacy parameters, for the parameter regime $\varepsilon=O(1/\sqrt{n})$ and $δ=O(1/n^{5/2})$, and with the same sample and communication complexities. (2) If the verifier's message in the private-coin interactive proof is $O(1/\sqrt{\log n})$ locally DP -- a far more relaxed privacy parameter regime in a different model -- then applying one additional transformation again yields a one-round public-coin protocol with the same privacy bound and the same sample and computational complexities. (3) However, when the privacy guarantee is very relaxed ($\varepsilon\inΩ(\log n)$), private coins indeed reduce complexity. We also obtain a Merlin-Arthur (one-message) proof for privately testing whether samples are drawn from a product distribution, and prove that its sample complexity is optimal.

Tuesday, April 14 2026, 00:00

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic