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.
Monday, February 16, 2:45pm
:   Danny Harnik:
Completeness in Two-Party Secure Computation - A Computational View.
Monday, February 23, 2:45pm
:   Amos Beimel: A Quantitative Approach to Reductions in Secure
Monday, March 1, 2:45pm
:   Julia Chuzhoy: The Hardness of Metric Labeling.
Monday, March 8, 2:45pm
:   Ariel Elbaz: Extracting Randomness from Weak Random Sources.
Monday, March 22, 2:45pm
(joint with Quantum Computing seminar):   Igor Markov:
Automatic Synthesis and Simulation of Quantum Circuits.
Monday, March 29, 2:45pm
:   Ryan O'Donnell: Learning Mixtures of Product Distributions.
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
Monday, April 19, 2:45pm
:   Edward Farhi: Exponential Algorithmic Speedup by Quantum Walk.
Monday, April 26, 2:45pm
:   Garud Iyengar: Concurrent Flows in O*(1/epsilon) Time.
Friday, May 7, 11:00am
(note unusual date and time)
:   Toniann Pitassi: Learnability and Automatizability.
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)
Monday, May 24, 2:45pm
:   Yehuda Lindell: The Security of Protocols in Modern Network Settings - a Survey.
you want to volunteer to give a talk (especially encouraged
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
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
If you want to unsubscribe or change your options, send email to
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