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

Тестирование на монотонность 2 (Александр Логунов)
Sublinear alhorithms

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

Description

На этом докладе будут обобщаться результаты предыдущего доклада.

А именно, мы выясним, что задачу тестирования на монотонность функций из множества \([m]^l\) (оно же множество одномерных кубиков в \(l\)-мерном гиперкубе со стороной \(m\)) можно запросто свести к той же задаче при \(m=2\). Кроме того, окажется (при некоторых предположениях), что алгоритм, с хорошей вероятностью находящий немонотонные булевы функции, неплохо работает и на функциях с произвольным множеством значений.