Test your intuition
Sign up for the new posts via the RSS feed.
A new job is a good reason to start a (new) blog. The first post is in the spirit of the series by Gil Kalai.
Let $K$ be a convex body in $\mathbb{R}^d$ symmetric around the origin. Let $\mathcal{D}_1$ be a distribution supported on $K$, and let $\mathcal{D}_2$ be a distribution supported outside of $2K$. Can one always find a direction $v$ such that given projections of $\mathrm{poly}(d)$ i.i.d. samples from $\mathcal{D}_i$ on $v$, one can recover $i$ with high probability?
For example, suppose that $K = [-1, 1]^d$ is a cube. Then, each point in the support of $\mathcal{D}_2$ has at least one coordinate whose absolute value is large. It means that there exists a coordinate such that with probability at least $1/d$ over $\mathcal{D}_2$ it is outside of $[-2, 2]$. But then, using this coordinate, one can distinguish $\mathcal{D}_1$ and $\mathcal{D}_2$ using only $O(d)$ samples.
So, what is the answer? I really want to know by how much my intuition is off.
The answer is that it’s not always possible: there are examples, when you need 2^{d^{Omega(1)}} queries.
It *was* far off then. Are these examples for “pathological” D_1 and D_2, pathological D_1, pathological D_2, or natural D_1, D_2?