Let $R_r(k)$ denote the diagonal $r$-colour Ramsey number. We prove that there exist absolute constants $c,K>0$ such that $R_r(k)\le r^{rk}\exp\!\left(-c\frac{k}{r\log^2(2r)}\right)$ for every $r\ge2$ and every $k\ge Kr^2\log^6(2r)$. This improves the exponential saving in a recent bound of Yang and Mao by a factor of order $r\log^2(2r)$. The proof proceeds through an off-diagonal bound, which asymptotically improves the classical multinomial bound throughout a neighbourhood of the diagonal.
We settle the sample complexity of estimating the root Uhlmann fidelity $F(\rho,\sigma)=\operatorname{tr}\sqrt{\sqrt{\sigma}\rho\sqrt{\sigma}}$ between an unknown state $\rho$ and a known rank-$r$ reference state $\sigma$. Writing $S(r,\varepsilon)$ for the sample complexity at additive error $\varepsilon$, we resolve the open problem posed by Wang by closing, up to logarithmic factors, the gap between the previously known bounds $\Omega(r/\varepsilon^2)$ and $O(r^2/\varepsilon^2)$. We prove $S(r,\varepsilon)=\widetilde{\Theta}(r^2/\varepsilon^2)$ for all $0<\varepsilon\le\varepsilon_0$, where $\varepsilon_0>0$ is a universal constant. The lower bound already holds on a $2r$-dimensional system when $\sigma$ is maximally mixed on a fixed $r$-dimensional subspace, and for a hard family of states that do not commute with $\sigma$. The proof combines exact spectral moment matching, a radially size-biased doubly correlated Wishart model, and the Cauchy identity, reducing state indistinguishability to a long-cycle estimate for a weighted random permutation. A direct-sum embedding and binomial thinning yield the optimal $1/\varepsilon^2$ dependence. We also prove a near-quadratic lower bound $\widetilde{\Omega}(r^2)$ for quantum spectrum estimation at constant accuracy. Combined with the recent $O(r^2(\log\log r/\log r)^2)$ upper bound, this determines the polynomial order of the sample complexity in this regime and establishes a near-quadratic barrier.
This paper considers the design of optimal fixed-step first-order methods for high-dimensional minimization of $L$-smooth convex functions. For optimizing worst-case performance measured via suboptimality of the final function value (relative to the initial squared distance to a minimizer), we provide an algebraic proof of the optimality of the optimized gradient method (OGM) and establish its uniqueness among all fixed-step first-order methods. For the alternative measure of final squared gradient norm (relative to initial suboptimality), we prove the OGM-G method is optimal and uniquely so among fixed-step first-order methods. Finally, for the setting measuring the final squared gradient norm (relative to the initial squared distance to a minimizer), we show the recently proposed Lemniscate method is optimal and uniquely so. Our proofs rely on algebraic reductions for lower bound arguments rather than traditional information-theoretic bounds, which were previously only able to establish OGM's optimality but not uniqueness.
Benjamin Grimmer, Sunghyeon Jo, Chanwoo Park· 0 citations
Let $G\in\mathbb{R}^{M\times N}$ have independent standard Gaussian entries. For a fixed margin $\kappa\in\mathbb{R}$, the asymmetric binary perceptron asks for $\sigma\in\{\pm1\}^N$ such that $G\sigma/\sqrt{N}\ge\kappa\mathbf{1}_M$. We study the online version of this problem, in which the columns of $G$ arrive sequentially and each sign must be chosen irrevocably before future columns are revealed. We determine the exact threshold $\alpha_{\mathrm{on}}(\kappa)$ for every fixed $\kappa$: for $M/N\to\alpha$ with $\alpha<\alpha_{\mathrm{on}}(\kappa)$, there is a deterministic online algorithm, using $O(MN)$ arithmetic operations and polynomial bit complexity, that succeeds with high probability, while for $\alpha>\alpha_{\mathrm{on}}(\kappa)$, no online algorithm succeeds with high probability. The threshold is characterized by a one-dimensional stochastic control problem for Brownian motion. The main difficulty is to upgrade a single-coordinate Brownian limit to simultaneous feasibility of all $M=\Theta(N)$ constraints, which we do with half-line monotonicity and a short final correction block. At zero margin, we give a computer-assisted proof that $0.32747<\alpha_{\mathrm{on}}(0)<0.36664$. In particular, every density below $0.32747$ is achievable online by such an algorithm, more than tripling the best density previously proved attainable by any polynomial-time algorithm, online or offline (the previous bound was $\alpha\le0.1$, due to Li, Schramm, and Zhou). As $\kappa\to+\infty$, the online threshold agrees to first order with the offline storage capacity. As $\kappa\to-\infty$, it has the same asymptotic scale as the best known offline polynomial-time guarantee, while the storage capacity is larger by a factor of order $\kappa^2$.
Sunghyeon Jo, Taekyun Lee· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
