В докладе будет рассказываться про новые оценки на коммуникационную сложность в полудуплексной модели коммуникации. Полудуплексная коммуникационная модель - это обобщение классической модели коммуникационной сложности, предложенной Яо. Общение в такой полудуплексной модели напоминает общение по рации: в каждый момент времени каждый игрок находится либо в состоянии передачи сообщения, либо в состоянии приёма. При этом, если оба игрока передают сообщение одновременно, то они не слышат друг друга, а сообщения теряются. Мотивация для изучения данной модели происходит из исследований 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. Ссылка для подключения будет выслана в рассылку за пару часов до доклада.

Мы рассмотрим обобщение системы Polynomial Calculus, в котором дополнительно можно извлекать квадратный корень из многочлена и вводить новые переменные, записывающие многочлены от исходных переменных. Мы докажем экспоненциальную нижнюю оценку на размер опровержения в этой системе равенства $BVP_n$ ($1 + 2 x_1 + 2^2 x_2 + ... + 2^n x_n = 0$), при этом для доказательства нижней оценки на размер доказательства нам не потребуется нижняя оценка на степень. Благодаря тому, что эта система полиномиально моделирует Res-Lin (систему, оперирующую дизъюнкциями линейных уравнений; введена Разом и Цамеретом), мы получим альтернативное доказательство нижней оценки Парта и Цамерета на размер доказательств $BVP_n$ в Res-Lin.

Семинар будет проходить онлайн в конференции zoom. Ссылка для подключения будет выслана в рассылку за пару часов до доклада.

В современных сетях число пользователей растет экспоненциально, структура сети становится все более сложной, а количество поддерживаемых стандартов постоянно увеличивается. Все это приводит к тому, что состояние сети становится сложным по структуре. С другой стороны, требования эффективности тоже быстро растут (обработка одного пакета должна происходить на уровне десятков или сотен наносекунд). В результате нужно искать компромисс между выразительностью представления состояния сети и эффективностью обработки пакетов. В первой части мы рассмотрим три проекта, посвящённых эффективному представлению программ, обрабатывающих пакеты. Во второй части мы покажем, как можно использовать ресурсы всей сети для задачи мониторинга трафика, уменьшающего локальный размер состояния в каждом отдельном элементе.

Семинар будет проходить онлайн в конференции zoom. Ссылка для подключения будет выслана в рассылку за пару часов до доклада.