[Computational Complexity] Live from Russia
- This week I am giving some lectures at the NoNA Summer School on Complexity Theory in St. Petersburg.This is my first time in Russia, a country I never expected to visit when I grew up during the cold war. One has to go a few generations back, but most of my ancestors came from Russia (think Fiddler on the Roof) or one of the former Soviet republics. Fortnow is derived from a Russian name. My father was born Fortunow but dropped the silent "u" because no one knew it was silent.In almost every European country I usually pass as a native of that country (until I open my mouth). Less so in St. Petersburg, a bit strange since I got most of my genes from this country.Summer schools are interesting affairs. Usually a week long where speakers give several lectures introducing usually local students to a specific topic. This is my third such school: I gave lectures on Kolmogorov complexity in the small town of Kaikoura in New Zealand and in Marseilles. This time the topic is "Structural Complexity," basically I'm shrinking a semester-long complexity class into six hours with very few proofs. A bit challenging because the students have very different academic backgrounds but it seemed to go reasonably well. I broke the four lectures into themes:
Next week I'm on vacation in Europe and off the net. Bill is on his own. See you when I get back.
- Deterministic and Nondeterministic time and space including the polynomial-time hierarchy
- Probabilistic Computation with a whiff of quantum.
- Circuit Complexity
- Counting and Interactive proofs/PCPs.
Posted By Lance to Computational Complexity at 8/13/2009 08:36:00 AM