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