Laboratory of Mathematical Logic at PDMI

Понедельник, 11 декабря, 402. Начало в 12:00.

Докладчик: Смаль А..

Тема: PPZ lowerbound via entropy.

Abstract

На семинаре мы рассмотрим простое доказательство основной теоремы из статьи Or Meir, Avi Wigderson "Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds" (https://eccc.weizmann.ac.il/report/2017/149/), а точнее её более сильной версии. Кроме того, будет показано, как из этой более сильной теоремы следует нижняя оценка 2^(n/k - 1) на размер схемы глубины 3 (OR-k-CNF) вычисляющей функцию чётности.