Адрес e-mail:

Лекция Р. Рубинфельд "Алгоритмы для локальных вычислений", 06.06.2017

Дата и место проведения: 06.06.2017, 19:00, Яндекс, конференц-зал «Мулен Руж»

Докладчик: Ronitt Rubinfeld (MIT and Tel Aviv University)

Страница мероприятия: https://events.yandex.ru/events/science-seminars/06-jun-2017/

Аннотация:

Пусть вход алгоритма настолько большой, что за разумное время его нельзя даже прочесть целиком. Но и про выход (тоже очень длинный) нужно узнать лишь маленькую часть информации. В таком случае задача может быть решена за менее, чем линейное время без исследования всего входа. В докладе будет рассказано о последних достижений в области локальных вычислений, в том числе для таких задач на графах как поиск максимального независимого множества и поиск разреженного остовного подграфа.
Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2020 Московский физико-технический институт (национальный исследовательский университет)

Противодействие коррупции | Сведения о доходах

Политика обработки персональных данных МФТИ

Техподдержка сайта | API

Использование новостных материалов сайта возможно только при наличии активной ссылки на https://mipt.ru

МФТИ в социальных сетях