10 papers
Optimal discrepancy for triangles
Gleb Smirnov
We prove that every -point set in the plane has a two-coloring with discrepancy for all triangles. This improves the previous bound and ma…
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…
Deep belief networks are exact
Gleb Smirnov
We prove that every strictly positive probability distribution on \(\{-1,1\}^n\) is represented exactly by a sigmoid belief network with finite parameters. This answers a question…
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…
Improving discrepancy by moving a few points
Gleb Smirnov, Roman Vershynin
We show how to improve the discrepancy of an iid sample by moving only a few points. Specifically, modifying \( O(m) \) sample points on average reduces the Kolmogorov-Smirnov dist…
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…
Analyzing Deviations of Dyadic Lines in Fast Hough Transform
Gleb Smirnov, Simon Karpenko
Fast Hough transform is a widely used algorithm in pattern recognition. The algorithm relies on approximating lines using a specific discrete line model called dyadic lines. The wo…