Papers

We study the problem of learning nearest-neighbor maps from adaptive queries, which is equivalent to the following problem of reconstructing a hidden set $H$ via a nearest-neighbor query oracle. Let $K \subset \mathbb{R}^d$ be a compact domain in a normed space $(\mathbb{R}^d,\| \cdot\|)$ and let $H \subset K$ be a hidden set of $n$ points. Upon querying $q \in K$, the oracle returns some $h \in H$ with minimum distance from $q$. How many queries are required to exactly recover $H$? Previous work has studied this question in specific domains, namely the Boolean hypercube and the $\ell_2$-unit sphere. We generalize previous work and prove the tight worst-case query complexity bound of $\Theta(n\kappa)$, where $\kappa$ is the kissing number of the underlying norm. In the Euclidean norm, obtaining tight asymptotic bounds on $\kappa$ is a significant open question, although it is known that $\kappa = \exp(\Theta(d))$. Our second set of results shows that an exponential dependence on $d$ is required even in natural Euclidean domains: $\exp(\Omega(d))$ queries are needed in the ball, even when $n=2$, and $n\exp(\Omega(d))$ queries are needed in the cone. Lastly, we prove a sharper upper bound in the Euclidean sphere. Here, $d$ can be replaced by $\min(n,d)$ via a dimension reduction preprocessing step. This is a randomized version of a procedure due to Prabhu-Woodruff (ICML 2024) where we improve the query complexity from $O(nd)$ to $O(\min(n,d))$. This reveals a striking contrast between the sphere and the ball: when $n = O(1)$, the sphere admits an $O(1)$ query algorithm, whereas the ball requires $\exp(\Omega(d))$.

Trait-induced merge trees (TIMTs) provide a robust topology-based method for selecting and browsing feature level sets in multivariate data by analyzing the distance field induced by a user-specified trait in attribute space. Existing TIMT computations typically sample this distance field at mesh vertices and assume piecewise-linear interpolation, although the Euclidean distance-to-trait function is generally not piecewise linear on the original mesh. As a result, the resulting merge tree may miss zero-valued features and may perturb the locations and values of minima and merge events. We study the exact computation of TIMTs for piecewise-linear bivariate fields, focusing first on point traits. We show that the restricted sublevel sets inside each tetrahedron are convex and therefore have trivial local merge-tree structure, implying that global topological changes arise only through gluing across simplex boundaries. Based on this observation, we construct a weighted graph whose merge tree is isomorphic to the exact merge tree of the induced distance field. We further relate TIMTs to Jacobi sets, showing how nonzero edge events of the TIMT are localized by the singular structure of the underlying bivariate map. We establish a theoretical upper bound on the error of the vertex-sampled linear interpolation, expressed in terms of the maximum length of projected mesh edges in the range. We discuss extensions to line, line-segment, and finite point-set traits, and implement the method robustly using CGAL and VTK, demonstrating results on both synthetic and real-world datasets.

Recent advances in combinatorial dynamical systems that generalize the classic discrete Morse theory have prompted algorithmic studies of combinatorial vector fields. In this regard, authors in [7] recently proposed the concept of Conley-Morse persistence barcode that summarizes the continuation of invariant sets in an evolving vector field through homological persistence. They proposed an algorithm to compute this barcode using a filtration of the so called index pairs on a poset called transition diagram. The algorithm becomes costly due to multiple runs of zigzag persistence it executes on filtrations of `unwieldy' structures of index pairs. We overcome this difficulty by replacing the index pairs with blocks, which are structurally much simpler. These replacements need reversal of certain relations in the transition diagram resulting in a much simpler algorithm. The algorithm works by updating matrix decompositions akin to computing `vineyard' in standard persistence.

We seek to disentangle the hardness of finding a Hamiltonian path or cycle from the hardness of finding a non-crossing path or cycle by giving a direct reduction from 3-SAT to the non-crossing Hamiltonian path and cycle problems on non-planar graphs. Prior hardness proofs proceed by reduction to planar graphs, where every path is automatically non-crossing; this conflates the two sources of difficulty and leaves unclear why forbidding crossings on the path alone makes the problem hard. Our reduction places the difficulty squarely in the non-crossing constraint, avoids planar gadget constructions, and yields a more transparent proof that may be easier to extend to related problems.

In this paper, we build upon the analysis initiated by Gennadiy Averkov and Matthias Schymura (2022) and establish that the number of distinct columns of a $\Delta$-modular matrix $A \in \mathbb{Z}^{m \times n}$ of rank $m$ is $O(m^3 \Delta)$. This upper bound was previously known only for odd values of $\Delta$. Recall that a matrix is called $\Delta$-modular if the maximum of the absolute values of its $m \times m$ minors equals $\Delta$.

The Intersection Euler Characteristic Profile (Intersection ECP) of $k$ colored point clouds $X_1, \ldots, X_k \subset \mathbb{R}^d$ is the Euler characteristic $\chi(\bigcap_{i=1}^k \mathcal{U}(X_i; t_i))$ of the overlap of their ball unions—an integer-valued, multiparameter invariant of their topological interaction across scales. Its organizing framework is the Euler calculus on constructible functions: the profile is equally the Euler integral $\int \prod_{i=1}^k \mathbf{1}_{\mathcal{U}(X_i; t_i)} \, d\chi$ of the product of the $k$ data-dependent offsets, and this identity—our Intersection Theorem—is a commuting square interchanging geometric intersection and algebraic product. The invariant is rigid-motion invariant, scale-equivariant, and $L^1$-stable, and it is canonical: among pointwise-Euler interaction profiles it is the one forced by separation and normalization, the top floor of a spectrum of descriptors graded by how many clouds meet. For $n$ points a single sorted Alpha-complex sweep computes it in $O(n^{\lceil d/2 \rceil} \log n)$ time with no persistence reduction, worst-case optimal in even dimensions. Where the Euler characteristic cancels, a relative-homology refinement resolves the finer interaction and is stable in the two-parameter interleaving distance. Finally, for increasingly dense samples the profile and its refinement are consistent, recovering the (relative) homology and Euler characteristic of the underlying shapes—in the inverse limit for compact sets, and, under positive reach, persistently and with explicit sample complexity.

The fixed-parameter algorithm for coordinated motion planning on discretized simple polygons (ICALP 2026) rests on a single-port sector decomposition: grid vertices are labelled by the minimum number of bends needed to reach an oriented terminal. We develop the structure theory of this decomposition on grid domains with holes. Once its endpoint convention is made precise, bend distance extends to a canonical piecewise-affine function on the domain, and the sector graph is the parallel-edge shadow of the Reeb multigraph of that function. For a finite pure planar cubical domain with $h$ holes this yields $\beta_1(\Gamma_p) \le \beta_1(R_{f_p}) \le h$, together with a linear-time computable feedback set of at most $h$ sector vertices; coordinate-level one-hole examples show that the finer hole-free geometry – unique predecessors and straight baselines – fails. On hole-free cubical disks the machinery is exact: every positive sector is the one-sided extrusion of a unique straight parent interface, and the two-port common refinement has treewidth exactly $c_2^\square=3$, although sector count, cycle rank, and feedback number are unbounded already there. The endpoint precision is necessary rather than cosmetic: under the literal reading of the source's definition, one hole-free unit square has sector graph $C_3$, falsifying the single-port tree lemma; the augmented convention used here is exactly the metric computed by the source's own layering procedure. We do not obtain an $f(k,h)n^{O(1)}$ algorithm; the paper supplies the structural first step and a falsification tool for that program.

We consider spanners for point sets lying in the hyperbolic plane or on a closed hyperbolic surface with the restriction that spanner edges are not allowed to cross. This is a natural generalization of non-crossing Euclidean spanners. Thus, the resulting spanner graphs are embedded in the hyperbolic plane or on the hyperbolic surface. As our main contribution, we show that there are sparse $(1+\varepsilon)$-spanners for these problems when we are allowed to use Steiner points: - on the hyperbolic plane we get a non-crossing Steiner $(1+\varepsilon)$-spanner with $\mathcal{O}(n / \varepsilon^2)$ edges, - on hyperbolic surfaces of genus $g$ we get a Steiner $(1+\varepsilon)$-spanner with $\mathcal{O}(n / \varepsilon^{3/2} + g/\varepsilon^2)$ non-crossing edges, or with $\mathcal{O}(n / \sqrt{\varepsilon} + g/\varepsilon)$ edges that are allowed to cross. In particular, our spanners on surfaces have sparsity with linear dependence on $g$, rather than the easier-to-attain exponential dependence, and the terms $n/\varepsilon^{3/2}$ and $n/\sqrt{\varepsilon}$ match the current best Euclidean results for plane and crossing Steiner spanners, respectively. As a corollary of our non-crossing spanner and techniques from the existing literature on light spanners and minor-free TSP, we get an EPTAS for TSP on hyperbolic surfaces. Our surface constructions rely on the thick-thin decomposition, a standard tool for studying hyperbolic surfaces. For convex hyperbolic polygons, we introduce an analogous neck decomposition. We give algorithms that compute the thick-thin decomposition of a genus-$g$ surface in $\mathcal{O}(g^4\log g)$ time and the neck decomposition of an $n$-vertex polygon in $\mathcal{O}(n)$ time.

Tropical geometry turns a metric graph into a flat torus, its tropical Jacobian, and measures distances between the images of its points by a closest vector problem on the period lattice. We prove that for points of the graph this problem is solved by geodesics: the squared tropical polarization distance equals the path metric minus the Arakelov-Green (AG) distance, an effective-resistance kernel given in closed form by the Laplacian pseudoinverse. Equivalently, the AG distance and the path metric are the minimal energies of real and of integral unit flows, and the squared tropical distance is exactly their integrality gap. The full tropical distance matrix is thus computable in cubic time. On this identity we build CLEARMIND, a training-free descriptor of 3D neuronal morphology. A reconstruction is reduced to its branching skeleton, neurite tips near the soma are joined to it, short bridges are contracted, and the AG matrix of the result is summarized by its spectrum. Every step has an exact algebraic description; for instance, the period matrix records the shared soma-to-tip path lengths, and the spectrum has exactly one positive eigenvalue, so its absolute values determine it. The signature needs no lattice search, is invariant to vertex order, rigid motions and subdivision, and is Lipschitz in the edge lengths. On ACT-4, JML-4 and BIL-6, appending the 64-dimensional spectrum improves a point-cloud GNN and MorphVAE on every dataset, by up to 20.3 points; a Tree-LSTM with the spectrum outperforms every reimplemented baseline; and an MLP on the spectrum alone is a competitive classifier that surpasses every reimplemented deep baseline on ACT-4. On BREC, a GIN with AG eigenvector encodings distinguishes 70.0% of the pairs beyond the 1-WL limit, including 33% of the CFI pairs, more than PPGN (23%) and I$^2$-GNN (21%), and the spectrum alone separates 217 of 400 pairs without training.

Persistent Homology (PH) is an important tool in Topological Data Analysis for point clouds, but can be prohibitively expensive for large datasets. A practical approximation is to compute PH on a smaller subset of representative points, known as landmarks. Existing landmark selection methods mainly address challenges such as outlier contamination rather than restoring the topological features of the full dataset. To select topologically relevant landmarks, we propose a landmark selection method based on Hodge Laplacian. It assigns each point a topological relevance score based on its harmonic participation and selects points with high scores as landmarks. By quantifying each point's participation in global homological structures, our method restores the PH of the original point cloud more accurately than geometric baselines and a method built upon local PH on both synthetic and real-world datasets.

Robotic construction systems often treat the material system and the robot as separate design problems, locating intelligence primarily in hardware, sensing, motion planning, and control. This project instead investigates how geometric intelligence can be encoded within architected material systems to simultaneously address requirements for robotic grasping, self-alignment, reversible connection, structural performance, and three-dimensional aggregation. We introduce a self-aligning compound nested lattice module composed of conjoined cuboctahedral-octahedral units. The cuboctahedral features of the modules provide defined surfaces for robotic grasping and alignment, while the octahedral features incorporate screw-releasable snap-fit connectors and corresponding receptors. Additionally, we present a nested arrangement that enables interlocking aggregation along the x, y, and z axes. We demonstrate the system through furniture and architectural scale structures assembled using both a robotic arm and mobile assembler. The resulting configurations include seating, spanning structures, surfaces, and vertical frames. Compression testing of the compound module produced a stiffness of 4,556 N/mm, a maximum load of 3,445 N, and a compressive modulus of 17.5 MPa. The modules can also be disassembled and reused across different configurations, supporting reconfigurable and circular construction.

We develop a new algorithm for computing (persistent) discrete homology of graphs using reduction to zero differentials and active enumeration. This allows us to compute the fourth homology group of the Greene sphere, along with several previously unknown groups. We also show that persistent discrete homology computes faster than simplicial homology of Vietoris-Rips complex in the high-noise non-metric settings, making it a better choice for noisy data sets.

We present efficient algorithms for the bottleneck path problem in two geometric settings that arise naturally in applications: directional-antenna graphs in the plane with antenna angles bounded from below by a constant, and visibility graphs whose vertices lie on or above a 1.5-dimensional terrain, both with Euclidean distances as edge weights. We provide near-linear algorithms for the corresponding decision problems, namely, determining whether the subgraph obtained by retaining all edges with weight at most some threshold ${\bf bn}$ contains a path from $s$ to $t$. We then use the decision procedures to obtain algorithms for the bottleneck path problem that run in $O^*(n^{8/7})$ randomized expected time, where $n$ is the input size and the $O^*(\cdot)$ notation hides subpolynomial factors. Within the same performance bounds, we can also solve the bounded-hop version, in which we only consider $s$-$t$ paths with at most $k$ edges, for a given integer $k < n$.

For parameters $\alpha,\beta \geq 1$, a spanning tree $T$ of a weighted graph $G$ rooted at a designated vertex $r$ is called an $(\alpha,\beta)$-shallow-light tree (SLT) if (i) for every vertex $v$, $d_T(r,v) \leq \alpha \cdot d_G(r,v)$ (root-stretch $\alpha$), and (ii) $w(T) \leq \beta \cdot w(\mathsf{MST})$ (lightness $\beta$). The pioneering work of Khuller, Raghavachari, and Young (SODA 1993) constructed $\left(1+\epsilon, \tfrac{2}{\epsilon}+1\right)$-SLTs for general weighted graphs, and proved that this tradeoff between root-stretch and lightness is tight even for series-parallel graphs. They further asked whether even a slight improvement, namely reducing the lightness to $\tfrac{2-c}{\epsilon}$ for any constant $c>0$, is possible in the Euclidean plane. We resolve this longstanding question in the affirmative. Specifically, we show that every Euclidean instance admits an SLT with root-stretch $1+\epsilon$ and lightness at most $\left(\frac{5}{3} + o_\epsilon(1)\right) \cdot \frac{1}{\epsilon}$, thereby significantly improving upon the longstanding $2/\epsilon$ barrier. As our second main result, we provide a construction of SLTs in the Euclidean plane, with root stretch $1+\epsilon$ and lightness at most $\left(\frac{2\pi}{\sqrt{4\pi^2+1}}+o_\epsilon(1)\right)\frac{1}{\epsilon} \approx (0.987+o_\epsilon(1))\frac{1}{\epsilon}$. Notably, this reduces the leading $2/\epsilon$ term in the lightness bound by more than a factor of two, and comes quite close to the lower bound of $\left(\frac{2\pi}{2\pi+1} +o_\epsilon(1))\right) \cdot \frac{1}{\epsilon} \approx (0.862 +o_\epsilon(1))\frac{1}{\epsilon}$ by Elkin and Solomon (FOCS 2011).

The well-known persistence algorithm summarizes the evolution of homological cycles into what is called a barcode while scanning an input simplicial filtration. We show that this summarization process can be enriched by monitoring other algebraic structures that weave through different dimensions. In particular, we propose an algorithm to monitor the $(p+1)$-chains that make $p$-cycles to be $p$-boundaries and then morph into $(p+1)$-cycles. In effect, we get extra bars called links connecting the bars in dimension $p$ with the bars in dimension $p+1$ in the persistence barcode. The links produce extra barcodes, which we call link barcodes in addition to the usual ones obtained by standard persistence. The link barcodes, as such, are not stable. However, we can make them stable using a fixed “reference” filtration. We apply the link barcodes to the graph isomorphism problem and to the link prediction problem in temporal networks exhibiting its discriminating power through these experiments.