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

Тестирование на монотонность (Артур Рязанов)
Sublinear alhorithms

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

Description

В основной части доклада будут рассмотрены два способа тестирования монотонности булевых функций из куба ${0,1}^l$: edge test и path test. В оставшееся время будет рассмотрен неадаптивный алгоритм тестирования монотонности на прямой (т.е. для функций из $[n]$).