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
    (Abstract)


  • Mon, January 23rd, 11:00am in the Interschool Lab (7th floor CEPSR):   Mihalis Yannakakis: Knuth Lecture: Probability and Recursion
    (Abstract)


  • Thur, January 26th, 1:30pm, 520 Mudd (note unusual time and place):   Seffi Naor: Classification and Partitioning: Recent Bounds
    (Abstract)


  • Tue, February 14th, 4:00pm, Interschool Lab:   Petros Drineas: A relative-error CUR decomposition for matrices and its data applications
    (Abstract)


  • 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):   Paolo Ferragina: XML compression and indexing
    (Abstract)


  • Tue, March 21st, 4:00pm, Interschool Lab:   Risi Kondor: Learning on Groups and the Permceptron
    (Abstract)


  • Mon, March 27th, 4:00pm, CS Conference room (note unusual day, time, and place):   David Jao: Expanders and the Elliptic Curve DLOG problem
    (Abstract)


  • Tue, April 4th, 4:00pm, Interschool Lab:   Lisa Fleischer: Cost Shares and Approximation Algorithms for Network Design Problems
    (Abstract)


  • Tue, April 11th, 4:00pm, Interschool Lab:   Seth Pettie: Low-distortion Graph Spanners
    (Abstract)


  • Tue, April 18th, 4:00pm, Interschool Lab:   Lisa Zhang: Hardness of Directed Congestion Minimization
    (Abstract)


  • 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:   Retsef Levi: Provably Near-Optimal Sampling-Based Policies for Stochastic Inventory Control Models
    (Abstract)


  • Thur, May 18th, 4:00pm, CS Conference room:   Spyros Antonakopoulos: Fast Leader-Election Protocols with Bounded Cheaters' Edge
    (Abstract)


    Contact tal_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 2/10/2006.

    Back to Theory of Computation at Columbia main page