Laboratory of Mathematical Logic at PDMI

Пятница, 24 сентября, Zoom. Начало в 11:00.

Докладчик: Michal Garlik.

Тема: Some lower bounds for parity decision trees.

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.