Columbia Theory Seminar, Fall 2004

For Fall 2004, the usual time and place for the meetings will be Thursdays at 10am in the CS conference room. Here is a schedule of seminars:

  • Tuesday, September 14, 2:30pm in the Interschool Lab, joint with Quantum Computing Seminar:   Scott Aaronson: NP-Complete Problems and Physical Reality.
    (Abstract)

  • Thursday, October 7, 10:00am in the CS Conference Room (CSB 453):   Rocco Servedio: On learning random decision trees and DNF formulas.
    (Abstract)

  • Thursday, October 21, 10:00am in the CS Conference Room (CSB 453):   Alex Healy: Using Nondeterminism to Amplify Hardness.
    (Abstract)

  • Thursday, October 28, 10:00am in the CS Conference Room (CSB 453):   Andrew Wan will present "On the (Im)possibility of Obfuscating Programs" by Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan and Yang.
    (Abstract)

  • Monday, November 8, 2:00-3:30pm in the CS Conference Room, joint with Quantum Computing Seminar:   Krysta M. Svore: Local Fault-tolerant Quantum Computation.
    (Abstract)

  • Thursday, December 9, 10:00am in the CS Conference Room (CSB 453):   Fei Li: An optimal algorithm for packet scheduling with agreeable deadlines.
    (Abstract)

  • Thursday, December 16, 10:00am in the CS Conference Room (CSB 453):   Dimitris Achlioptas: A New Look at the Second Moment Method.
    (Abstract)
    Contact rocco_at_cs.columbia.edu if you want to volunteer to give a talk (especially encouraged for students!). The talk can be about your or others' work. It can be anything from a polished presentation of a completed result, to an informal black-board presentation of an interesting topic where you are stuck on some open problem. It should be accessible to a general theory audience. I will be happy to help you choose papers to talk about.
    There is a mailing list for the reading group. General information about the mailing list (including how to subscribe yourself to it) is available here. If you want to unsubscribe or change your options, send email to theoryread-request@lists.cs.columbia.edu with the word `help' in the subject or body (don't include the quotes), and you will get back a message with instructions.

    Comments on this page are welcome; please send them to rocco_at_cs.columbia.edu

    Last updated 11/26/2004.

    Back to Theory of Computation at Columbia main page