Пятница 24.09. Michal Garlik: "Some lower bounds for parity decision trees"

[PDMI seminars]

Семинар по теории сложности вычислений

Тема: Some lower bounds for parity decision trees
Место: Zoom
Время: 24.09.2021, 11:00
Докладчик: Michal Garlik

Abstract:
We will discuss some measures of parity decision trees, like size and depth. We demonstrate an elementary technique to lower bound the length of the shortest branch of a parity decision tree for some functions. As an example, we show that any branch in any parity decision tree computing the MOD^3 function on n bits has length at least n/2-1. This bound is tight.

The zoom link will be sent to the seminar mail list before the talk.

[Dmitry M. Itsykson]

Zoom link:  https://zoom.us/j/95294301096?pwd=dXJXOWtqcjVZcy9qdXZZUTNFRjl0UT09

Password (if needed): pdmi

вс, 19 сент. 2021 г. в 14:12, PDMI seminars <pdmi.l...@gmail.com>:

--
Вы получили это сообщение, поскольку подписаны на группу "spb-complexity".
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес spb-complexit...@googlegroups.com.
Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/spb-complexity/000000000000e3505905cc573db9%40google.com.