# 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 |