slideshow 3

Complexity seminar

The seminar takes place in the seminar room of IM, rear building, ground floor, Friday  at  14:00 - 16:00
Chair: Michal Koucky, Pavel Pudlak
The programme is announced via the mailing list.

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

Combinatorial miniatures from low depth complexity, chapter two

Navid Talebanfard
Institute of Mathematics, CAS
Friday, 13. November 2020 - 14:30 to 16:30
Motivated by proving lower bounds for affine dispersers, in this chapter we will see a graph theoretic characterization of affine spaces accepted by 2-CNFs.