Понедельник 11.12. Смаль А.: "PPZ lowerbound via entropy"

Speaker: 
Смаль А.
Date: 
Monday, December 11, 2017 - 12:00
Place: 
402
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) вычисляющей функцию чётности.