**
Theory Seminar & talks**

2006-2007

Academic Year

WednesdayAugust 1, 2007 |
Theory Seminar: FCRC presentation Verifying and Decoding in Constant Depth (by S. Goldwasser,
D. Gutfreund, A. Healy, T. Kaufman, and G.N. Rothblum)
Jeff Kinne 2:30 p.m. in 4310 CS |

WednesdayJuly 25, 2007 |
Theory Seminar: FCRC presentation Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication
Gates (by A. Shpilka)
Matt Anderson 2:30 p.m. in 4310 CS |

WednesdayJuly 18, 2007 |
Theory Seminar: FCRC presentationLinear Probing with constant Independence (by A.
Pagh, R. Pagh, and M. Ruzic)
Scott Diehl 2:30 p.m. in 3310 CS |

WednesdayJuly 11, 2007 |
Theory Seminar: FCRC presentationUncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1 (by P. Indyk)
Bess Berg 2:30 p.m. in 4310 CS |

WednesdayMay 9, 2007 |
Theory Chit-ChatCS 880 presentation: The Unique Games conjecture
Tom Watson 4:00 p.m. in 4310 CS |

MondayMay 7, 2007 |
Theory of Computing SeminarFeasibility of Complex Equations and Primes in Arithmetic Progressions
Maurice Rojas, Texas A&M University 4:00 p.m. in 4310 CS |

WednesdayMay 2, 2007 |
Theory of Computing SeminarLower Bounds for AC^0 Circuits Augmented with Few Special Gates
Kristoffer Hansen, University of Chicago 4:00 p.m. in 4310 CS |

FridayApril 27, 2007 |
Theory of Computing SeminarOn defining integers and proving arithmetic circuit lower bounds
Peter Buergisser, University of Paderborn 11:00 a.m. in 2310 CS |

WednesdayApril 25, 2007 |
PrelimSpace Hierarchy Results for Semantic Models
Jeff Kinne noon in 4310 CS |

WednesdayApril 18, 2007 |
Theory Chit-ChatAzuma's inequality
Andrew Shallue 4:00 p.m. in 4310 CS |

WednesdayApril 11, 2007 |
Theory Chit-ChatCorrelation-immune Boolean functions
Eric Bach 4:00 p.m. in 4310 CS |

WednesdayMarch 21, 2007 |
Theory Chit-ChatLower bounds for swapping Arthur & Merlin
Scott Diehl 4:00 p.m. in 4310 CS |

WednesdayFebruary 14, 2007 |
Theory Chit-ChatHolographic Algorithms
Pinyan Lu, Tsinghua University 4:00 p.m. in 4310 CS |

WednesdayFebruary 7, 2007 |
Theory Chit-ChatStochastic Optimization
Shuchi Chawla 4:00 p.m. in 4310 CS |

ThursdayNovember 30, 2006 |
Theory of Computing SeminarHolographic Algorithms
Leslie Valiant, Harvard University 9:00 a.m. in 2310 CS |

WednesdayNovember 29, 2006 |
Distinguished Lecture SeriesBiology as Computation
Leslie Valiant, Harvard University 4:00 p.m. in 1221 CS |

FridayNovember 17, 2006 |
Theory of Computing SeminarExtractors and condensers from univariate polynomials
Chris Umans, Caltech 1:30 p.m. in 2310 CS |

ThursdayNovember 16, 2006 |
Theory of Computing Seminar Algebraic Property Testing
Madhu Sudan, MIT 9:30 a.m. in 2310 CS |

WednesdayNovember 15, 2006 |
Distinguished Lecture Series Modelling Errors and Recovery for Communication
Madhu Sudan, MIT 4:00 p.m. in 1221 CS |

ThursdayNovember 9, 2006 |
Theory of Computing SeminarGeometry and Expansion: A survey of recent results
Sanjeev Arora, Princeton University 9:30 a.m. in 2310 CS |

WednesdayNovember 8, 2006 |
Distinguished Lecture SeriesWhy NP got a new definition: the quest to understand the
approximation properties of NP-hard optimization problems
Sanjeev Arora, Princeton University 4:00 p.m. in 1221 CS |

Thursday,October 19, 2006 |
Theory of Computing Seminar The sum-product theorem and its applications
Avi Wigderson, Institute for Advanced Study, Princeton 9:30 a.m. in 2310 CS |

Wednesday,October 18, 2006 |
Distinguished Lecture SeriesThe Power and Weakness of Randomness in Computation
Avi Wigderson, Institute for Advanced Study, Princeton 4:00 p.m. in 1221 CS |

Friday,September 29, 2006 |
Theory of Computing Seminar Uniform Proof Complexity
Stephen Cook, University of Toronto 10:00 a.m. in 2310 CS |

Thursday,September 28, 2006 |
Distinguished Lecture SeriesThe P vs NP Problem and its Place in Complexity Theory
Stephen Cook, University of Toronto 4:00 p.m. in 1800 Engineering Hall |

Thursday,September 7, 2006 |
Theory of Computing SeminarOptimal Cost-Sharing Mechanisms
Tim Roughgarden, Stanford University 4:00 p.m. in 2310 CS |

Thursday,August 3, 2006 |
Theory of Computing SeminarFlow Algorithms for Two
Pipelined Filtering Problems
Lisa Hellerstein, Polytechnic University, Brooklyn, NY 3:30 p.m., 2310 CS |