Complexity Theory with a Human Face, Third Edition
27 June - 1 July, 2022, Prague and Špindlerův Mlýn
About
This year's human face belongs to Pavel Pudlák who is turning 70. We will celebrate his lifetime of contribution to complexity theory and logic.
The program starts with a reception at Vila Lanna in Prague. We will then move to the picturesque mountain resort of Hotel Erlebachova Bouda for the workshop, which is about two hours from Prague. You are welcome to participate in all or part of the event.
See here and here for previous Complexity Theory with Human Face workshops.
Registration
There is no need to register for the event at Vila Lanna. For the rest of the workshop there is no registration fee, but please fill out this form if you wish to participate.
Practicalities
After we have a better idea of the number of participants, we will add more details about bookings.
- Accommodation. Most participants will be expected to make their own reservations at Hotel Erlebachova Bouda.
- Transportation. We expect to organize carpool or shuttle to Špindlerův Mlýn on June 28th.
Program
June 27, Vila Lanna, Prague:
- Honorary medal “De scientia et humanitate optime meritis” of CAS for Pavel Pudlák
- 15:00 - 16:00, Sam Buss Pavel Pudlak's work on Logic and Foundations of Computer Science
- 16:15 - 17 00, Medal awarding ceremony with Jaroslav Nešetřil and the president of the CAS Eva Zažímalová
- 17:00 - 19:00, reception
June 28, morning, departure from Prague to Špindelrův Mlýn, details to be specified
Tuesday, June 28:
- 14:00 - 14:15, Pavel Hrubeš, Jan Žižka, Pavel Pudlák, and Beyond
- 14:20 - 15:00, Jiří Tůma, Pavel's Contribution to Lattice Theory (His Mathematical Infancy)
- 15:10 - 15:40, Ramamohan Paturi, The Magical Power of PPZ
- 16:00 - 17:00, Open problem session
Wednesday, June 29:
- 9:00 - 10:00, Amir Shpilka, Points, Lines, and Polynomial Identities
- 10:10 - 10:40, Prerona Chatterjee, Separating ABPs and Some Structured Formulas in the Non Commutative Setting
- 11:00 - 12:00, Igor Carboni Oliveira, Probabilistic Kolmogorov Complexity
- 12:10 - 12:40, Diptarka Chakraborty, Support Size Estimation: The Power of Conditioning
Thursday, June 30:
- 9:00 - 9:30, Ilario Bonacina, On Vanishing Sums of Roots of Unity in Polynomial Calculus and Sum-of Squares
- 9:40 - 10:10, Emil Jeřábek, Elementary analytic functions in VTC^0
- 10:30 - 11:00, Michal Koucký, Turing Machines vs. Circuits - Who Wins.
- 11:10 - 11:40, Pavel Pudlák, Complexity, Random Graphs, and Matroids (and Lattices too)
- Afternoon, hike
Friday, July 1:
- 9:00 - 9:30, Lukáš Folwarczný, On Graph Functionality
- 9:40 - 10:10, Hunter Monroe, Pudlák’s Feasible Incompleteness Thesis and Extensions
- Afternoon, departure from Špindlerův Mlýn to Prague
