We establish variance upper bounds for the minimum perfect matching problem in general metric spaces under a geometric partition condition. As a principal application, let $H_n$ be the minimum perfect matching cost of $n$ independent uniform points in $[0,1]^d$, where $n$ is even and $d\ge2$. We prove $$\operatorname{Var}(H_n)\le C d n^{1-2/d},$$ where $C$ is independent of $n$ and $d$. This removes the logarithmic losses in earlier upper bounds in every dimension (Talagrand, 1995); in particular, the variance remains bounded in dimension two, answering an open question (Rhee, 1994). The proof relies on constructing a rapidly mixing Markov process with a multinomial stationary distribution.
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$...
Let $M_n$ be an $n\times n$ matrix with independent uniform sign entries. We prove that there exist absolute constants $C,c>0$ such that, for all sufficiently large $n$, \[ \mathbb{P}\!\left( \left|\operatorname{Per}(M_n)\right| \ge e^{-Cn}\sqrt{n!} \right) \ge 1-n^{-c}. \] This establishes the exponential scale lower...
The randomized component-oracle complexity of finite-sum nonconvex-concave optimization with a bounded dual domain is characterized, taking the worst case over admissible known dual domains and finite dimensions.
We study the random geometric graph formed by connecting $n$ independent uniform points on $\mathbb S^{d-1}$ whenever their inner product exceeds a threshold chosen to give edge density $p$. We establish the conjectured dimensionality threshold for indistinguishability from the Erd\"{o}s-R\'enyi graph $G(n,p)$ througho...
We prove that finding a fixed point of a monotone map on the nine-dimensional grid $[N]^9$ requires $\Omega((\log N)^3)$ deterministic queries, even when the fixed point is unique and each query returns the entire function value. The proof gives a construction that raises the dimension from $d$ to $4d+1$, preserves uni...
Does randomization improve the worst-case first-order complexity of nonconvex optimization when the objective is very smooth? We prove that, for every fixed finite integer $p\ge3$, finding an $\eps$-stationary point requires $\Omega_p(\eps^{-5/3})$ exact value-and-gradient queries, even for $C^\infty$ objectives with i...
Hai-Han Zhang, Wen-Dao Wu, Fang-Qing Zhang et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
