6 papers · 1 filter
TV between Bernoulli products, up to constants
Gleb Smirnov
We obtain upper and lower bounds on the total variation distance between two product Bernoulli measures. The bounds are efficiently computable and match up to an absolute constant…
MaxCut for Covariances
Gleb Smirnov
Let have a multivariate totally positive () law. We prove that $$ \sum_{i<j}\mathbb{E}\left[\left|\mathrm{Cov}(X_i,X_j \mid X_{[n]\s…
Random sets are close to low-discrepancy sets
Gleb Smirnov, Roman Vershynin
We show that a random sample from an arbitrary probability measure on is close to a low-discrepancy point set. Namely, after moving only a small fraction of the samp…
Discrepancy and Fisher information
Gleb Smirnov, Roman Vershynin
We give an online algorithm that keeps a symmetric random walk inside a convex body by discarding some of its steps. The expected number of discarded steps is controlled by a Fishe…
Thinning to improve two-sample discrepancy
Gleb Smirnov, Roman Vershynin
The discrepancy between two independent samples \(X_1,\dots,X_n\) and \(Y_1,\dots,Y_n\) drawn from the same distribution on typically has order \(O(\sqrt{n})\) even…
Detecting adversarial attacks on random samples
Gleb Smirnov
This paper studies the problem of detecting adversarial perturbations in a sequence of observations. Given a data sample drawn from a standard normal distributio…