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

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