Papers

Widely used methods for identifying crystal structure in atomistic simulations are limited in practice to a handful of simple structures, leaving many important crystalline systems without automated classification techniques. Voronoi topology analysis offers a route to classifying arbitrary crystalline and defect environments, but realizing this potential first requires enumerating the Voronoi cell topologies that can arise under thermal perturbation of a structure of interest. We present an algorithm that deterministically enumerates all Voronoi cell topologies arising from generic infinitesimal perturbations of an arbitrary crystal structure, producing structural classifiers that extend automated identification to general crystalline systems. We demonstrate the approach on several structures of general interest.

We study multi-robot motion planning in a polygonal environment with polygonal robots. The setting of the problem consists of a polygonal domain $\mathcal{W}$ with $n$ vertices and $k$ robots $R_1,\dots,R_k$ translating in $\mathcal{W}$ each of which is represented by a polygon of constant complexity. Given a source configuration $\mathbf{s}$ and a target configuration $\mathbf{t}$ of the robots in $\mathcal{W}$, the goal of the problem is to find a collision-free motion plan from $\mathbf{s}$ to $\mathbf{t}$ that is shortest with respect to some cost function. We present the first fully polynomial-time approximation schemes (FPTAS) for motion planning with any fixed number $k$ of robots, under the min-sum objective, the min-max objective, and the min-makespan objective. Here, the min-sum variant aims to minimize the total traveling distance of all robots, the min-max variant aims to minimize the maximum traveling distance of a single robot, and the min-makespan variant aims to minimize the total time cost under the assumption that all robots move with a maximum speed $1$. The algorithm directly generalizes to the problem in any fixed dimension $d$, with a polytope environment and polytope robots. Our result settles an open question of Agarwal, Halperin, Sharir, Steiger [SODA'24] and Agarwal, Holmgren, Steiger [SODA'26], who gave an FPTAS for $k=2$ unit-square robots and a bicriteria-approximation algorithm for a fixed number $k$ of unit-square or unit-disk robots, respectively. Compared to the previous results, our algorithm is substantially simpler.

Extremal constructions play a central role in the design and analysis of algorithms. Integrality-gap instances expose the limitations of relaxations, while hard configurations reveal structural sources of computational difficulty. Such constructions, however, are still typically discovered through a slow, manual process. This paper investigates how machine learning can accelerate their discovery to support algorithm design and analysis. We build on PatternBoost, a framework alternating local search with generation from a trained transformer, using its Axplorer implementation to investigate three problems: integrality gaps for maximum independent set of rectangles, integrality gaps for stabbing unit squares with axis-parallel lines, and hard instances for recursive guillotine cutting. By exploring candidate representations, local search operations, and surrogate models used to rank candidates before exact verification, we carefully adapt the framework to these combinatorial geometry problems.While naive representations and search strategies fail to find non-trivial instances, our tailored adaptation discovers numerous non-trivial constructions. For stabbing unit squares, the method reaches a gap of $20/13\approx 1.54$, improving on the literature's best known lower bound of $3/2$. Purely automated search converges rapidly and then plateaus, prompting the question of what is required to push the bound higher still. We find that initial instance diversity plays an important role: with modest expert input via a structured staircase construction, the system reaches an improved integrality gap of $14/9\approx 1.555$. These results demonstrate that machine learning and domain expertise can be combined to discover new extremal constructions that advance algorithmic lower bounds.

Quantifying the diversity of a set of objects is a fundamental problem in machine learning and statistics. Mironov and Prokhorenkova (2025) recently showed that three axioms-monotonicity, uniqueness, and continuity-are crucial for a reliable diversity measure and that none of the standard metrics in the literature satisfy all three. They also constructed two measures that do satisfy the axioms, but both are NP-hard to compute, leaving open the question of whether efficient axiomatic diversity measures can exist. We study a Euclidean-restricted version of this question. We introduce Geometric Kernel Diversity (GKD), which associates a radial kernel solid with each point and measures the volume of their union. We show that canonical GKD satisfies all three Mironov-Prokhorenkova axioms on Euclidean-realizable inputs. For canonical GKD, we give exact polynomial-time algorithms in dimensions $d \le 3$. In arbitrary dimensions, we give a randomized algorithm that returns a $(1 \pm \varepsilon)$-approximation with probability at least $1-\delta$ in time $O \left(\frac{nd}{\varepsilon^2}\log\frac{2}{\delta}\right)$ for $n$ points. The axiomatic guarantee applies to exact canonical GKD; the randomized algorithm approximates this deterministic quantity. We further show that the two diversity measures of Mironov and Prokhorenkova (2025) remain NP-hard on Euclidean-realizable inputs and, unless $\mathrm{NP} = \mathrm{RP}$, admit no FPRAS even on this restricted domain.

In the classical art gallery problem, a guard sees a target when the segment joining them lies entirely within the polygon. We explore what changes when sight may bend along regular arcs on absolutely irreducible curves, but only those defined by primitive integer polynomials of total degree at most \(d\) and coefficient height at most \(H\). We call such curves admissible sight carriers. Arcs can dramatically improve sight. In a one-sided comb, no straight-line guard sees selected targets in two different teeth, yet a single central guard sees a chosen target in every tooth along parabolic carriers. Sight can also fail in two different ways. Geometrically, the polygon may block every sight arc of the allowed degree between two points. For instance, in an alternating comb, the number of guards needed for a row of targets spanning the comb grows linearly with the number of sides at each fixed degree, even for carriers with arbitrary real coefficients. Arithmetically, no admissible carrier may pass through the points at all. Even in the unit square, at fixed \(d\) and \(H\), the proportion of rational targets that must guard themselves tends to one as the height bound grows. An algebraic target may lie on no rational curve of degree at most \(d\), however large \(H\) is. Both failures can be overcome for finite target sets by allowing the degree and coefficient height to grow. We show that every finite set of algebraic targets in a rational polygon becomes visible from any rational interior guard, with explicit bounds. We also construct, for every \(d\), arbitrarily large Galois orbits in the unit square, all of projective height \(4^{d+1}\), whose points must each guard themselves at degree \(d\) for every \(H\). Yet at degree \(d+1\) and coefficient height one, a single guard sees the whole orbit along \(Z(Y-X^{d+1})\).

Stack and queue layouts are two extensively studied and complementary linear representations of graphs. A stack (queue) layout $\langle \prec, \sigma \rangle$ of a graph $G$ consists of a total ordering $\prec$ of its vertices and of a partitioning $\sigma$ of its edges into pages, such that no two independent edges on the same page cross (nest). We propose a generalized model with colored edges (one color per edge) and capacitated pages. Namely, the input graph is equipped with colored edges and a prescribed budget for each page-color pair $(p,c)$ - this budget determines the maximum number of edges of color $c$ that page $p$ can accept. This model is motivated by fair allocation scenarios where budgets can be used to control the share of monochromatic edges on each page. Unfortunately, it is known that deciding whether a stack (queue) layout exists is NP-hard already with two (one) pages. Thus, we focus on the fixed-order setting - where the linear order $\prec$ is part of the input - for which an ordinary 2-page stack or $\ell$-page queue layout can be computed in polynomial time. Despite the restrictive setting, we show that both capacitated problems are NP-complete already for two pages. Furthermore, we study the complexity of the problems when parameterized by the number of pages, colors, and/or the structure of the edge conflict graph with respect to the fixed linear order $\prec$. Our analysis paints a detailed complexity landscape and uncovers a surprisingly intricate interplay between the considered parameters.

We study the compositional, intensional information geometry of probabilistic programs. For a first-order probabilistic programming language with finite random variables, we construct a contravariant lax monoidal functor that, for a program of type $X \to Y$, pulls back a (degenerate) Riemannian metric on $Y$ to $X$. It specialises to the Fisher metric in the case of standard statistical models and to ordinary pullback in the case of deterministic programs. We further justify this construction in two ways. First, we show that this functor arises as a pullback of geometry from a universal space of programs over a type $Y$ with a fixed trace space. Second, we show that it is a special case of a more general pullback construction over weighted measures. Our compositional geometry depends on the presentation of the program, and we study how it relates to the (non-compositional) geometry of the realised measures by establishing a three-level inequality relating our score-velocity metric for the program, the program's corresponding output-conditioned metric, and the standard Wasserstein-Fisher-Rao metric of the realised family. Finally, we show how the theory can be extended to accommodate continuous random variables using diffeological quasi-Borel spaces. We also discuss several concrete directions for future work.

Given a set $P$ of $n$ point sites in the plane, the $k$ nearest neighbors problem is to build a data structure that, for a query point $v$ and a query integer $k$, reports the $k$ nearest point sites of $v$ in $P$ efficiently. For the Euclidean metric, after four decades of efforts, an optimal data structure has been developed with $O(n)$ space, $O(\log n+k)$ query time and $O(n\log n)$ preprocessing time [Mat92b, Cha00, AC09, CT16]. In contrast, for a family of distance functions, the state-of-the-art data structure [AES99, KMR+20, Liu22] attains $O(n\log\log n)$ space, $O(\log n+k)$ query time and expected $O(n\log n)$ preprocessing time. An open question is the existence of an optimal data structure with $O(n)$ space and $O(\log n + k)$ query time for distance functions more general than the Euclidean metric. Such an optimal data structure also remains unknown for non-point sites in the Euclidean metric, even for disk sites or, more generally, additively weighted Euclidean distances. We develop an optimal $k$-nearest-neighbors data structure for additively weighted Euclidean distances with $O(n)$ space, $O(\log n + k)$ query time and expected $O(n\log n)$ preprocessing time. Since this data structure can be adjusted to disk sites, it serves as an initial result toward optimality for non-point sites. We also adapt our data structure to point sites under a family of convex metrics, including commonly used $L_p$ metrics and uniform orientation metrics. The data structure can be further extended to distance functions that satisfy certain axioms. Thus, we demonstrate the existence of optimal $k$-nearest-neighbors data structures for distance functions more general than point sites in the Euclidean metric. Our main technical advance is to generalize Matoušek's shallow partition theorem for hyperplanes [Mat92b] to these settings, while achieving a logarithmic crossing number.

In this paper, we prove that the synchronicity provided by the syncTAM can be leveraged to perform two additional feats impossible in the asynchronous aTAM. The aTAM has long been known to be equivalent to finite automata in the one-dimensional case. For our first set of results, we prove that this still holds when a finite, fixed amount of space is available in the second dimension. Yet, surprisingly, in the synchronous setting, a small, fixed, width is enough to simulate a Turing Machine. This holds even in the non-cooperative setting. For our second set of main results we prove that there exists a single set of syncTAM tiles that can be used to simulate any syncTAM system simply by using those tiles to create a scaled version of the seed structure of the original system and then letting the tiles from that set self-assemble from the scaled seed structure. While it has been shown (FOCS 2012) that such a tile set also exists in the aTAM for simulating all aTAM systems, that "intrinsically universal" (IU) tile set requires cooperativity (and is impossible without cooperativity as shown in SODA 2014). We prove there exists an IU tile set in the syncTAM that works without cooperativity. Furthermore, there exists a tile set that is IU for the class of directed systems (i.e. systems which each have a single terminal assembly) while remaining directed during simulation. This was shown to be impossible in the aTAM (FOCS 2016).

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.

We revisit the classical computational geometry problem of computing the exact (discrete or continuous) Fréchet distance between two given polygonal curves with $n$ vertices in a constant dimension $d$. 1. We present an $O((n^2/\log^2n)\log^2\log n)$-time deterministic algorithm for the discrete Fréchet distance problem, improving the previous $O((n^2/\log n)\log\log n)$ result by Agarwal, Ben Avraham, Kaplan, and Sharir [SODA'13]. 2. We present an $O((n^2/\log^2n)\log^2\log n)$-time deterministic algorithm for the decision version of the continuous Fréchet distance problem, improving the previous $O((n^2/\log n)\log^2\log n)$ result by Buchin, Buchin, Meulemans, and Mulzer [SODA'14] and the recent $O(n^2/\log^{1+\mu}n)$ randomized result by Cheng and Huang [SODA'25] for a small unspecified constant $\mu>0$ (which converges to 0 as $d$ increases). 3. Finally, we present an $O((n^2/\log^2 n)\log^{O(1)}\log n)$-time Las Vegas randomized algorithm for the continuous Fréchet distance problem, improving the previous $O(n^2\log^2\log n)$ randomized result by Buchin, Buchin, Meulemans, and Mulzer [SODA'14] and the recent $O(n^2/\log^{\mu}n)$-time randomized result claimed by Cheng and Huang [SODA'25]. Since these problems have near-quadratic OV-based conditional lower bounds and shaving of two log factors is the best that is known for similar, simpler problems such as longest common subsequence and edit distance, our results reach the natural limit of the current state of the art (up to $\log\log$ factors).

This paper presents an algorithm for detecting and fitting multiple ellipsoids in 2D, 3D and higher-dimensional data. The representation is based on tangents to the ellipsoid together with their contact points, rather than on points alone. A tangent contributes d independent equations where a point contributes one, so each hypothesis needs fewer samples, which in turn reduces the number of iterations required to recover every ellipsoid. The problem is posed as sets of linear equations whose solutions – the ellipsoid parameters – are recovered robustly by clustering in parameter space. The algorithm works in all dimensions and outperforms the state of the art in 2D. The approach applies in general to the robust solution of linear equations, and so has utility beyond ellipsoid fitting.

A well-separated pair decomposition (WSPD) of a set $P$ of $n$ points covers all $\binom{n}{2}$ pairs of points by a family of dumbbells $\{X,Y\}$, each covering the pairs of $X\times Y$, such that the diameters of $X$ and $Y$ are at most an $\varepsilon$-fraction of their distance. In $\mathbb{R}^d$, WSPDs with $O(n/\varepsilon^d)$ dumbbells always exist, but many inputs admit much smaller ones. However, computing a WSPD of minimum size is NP-hard in the plane. For $d\ge2$, the only known approximation that preserves the separation has a factor of $2^{O(d)}$, and Buchin et al. (ESA 2026) asked whether a $(1+\delta)$-approximation exists. We give a bicriteria approximation scheme: for fixed $d$ and $\delta\in(0,1]$, we compute in $f(d,\delta)\cdot n^{6}$ time a $(1+\delta)\varepsilon$-WSPD whose size is at most $(1+\delta)$ times the minimum size of an $\varepsilon$-WSPD. The same holds in metric spaces of bounded doubling dimension. The algorithm combines shifting over scales with the local-growth technique of Nieberg, Hurink, and Kern, applied to a graph whose vertices are the pairs of points. In contrast, we show that in general metric spaces, relaxing the separation by a factor below $2$ keeps the problem hard: for every fixed rational $\varepsilon\le1/4$, it is NP-hard to compute such a relaxed WSPD whose size is within a factor $n^c$ of the minimum, for every $c<2/3$.

A geometric $(n_4)$ configuration is a set of $n$ points and $n$ lines in the real projective plane such that every point lies on exactly four of the lines and every line contains exactly four of the points. The question of which $n$ admit such a configuration was posed by Grünbaum in 2000, following his 1990 paper with Rigby that gave the first geometric $4$-configuration, a $(21_4)$. Successive work of Bokowski-Schewe, of Bokowski, Grünbaum and Schewe, of Bokowski-Pilaud, and of Cuntz settled every case but one. Cuntz's 2018 paper, which constructed $(22_4)$ and $(26_4)$ configurations, states that only $n=23$ remained open. We settle this last case. We prove that for every prime $n\equiv3\pmod4$, in particular for $n=23$, the group of projective symmetries of a geometric $(n_4)$ configuration has order at most four, which explains why $n=23$ resisted the symmetric constructions that settled the other values. Reducing the case of a Klein four-group of symmetries to a few thousand bilinear polynomial systems in $18$ unknowns, and solving all of them exactly with Gröbner bases and saturation, we show that exactly two geometric $(23_4)$ configurations reach this bound, up to projective equivalence, and that there are no others even over $\mathbb{C}$. Both are self-polar with respect to a conic. The first has integer homogeneous coordinates; the second is defined over $\mathbb{Q}(\sqrt{17})$, but not over $\mathbb{Q}$. Consequently geometric $(n_4)$ configurations exist if and only if $n\ge18$ and $n\ne19$. A third configuration, self-polar and defined over a real cubic field, has only a single symmetry of order two. The same classification at $n=22$ and $n=26$ recovers Cuntz's configurations and finds three new combinatorial types at $n=22$ and $94$ at $n=26$, among them a $(26_4)$ configuration that is self-polar with respect to a conic without real points.

We prove co-RE-completeness, and thus undecidability, of the following problem: given a single (connected) polycube, decide whether it tiles 3D Euclidean space by translations. We reduce from Wang tiling using the decorated two-prime Sudoku construction of Greenfeld and Tao and a cyclic encoding adapted from OpenAI's 3D aperiodic tile, and apply a reduction of Kim to make the prototile connected (via faces). Dimension three is optimal: translational monotiling is known to be decidable in $\mathbb{Z}^2$ and for a single (possibly disconnected) polyomino in $\mathbb{R}^2$.

Large-scale information retrieval systems, including retrieval-augmented generation (RAG) and recommendation engines, widely use multi-layered hierarchical data structures for ultra-fast approximate nearest-neighbor search in high-dimensional vector spaces. However, the geometric conditions that ensure accurate and efficient greedy navigation remain poorly understood. In this work, we study the efficiency of greedy navigation on a hierarchy of proximity graphs constructed from \(n\) data points on the \(d\)-dimensional torus~$\mathbb{T}^d$. We identify a deterministic coverage condition under which, given any query $q\in \mathbb{T}^d$, greedy search returns a point within $(1+\varepsilon)$-factor of the distance to the closest point. This coverage property holds with high probability when the data is distributed as a homogeneous Poisson process, a Hermitian determinantal process, or a bounded-density Cox process, as long as $d = o(\log n/\log \log n)$. Under the same assumptions, the expected number of greedy hops for a fixed query is \(O\!\left(\exp\!\left(\tfrac12 d\log d+O(d)\right)\log n\right)\), yielding logarithmic expected hop count in fixed dimension.

Chekuri, Gupta, Newman, Rabinovich, and Sinclair [SODA'03] showed that $k$-outerplanar graphs can be embedded into trees and $\ell_1$ with distortion $2^{O(k)}$. Their result is perhaps the strongest evidence supporting the still-open planar $\ell_1$-embedding conjecture: planar metrics can be embedded into $\ell_1$ with constant distortion. However, the exponential dependency on $k$ in their distortion bound remains the state of the art. Their embedding is obtained by a so-called onion-peeling approach: removing one layer of the graph at a time at the cost of incurring $O(1)$ distortion multiplicatively, and recursively embedding the resulting $(k-1)$-outerplanar graph. In this paper, we devise a new onion peeling approach that peels $k/2$ layers off the input $k$-outerplanar graph at every step. As a result, we obtain the first embedding of $k$-outerplanar graphs into trees and $\ell_1$ with distortion $\operatorname{poly}(k)$, an exponential improvement over the best-known distortion bound [SODA'03]. Our result of embeddings into trees comes closer to the distortion lower bound $\Omega(k)$ for $k$-outerplanar graphs.

Let $P$ be a set of $n$ points in the plane. Given an integer $K$ with $1\le K\le {n\choose 2}$, the distance selection problem asks for the $K$-th smallest distance among all pairwise distances of the points of $P$. The problem has been studied extensively over the past four decades. Recently, Chan and Zheng (2023) gave a randomized algorithm with $O(n^{4/3})$ expected running time, while the best known deterministic algorithm runs in $O(n^{4/3}\log n)$ time. In this paper, we present a deterministic $O(n^{4/3})$-time algorithm for the problem, matching the best known randomized complexity. We also consider the more general bichromatic version of the problem, where two point sets $A$ and $B$ are given, with $m=|A|$ and $n=|B|$, and the goal is to find the $K$-th smallest distance among the $mn$ distances between points of $A$ and points of $B$. For this problem, the best previously known algorithm runs in $O((m\log n+n\log m+m^{2/3}n^{2/3})\log(m+n))$ time. We present a new deterministic algorithm with running time $O(m\log^2 n+n\log^2 m+m^{2/3}n^{2/3})$.

The existential theory of the reals asks whether polynomial constraints with integer coefficients have a real solution. We give a proof placing this problem in the counting hierarchy. The first argument is intended to expose the essential steps, and a separate analysis lowers the bound to $\exists \mathbb{R}\subseteq\textsf{BPP}^{\textsf C_3\textsf P}\subseteq\textsf C_4\textsf P$, the fourth level of the hierarchy. For each fixed $w$, sentences with $w$ alternating real quantifier blocks lie in $\textsf C_{9w+17}\textsf P$. We then treat exact semidefinite feasibility, PosSLP, square-root sum, geometric real counting, Euler characteristic, and complex feasibility in separate applications. The corresponding bounds include $\textsf{BPP}^{\textsf C_2\textsf P}$ for general SDP, $\textsf{BPP}^{\textsf{PP}}\cap\textsf{P}^{\textsf{NP}^{\textsf{PP}}}$ for PosSLP and square-root sum, and $\textsf{FP}^{\textsf C_4\textsf P}$ for total geometric real counting. Note: These proofs were discovered by ChatGPT after a series of conversations ending on September 29th 2026. A group of researchers has been working to digest the proof, and while the most essential arguments appear correct, we are endeavoring to give this result the treatment it deserves and a proper exposition and development to benefit of the community. However, on October 6th, OpenAI released a very similar result, with a slightly weaker bound. While we work to improve our exposition of this proof, the current version has been uploaded as a service to the community to compare the different proof techniques. While the listed author takes responsibility that the proofs appear to be correct, he has not played a nontrivial role in developing them, and believes the human value will be in good exposition and canonicalization of the results.

Procrustes-Wasserstein alignment jointly estimates a matching and rotation without supplied correspondences, but alternating minimization can stop at suboptimal solutions. Rubix solves the equally weighted planar problem globally under squared Euclidean loss. Each matching $\sigma$ of two centered $n$-point sets defines a complex correlation $z_\sigma=\sum_i\bar x_i y_{\sigma(i)}$. Their convex hull is the permutation polygon: supporting vertices give optimal matchings at fixed rotations, and the farthest vertex gives the global alignment. We prove the sharp bound of $n(n-1)$ vertices for $n\ge2$, answering Rote's rotation-assignment open problem. In exact arithmetic, assignment queries recover the polygon in $\mathcal O(n^5)$ operations. Assignment-based bounds extend the approach to three-dimensional rotations and partial matching at a supplied translation through branch-and-bound. On timed MPEG-7 shape pairs, Rubix attains every numerical reference value in 12 ms on average, 50 times faster than a rotation grid at the same accuracy. Its distances improve gravity-aligned matching of real 3D scans, shape retrieval and noisy crystal classification over alternating minimization.

The 2026 ACM SIGSPATIAL GIS Cup posed the following geometric challenge: Given a set of simple, pair-wise disjoint polygons, compute $k$ antennas (points) on polygon boundaries, maximizing the number of polygons with at least a fraction $\tau$ of their perimeter visible from the antennas. Contestants had 24 hours to produce the best possible solutions. We describe an approach that separates geometric visibility preprocessing from a portfolio of incremental combinatorial searches. A construction pool provides initial solutions with antennas restricted to polygon vertices; simulated annealing explores one-for-one antenna swaps, complemented by exact discrete one-swap descent, ruin-and-recreate, and elite crossover. A secondary objective rewards progress toward the service threshold without overriding the primary score. Candidate antennas are later expanded to include points in polygon-edge interiors. Our submitted solutions cover between 261 and 16,273 buildings across the nine parameter combinations, and the team was invited to present as one of the top entries. The code is available at https://github.com/JacobusTheSecond/giscup.

We study $\varepsilon$-relative approximation of mixed volumes of a fixed number $k$ of full-dimensional convex bodies in $\mathbb{R}^n$, given membership oracles and a known bound $B_n\subseteq K_i\subseteq R_0B_n$. We present a randomized algorithm that estimates any prescribed mixed volume within relative error $\varepsilon$ with probability at least $1-\delta$, using polynomially many oracle calls and bit operations in $n$, $\log R_0$, $\varepsilon^{-1}$, and $\log\delta^{-1}$ for fixed $k$.

We show that the worst-case combinatorial discrepancy of $n$ points in the plane with respect to axis-parallel rectangles is $\Theta(\log^{3/2}n)$. The known bounds were $\Omega(\log n)$ and $O(\log^{3/2}n)$; we prove the matching lower bound. It holds for random point sets: for every $A>0$, there is a constant $c_A>0$ such that, with probability at least $1-e^{-An}$, every coloring of $n$ independent uniform points in the unit square has an anchored rectangle with imbalance at least $c_A(\log_2n)^{3/2}$. The proof is surprisingly simple and elementary. It reveals one coordinate digit by digit. With overwhelming probability over the points, the conditional gains of an oscillation potential add up to $\Omega(\log^{3/2}n)$ over $\Theta(\log n)$ digits. Bounded differences control the fluctuations well enough for a union bound over all colorings.

Consider the "snaky" corridor $K_4 \subset \mathbb{R}^3$ from Problem 6.64 of arXiv:2511.02864: a tube of unit-square cross-section whose two right-angle turns lie in perpendicular planes, with a straight middle section of clear length $4$. We exhibit explicit rigid motions of connected bodies through $K_4$ and certify their volumes with the problem's own evaluation pipeline, unmodified, at the tight motion tolerances of its final scoring stage (translation $0.005$, rotation $0.05$ degrees). The certificates give $V^*(K_4) \ge 1.8355162$ at grid fineness $0.002$ and $V^*(K_4) \ge 1.8558404$ at grid fineness $0.001$, against the previously reported $1.81$; rerunning the pipeline's published best path under the identical configuration yields $1.8179428$, so every comparison is path against path under one fixed certifier. Three stages produce the record motion: a simple "staggered twist" backbone in which the whole 90-degree twist about the tube axis happens inside the second turn; evolutionary (CMA-ES) refinement, including a mixed-fidelity scheme that re-scores each generation's leading candidates on a grid twice as fine and lets those ranks steer recombination; and a gradient polish carried out directly at the finer carve resolution, guarded by periodic rebuilding of the frozen interpolation structure and by a penalty on control-pose spacing. These guards close three documented failure modes in which an optimizer inflates its own objective: frozen-structure inflation, spacing stretch, and exploitation of a coarse grid by optimizing and selecting on it. A staircase-based predictor with two grid bases, anchored by matching grid sensitivity, forecast the certificates to about $0.001$ before the runs. With the companion note's upper bound $V^*(K_4) \le 3.4083$, the problem now sits in the bracket $1.8558404 \le V^*(K_4) \le 3.4083$. All paths, notebooks and certified results are public.

Let $K_M \subset \mathbb{R}^3$ be the "snaky" corridor with unit-square cross-section: an infinite entry arm parallel to the $x$-axis, a middle arm parallel to the $y$-axis whose clear straight section has length $M$, and an infinite exit arm parallel to the $z$-axis, with the two turns lying in the $x$-$y$ and $y$-$z$ planes. Let $V^*(K_M)$ be the supremum of the volumes of connected bodies that can be moved continuously (by rigid motions) from the entry arm to the exit arm while remaining inside $K_M$. We prove $V^*(K_M) \le 7.8691$ for every $M \ge 3.53$ (Theorem A); by a sharper analysis of the same mechanism, $V^*(K_M) \le 4.2862$ for every $M \ge 2.61$ (Theorem B); and, by replacing the final analytic caps with a certified branch-and-bound computation over the compact family of entry tubes compatible with the forced events, $V^*(K_M) \le 3.4083$ for every $M > 2.2$ (Theorem C; computer-assisted, in double precision with conservative slack). In particular all three bounds apply to the corridor with $M = 4$ used in Problem 6.64 of Georgiev, Gómez-Serrano, Tao and Wagner (arXiv:2511.02864), and uniformly to every "turns far apart" reading of that problem. To the best of our knowledge, this is the first upper bound for the snaky-corridor 3D moving sofa problem; previously not even finiteness of $V^*$ had been recorded. This note proves upper bounds only; combined with the certified lower bound 1.8558404 from the author's separate certification work via the problem's own evaluation pipeline, the state of the problem becomes $1.8558404 \le V^*(K_4) \le 3.4083$. Theorems A and B are elementary and self-contained: a first-crossing (elbow) event forces a definite tilt of the body's own entry tube, and Fubini-type chord estimates for tilted tubes cap the volume. Theorem C certifies, by the same forced-event skeleton, the largest corridor volume that any admissible entry tube can carry.

Multiparameter persistent homology is a rapidly developing branch of topological data analysis that improves the robustness of single-parameter persistent homology to outliers, while still capturing the metric characteristics of the data. However, a notable limitation is its lack of scalability. In this paper, we introduce a novel approach for efficiently computing 2-parameter persistent homology on large point sets. Our work extends the Flood filtration, originally developed for single-parameter persistence. Our construction, called the sublevel Flood bifiltration, offers a scalable approximation of the sublevel offset bifiltration. We show that it benefits from theoretical stability properties and describe how to compute it efficiently. We demonstrate the performance of our approach in classification tasks on low-dimensional synthetic datasets, where density awareness is critical, as well as on real-world time series datasets.

A kernel $k(x,y)$ is LSHable if there exists a locality sensitive hashing scheme $H$ such that $k(x,y)=\Pr_{h\sim H}[h(x)=h(y)]$ for all $x,y$. This notion plays a key role in efficient kernel methods in high dimensions. In this work, we show that the $p$-exponential kernel $k(x,y)=\exp(-\lVert x-y \rVert_p)$ is LSHable in bounded regions for all $1<p\leq2$. Previously, this was known only for $p=1$. Our new "mosaic LSH" scheme is based on a Poisson hyperplane process with hyperplanes sampled as $\ell_1$-biased $p$-stable vectors, for which we develop efficient sampling procedures. As applications, our results yield new and efficient density estimation methods based on LSHability for those $p$-exponential kernels.

Given a set of point robots $\mathcal{R}$ in the Euclidean plane and a target circle $\mathbf C$ enclosing all robot positions, the Min-Max Uniform Circle Formation (MMUCF) problem requires the robots to move to distinct positions on $\mathbf C$ such that the final configuration forms a regular $n$-gon while minimizing the maximum distance traveled by any robot. Uniform circle formation is a fundamental coordination task in swarm robotics with applications in perimeter monitoring, surveillance, boundary coverage, and pattern formation. The literature does not address the optimization of the maximum individual displacement during the formation process. In this work, we study the min–max versions of the circle formation and uniform circle formation problems, where the goal is to minimize the maximum distance traveled by any robot. We consider these problems under the $\mathcal{ASYNC}$ model, where robots are autonomous, anonymous, identical, homogeneous, oblivious, and silent, and operate under the Look–Compute–Move model with non-rigid motion. We first give necessary conditions for a deterministic solution and then present deterministic, distributed, and collision-free algorithms that form a circle and a uniform circle in finite time while minimizing the maximum movement. The algorithms ensure that robots reach distinct positions on the circle and, in the uniform case, equally spaced positions on $\mathbf C$ under the considered model.

Estimating the volume of a high-dimensional convex body is a fundamental problem in theoretical computer science. Given a quantum membership oracle for a convex body $K\subset\mathbb{R}^d$, we show that estimating $\mathrm{vol}(K)$ to relative error $\varepsilon$ takes $\widetilde O(d^{5/2}+d^{3/2}/\varepsilon)$ queries. This improves the previous quantum upper bound $\widetilde O(d^3+d^{9/4}/\varepsilon)$ of Chakrabarti et al. (ACM TQC 2023) and Cornelissen–Hamoudi (SODA 2023), and achieves a larger quantum speedup over the currently best classical upper bound $\widetilde O(d^{7/2}+d^3/\varepsilon^2)$ of Jia et al. (JACM 2026). Our quantum algorithm combines two new ingredients: an input-dependent effective spectral-gap analysis of quantum walks based on uniform classical warm-start mixing bounds, and a single quantum estimator for products of normalizer ratios in simulated annealing based on classical bridge sampling. We also prove an $\Omega(d)$ quantum query lower bound for constant relative error, improving the previous $\Omega(\sqrt d)$ lower bound.

We study the optimal gathering problem over a finite set of designated meeting nodes for asynchronous, anonymous, and oblivious mobile robots on an infinite grid under crash faults. The robots have global visibility and strong multiplicity detection, but share neither a coordinate system nor chirality. The objective is to gather all non-faulty robots at a Weber Meeting Node, minimizing the total Manhattan distance from their initial positions. Up to $n-2$ robots may crash permanently, and such crashes are indistinguishable from arbitrary delays. Existing approaches often rely on a designated robot to break symmetry, whose crash may block the remaining robots indefinitely. Instead, our approach enables every robot to independently select the same target from its snapshot, while target-dependent restricted shortest paths preserve the target as a Weber Meeting Node. We prove that, under strong multiplicity detection, optimal gathering is impossible from certain fully symmetric configurations. For all remaining configurations, our algorithm CrashTolerantWeberGathering() selects a unique common target, preserves its optimality throughout the execution, and allows non-faulty robots to progress without waiting for crashed robots, thereby guaranteeing gathering in finite time.