CS Paper Radar

Bellman--Shoreline Search in Arbitrary Dimension: Exponential Vector Oscillators, Active Memory, Precession, and Effective Computability

Florentin Koch

cs.CG math.MGmath.OC ·submitted 2026-08-29 05:29 UTC · v1
theory

Abstract

We study online search for an unknown affine hyperplane in $\mathbb{R}^D$, for arbitrary fixed finite dimension. Building on a companion self-similar cell reduction and support-function formulation, we ask how the mechanism changes as the normal space grows from $\mathbb{S}^0$ to $\mathbb{S}^{D-1}$. In $D=1$, alternation and productivity yield an equal-ripple principle and the exact stationary constant $9$. In $D=2$, the analogous relative equilibrium is a logarithmic spiral whose bottleneck chord imposes tangency and selects the pitch. For exponential orbits $Γ(σ)=e^{κσ}ω(σ)$, we develop log-directional geometry, exponentially discounted memory, gauges, and recursive hyperspherical parametrizations. Without a shape ansatz, the bottleneck admits a certificate supported by at most $D$ historical suppliers, and at globally worst phases the current point lies on the active face. Within regular chambers we derive exact variation, tangency, pitch, age, and, in $D=3$, delay-system identities. Odd-dimensional obstructions, antipodal subclasses, and harmonic towers provide constraints and explicit candidate families but are not claimed globally optimal. Finally, the N-COMP theorem shows that $C_D^*$ is a computable real for every fixed finite $D$ and that algebraic polygonal $\varepsilon$-optimal cells can in principle be synthesized. Numerical screening through $D=10$ is kept separate from the proved results.

Comment
26 pages, 5 figures. Zenodo DOI: 10.5281/zenodo.22153950

Closest papers

Nearest neighbours by meaning across the whole index.

Bellman Search in Arbitrary Finite Dimension: A Self-Similar Cell Theorem and Effective Computability of Planar Shoreline Search

cs.CG math.MGmath.OC ·2026-08-29 ·Florentin Koch
theory similarity 0.62
Abstract · 23 pages, 1 figure. English revision 8.3

A shoreline-search path starts at the origin and must meet an unknown affine line, without knowing either its normal or its distance. We first establish a self-similar reduction theorem for homogeneous search problems whose historical information is a record profile updated by pointwise maximum. Two quasi-returns of the normalized state delimit a block that renews the required profile by itself; a short connector closes this block into a cell. Every finite-ratio path can therefore be approximated, with arbitrarily small loss, by repetitions of a single cell at all scales. The main chain is then made effective. A finite coding of the state space computably bounds the scale factor and normalized length of a nearly optimal cell. For planar Shoreline search, the support function of the convex hull gives an exact cell functional. A one-sided polygonalization then reduces the problem to a computable number of vertices, after which quantifier elimination decides whether a polygonal cell exists below a rational threshold. It follows that the optimal deterministic planar Shoreline value $C_2^*$ is a computable real: for every rational $ε>0$, an algorithm terminates with a rational interval of width at most $ε$ containing $C_2^*$. Additional results---sliding memory, Bellman transitions, deadlines, geometric filters, and relative equilibria---are presented separately as a toolbox for certified computation and for the study of spiral rigidity; they are not used in the computability proof.

0.60

The logarithmic spiral is optimal for shoreline search: a computer-assisted proof

cs.CG math.OCmath.MG ·2026-09-21 ·Alexander Temerev
similarity 0.61
Abstract · 20 pages (13 of main text, then four appendices), 3 figures, 1 table

A ship starts at a point of the plane and moves at unit speed; it has to reach an unknown straight line, of which neither the distance nor the direction is known. The competitive ratio of a path is the supremum, over all lines, of the time at which the line is reached divided by its distance. Baeza-Yates, Culberson and Rawlins conjectured that a logarithmic spiral, with ratio $C_{\mathrm{sp}} = 13.8111351794611\ldots$, is optimal. We give a computer-assisted proof. Paths are arbitrary: the distance from the start and the polar angle may both decrease. The proof lifts the set of found directions to the universal cover of the circle, where unfolding the polar angle can only increase it (Kneser-Poulsen on the line); a bookkeeping inequality with a monotone final source then bounds the covered measure by the reward of a three-state relaxed control problem, in which inward motion is an ordinary control and excursions below the guaranteed disk are impulses. An explicit $C^1$ storage function, a tensor cubic B-spline plus a closed-form term, satisfies the dissipation inequalities of that problem at the spiral's level and is tight only at the spiral; this is verified with about $10^6$ boxes of Arb ball arithmetic, an exact jet and an interval Hessian at the spiral.

0.44

TSP instances that require exponentially many subtour elimination constraints

cs.DM math.CO ·2026-11-11 ·Eleonora Vercesi, Austin Buchanan
theory similarity 0.52
Abstract

We construct pathological TSP instances that require exponentially many subtour elimination constraints (SECs) in the sense that, if a smaller collection of SECs is imposed, then the Dantzig-Fulkerson-Johnson model returns a disconnected solution costing less than an optimal tour. For asymmetric instances on $n$ vertices, we prove a growth rate of \(Ω(φ^n)\), where \(φ\approx 1.618\) is the golden ratio. A node-splitting reduction gives metric instances with \(Ω(φ^{n/2})\) growth. We also give instances in the plane under the Euclidean, Rectilinear, and Maximum metrics that require exponentially many SECs. Concorde struggles on them, with solve times growing exponentially despite tiny integrality gaps.

0.28

The Quantum Sphere: A Physically Realizable Optimization Benchmark with Provable Linear Convergence in White- and Black-Box Settings

cs.NE quant-ph ·2026-09-30 ·Ofer M. Shir
benchmarktheoryhot direction similarity 0.51
Abstract

We revisit an established Quantum Control objective, characterize its exact local metric geometry, and reposition it as a rigorous benchmark for Search and Optimization. The trap-free topology of the landscape, established two decades ago, guarantees unhindered optimal pathways, but global topology alone does not govern convergence speed. Although the so-called Quantum Sphere is defined by the fourth power of the control field, we show that its yield gap admits an exact representation as a nonnegative linear combination of $\sin^2$ terms. From this single identity, we derive a two-sided quadratic sandwich with ratio $4/π^2$ on a certified, worst-case quarter-wave region, proving the optimal peak nondegenerate modulo its affine gauge and well-conditioned. For white-box optimization, on a halved (eighth-wave) region, the objective satisfies a Polyak-Łojasiewicz inequality with an explicit constant, granting Gradient Descent a linear rate of $1 - 16/(π^4κ_r)$, where $κ_r$ is the condition number of the relevant Hessian block. For black-box optimization, we prove that the elitist single-parent Evolution Strategy converges linearly, almost surely and in expected hitting time, from a certified sublevel set, despite the landscape's continuous gauge symmetry and its lattice of periodic optima; the certified level is explicit whenever the landscape is trap-free, and near the optimum the strategy provably sees only the quadratic tangent of the peak. Systematic numerical simulations corroborate the theory. Finally, we show that additive input (actuator) noise reweights each term of the representation by a Debye-Waller factor without disrupting the landscape's structure, and outline open challenges: output (signal) noise, far-field plateau escape, angular-synchronization certificates, and another physically scalable benchmark (SHG with Glass).

0.34

Sequential Euclidean connections with exponential memory: distributional performance and adversarial robustness

cs.CG math.OC ·2026-08-26 ·Pedro M. M. de Castro
similarity 0.51
Abstract · 44 pages, 6 figures, 3 tables. Substantially expanded and retitled version. Includes numerical evaluation, endpoint distribution limits, add…

Points in the unit ball of $\mathbb R^d$ are processed sequentially. Each new point $p_i$ is connected to a state $x_{i-1}$ that summarizes earlier observations, after which $x_i=γx_{i-1}+(1-γ)p_i$, with $0\leqγ\leq1$. The cost is the sum of the $α$-powers of the connection lengths. This constant-gain rule interpolates between the input-order path and the star centered at the initial point. For independent uniform points, we establish the stationary insertion-length distribution and prove that it decreases in stochastic order as $γ$ increases. If $d+α>2$, or if $(d,α)=(1,1)$, the optimal constant parameter satisfies $1-γ_N^*=Θ(N^{-1/2})$, with an explicit asymptotic constant and closed bounds. For $α=1$, its leading expected tree length equals that of the center star and is eventually smaller than the expected lengths of both endpoint constructions. For $α=2$, the optimizer is unique and characterized exactly. For the same $N$, choosing $1-γ_N$ as a fixed positive multiple of $N^{-1/2}$ gives a sharp two-term expansion of the expected uniform-input cost and a maximal adversarial mean cost of $1+O(N^{-1/2})$. For every fixed $0\leqγ<1$ and $0<α\leq3$, the exact asymptotic adversarial value is $(2/(1+γ))^α$. When $d\geq2$, exponential weighting is within a factor smaller than $1.161^α$ of the best fixed nonnegative weighted rule with the same average look-back, for $0<α\leq3$. Comparison with the running mean highlights its time-homogeneous update, stationary coefficient profile, and fixed effective memory.

0.53

Matched Queries for Curvature and Density at Branching Junctions

cs.LG stat.ML ·2026-09-01 ·Ziqi Zhao, Qingjian Ni
similarity 0.50
Abstract

At a junction, a score field can reveal weighted tangent rays, yet these first-order quantities do not determine how individual branches bend or how their densities change away from the center. Recovering this missing information is necessary for describing local continuation beyond a single point, but finite observations must separate branchwise second-order effects while allowing error in the estimated center. We address this inverse problem using matched score queries at noise scales $σ$ and $λσ$. For a finite union of $C^{2,α}$ half-branches in $\mathbb{R}^D$, the normalized score has the expansion $F_σ=F_0+σG+O(σ^{1+α})$. Matched subtraction cancels the tangent contribution and exposes $G$, which depends linearly on branchwise curvature and log-density slope. Given tangent directions and weights on distinct rays, $G$ uniquely identifies all $sD$ branch parameters, and $sD$ scalar component observations are necessary. An $O(σ^2)$ center error introduces $D$ translation modes, leading to $(s+1)D$ observations under full-rank calibration, except for a translation-invariant full line. We also establish a perturbation bound and a conditional kernel-density-estimation rate. Experiments reproduce the predicted population and $N^{-1/5}$ trends and remain full rank up to $D=20$ with 16 supplied branches. In end-to-end tests for $D=3$--$5$, a known-count first-order frontend yields full rank in all 135 population systems and a median relative jet error of 0.132. With strong first-order error, matched responses reduce median parameter error by a factor of 49.4 relative to naive tangent subtraction.

0.27

Basin-Preserving Discretizations of Modern Hopfield Retrieval Dynamics: Energy Cells, Dissipation, and the Attention Limit

cs.NE math.NA ·2026-08-21 ·Francisco R. Villatoro
theory similarity 0.50
Abstract · 37 pages, 1 figure, 4 tables. Reproducibility code and numerical data: Zenodo DOI 10.5281/zenodo.22048179

The retrieval dynamics of a modern Hopfield network is the gradient flow of a log-sum-exp energy, while the attention update is its exact difference-of-convex minimization step. We study which time discretizations preserve not only energy decay and equilibria but also basins of attraction. We introduce energy cells, connected components of sublevel sets containing one attractor and no other critical point. Our main theorem shows that every finite energy cell below the escape energy is contained simultaneously in the basin of the continuous flow, every relaxed attention map $Ψ_θ=(1-θ)\,\mathrm{id}+θ\,\mathrm{attention}$ for $0<θ<2$, and implicit Euler throughout its uniqueness regime. A parameter-uniform unit-curvature majorant yields unconditional dissipation and a monotone interpolation of each discrete step. We also derive explicit local contraction bounds near well-separated patterns, with a certified optimal slight overrelaxation; characterize proximal tunneling and overshoot beyond the preservation regimes; compare first-order error constants; establish an order barrier for scalar reparametrizations of the relaxed family; construct a second-order scalar-auxiliary-variable scheme; and extend cell preservation to damped difference-of-convex iterations in Bregman geometry, including a certified overrelaxed window under bounded asymmetry. Nine numerical campaigns test the bounds and failure mechanisms. In two-dimensional basin experiments, all observed disagreements between continuous and discrete retrieval occur above the attractor-specific numerically inferred escape level.

0.32

Effect of Spherical Parameter Space on Number of Non-Forgetting Tasks and Capacity of Continual Learning

cs.LG cs.ITstat.ML ·2026-10-12 ·Nazanin Mirhosseini
theory similarity 0.50
Abstract

We propose a continuous learning formulation for $T$ non-forgetting tasks with the spherical parameter space $\mathbb{S}^{d-1}(\sqrt{d})$ in asymptotic regime $d\rightarrow \infty$. Each task $i$ has an optimum $\bmΘ_i$, minimizing its corresponding loss function $R_i(\bm{w})$ on sphere. We reduce each task $i$ to an acceptable loss region modeled by a geodesic ball $B_{\bmΘ_i}(r_i(d))$ on $\mathbb{S}^{d-1}(\sqrt{d})$ centered at $\bmΘ_i$ with radius $r_i(d)$. To model task dependencies (similarities), task optima $\bmΘ_i$ are distributed by a Neyman-Scott clustered point process $Φ$. Cluster centers $\{\bm{Y}_j\}_{j=1}^{N_p}$ form a homogeneous Poisson point process on sphere, while intra-cluster task optima follow a von Mises-Fisher distribution with mean $\bm{Y}_j$ and concentration $κ$. Each task $t\in \{1, ..., T\}$ learning algorithm is considered to be a channel $Q_{t}(\mathrm{d}\bm{w}_t | \bm{w}_{t-1}, \mathcal{K}_{t-1}(\bmθ_{1:t-1}), \bmθ_t)$, where $\bm{W}_t$ is the learned parameter of task $t$ and $\mathcal{K}_{t-1}(\bmΘ_{1:t-1})=\bigcap_{i=1}^{t-1}B_{\bmΘ_i}(r_i(d))$. Since in continual learning, the learner does not need to reach $\bmΘ_t$ exactly to successfully learn task $t$, to avoid forgetting as well as reliable learning, it only needs for the learned parameter vector $\bm{W}_{t}$ to enter $B_{\bmΘ_t}(r_t(d)) \cap \mathcal{K}_{t-1}(\bmΘ_{1:t-1})$. Using this model, we derive an upper bound on $T$ ensuring $\mathbb{P}[\mathcal{K}_{T}(\bmΘ_{1:T}) \neq \emptyset] \rightarrow 1$ as $d\rightarrow \infty$ and $κ/d \rightarrow α$, where $α>0$ is a constant. Finally, for $T$ tasks sampled uniformly from $Φ$, we derive an upper bound for total information theoretic capacity under the non-forgetting constraint for each task.

0.26