Complexity Theory with a Human Face, 2nd Edition
17-20 October 2021, Hotel Erlebachova Bouda, Špindlerův Mlýn
About
After a successful first edition we resume our workshop in the beautiful Czech mountains of Krkonoše where we celebrate complexity theory with excellent contributed talks, and long hikes imbued with heated exchange of open problems, new ideas and visions.
The human face of this year's workshop is Krakonoš, the guardian of the mountains.
Registration
Please fill out this form as soon as possible if you wish to participate.
Practicalities
- Accommodation: Participants are expected to make their own reservations at Hotel Erlebachova Bouda. Please mention you are with the Institute of Mathematics in your reservation.
- Transportation: There is a three hour bus ride from Prague to the town near the workshop venue. See here for schedule. Depending on the number of participants we might consider renting a shuttle or arranging carpool.
Program
October 17: arrival
October 18:
9:00 - 9:25. Pavel Hrubeš, Complexity theory under the shadow of Krakonoš
9:30 - 9:55. Pavel Hubáček, On the complexity of the parity argument on directed cycles
10:00 - 10:25. Pavel Veselý, Streaming algorithms for geometric steiner forest
10:30 - 11:00. Coffee break
11:00 - 12:00. Open problems
October 19:
- 9:00 - 9:25. Ilario Bonacina, (Semi)-algebraic proof systems and combinatorial principles
- 9:30 - 9:55. Bruno Loff, Hardness of Constant-round Communication Complexity
- 10:00 - 10:25. Svyastoslav Gryaznov, Linear branching programs and lower bounds
- 10:30 - 11:00. Coffee break
- 11:00 - 11:25. Emil Jeřábek, Hereditarily bounded sets
October 20:
- 9:00 - 9:55. Michal Koucký, Data structures lower bounds and popular conjectures
Organizers