slideshow 3

Complexity seminar

usually takes place each Friday at 14:00 - 16:00 temporarily on Zoom, normally in IM, rear building, ground floor
Chair: Michal Koucky, Pavel Pudlak
The programme is announced via the mailing list.


Friday, 19. February 2021 - 14:30 to 16:30

in IM, rear building, ground floor

Apologies for the inconvenience.

Interlude: how many error correcting codes are there?

Navid Talebanfard
Institute of Mathematics, CAS
Friday, 11. December 2020 - 14:30 to 16:30
We continue our journey through the landscape of extremal combinatorics. This time we will acquaint ourselves briefly with the powerful technique of (hyper)graph containers which is used to bound the number of independent sets in various graphs and hypergraphs. Specifically, possibly of interest of complexity theorists, we will see a result of Balogh, Treglown and Wagner which gives a close to tight bound on the number of possible error correcting codes of a given relative distance.

Tau conjectures

Pavel Hrubeš
Institute of Mathematics, CAS
Friday, 27. November 2020 - 14:30 to 16:30
Tau conjectures of Koiran and Poitier are an approach towards proving arithmetic circuit lower bounds. Besides that, they are related to some interesting mathematics. I will explain the background and whatever I feel like at the moment. 

KRW Composition Theorems via Lifting

Susanna F. de Rezende
Institute of Mathematics, CAS
Friday, 20. November 2020 - 14:30 to 16:30
Proving super-logarithmic lower bounds on the depth of circuits (i.e., P \neq NC^1) is one of the main frontiers of circuit complexity. 
In 1991, Karchmer, Raz and Wigderson observed that we could resolve this question by proving the following conjecture: Given two non-constant boolean functions f, g, the depth complexity of their composition is approximately equal to the sum of their individual depth complexities. ... more