Fwd: [SOCIAL]Logic Online Seminar + S.I. Adian Seminar, 12.05.25, V.V. Podolskii

[Alexander Shen]

I guess Shekhovtsov is the Danya Musatov's student who improved the
cat-mouse bound for enumeration complexity (and, it seems, never
published anything)...

-------- Forwarded Message --------
Subject: [SOCIAL]Logic Online Seminar + S.I. Adian Seminar, 12.05.25,
V.V. Podolskii
Date: Mon, 5 May 2025 23:08:28 -0700 (PDT)
From: Lev Beklemishev <lev...@gmail.com>
To: Mathlogic-Moscow <mathlogi...@googlegroups.com>



*Logic Online Seminar <https://www.mathnet.ru/eng/conf876>, *Monday
16:00 MSK (UTC+3), Kontur Talk

*12.05.2025, jointly with S.I. Adian seminar,* Vladimir Podolskii
<https://homepage.mi-ras.ru/~podolskii/> (Steklov Mathematical Institute
and Tufts University): /Randomized Lifting to Semi-Structured
Communication Complexity/

Lifting is a general technique which takes lower bounds for the
complexity of some functions in a weak computational model and
translates it into a bound for some new function in a stronger
computational model. New function is obtained from the original one by
combining it with some small gadget function. In this talk we will be
interested in lifting from decision tree complexity to communication
complexity. The major open problem in this area is to prove a lifting
theorem for gadgets of constant size. The recent paper [Beame, Koroth,
2023] introduces semi-structured communication complexity, in which one
of the players can only send parities of their input bits. They have
shown that deterministic decision tree complexity can be lifted to
semi-structured deterministic communication complexity using Indexing
gadget of constant size. In this talk we will discuss the extension of
this result to randomized case and to the larger family of gadgets. From
our result it follows that deterministic/randomized decision tree
complexity lifts to deterministic/randomized parity decision tree
complexity. For randomized case this is the first result of this type.
For deterministic case, our result improves the bound in [Chattopadhyay
et al., 2023] for Inner Product gadget.

The talk is based on the joint paper with Alexander Shekhovtsov:
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.78

Join via Kontur Talk by this link:
https://mian.ktalk.ru/hbaq9v2c5ar8?pinCode=0470

--
Вы получили это сообщение, поскольку подписаны на группу "Mathlogic-Moscow".
Чтобы отменить подписку на эту группу и больше не получать от нее
сообщения, отправьте письмо на электронный адрес
mathlogic-mosc...@googlegroups.com.
Чтобы посмотреть обсуждение, перейдите по ссылке
https://groups.google.com/d/msgid/mathlogic-moscow/07ea1dcd-9436-4b3a-88d1-9d74318103c3n%40googlegroups.com
<https://groups.google.com/d/msgid/mathlogic-moscow/07ea1dcd-9436-4b3a-88d1-9d74318103c3n%40googlegroups.com?utm_medium=email&utm_source=footer>.