CS Paper Radar

Fast Stencil Computations on a Single Arbitrarily Moving Interval

Aaron Gregory

cs.DS cs.DC ·submitted 2026-09-14 00:59 UTC · v2
theoryunusual

Abstract

A stencil computation repeatedly updates every cell of a grid from its neighbours' values at the previous timestep. Simulating T steps on N cells directly costs Theta(NT), and a line of work beginning with Ahmad et al. reduces this by composing many timesteps into one linear operator and applying it with a Fast Fourier Transform. That technique needs to know which cells will still obey the same operator when the composed step ends, and in a free-boundary problem they do not: the region governed by a given rule is determined by the solution and moves as it evolves. We study one spatial dimension, a three-point stencil with time-varying coefficients, and a computed region that is a single interval whose two endpoints move by arbitrary amounts at every step, revealed online. Let B be the horizon plus the total variation of the boundary trajectory. We give a schedule whose work is O((B+N) log T log(N+B)) and whose span is O(T log T log(N+B)), and we prove that the values it computes are exact. The best existing bound for a region that moves requires its boundary to travel at most one cell per timestep. We drop that requirement and lose nothing by it: a boundary obeying it has B <= 3T, so our bound stays near-linear on every trajectory the earlier result covers. Elsewhere, B grows only by the distance the boundary actually travels -- one jump of width N costs T + 2N. The reason total variation suffices is that everything the two endpoints touch over a time window of any length lies in two intervals, one per endpoint. This cannot be relaxed: with p regions the bound degrades by a factor p, and at p = sqrt(T) there is an instance on which the work is Theta(T^{3/2}) while B + N = Theta(T). All results are machine-checked in Lean 4, apart from the classical convolution bound, which is imported as an interface.

Closest papers

Nearest neighbours by meaning across the whole index.

Three-Color Free-Flood-It on Fixed-Height Grids Is Polynomial-Time Solvable

cs.CC cs.DS ·2026-09-29 ·Yuxuan Zhou
similarity 0.55
Abstract

We give a deterministic algorithm for \textsc{Free-Flood-It} on rectangular grids $P_k\square P_n$ with at most three colors. For every fixed height $k$, it computes the minimum number of moves and an optimal sequence in $N^{O(k^2)}$ time, where $N=kn$. This resolves the previously open three-color case on complete $3\times n$ boards. The proof uses a representation of flooding strategies as paintings by connected regions. We show that an optimal painting can be chosen so that its regions form a rooted tree with strong restrictions on the colors along ancestral paths. These restrictions make the part of the tree visible in any fixed-size connected window admit only polynomially many descriptions. The remaining common ancestors may form an arbitrarily long chain. We retain that chain on a stack and use a finite context-free recurrence to minimize the total painting cost without enumerating all possible stack contents. Connectivity information at the boundary ensures that the resulting local descriptions assemble into one valid global painting. The argument also applies to graphs supplied with an ordering into connected layers of bounded size, provided every edge lies within one layer or joins consecutive layers. A family of three-row boards shows that the unbounded ancestor chains handled by the algorithm are necessary even for optimal paintings. For any fixed height and palette size, we also give a deterministic EPTAS and a randomized sampling variant with an explicit failure-probability bound. These approximation results use a separate algorithm with single-exponential dependence on the move budget.

0.17

Rotate the Loop: Blockwise Conformality for Looped Transformers

cs.LG cs.AIstat.ML ·2026-09-30 ·Alexey Zemtsov, Albina Klepach, Vadim Lomshakov, Andrei Polubarov, Nikita Lyubaykin +3 more
published similarity 0.53
Abstract · Accepted at NeurIPS 2026 Workshop "Transitioning from Pre-Training to Post-Training"

Looped transformers reuse one shared block across many recurrent steps, so depth becomes a quantity that can be spent at runtime rather than a stack of distinct layers. Those extra steps help only if a write made on one recurrent step is still readable on later ones, and that depends on the linear map applied to the residual between recurrent steps. We show that whether the loop learns to track state is a geometric question about the form of this map, and we propose blockwise conformal injections: the residual splits into coordinate-aligned groups and rotates inside each one, so every group has its own timescale while the geometry stays exact within it. Our experiments show a performance increase on a demanding form of state tracking - last-token accuracy when the rest of the prefix is already correct - and on language modelling, where a signal written earlier has to be retrieved at the end of the sequence.

0.37

Hypergeometric Bridges for Multidimensional Grid Visibility

cs.CG ·2026-10-12 ·Ibrahim Ibrahim, Wilm Decré
theory similarity 0.52
Abstract · 24 pages, 8 figures, 3 tables

Established interpolation-based methods efficiently compute visibility from one source to every grid cell using values computed closer to the source. Interpolation yields fractional values even on binary grids of free or fully blocking cells. Two-dimensional path-counting theory interprets these values as fractions of unobstructed grid paths, but three-dimensional methods use different predecessor structures. Interpreting these values consistently across dimensions and on nonbinary grids remains unresolved. We provide a unified mathematical account that gives every visibility value a precise meaning in any dimension. We establish when grid refinement yields eventual agreement with continuous visibility, implement parallel solvers, and compare four three-dimensional methods in accuracy and throughput. We define cell transmission: zero blocks visibility, one preserves it, and intermediate values attenuate it proportionally. We prove each computed value equals the uniform finite-path average of transmission products over finitely many source-to-cell grid paths. It is the fraction of clear paths on binary grids and the mean path transmission on nonbinary grids. For a source--target query, the fractions of paths passing through cells at each step form a hypergeometric distribution in 2D, which we call the hypergeometric bridge. On the last step into the target, these probabilities equal the interpolation weights. Higher-dimensional interpolation weights arise from products of hypergeometric bridges. For any fixed dimension, the full-field algorithm remains linear in grid size. Exact path enumeration reproduces every checked visibility value. NumPy, OpenMP, and CUDA agree numerically, and our OpenMP solver achieves the highest throughput in the four-method CPU comparison at every tested resolution.

0.27

Faster Treasure Hunt via Strongly Universal Exploration with Polylogarithmic Overhead

cs.CC ·2026-11-05 ·Qin Xin
similarity 0.52
Abstract · 27 pages

We study deterministic exploration and delayed-activation treasure hunt in anonymous undirected port-labeled graphs with incoming-port information. From polynomial-time constructible ordinary universal exploration sequences of length \(O(n^c)\) for a fixed regular degree, we construct a single infinite strongly universal exploration sequence with cover time \(O(n^c\log^2n)\). Summable dyadic insertion schedules yield the sharper bound \(O_\eps(n^c\log n(\log\log n)^{1+\eps})\) for every fixed \(\eps>0\), together with refinements at every fixed iterated-logarithm depth. The proof combines reversible excursions, neutral guards and an arbitrary-window argument that treats both orientations simultaneously. For this recurrence, uniform linear expansion is equivalent to convergence of the normalized period sum. Exact counting identities also permit direct instruction access. With a logspace ordinary generator, table-free enumeration of decreasing scale paths computes instruction \(t\) using \(O(\log(t+2))\) working bits and time polynomial in \(t\). The earlier polynomial-slack bounds follow as corollaries. A local cubic simulation extends the treasure-hunt application to arbitrary-degree graphs, with the \(2m\)-vertex replacement size included explicitly in the bound.

0.36

Real-Time Synthesis of Robust Controlled Invariant Sets for Monotone Systems

eess.SY cs.AIcs.RO ·2026-09-12 ·Yasin Sonmez, Mahmoud Khaled, Majid Zamani, Murat Arcak
published similarity 0.52
Abstract

Safety-critical control of autonomous systems requires formal safety certificates, such as controlled invariant sets, that must be computed online as conditions change. Although standard synthesis algorithms scale poorly with state dimension, monotone dynamical systems with lower-closed safety specifications allow for accelerated computation of controlled invariant sets. In particular, lazy fixed-point algorithms exploit monotonicity and track only the antichain basis of the set. However, membership tests and redundancy checks against an evolving basis remain major bottlenecks. We introduce a threshold-function reformulation in which a lower-closed set on a d-dimensional grid is represented by its column heights along a designated axis. This reformulates the greatest-fixed-point iteration as independent one-dimensional binary searches, one per grid column, yielding an embarrassingly parallel iteration with asymptotically lower computational complexity than the lazy fixed-point algorithm. Experiments synthesize invariant sets on 3D grids with 10^9 cells in under 50 ms and 10^14 cells in under two minutes. We further demonstrate online re-synthesis in a safety-informed model predictive controller example.

0.28

KernelPack-JAX: a meshless differentiable GPU framework for node generation and forward and inverse PDE problems

cs.MS math.NA ·2026-10-18 ·Alberto Cattaneo, M. Keith Ballard, Robert M. Kirby, Grady B. Wright, Varun Shankar
similarity 0.52
Abstract

We present KernelPack-JAX, a meshless, differentiable, GPU framework in JAX for solving forward and inverse PDE problems in domains whose boundaries, including internal obstacles, are given only by samples of their smooth pieces. Our node generator is based on a new stacked representation of piecewise-smooth boundaries, in which a parametric partition of unity of each smooth piece induces the supports of a curl-free implicit partition of unity of the whole boundary. This representation keeps the edges and corners of the boundary and classifies every point of space without a global fit. Boundary and interior nodes are then selected by a parallel greedy independent-set algorithm that reproduces sequential Poisson-disk sampling exactly. We discretize elliptic and parabolic problems with radial basis function-generated finite differences (RBF-FD) on stencils selected by a new visibility heuristic to avoid crossing the boundary, with ghost nodes for the boundary conditions. In addition, our framework exposes a GPU sparse direct solver to JAX as a differentiable linear solve, so that Jacobians of time-dependent problems cost a small multiple of a forward solve. We derive error estimates that separate consistency from stability and bound the parameter error by the forward error. We demonstrate high-order convergence for Darcy flow, reaction-diffusion, and advection-diffusion in 2D and 3D domains, including one with an internal obstacle, and show that the recovered parameters largely follow the forward errors. We also present timings for every stage.

0.20

Best of Two Worlds: Combining High and Low Resolution to Compute Viewsheds on terrains

cs.DS ·2026-10-01 ·Laura Toma
published similarity 0.52
Abstract · 27 pages, 19 figures, short version appeared in Proc. ACM SIGSPATIAL GIS 2018

The viewshed of a point $v$ on a grid terrain $T$, viewshed$_T(v)$, is defined as the set of grid points in $T$ that are visible from $v$. We describe a novel algorithm for computing viewshed$_T(v)$ using a multi-resolution approach: Given a parameter $k >1$ that represents the block size, we create a grid $T'$ which is a lower-resolution version of $T$, such that each point in $T'$ corresponds to a block of $\lceil \sqrt k \rceil $-by-$\lceil \sqrt k \rceil$ points in $T$. The key of our approach is using $T'$ to speed up the computation of viewshed$_T(v)$ while not introducing approximation. We compute viewshed$_T(v)$ in two steps: First we compute the viewshed of $v$ on $T'$, while maintaining the invariant that any block in $T'$ that is labeled as invisible may not contain any visible points. Thus, the first step's role is to use $T'$ to filter out blocks in $T$ that are guaranteed to be invisible. The second step considers the blocks that were labeled as visible in $T'$ and computes the visibility of their points with full accuracy using the data in $T$. Overall the algorithm runs in $O(n + \frac nk \lg \frac nk + k \lg k + l \cdot \lg n)$, where $l$ is the total size of visible blocks in $T'$. When $k = Ω(1)$ and $l = o(n) $, the running time of our algorithm improves on the previous best bound of $O(n \lg n)$. Our experimental results show the performance of the new algorithm in practice and a speedup of more than an order of magnitude compared to previous algorithms.

0.46

Temporal Exploration and Rendezvous via Weisfeiler-Leman Colorings

cs.DS cs.CCcs.DMmath.CO ·2026-10-21 ·Frank Kammer, Sandra Kiefer, Johannes Meintrup
top venuetheory similarity 0.51
Abstract · Full version of a paper accepted for publication at SODA 2027. 37 pages, 3 figures

Temporal graphs are graphs whose edge relation changes in discrete time steps. The Temporal Exploration Problem (TEXP) asks for a temporal walk that visits all vertices. We show that every connected temporal graph with $n$ vertices can be explored in $O(qn\log^3(n))$ time steps, where $q$ is the number of vertex color classes induced by the 2-dimensional Weisfeiler-Leman (2-WL) coloring. For small $q$, our bound substantially improves on the known worst-case bound of $Θ(n^2)$ in general connected temporal graphs. A corresponding walk can be constructed in deterministic polynomial time. The upper bound is complemented by lower bounds of $Ω(n\log(n))$ when $q$ is constant and $Ω(qn)$ when $1 \leq q \leq n$. We also apply our techniques to the Temporal Rendezvous Problem (TRP), in which two agents that do not communicate have to meet on a vertex of the temporal graph. Our exploration algorithm yields that, with only polynomial-time computational power, the agents can meet in $O(n\log^3(n))$ time steps, leaving a gap of only $\log^2(n)$ to the known lower bound. Dogeas, Erlebach, Kammer, Meintrup, and Moses Jr. [ICALP'24] have shown an $O(rn^{1+ε})$ bound for TEXP, for every fixed $ε> 0$, where $r$ is the number of orbits, and an $O(n^{1+ε})$ bound for TRP. Both results require superpolynomial computation time. Our contribution improves upon these results in several ways. First, the dependence on $n$ in the upper bounds on the number of time steps is decreased from $n^{1+ε}$ to $n\log^3(n)$ for both TEXP and TRP. Second, for TEXP, we bound the number of time steps linearly by the parameter q, which is efficiently computable and upper bounded by $r$. Third, we provide novel deterministic polynomial-time algorithms for both TEXP and TRP.

0.42