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