**
Theory Seminar
2004-2005
Academic Year
**

Monday,
July 26, 2004 | Theory of Computing Seminar
Top-down Analysis of Path Compression
Raimund Seidel, Saarland University 2:30 pm, 2310 CS |

Friday,
November 19, 2004 | Theory of Computing Seminar
Learning Intersections of Halfspaces
Adam Klivans, Toyota Technological Institute at Chicago and University of Texas at Austin 2:30 pm, 1221 CS |

Tuesday,
November 23, 2004 | Theory of Computing Seminar
Three applications of dynamic programming
to network management
David S. Johnson, AT&T Labs-Research 4:00 pm, 1240 CS |

Monday,
December 6, 2004 | Theory of Computing Seminar
Average-Case Analysis of an Algorithm from Computer Algebra
Kevin Compton, University of Michigan 2:30 pm, 2310 CS |

Thursday,February 10, 2005 |
Workshop on Quantum Computation
Quantum information, computation, and communicationRichard Cleve, University of Waterloo 2:30 p.m., 1800 Engineering Hall |

Thursday,February 10, 2005 |
Workshop on Quantum Computation
Prospects for real quantum information processing devices in the laboratoryDavid DiVincenzo, IBM Watson Research Center 3:45 p.m., 1800 Engineering Hall |

Thursday,February 10, 2005 |
Workshop on Quantum Computation
The future of quantum information processing: how big, how fast, how powerful?Seth Lloyd, MIT 5:00 p.m., 1800 Engineering Hall |

Thursday,February 24, 2005 |
Faculty Candidate Talk
Linear Programming and ArrangementsVladlen Koltun, University of California-Berkeley 4:00 p.m., 1221 CS |

Tuesday,April 5, 2005 |
J. Barkley Rosser Memorial Lecture
Secrets and Proofs: The Role of RandomnessProf. Shafi Goldwasser, M.I.T. 3:30 p.m., AB20 Weeks Hall |

Thursday,April 7, 2005 |
Faculty Candidate Talk
Algorithms for Path PlanningShuchi Chawla, Carnegie Mellon University 4:00 p.m., 1221 CS |

Monday,May 23, 2005 |
Theory of Computing Seminar
Algorithms PSSPS - The Pseudosquares Prime Sieve
Jon Sorenson, Butler University 2:30 p.m., 2310 CS |

Tuesday,June 21, 2005 |
Theory of Computing Seminar
The Unique Games Conjecture, Integrality Gap for Cut
Problems and the Embeddability of Negative Type Metrics into L_1
Nisheeth K. Vishnoi, IBM Research, New Delhi 10:00 a.m., 2310 CS |

Thursday,June 30, 2005 |
Practice Talk
Time-Space Lower Bounds for the Polynomial-Time
Hierarchy on Randomized Machines
Scott Diehl 4:00 p.m., 3331 CS |