Aug 2026· 1 citation· ⚡ 1 influential· 21 references
Computer ScienceMathematics
Abstract
Let $p_0,p_1,\ldots,p_N$ be points of the unit ball of $\mathbb R^d$, processed in a prescribed order. We study the insertion cost $\sum_{i=1}^N\lVert p_i-x_{i-1}\rVert^\alpha$, where each $x_{i-1}$ is computed from the previously observed points. The input-order path is sensitive to the input distribution but can repeatedly pay the diameter under adversarial input. The center star has controlled worst-case scale but ignores the observed sequence. We compress the past into one point through $x_0=p_0$ and $x_i=\gamma x_{i-1}+(1-\gamma)p_i$, where $0\leq\gamma\leq1$. Thus $x_i$ is an exponentially weighted memory of the input, maintained with one $d$-dimensional point of working state. For independent uniform points, the stationary insertion length is nonincreasing in the usual stochastic order as $\gamma$ increases. If $d\geq2$ and $\alpha>0$, every optimal constant parameter for $N$ insertions satisfies $1-\gamma_N^*=\Theta(N^{-1/2})$. We determine its asymptotic constant and the resulting $\sqrt N$ correction, with explicit bounds in $d$ and $\alpha$. For $\alpha=1$, the leading expected tree length equals that of the center star and is strictly smaller than those of the endpoint constructions. For $\alpha=2$, the minimizer is unique for $N\geq2$, with $1-\gamma_N^*=N^{-1/2}-\tfrac12N^{-1}+O(N^{-3/2})$. For arbitrary input sequences and fixed $0\leq\gamma<1$, the largest asymptotic mean cost is $(2/(1+\gamma))^\alpha$ for $0<\alpha\leq3$, strictly below the path value when $\gamma>0$. Among fixed nonnegative weighting rules whose contributing points have the same average distance in the input order from the most recent point, exponential weighting is within a factor smaller than $1.161^\alpha$ of the best adversarial value in dimension at least two; this ratio tends to one as that average distance grows.
We study the edge-power cost of the labelled tree generated by the $\gamma$-strategy, a constant-gain rule for sequential Euclidean connections. Starting with $x_0=p_0$, each input point $p_i$ is attached to $x_{i-1}$, and the state is updated by $x_i=\gamma x_{i-1}+(1-\gamma)p_i$. Retaining $x_i$ subdivides the insertion segment into a spine edge and a leaf edge. The memory parameter $\gamma$ controls how long earlier points influence subsequent attachment points. We minimize the sum of the $\alpha$-powers of the edge lengths under independent uniform input and arbitrary input sequences. For uniform points in the unit ball, the stationary problem has a transition at $\alpha=1$. Its continuous extension is minimized at the boundary for $0<\alpha\leq1$, while every global minimizer is interior for $\alpha>1$. We determine the finite optimizer in the joint window $\alpha_N=1+\varepsilon_N$, $\varepsilon_N\log N\to\lambda$. Below an explicit threshold it lies on the $N^{-1/2}$ scale, at the threshold its scale is $\sqrt{\log N/(N\log\log N)}$, and above the threshold it approaches an explicit stationary root with two computable corrections. A second threshold identifies the governing correction, and differentiated estimates prove eventual uniqueness. At $\alpha=3d+8$, the linear coefficient at the stationary endpoint changes sign and a branch of strict local maxima enters the parameter interval. For arbitrary input sequences, the optimal parameter and asymptotic worst-case edge-power cost per point are explicit for $0<\alpha\leq3$. At high powers, periodic antipodal block inputs give explicit lower bounds which, with a separation argument, show that the optimized cost is asymptotic to $2\log2/\log\alpha$. Exact results for powers two and four, a rational recursion for every even power, and a high-dimensional expansion complete the analysis.
Let $\mu$ be an $n$-AD-regular measure in $\mathbb{R}^d$. Chousionis, Garnett, Le and Tolsa [CGLT] proved that $\mu$ is uniformly $n$-rectifiable if and only if the square function built from the density differences $\Delta_\mu(x,r)=\mu(B(x,r))/r^n-\mu(B(x,2r))/(2r)^n$ satisfies a Carleson condition. In this paper we show that the same characterization holds if the density is first composed with a function $F$ which is bi-Lipschitz on the interval $[c_0^{-1},c_0]$ determined by the AD-regularity constant $c_0$. The main example is $F=\log$, introduced in [Le], for which the square function takes the scale-invariant form $\Delta_\mu^{\log}(x,r) = \log\bigl(\mu(B(x,r))/\mu(B(x,2r))\bigr)+n\log 2$. We give a complete proof, extend the statement to the smooth square functions of [CGLT], where the density is replaced by the convolution of $\mu$ with a Gaussian or a more general radial kernel, discuss what happens when $F$ is not bi-Lipschitz, and treat the case $\mu(\mathbb{R}^d)<\infty$, where the behavior of $F$ near zero enters in only one of the two implications. We also show that the qualitative characterization of $n$-rectifiable measures by Tolsa and Toro [TT], in terms of the same square function at $\mu$-almost every point, holds after composition with any locally bi-Lipschitz $F$. This requires neither AD-regularity nor doubling, and for $F=\log$ the condition $\lim_{r\to0}\Delta_\mu(x,r)=0$ becomes $\lim_{r\to0}\mu(B(x,r))/\mu(B(x,2r))=2^{-n}$.
The dense result substantially generalizes a theorem of Bansal and Spencer (2020) for Rademacher inputs and gives an efficient $O(\sqrt{n})$ bound for Gaussian inputs, as conjectured by Gamarnik et al. (2022).
A set of intervals $I = \{ I_1, I_2, \dots, I_n \}$ forms a simple chain if, for every $2\leq i \leq n-1$, interval $I_i$ overlaps only with $I_{i-1}$ and $I_{i+1}$. We show that a deterministic memoryless one-directional revoking algorithm achieves a competitive ratio of $2(1 - 1/\sqrt{e}) \approx 0.786$ on the simple chain in the random order model, hence performs worse than the basic greedy algorithm without revoking that has a competitive ratio of $(1 - 1/e^2) \approx 0.864$, but better than any deterministic revoking algorithm in the adversarial model that has a competitive ratio of at most $0.75$. The proof of the latter also leads to a lower bound of $n/4$ for the advice complexity.
Yaqiao Li, Ali Mohammad Lavasani, D. Pankratov· Theoretical Computer Science· 0 citations
We study a null model of high-dimensional projection pursuit: we are given $M$ points sampled i.i.d. from a standard gaussian in $N$ dimensions, where $M,N\to\infty$ with $M/N\to\alpha\in(0,\infty)$. Our goal is to characterize the possible empirical distributions of these points'projections along a data-dependent direction $x$, which ranges over either the sphere $S_N=\sqrt{N}\mathbb{S}^{N-1}$ or cube $\Sigma_N=\{-1,+1\}^N$. We consider this problem in an algorithmic setting, where $x$ must be the output of an algorithm with dimension-free Lipschitz dependence on the input; this class of algorithms includes general gradient-based methods such as Langevin dynamics and approximate message passing (AMP). Our main result exactly characterizes the set of empirical distributions attainable by this class in terms of a one-dimensional stochastic control problem. As a consequence of our main result, we obtain exact algorithmic thresholds for optimizing the Hamiltonian of a spherical or Ising perceptron model with general bounded continuous activation. For the spherical problem, independent work of Montanari and Zhou (2024) characterized the empirical distributions attainable by a related two-stage AMP algorithm, also in terms of stochastic control. Our proof of hardness builds on the branching overlap gap property introduced in earlier work by the first two authors. Our main innovation is to develop stochastic control theory within the branching OGP framework, significantly expanding the settings in which it locates an exact algorithmic threshold. Notably, our methods apply even though the non-algorithmic problem of characterizing all feasible projections remains a major outstanding challenge. For the matching algorithmic result, we construct a new incremental AMP algorithm that acts on a Brownian-bridge revelation of the gaussian disorder and simulates the same family of controlled SDEs.
Brice Huang, Mark Sellke, Ni-Ke Sun· 1 citation· ⚡1
Let $x_1,\ldots,x_n$ be independent standard Gaussian vectors in $\mathbb{R}^d$. An \emph{ellipsoid fit} is a matrix $S \succeq 0$ such that $x_i^\top S x_i =d$ for every $i$, so that all the points lie on the boundary of the centered ellipsoid $\{ x : x^\top S x = d\}$. Saunderson, Parrilo and Willsky conjectured that, as $n,d \to \infty$, this semidefinite feasibility problem undergoes a sharp transition at $n \sim d^2/4$. We prove this conjecture. If $\lim \sup n/d^2 = \alpha^*<1/4$, then, with probability tending to one, an ellipsoid fit exists; moreover, one can choose $S$ with all eigenvalues in a fixed interval $[\lambda_- , \lambda_+] \subset (0,\infty)$ depending only on $\alpha^*$. Conversely, if $\lim \inf n/d^2>1/4$, then, with probability tending to one, no ellipsoid fit exists, without any spectral restriction. Our proof builds on the Gaussian-equivalence framework developed by Bandeira and Maillard (2025) and closes the two gaps left open in their work: establishing exact fitting and removing the operator-norm constraint. On the satisfiable side, the new ingredients are a head-tail decomposition of the dual vector, exact correction of the sparse head constraints, and a Gaussian comparison principle for the low-influence tail. On the unsatisfiable side, we split a candidate into a low-rank spectral head and a Schatten-3 diffuse bulk, Gaussianize the bulk conditionally on the head, and apply a projected Gordon escape argument. The threshold is governed by the statistical dimension $d(d+1)/4$ of the positive semidefinite cone.
Theodor Misiakiewicz, Garrett Wen· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
