Columbia Theory Seminar, Spring 2006
For Spring 2006, the usual time for the meetings will be Tuesdays at 4pm,
at the Interschool Lab (7th floor CEPSR building).
Here is a schedule of the talks so far.
Thur, January 19th, 1:30pm, Davis Auditorium:
Jon Kleinberg: Strategic Models for Information Flow in
Social Networks and Peer-to-Peer Systems
Mon, January 23rd, 11:00am in the Interschool Lab (7th floor
Mihalis Yannakakis: Knuth Lecture: Probability and Recursion
Thur, January 26th, 1:30pm, 520 Mudd (note unusual time
Seffi Naor: Classification and Partitioning: Recent Bounds
Tue, February 14th, 4:00pm, Interschool Lab:
Petros Drineas: A relative-error CUR decomposition for matrices and its data applications
Saturday March 4th -- Tuesday March 7th:
Theory of Cryptography Conferece
(TCC 2006) in Columbia University. Registration required.
Wed, March 8th, 10:00am, Italian Academy (1161 Amsterdam ave, south of 118th st):
XML compression and indexing
Tue, March 21st, 4:00pm, Interschool Lab:
Risi Kondor: Learning on Groups and the Permceptron
Mon, March 27th, 4:00pm, CS Conference room (note unusual day, time, and place):
Expanders and the Elliptic Curve DLOG problem
Tue, April 4th, 4:00pm, Interschool Lab:
Lisa Fleischer: Cost Shares and Approximation Algorithms for Network Design Problems
Tue, April 11th, 4:00pm, Interschool Lab:
Seth Pettie: Low-distortion Graph Spanners
Tue, April 18th, 4:00pm, Interschool Lab:
Hardness of Directed Congestion Minimization
Monday April 24th -- Wednesday April 26th:
9th International Conference on
Practice and Theory in Public Key Cryptography (PKC 2006).
Friday April 28th:
The IBM Research | Columbia | NYU Theory Day.
Tue, May 2nd, 4:00pm, Interschool Lab:
Provably Near-Optimal Sampling-Based Policies for Stochastic Inventory Control Models
Thur, May 18th, 4:00pm, CS Conference room:
Fast Leader-Election Protocols with Bounded Cheaters' Edge
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 on this page are welcome; please send them to
Last updated 2/10/2006.
Back to Theory of Computation at Columbia