Методы доказательства нижних оценок на число запросов (Людмила Глинских)
Семинар по сублинейным алгоритмам


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

Описание

Мы рассмотрим две техники доказательства нижних оценок на число запросов для тестирования свойств. Первая техника будет основана на предъявлении сложных распределений на входах, вторая основана на сведении задач с известной коммуникационной сложностью.