City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Тестирование свойств распределений (Кирилл Симонов)
Sublinear alhorithms

What: Lecture
When: Friday, 02 December 2016, 19:00–20:20
Where: ПОМИ РАН, аудитория 106

Description

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

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