Новости

Семинар по коммуникационной сложности

Семинар по коммуникационной сложности пройдет 17 марта (четверг), 17:30, ауд. 146.
Коммуникационная сложность — это одна наиболее интересных и наглядных областей теоретической информатики. Простейшая модель в теории коммуникационной сложности такова. Имеются два участника (компьютера или человека), которые совместно хотят решить некоторую задачу. Ни один из них самостоятельно решить задачу не может (например, у каждого из них недостаточно данных или ресурсов). Поэтому им необходимо общаться. Коммуникационная сложность измеряет минимально возможное количество битов, которым необходимо обменяться участникам, чтобы решить задачу. Время, необходимое для проведения локальных вычислений каждым из участников, не принимается во внимание — в этом принципиальное отличие от теории сложности вычислений. Коммуникационная сложность имеет множество приложений в других областях в теоретической информатики.

Кроме того, коммуникационная сложность представляет особый интерес, так как в отличие от классической теории сложности, большинство оценок в ней безусловные, т.е. не в предположении вроде P не равно NP.

В течение семинара планируется разобрать большую часть материала книги E. Kushilevitz, N. Nisan "Communication Complexity".

Руководитель семинара: выпускник КТ 2011 года, к.ф.-м.н. Дмитрий Соколов, м.н.с. ПОМИ РАН.

Информация © 2015-2017 Университет ИТМО
Разработка © 2015 Департамент информационных технологий