Complexity Reading Group 2007/08

 

Syllabus

Our main text so far has been the notes from the currently-dormant 4th-year/PhD course on "Computational Complexity". The notes are available on the "Computational Complexity" webpage. As a supplementary text we are also using the wonderful book, "Complexity Theory: A Modern Approach", by Sanjeev Arora and Boaz Barak. This has not been published yet, but a draft of the entire book is available online at http://www.cs.princeton.edu/theory/complexity/. Other useful references are the textbooks of Papadimitriou and of Sipser. In semester 2, the syllabus will be determined by the interests of the participants.

When/where

For semester 2, we will meet in JCMB 2509 during 2-4pm on Wednesdays, starting on January 9th, 2008.

Participants

Mary Cryan (coordinator), Julian Gutierrez, (Anand Kulkarni, now back in Berkeley), Jie Liu, Anthony Widjaja To, Yinghui Wu, and other occasional participants.

Schedule

Semester 1

During semester 1 we read and discussed Chapters 1-4 of the Computational Complexity notes (covering Turing machines and complexity classes, Natural classes and Completeness, Circuit Complexity, and Randomized computation) . On our last meeting of semester 1, 27th December, 2007, Anand presented the Razborov and Rudich paper on "Natural Proofs" (which killed off, at one stroke, an entire thread of research in Circuit Complexity).

Semester 2

datespeaker(s)/reader(s)topicJan 9, 2008Mary Cryan Chapter 5 of "Computational Complexity" notes (Provably Intractable Problems)
Jan 16, 2008Julian Gutierrez Introduction to Petri Nets and their Complexity
+ very end of Chapter 5 (today we finish at 3:30)
Jan 23, 2008 ? ?

Possible future topics

  • most likely In March (once conference deadlines die down), Kousha may offer 4 hours of lectures on problems between P and NP (PPAD etc).
  • Some topics on Descriptive Complexity, by Anthony.
  • Proof Complexity, by Grant Passmore.
  • NP-hardness and/or Approximation hardness, Jie and Yinghui.
  • Randomized Algorithms, by anyone.
 
email: mcryan AT inf DOT ed DOT ac DOT uk