Computational Complexity Reading Group

Format

• Following Computational Complexity: A Modern Approach
• Weekly meetings
• Each meeting has two parts: a presenter outlines the main ideas of the reading, and then goes over problems and subtleties
• Each week the presenter will prepare (a week before the reading is to be discussed) problems and questions for the others

Schedule

• 2009-06-23: Michael will discuss Chps. 1 and 2
  • Notes and Problems
    • Everyone 'knows' that poly(n)=o(exp(n)), and polylog(n)=o(poly(n)), remind yourself of a proof.
    • AB: #1.5,1.6
    • In the AB definition of 'time-constructible', shouldn't we require the binary representation of T(n) to be constructed in O(T(n)) time (instead of exactly T(n) time)?
    • Show that T(n)=n is time-constructible (so given 1^n, output the binary representation of n in O(n) time). I'd be interested to know if this is possible in exactly n steps, as I think the AB definition of 'time-constructible' should be changed.
    • In Claims 1.5,1.6 and 1.8, the hypothesis of time-constructibility is not needed.
    • In the proof of the relaxed version of Theorem 1.9, note that the transformations of the input TM given by Claims 1.5 and 1.6 do take time, but that this doesn't matter as it is absorbed in the machine dependent constant C_\alpha.
    • In the proof of Theorem 1.9, note that the shifting of the tapes takes linear time as we use an auxilary tape to perform the copying
    • AB #2.6,2.12, perhaps 2.30, 2.13
  • Topics of Discussion
    • The proof of Theorem 1.9, in more detail
    • AB #1.6,2.6,2.12
    • How to handle errata
    • Solutions (requires certificates)
• 2009-06-30: David will discuss Chp. 3
• Notes and Problems
• Most of Chapter 3 is a review, but try to check out the Nondeterministic Time Heirarchy, and remind yourself of the proof of Ladner's Theorem
• Note that the bounds on the Time Heirarchy hinge on fast universal simulation
• Baker, Gill, Solovay results
• BA 3.4
• BA 3.7: Show that there is an oracle A and a language L in NP^A such that L is not polynomial time reducible to 3SAT even when the machine computing the reduction is allowed access to A
• 2009-07-14: Asilata will discuss Chp. 5
• Topics of Discussion
• Review of PH, alternating TMs
• The theorem about Time/Space tradeoffs for SAT (Theorem 5.11 in AB)
• Exercises 5.6 and 5.10 in AB

Last Updated: 2009-07-14