Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Live from Russia

Expand Messages
  • Lance
    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
    Message 1 of 1 , Aug 13, 2009
    • 0 Attachment
      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:
      1. Deterministic and Nondeterministic time and space including the polynomial-time hierarchy
      2. Probabilistic Computation with a whiff of quantum.
      3. Circuit Complexity
      4. Counting and Interactive proofs/PCPs.

      Next week I'm on vacation in Europe and off the net. Bill is on his own. See you when I get back.



      --
      Posted By Lance to Computational Complexity at 8/13/2009 08:36:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.