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

Методы доказательства нижних оценок на число запросов (Людмила Глинских)
Sublinear alhorithms

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

Description

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