Finding Skewed Subcubes Under a Distribution

Parikshit Gopalan, Roie Levin, Udi Wieder

Say that we are given samples from a distribution $\psi$ over an $n$-dimensional space. We expect or desire $\psi$ to behave like a product distribution (or a $k$-wise independent distri…