Columbia Theory Seminar, Spring 2004

For Spring 2004, the usual time and place for the meetings will be Mondays 2:45-4:00 at the CS conference room (CSB 453) unless otherwise noted.

The schedule so far is:

  • Thursday, January 29, 2:45pm in Interschool Lab (note unusual date and place):   Shakhar Smorodinsky: On Conflict-Free Colorings.
    (Abstract)

  • Monday, February 16, 2:45pm :   Danny Harnik: Completeness in Two-Party Secure Computation - A Computational View.
    (Abstract)

  • Monday, February 23, 2:45pm :   Amos Beimel: A Quantitative Approach to Reductions in Secure Computation.
    (Abstract)

  • Monday, March 1, 2:45pm :   Julia Chuzhoy: The Hardness of Metric Labeling.
    (Abstract)

  • Monday, March 8, 2:45pm :   Ariel Elbaz: Extracting Randomness from Weak Random Sources.
    (Abstract)

  • Monday, March 22, 2:45pm (joint with Quantum Computing seminar):   Igor Markov: Automatic Synthesis and Simulation of Quantum Circuits.
    (Abstract)

  • Monday, March 29, 2:45pm :   Ryan O'Donnell: Learning Mixtures of Product Distributions.
    (Abstract)

  • Tuesday, April 6, 10:00am (note unusual date and time, joint with Quantum Computing seminar):   Sean Hallgren: A Fast Quantum Algorithm for Computing the Unit Group of a Number Field
    (Abstract)

  • Monday, April 19, 2:45pm :   Edward Farhi: Exponential Algorithmic Speedup by Quantum Walk.
    (Abstract)

  • Monday, April 26, 2:45pm :   Garud Iyengar: Concurrent Flows in O*(1/epsilon) Time.
    (Abstract)

  • Friday, May 7, 11:00am (note unusual date and time)   :   Toniann Pitassi: Learnability and Automatizability.
    (Abstract)

  • Monday, May 10, 2:45pm in 520 Mudd (note unusual room) :   Tim Roughgarden: Approximation via Cost Sharing (or, How to Build Good Networks by Flipping Coins)
    (Abstract)

  • Monday, May 24, 2:45pm :   Yehuda Lindell: The Security of Protocols in Modern Network Settings - a Survey.
    (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 welcome. (last updated 1/12/04).

    Back to Theory of Computation at Columbia main page