Columbia Theory Seminar, Spring 2005

For Spring 2005, the usual time and place for the meetings will be Thursdays at 2:30pm in the CS conference room. Here is a schedule of seminars:

  • Thurs, February 17, 2:30pm in the CS Conference Room:   Homin Lee: Cryptography in NC^0 (Appelbaum, Ishai, Kushilevitz).
    (Abstract)

  • Tues, February 22, 2:00pm in Interschool Lab (note unusual time and place) : Umesh Vazirani: AdWords and Generalized Online Matching
    (Abstract)

  • Thurs, February 24, 1:30pm in 303 Mudd, joint seminar with IEOR (note unusual time and place) : Chaitanya Swamy: Approximation Algorithms for Stochastic Optimization
    (Abstract)

  • Tues, March 22, 2:30pm in Interschool Lab (note unusual time and place) : Christina Fragouli: Information Flow Decomposition for Network Coding
    (Abstract)

  • Thurs, March 24, 1:30pm in 307 Uris, joint seminar with IEOR (note unusual time and place) : Andrew Goldberg: A* Search with Triangle Inequality
    (Abstract)

  • Wed, March 30, 10:00am in the CS conference room (note unusual date and place): Krysta Svore: Pseudothreshold or threshold? - Identifying quantum fault-tolerance thresholds
    (Abstract)

  • Thurs, March 31, 2:30pm in the CS conference room: David Phillips: Approximation Algorithms for Semidefinite Packing Problems with Applications to Max-Cut and Graph Coloring
    (Abstract)

  • Thurs, April 14, 2:30pm in 620 Mudd (note unusual location): Mihalis Yannakakis: Recursive Markov Chains
    (Abstract)

  • Fri April 15, 9:30am-4:30pm in Davis Auditorium: (note unusual time, date, and location):

    The Columbia | NYU | IBM Research THEORY DAY

  • Thurs, April 21, 2:30pm in the CS conference room: Salil Vadhan: An Unconditional Study of Computational Zero Knowledge
    (Abstract)

  • Thurs, April 28, 2:30pm in the CS conference room: Guy Rothblum: The Complexity of Online Memory Checking
    (Abstract)

  • Thurs, May 5, 2:30pm in the CS conference room: Uri Rothblum: Linear Problems and Linear Algorithms
    (Abstract)

  • Thurs, May 12, 2:30pm in the CS conference room: Noga Alon: Property Testing and Additive Approximation for Edge Deletion Problems
    (Abstract)

  • Thurs, May 26, 2:30pm in the CS conference room: Krishnaram Kenthapadi: Balanced Allocations on Graphs
    (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 5/3/2005.

    Back to Theory of Computation at Columbia main page