Thursday, August 13, 2009

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:
  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.


  1. Hi Lance,

    possible topic for a future blog post: do you consider yourself a 'structural' complexity theorist, and if so what differentiates this outlook from others?

  2. Hello Lance,

    Thanks for your lectures and for the book on quantum computation you've recommended me to read. (I've just handled a chapter about teleportation and feel so inspired!)

    Anna Yudina

  3. Curious about these things:
    Are you using your Kindle in Russia?
    Does you kindle have the whispernet connection in Russia?

    Your summer school students will appreciate your efforts and be thankful to you.

  4. Anon 3: Yes I am using the Kindle here though Whispernet doesn't work outside the US. Instead I download through the USB cord.

  5. Thanks a lot, Lance! You did a really exciting attempt to squeeze a semester course into four lectures. I think people with any background found something useful in your lectures.

    Hope you enjoyed the school's organization and had no problems. Please, tell us if something went wrong.

  6. Thank you for your lectures! They were great as a comprehensive summary to the course, that I attended during the academic year. Nevertheless, it was very useful.

    Ilya Razenshteyn.