Theory Seminar & talks
2006-2007
Academic Year
| Wednesday August 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 |
| Wednesday July 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 |
| Wednesday July 18, 2007 |
Theory Seminar: FCRC presentation Linear Probing with constant Independence (by A. Pagh, R. Pagh, and M. Ruzic) Scott Diehl 2:30 p.m. in 3310 CS |
| Wednesday July 11, 2007 |
Theory Seminar: FCRC presentation Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1 (by P. Indyk) Bess Berg 2:30 p.m. in 4310 CS |
| Wednesday May 9, 2007 |
Theory Chit-Chat CS 880 presentation: The Unique Games conjecture Tom Watson 4:00 p.m. in 4310 CS |
| Monday May 7, 2007 |
Theory of Computing Seminar Feasibility of Complex Equations and Primes in Arithmetic Progressions Maurice Rojas, Texas A&M University 4:00 p.m. in 4310 CS |
| Wednesday May 2, 2007 |
Theory of Computing Seminar Lower Bounds for AC^0 Circuits Augmented with Few Special Gates Kristoffer Hansen, University of Chicago 4:00 p.m. in 4310 CS |
| Friday April 27, 2007 |
Theory of Computing Seminar On defining integers and proving arithmetic circuit lower bounds Peter Buergisser, University of Paderborn 11:00 a.m. in 2310 CS |
| Wednesday April 25, 2007 |
Prelim Space Hierarchy Results for Semantic Models Jeff Kinne noon in 4310 CS |
| Wednesday April 18, 2007 |
Theory Chit-Chat Azuma's inequality Andrew Shallue 4:00 p.m. in 4310 CS |
| Wednesday April 11, 2007 |
Theory Chit-Chat Correlation-immune Boolean functions Eric Bach 4:00 p.m. in 4310 CS |
| Wednesday March 21, 2007 |
Theory Chit-Chat Lower bounds for swapping Arthur & Merlin Scott Diehl 4:00 p.m. in 4310 CS |
| Wednesday February 14, 2007 |
Theory Chit-Chat Holographic Algorithms Pinyan Lu, Tsinghua University 4:00 p.m. in 4310 CS |
| Wednesday February 7, 2007 |
Theory Chit-Chat Stochastic Optimization Shuchi Chawla 4:00 p.m. in 4310 CS |
| Thursday November 30, 2006 |
Theory of Computing Seminar Holographic Algorithms Leslie Valiant, Harvard University 9:00 a.m. in 2310 CS |
| Wednesday November 29, 2006 |
Distinguished Lecture Series Biology as Computation Leslie Valiant, Harvard University 4:00 p.m. in 1221 CS |
| Friday November 17, 2006 |
Theory of Computing Seminar Extractors and condensers from univariate polynomials Chris Umans, Caltech 1:30 p.m. in 2310 CS |
| Thursday November 16, 2006 |
Theory of Computing Seminar Algebraic Property Testing Madhu Sudan, MIT 9:30 a.m. in 2310 CS |
| Wednesday November 15, 2006 |
Distinguished Lecture Series Modelling Errors and Recovery for Communication Madhu Sudan, MIT 4:00 p.m. in 1221 CS |
| Thursday November 9, 2006 |
Theory of Computing Seminar Geometry and Expansion: A survey of recent results Sanjeev Arora, Princeton University 9:30 a.m. in 2310 CS |
| Wednesday November 8, 2006 |
Distinguished Lecture Series Why 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 Series The 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 Series The 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 Seminar Optimal Cost-Sharing Mechanisms Tim Roughgarden, Stanford University 4:00 p.m. in 2310 CS |
| Thursday, August 3, 2006 |
Theory of Computing Seminar Flow Algorithms for Two Pipelined Filtering Problems Lisa Hellerstein, Polytechnic University, Brooklyn, NY 3:30 p.m., 2310 CS |