Columbia Theory Seminar, Spring 2008

For Spring 2008, the usual time for the meetings will be Wednesdays at 4:00pm in the CS conference room. Here is the current schedule of talks:

  • Friday, January 18, 11:00am, CSB 477 (Note unusual time and place): Ilias Diakonikolas (Columbia University): Succinct Approximate Convex Pareto Curves (Abstract)

  • Wednesday, January 30, 4:00pm, CS conference room: Uri Nadav (Tel Aviv University): Competitive Queue Management for Latency Sensitive Packets (Abstract)

  • Thursday, February 7th, 2:30pm, CSB 477 (Note unusual time and place): Emanuele Viola (Columbia University): Lower Bounds and the Power of Randomness (Abstract)

  • Wednesday, February 27, 4:00pm, CS conference room: Gregory V. Bard (Fordham University): Partitioning a System of Polynomial Equations via Graph Theory (Abstract)

  • Thursday, February 28, 4:10pm, CSB 477 (Note unusual time and place): Dana Dachman-Soled (Columbia University): Black-box Construction of a Non-Malleable Encryption Scheme from Any Semantically Secure One (Abstract)

  • Wednesday, March 5, 4:00pm, CS Conference Room: Nikhil Bansal (IBM TJ Watson Research Center): Degree bounded network design (Abstract)

  • Thursday, March 6th, 4:10pm, CSB 477 (Note unusual time and place): Mohammad Mahmoody-Ghidary (Princeton University): Optimality of Merkle's Scheme, and Black-Box Separation of Key-Exchange from One-Way Function. (Abstract)

  • Thursday, March 13, 4:10pm, CSB 477 (Note unusual time and place): Chris Peikert (SRI International):Lossy Trapdoor Functions and Their Applications (Abstract)

  • Wednesday, March 26th, 4:00pm, CS conference room: Iordanis Kerenidis (CRNS - Univ of Paris): Interactive and Noninteractive Zero Knowledge are equivalent in the Help Model (Abstract)

  • Wednesday, April 2nd, 4:00pm, CS conference room: Jin-Yi Cai (U of Wisconsin--Madison and Radcliffe Institute, Harvard University): Developments in Holographic Algorithms (Abstract)

  • Monday, April 14th, 12:45pm, CS conference room (Note unusual time): Alexandra Kolla (UC Berkeley and Princeton University): Unique Games on Expanding Constraint Graphs are Easy (Abstract)

  • Wednesday, April 16th, 4:00pm, CS conference room: Hoeteck Wee (Columbia University): Simple encryption schemes against sophisticated attacks (Abstract)

  • Wednesday, April 23rd, 4:00pm, CS conference room: Vitaly Feldman (IBM Almaden Research Center): Evolvability from Learning Algorithms (Abstract)

  • Wednesday, April 30th, 4:00pm, CS conference room: Emanuele Viola (Columbia University): Hardness amplification proofs require majority (Abstract)

  • Wednesday, May 7th, 4:00pm, CS conference room: Prasad Raghavendra (University of Washington): Optimal Algorithms and Inapproximability Results for Every CSP? (Abstract)

  • Wednesday, May 14th, 1:30pm, Interschool Lab (7th floor CEPSR) (Note unusual time and place): Andrew Wan (Columbia University): Optimal Cryptographic Hardness of Learning Monotone Functions (Abstract)

  • Wednesday, May 14th, 4:00pm, Interschool Lab (Note unusual place): Amir Shpilka (Technion): Reconstruction of depth-3 arithmetic circuits (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 02/01/2008.

    Back to Theory of Computation at Columbia main page