Apologies for the inconvenience.

Chair: Michal Koucky, Pavel Pudlak

The programme is announced via the mailing list.

n/a

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

in IM, rear building, ground floor

Apologies for the inconvenience.

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.

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.

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