Прежде на семинаре мы проверяли некоторые свойства функций, имея к ним оракульный доступ. Можно рассмотреть и аналогичную постановку вопроса для распределений. А именно, хочется научиться проверять, обладает ли заданным свойством распределение, к выборке из которого мы имеем доступ. Но точно определить распределение выборкой конечного размера, тем более сублинейного, в принципе невозможно, поэтому проверяется $\varepsilon$-близость распределения к свойству.

На докладе мы введем модель, в которой постановка вопроса выше имеет смысл, и научимся проверять неизвестное распределение на $[n]$ на $\varepsilon$-близость к заданному распределению выборкой размера $\text{poly}(\frac{1}{\varepsilon}) n^{1/2}$.