Тестирование на монотонность (Артур Рязанов)
Семинар по сублинейным алгоритмам


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

Описание

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