Conjecture on Brownian tracking horizon for geometric matchings

About 5 years old · traced to

Let nn particles move in dd dimensions, sampled at intervals of length δ\delta, and let π^k\widehat{\pi}_k be the estimator at time step kk. Let Tmax⁡T_{\max} denote the maximum tracking time before the estimator incurs a macroscopic number of errors. "Brownian tracking conjecture." Suppose that d≥2d\geq2 and δ=n−ξ/d\delta=n^{-\xi/d} for some ξ∈[2,4]\xi\in[2,4]. Then

Tmax⁡∼δ1−d/2nf(n)=nξ/2−ξ/d−1f(n),T_{\max}\sim\frac{\delta^{1-d/2}}{n}f(n)=n^{\xi/2-\xi/d-1}f(n),

for some 1/polylog⁡(n)≤f(n)≤polylog⁡(n)1/\operatorname{polylog}(n)\leq f(n)\leq\operatorname{polylog}(n). The heuristic is based on Brownian displacements between snapshots and is explicitly not expected to apply in dimension one, where particle collisions dominate the tracking error; the conjectured behavior remains unproved for the stated higher-dimensional regime.

References

Primary source

Dmitriy Kunisky and Jonathan Niles-Weed, “Strong recovery of geometric planted matchings”, arXiv:2107.05567 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.