Тестирование свойств распределений (Кирилл Симонов)
Семинар по сублинейным алгоритмам


Что: Лекция
Когда: Пятница, 02 декабря 2016, 19:00–20:20
Где: ПОМИ РАН, аудитория 106

Описание

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

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