Пятница, 8 июля, ауд. 106. Начало в 18:00.
Докладчик: Mark Braverman (University of Toronto).
Тема: Poly-logarithmic independence fools bounded depth circuits.
In this talk we will discuss some of these connections. We will then
present a proof of the 1990 Linial-Nisan conjecture on the
computational power of bounded-depth circuits. The conjecture stated
that bounded-depth Boolean circuits of size cannot distinguish
inputs drawn from a
-wise independent distributions from uniform
inputs, where
.
The talk will be almost completely self-contained.