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.

XOR-KRW conjecture and composition of universal relation and a function

Ivan Mihajlin
Steklov Institute, Saint Petersburg
Friday, 4. June 2021 - 14:30 to 16:30

One of the major open problems in theoretic computer science is
showing the existence of a problem that could be solved in polynomial
time but not by a logarithmic depth circuit (P vs NC_1). One approach
that has a lot of progress in the last several years is to prove
Karchmer, Raz, and Wigderson conjecture. It states that there is no
better way to compute the composition... more


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.