# 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, BerkeleyMixing in Time and Space on the Integer Lattice - A Combinatorial View Monday, September 23, 2002 Joel Spencer, Courant InstitutePhase Transitions for Random Processes Monday, September 23, 2002 Jiri Matousek, Charles University, PragueTopological Lower Bounds for the Chromatic Number: A Hierarchy Tuesday, September 24, 2002 Sanjeev Arora, Princeton UniversityProving Integrality Gaps Without Knowing the Linear Program Monday, September 30, 2002 Moses Charikar, Princeton UniversityDimension Reduction in the 1_1 Norm Tuesday, October 1, 2002 Harmut Klauck, IASQuantum Secruity in the Bounded Storage Model Monday, October 7, 2002 Tim Roughgarden, CornellThe Elusiveness of Braess's Paradox: Designing Networks for Selfish Users is Hard Tuesday, October 8, 2002 Ran Canetti, IBM Watson Research CenterUniversally 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, IASTime-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, IASTime-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, IndiaDerandomizing 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, IASA 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, IASA Lower Bound for Approximate Nearest Neighbor Searching Monday, November 25, 2002 Christian Borgs, Microsoft, ResearchErdos-Renyi Scaling for the n-Cube and Beyond Monday, November 25, 2002 Michael Langberg, Weizmann InstituteGraphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers Tuesday, November 26, 2002 Luke Pebody, IASCombinatorial 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 UniversityForbidden 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 UniversityDerandomizing Low Degree Tests via Epsilon-Biased Spaces Tuesday, December 17, 2002 Daniel Rockmore, IASPath Algebras for FFTs on Groups Monday, January 13, 2003 Amir Shpilka, Harvard University and MITLower Bounds for Matrix Multiplication Tuesday, January 14, 2003 Oded Regev, IASNew Lattice Based Cryptographic Constructions Monday, January 20, 2003 Peter Winkler, Bell LabsA Second Threshold for the Hard-Core Model Tuesday, January 21, 2003 Michael Elkin, IASInapproximability of the Distributed Minimum Spanning Tree Problem Monday, January 27, 2003 Peter Keevash, Princeton UniversityThe Exact Turan Number of the Fano Plane Tuesday, January 28, 2003 Paul Seymour, Princeton UniversityPerfect Graphs Monday, February 3, 2003 Janos Pach, City College, NY and Renyi Institute, BudapestThe Number of Directions Determined by n Points in Space Tuesday, February 4, 2003 Noga Alon, Tel Aviv University and IASTesting Large Directed Graphs Monday, February 10, 2003 Ehud Friedgut, Hebrew University of JerusalemColoring Products of Graphs, a Fourier Approach Tuesday, February 11, 2003 Benny Sudakov, Princeton University and IASSet-Systems with Restricted $k$-wise intersections Monday, February 17, 2003 Alexander Soifer, DIMACS, Rutgers University and University of ColoradoChromatic Number of the Plane and its Relatives: History, Problems, Results Tuesday, February 18, 2003 Hartmut Klauck, IASQuantum Time-Space Tradeoffs for Sorting Monday, February 24, 2003 Marek Karpinski, University of BonnApproximation Complexity of MIN-BISECTION Problems Tuesday, February 25, 2003 Alexander Razborov, IASSystems of Linear Equations Hard for k-DNF Resolution Monday, March 3, 2003 Ryan O'Donnell, MITCoin Flipping From a Cosmic Source; or, On Error Correction of Truly Random Bits Tuesday, March 4, 2003 Xiaodong Sun, IASExponential 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 UniversityLearning Juntas Tuesday, March 11, 2003 Van Vu, University of California at San DiegoLong Arithmetic Progressions in Sumsets and Erd�s-Folkman Conjecture Monday, March 17, 2003 Alexander Soifer, DIMACS, Rutgers University and University of ColoradoChromatic Number of the Plane and Its Relatives: History, Problems, Results Tuesday, March 18, 2003 Amit Chakrabarti, IASLower Bounds for Multi-Party Set Disjointness Monday, March 24, 2003 Daniele Micciancio, University of California, San DiegoGeneralized Compact Knapsacks, Cyclic Lattices, and efficient One-Way Functions from Worst-Case Complexity Assumptions Monday, March 24, 2003 Laslo Lovasz, Microsoft ResearchDiscrete Analytic Functions and Global Information from Local Observation Tuesday, March 25, 2003 Madhu Sudan, MITAlgebraic Constraint Satisfaction Problems Tuesday, March 25, 2003 Luca Trevisan, Berkeley UniversityList-Decoding Using the XOR Lemma Monday, March 31, 2003 Bo Brinkman, Princeton UniversityOn the Impossibility of Dimension Reduction in l1 Tuesday, April 1, 2003 Omer Reingold, IASExtractors - Optimal Up To Constant Factors Monday, April 7, 2003 Bela Bollobas, University of Memphis and University of CambridgeScale-free Random Graphs Monday, April 14, 2003 Michael Krivelevich, Tel Aviv University, IsraelAdding 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 UniversityPartial Results on the Total Colouring Conjecture Monday, May 5, 2003 Leonid Khachiyan, Rutgers UniversityDual-Bounded Monotone Properties Monday, May 12, 2003 Edith Elkind, Princeton UniversityFrugality in Path Auctions Monday, June 2, 2003 Graham Cormode, DIMACSTracking Frequent Items Dynamically Tuesday, June 3, 2003 Hartmut Klauck, IASOn the Rectangle Bound in Communication Complexity Thursday, June 5, 2003 Guy Kindler, Tel-Aviv UniversityNoise-Resistant Boolean Functions are Juntas Monday, June 16, 2003 Jozsef Balogh, Ohio State UniversityOptimal Integer Arrangement on the Square Grid