Let$\nu $and$\mu $be probability distributions on$\mathbb {R}^{n}$, and$\nu _{s},\mu _{s}$be their evolution under the heat flow, that is, the probability distributions resulting from convolving their density with the density of an isotropic Gaussian random vector with variancesin each entry. This paper studies the rate of decay of$s\mapsto D(\nu _{s}\|\mu _{s})$for various divergences, including the$\chi ^{2}$and Kullback-Leibler (KL) divergences. We prove upper and lower bounds on the strong data-processing inequality (SDPI) coefficients corresponding to the source$\mu $and the Gaussian channel. We also prove generalizations of de Bruijn’s identity, and Costa’s result on the concavity insof the differential entropy of$\nu _{s}$. As a byproduct of our analysis, we obtain new lower bounds on the mutual information betweenXand$Y=X+\sqrt {s} Z$, whereZis a standard Gaussian vector in$\mathbb {R}^{n}$, independent ofX, and on the minimum mean-square error (MMSE) in estimatingXfromY, in terms of the Poincaré constant ofX.

The convex body chasing problem, introduced by Friedman and Linial [FL93], is a competitive analysis problem on any normed vector space. In convex body chasing, for each timestep t ϵ ℕ, a convex body Kt ⊆ ℝd is given as a request, and the player picks a point xt ϵ Kt. The player aims to ensure that the total distance moved is within a bounded ratio of the smallest possible offline solution. In this work, we consider the nested version of the problem, in which the sequence (Kt) must be decreasing. For Euclidean spaces, we consider a memoryless algorithm which moves to the so-called Steiner point, and show that in an appropriate sense it is exactly optimal among memoryless algorithms. For general finite dimensional normed spaces, we combine the Steiner point and our recent algorithm in [ABC+19] to obtain a new algorithm which is nearly optimal for all spaces with p ≥ 1, closing a polynomial gap.

Let X be a set of n points of norm at most 1 in the Euclidean space R^k, and suppose ≥0. An ≥-distance sketch for X is a data structure that, given any two points of X enables one to recover the square of the (Euclidean) distance between them up to an additive} error of ≥. Let f(n,k,≥) denote the minimum possible number of bits of such a sketch. Here we determine f(n,k,≥) up to a constant factor for all n ≥ k ≥ 1 and all ≥ ≥ \frac{1}{n^{0.49}}. Our proof is algorithmic, and provides an efficient algorithm for computing a sketch of size O(f(n,k,≥)/n) for each point, so that the square of the distance between any two points can be computed from their sketches up to an additive error of ≥ in time linear in the length of the sketches. We also discuss the case of smaller ≥2/√ n and obtain some new results about dimension reduction in this range. In particular, we show that for any such ≥ and any k ≤ t=\frac{\log (2+≥^2 n)}{≥^2} there are configurations of n points in R^k that cannot be embedded in R^{ℓ} for ℓ

In STOC 1999, Raz presented a (partial) function for which there is a quantum protocol communicating only O(log n) qubits, but for which any classical (randomized, bounded-error) protocol requires poly(n) bits of communication. That quantum protocol requires two rounds of communication. Ever since Raz's paper it was open whether the same exponential separation can be achieved with a quantum protocol that uses only one round of communication. Here we settle this question in the affirmative.