Columbia Theory Seminar, Fall 2007

For Fall 2007, the usual time for the meetings will be Wednesdays at 1:30pm in the open area conference room, 476 CS building. Here is the current schedule of talks:

  • Wednesday, September 19, 1:30pm, CSB 476: Ilias Diakonikolas (Columbia University): Succinct Approximation of Multiobjective Optimization Problems (Abstract)

  • Wednesday, October 3, 1:30pm, CSB 476: Venkatesan Guruswami (Univ. of Washington and Institute for Advanced Study): Lossless Expanders from Parvaresh-Vardy Codes with applications to Randomness Extraction (Abstract)

  • Wednesday, October 10, 1:30pm, CSB 476: Sergei Vassilvitskii (Yahoo Research): k-means++: The advantages of careful seeding (Abstract)

  • Wednesday, October 17, 1:30pm, CSB 476: Practice FOCS talks: Emanuele Viola (Columbia University): Pseudorandom Bits for Polynomials and Spyros Antonakopoulos (Columbia University): Buy-at-Bulk Network Design with Protection (Abstracts)

  • Wednesday, October 31, 1:30pm, CSB 476: Jason Hartline, Northwestern University: Optimal Mechanism Design: from the 2007 Nobel Prize in Economics to the Foundations of Internet Algorithms (Abstract)

  • Wednesday, November 7, 1:30pm, CSB 476: Elliot Anshelevich (Rensselaer Polytechnic Institute): Terminal Backup, 3D Matching and Covering Cubic Graphs (Abstract)

  • Wednesday, November 14, 1:30pm, CSB 476: Anup Rao (Institute for Advanced Study): Deterministic Extractors for Small Space Sources (Abstract)

  • Wednesday, November 28, 1:30pm, CSB 476: Tal Rabin (IBM TJ Watson Research Center): Information-Theoretically Secure Protocols and Security Under Composition (Abstract)

  • Wednesday, December 5th, 1:30pm, CEPSR 620: Costas Daskalakis (UC Berkeley): Computing Approximate Nash Equilibria (Abstract)

  • Friday, December 7th: New York Area Theory Day at NYU

  • Wednesday, December 12th, 1:30pm, CSB 476: Vinod Vaikuntanathan (MT): Trapdoors for Hard Lattices, and New Cryptographic Constructions (Abstract)
    Contact 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 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 9/10/2007.

    Back to Theory of Computation at Columbia main page