Еще про нижние оценки на количество запросов (Олег Вайнзихер)
Семинар по сублинейным алгоритмам


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

Описание

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