Пятница 28.08. Артур Игнатьев (СПбГУ): "Новые оценки на полудуплексную коммуникационную сложность"
PDMI seminars
Тема: Новые оценки на полудуплексную коммуникационную сложность
Место: Zoom
Время: 28.08.2020, 18:00
Докладчик: Артур Игнатьев (СПбГУ)
Abstract:
В докладе будет рассказываться про новые оценки на коммуникационную сложность в полудуплексной модели коммуникации. Полудуплексная коммуникационная модель - это обобщение классической модели коммуникационной сложности, предложенной Яо. Общение в такой полудуплексной модели напоминает общение по рации: в каждый момент времени каждый игрок находится либо в состоянии передачи сообщения, либо в состоянии приёма. При этом, если оба игрока передают сообщение одновременно, то они не слышат друг друга, а сообщения теряются. Мотивация для изучения данной модели происходит из исследований KRW гипотезы для композиции функции и мультиплексера. В докладе будет рассказано о новых верхних и нижних оценках для функции $DISJ_n$, а также для игр Карчмера-Вигдерсона для функций подсчёта по модулю и рекурсивной функции большинства. Кроме того, будет сформулировано определение недетерминированной полудуплексной коммуникационной сложности и доказаны оценки, связывающие её с классической недетерминированной коммуникационной сложностью.
По материалам статьи: Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, Mikhail Ushakov, "New bounds on the half-duplex communication complexity" (https://eccc.weizmann.ac.il/report/2020/117/)
Семинар будет проходить онлайн в конференции zoom. Ссылка для подключения будет выслана в рассылку за пару часов до доклада.
Alexander V. Smal
Ссылка для подключения:
https://us02web.zoom.us/j/8141238054?pwd=Q2RMak9XU2dQSFlZcm5xV3VzZzdPZz09
Саша
> Вы получили это сообщение, поскольку подписаны на группу "spb-complexity".
> Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес spb-complexit...@googlegroups.com.
> Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/spb-complexity/0000000000004843f105ad7f3c1b%40google.com.
--
Alexander V. Smal
St. Petersburg Department of Steklov Mathematical Institute
27 Fontanka, St. Petersburg, 191023, Russia