Princeton Seminars in Theoretical Computer Science

Princeton Seminars in Theoretical Computer Science, Spring 2001

(All events held at the Computer Science Department, 35 Olden St., unless if stated otherwise).

Feb 9, Friday 12noon Mikkel Thorup, AT&T Approximate Distance Oracles
Feb 12, Monday, 4pm (not a lunch, of course): Dan Spielman, MIT Quasi-worst case analysis
Feb 16, Friday, Theory Lunch: Yevgeniy Dodis, NYU: "Exposure-Resilient Cryptography"
Mar 16, Friday, Theory Lunch: Yuval Ishai, DIMACS: "Randomizing Polynomials"
Apr 6, Friday, Theory Lunch: Ran Canetti, IBM: "Universal Reductions for Security"
Apr 20, Friday, Theory Lunch: Ronitt Rubinfeld, NEC: "Testing Distributions"
May 18, Friday, Theory Lunch: Jason Hartline, University of Washington: On Auctions (Title TBA).

Princeton Seminars in Theoretical Computer Science, Fall 2000

(All events held at the Computer Science Department, 35 Olden St., unless if stated otherwise).

Fri, Sept 29, 12noon. Dieter van Melkebeek, IAS. Time-space tradeoffs for satisfiability.
Fri Oct 13, 12noon. Gil Kalai, IAS. Some thoughts on the fourier transform of finite functions.
Thurs. Oct 26, 12noon. Harvey Friedman, Ohio State. How to use a large cardinal.
Fri Nov 17. Lisa Fleischer, CMU. Strongly polynomial algorithms..
Fri Dec 1, 12 noon. Timothy Gowers, Cambridge and Princeton.
Fri. Dec 8, 12 noon. Mihalis Yannakakis, Lucent Bell Labs. Approximability of tradeoffs.

Princeton Seminars in Theoretical Computer Science, Spring 2000

Tues., March 7, 12:10pm. Avi Wigderson. Computational Pseudorandomness.
(CS-Math Joint Seminars, Fine Hall 314. Lunch served in Math Common Room at 11:45am)

Wed. March 8, 4pm, Small Auditorium : Moses Charikar, Stanford University. Algorithms for Clustering

Tues, March 21. 12 noon in Room 103, CS Building. Charles Fefferman, Princeton University.
The Uniqueness Problem for Neural Nets
Wed., March 22, 4pm, Small Auditorium: Salil Vadhan, MIT. Pseudorandomness: Connections and Constructions
Thurs. March 23, 9:50am-5pm PACT Theory Day at NEC Research (4 Independence Way, 3miles N of Princeton on Route 1)
Talks by A. Wigderson, M. Goodrich, J. Kleinberg, S. Arora, B. Charron, J. Stern, D. Johnson.
Wed. March 29, 4:30 PM: Avi Wigderson at Wolfensohn Hall, IAS. The Digital Envelope - A Crash Course in Modern Cryptography.
Mon, April 3, 3:30pm. Small Auditorium. Piotr Indyk, Stanford. High-dimensional Computational Geometry.
Thurs., April 6, 4pm. Small Auditorium. Amit Sahai, MIT. Statistical Zero Knowledge
Wed. April 12, 4:30 PM: Avi Wigderson at the Math Dept Colloquium, Fine Hall 314. Some Insights of Computational Complexity Theory
Thurs., April 13, 4pm. Small Auditorium. Kamal Jain. Enhancing techniques in LP based approximation algorithms.
Fri., April 14 12:05pm: Richard Ladner, University of Washington. Algorithms for On-Demand Stream Merging
Fri, April 21, 12noon: Rafail Ostrovsky, Telcordia Research. Recent results in private info retrieval.
Tues, April 25 12:10 (lunch served 11:45): Room 314 of Fine Hall. Math-CS Seminar. Sanjeev Arora,
Princeton University. Polynomial-time algorithm to learn mixtures of arbitrary gaussians.

Princeton Dimacs Seminars (Theory Lunches), Fall 1999

Held on Fridays at noon in Room 402, CS Building

Sept 24: Ronitt Rubinfeld, NEC Research. "Highly Efficient PCPs for Optimization Problems."
Oct 1: TBA
Oct 8: Lance Fortnow. One complexity theorist's view of quantum computing.