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}\).