2002-2003 seminars
| Monday, September 9, 2002 | Valentine Kabanets, University of California, San Diego Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds |
| Monday, September 9, 2002 | Russell Impagliazzo, Universityo f California, San Diego A Switching Lemma for Small Restrictions and Lwer Bounds for k-DNF Resolution |
| Tuesday, September 17, 2002 | Dror Weitz, University of California, Berkeley Mixing in Time and Space on the Integer Lattice - A Combinatorial View |
| Monday, September 23, 2002 | Joel Spencer, Courant Institute Phase Transitions for Random Processes |
| Monday, September 23, 2002 | Jiri Matousek, Charles University, Prague Topological Lower Bounds for the Chromatic Number: A Hierarchy |
| Tuesday, September 24, 2002 | Sanjeev Arora, Princeton University Proving Integrality Gaps Without Knowing the Linear Program |
| Monday, September 30, 2002 | Moses Charikar, Princeton University Dimension Reduction in the 1_1 Norm |
| Tuesday, October 1, 2002 | Harmut Klauck, IAS Quantum Secruity in the Bounded Storage Model |
| Monday, October 7, 2002 | Tim Roughgarden, Cornell The Elusiveness of Braess's Paradox: Designing Networks for Selfish Users is Hard |
| Tuesday, October 8, 2002 | Ran Canetti, IBM Watson Research Center Universally Composable Security: Overview of the Paradigm and some Constructions |
| Monday, October 14, 2002 | Irit Dinur, NEC Research The Hardness of 3-Uniform Hypergraph Coloring |
| Tuesday, October 15, 2002 | Xiaodong Sun, IAS Time-Space Tradeoff Lower Bounds for Randomized Computation |
| Monday, October 21, 2002 | Jan Krajicek, Czech Academy of Sciences, Prague Free and Pseudo-Surjective Functions, and Provability of Circuit Lower Bounds |
| Tuesday, October 22, 2002 | Xiaodong Sun, IAS Time-Space Tradeoff Lower Bounds for Randomized Computation (Continued) |
| Monday, October 28, 2002 | Ravindran Kannan, Yale University Random Sub-Problems of a Given Problem |
| Tuesday, October 29, 2002 | Manindra Agarwal, IIT Kanpur, India Derandomizing Special Polynomial Identities via Cyclotomic Rings |
| Monday, November 4, 2002 | Assaf Naor, Microsoft Research Non-Linear Versions of Dvorestzky's Theorem |
| Tuesday, November 5, 2002 | Amit Chakrabarti, IAS A Lower Bound for Approximate Nearest Neighbor Searching |
| Monday, November 11, 2002 | Vijay V. Vazirani, Georgia Tech How Intractable is the "Invisible Hand": Polynomial Time Algorithms for Market Equilibria |
| Tuesday, November 12, 2002 | Amit Chakrabarti, IAS A Lower Bound for Approximate Nearest Neighbor Searching |
| Monday, November 25, 2002 | Christian Borgs, Microsoft, Research Erdos-Renyi Scaling for the n-Cube and Beyond |
| Monday, November 25, 2002 | Michael Langberg, Weizmann Institute Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers |
| Tuesday, November 26, 2002 | Luke Pebody, IAS Combinatorial Reconstruction using Invariant Polynomials |
| Tuesday, December 3, 2002 | Luke Pebody, IAS Combinatorial Reconstruction Using Invariant Polynomials (Continued) |
| Monday, December 9, 2002 | Leonid A. Levin, Boston University Forbidden Information |
| Tuesday, December 10, 2002 | Michael Elkin, IAS Inapproximability and Instance Complexity of the Distributed Minimum Spanning Tree Problem |
| Monday, December 16, 2002 | Eli Ben-Sasson, Harvard University Derandomizing Low Degree Tests via Epsilon-Biased Spaces |
| Tuesday, December 17, 2002 | Daniel Rockmore, IAS Path Algebras for FFTs on Groups |
| Monday, January 13, 2003 | Amir Shpilka, Harvard University and MIT Lower Bounds for Matrix Multiplication |
| Tuesday, January 14, 2003 | Oded Regev, IAS New Lattice Based Cryptographic Constructions |
| Monday, January 20, 2003 | Peter Winkler, Bell Labs A Second Threshold for the Hard-Core Model |
| Tuesday, January 21, 2003 | Michael Elkin, IAS Inapproximability of the Distributed Minimum Spanning Tree Problem |
| Monday, January 27, 2003 | Peter Keevash, Princeton University The Exact Turan Number of the Fano Plane |
| Tuesday, January 28, 2003 | Paul Seymour, Princeton University Perfect Graphs |
| Monday, February 3, 2003 | Janos Pach, City College, NY and Renyi Institute, Budapest The Number of Directions Determined by n Points in Space |
| Tuesday, February 4, 2003 | Noga Alon, Tel Aviv University and IAS Testing Large Directed Graphs |
| Monday, February 10, 2003 | Ehud Friedgut, Hebrew University of Jerusalem Coloring Products of Graphs, a Fourier Approach |
| Tuesday, February 11, 2003 | Benny Sudakov, Princeton University and IAS Set-Systems with Restricted $k$-wise intersections |
| Monday, February 17, 2003 | Alexander Soifer, DIMACS, Rutgers University and University of Colorado Chromatic Number of the Plane and its Relatives: History, Problems, Results |
| Tuesday, February 18, 2003 | Hartmut Klauck, IAS Quantum Time-Space Tradeoffs for Sorting |
| Monday, February 24, 2003 | Marek Karpinski, University of Bonn Approximation Complexity of MIN-BISECTION Problems |
| Tuesday, February 25, 2003 | Alexander Razborov, IAS Systems of Linear Equations Hard for k-DNF Resolution |
| Monday, March 3, 2003 | Ryan O'Donnell, MIT Coin Flipping From a Cosmic Source; or, On Error Correction of Truly Random Bits |
| Tuesday, March 4, 2003 | Xiaodong Sun, IAS Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument (on the paper by Iordanis Kerenidis and Ronald de Wolf) |
| Monday, March 10, 2003 | Rocco Servedio, Columbia University Learning Juntas |
| Tuesday, March 11, 2003 | Van Vu, University of California at San Diego Long Arithmetic Progressions in Sumsets and Erd�s-Folkman Conjecture |
| Monday, March 17, 2003 | Alexander Soifer, DIMACS, Rutgers University and University of Colorado Chromatic Number of the Plane and Its Relatives: History, Problems, Results |
| Tuesday, March 18, 2003 | Amit Chakrabarti, IAS Lower Bounds for Multi-Party Set Disjointness |
| Monday, March 24, 2003 | Daniele Micciancio, University of California, San Diego Generalized Compact Knapsacks, Cyclic Lattices, and efficient One-Way Functions from Worst-Case Complexity Assumptions |
| Monday, March 24, 2003 | Laslo Lovasz, Microsoft Research Discrete Analytic Functions and Global Information from Local Observation |
| Tuesday, March 25, 2003 | Madhu Sudan, MIT Algebraic Constraint Satisfaction Problems |
| Tuesday, March 25, 2003 | Luca Trevisan, Berkeley University List-Decoding Using the XOR Lemma |
| Monday, March 31, 2003 | Bo Brinkman, Princeton University On the Impossibility of Dimension Reduction in l1 |
| Tuesday, April 1, 2003 | Omer Reingold, IAS Extractors - Optimal Up To Constant Factors |
| Monday, April 7, 2003 | Bela Bollobas, University of Memphis and University of Cambridge Scale-free Random Graphs |
| Monday, April 14, 2003 | Michael Krivelevich, Tel Aviv University, Israel Adding Random Edges to Dense Graphs |
| Monday, April 21, 2003 | Muli Safra, Tel Aviv University, Analysis of Boolean Functions and Various Applications |
| Monday, April 28, 2003 | Bruce Reed, McGill University Partial Results on the Total Colouring Conjecture |
| Monday, May 5, 2003 | Leonid Khachiyan, Rutgers University Dual-Bounded Monotone Properties |
| Monday, May 12, 2003 | Edith Elkind, Princeton University Frugality in Path Auctions |
| Monday, June 2, 2003 | Graham Cormode, DIMACS Tracking Frequent Items Dynamically |
| Tuesday, June 3, 2003 | Hartmut Klauck, IAS On the Rectangle Bound in Communication Complexity |
| Thursday, June 5, 2003 | Guy Kindler, Tel-Aviv University Noise-Resistant Boolean Functions are Juntas |
| Monday, June 16, 2003 | Jozsef Balogh, Ohio State University Optimal Integer Arrangement on the Square Grid |