TOC Seminar Fall 2000

September 14, 2000
Russell Impagliazzo, University of California, San Diego
Title: HILL CLIMBING IS AS GOOD AS METROPOLIS FOR PLANTED BISECTION PROBLEMS
Host: Madhu Sudan

September 21, 2000
CANCELLED Instead, see Operations Research Seminar
September 28, 2000
Igor Pak, MIT
Title: GENERATING RANDOM ELEMENTS IN FINITE GROUPS AND THE PRODUCT REPLACEMENT ALGORITHM
Host: Madhu Sudan

October 5, 2000
Piotr Indyk, MIT
Title: STABLE DISTRIBUTIONS, PSEUDORANDOM GENERATORS, EMBEDDINGS AND DATA STREAM COMPUTATION
Host: Madhu Sudan

October 12, 2000
No TOC seminar, LCS Distinguished Lecture Series instead
Edgerton Hall, Room 34-101, 3:30 PM (reception 3:15)
Dr. Michael Stonebraker, Chief Technology Officer, Cohera Corporation
Title: The Future of Object-Relational Technology

October 19, 2000
Phillip Rogaway, University of California, Davis
Title: RECONCILING TWO VIEWS OF CRYPTOGRAPHY
Host: Silvio Micali

Wednesday, November 1, 2000
Prabhakar Raghavan, Verity, Inc.
Title: NETWORKS AND SUB-NETWORKS IN THE WORLD-WIDE WEB
Host: Madhu Sudan

November 2, 2000
Adam Meyerson, Stanford University
Title: ALGORITHMS FOR BUY-AT-BULK NETWORK DESIGN
Piotr Indyk

November 9, 2000
Venkatesan Guruswami, MIT
Title: HARDNESS OF APPROXIMATE HYPERGRAPH COLORING
Piotr Indyk

Tuesday, November 21, 2000
Refreshments at 3:45 p.m., talk at 4 p.m.
Mikhail Alekhnovitch, Institute for Advanced Study
Title: RESOLUTION: LOWER BOUNDS AND COMPLEXITY OF SEARCH FOR OPTIMAL PROOFS
Host: Michael Sipser

November 23, 2000
No TOC seminar: Thanksgiving.

Tuesday, November 28, 2000
Tal Malkin, AT& T Shannon Labs
Title: THE RELATIONSHIP BETWEEN PUBLIC-KEY ENCRYPTION AND OBLIVIOUS TRANSFER
Host: Silvio Micali

November 30, 2000
No TOC seminar, LCS Distinguished Lecture Series instead
Edgerton Hall, Room 34-101, 3:30 PM (reception 3:15)
Professor Robert Brodersen, Professor of Electrical Engineering and Computer Science, University of California at Berkeley
Title: The Case Against Von Neumann Architectures in System-on-a-Chip Design

Tuesday, December 5, 2000
David Johnson, AT& T Labs -- Research
Title: PET PEEVES AND PITFALLS IN THE EXPERIMENTAL ANALYSIS OF HEURISTICS
Host: Madhu Sudan

December 7, 2000
Michael Mitzenmacher, Harvard University
Title: IP ROUTING BASED ON DOUBLE HASHING
Host: Madhu Sudan

December 14, 2000
Lars Engebretsen, MIT
Title: TOWARDS OPTIMAL LOWER BOUNDS FOR CLIQUE AND CHROMATIC NUMBER
Host: Piotr Indyk