slideshow 3

Complexity seminar

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.