# 2001-2002 seminars

Monday, 24 September 2001 | Michael Elkin, Weizmann Institute (1 + \epsilon, \beta)-spanner constructions for general graphs |

Monday, 01 October 2001 | Ronitt Rubinfeld, NEC What can we do in sublinear time? |

Tuesday, 2 October 2001 | Boaz Barak, Weizmann Institute How to go beyond the black-box simulation barrier |

Monday, 08 October 2001 | Ehud Friedgut, The Hebrew University What makes a graph be a Ramsey Graph? An analysis via random graphs, a threshold phenomenon, and Szemeredi (hypergraph) regularity. |

Tuesday, 9 October 2001 | Michael Capalbo, IAS Explicit unique-neighbor expanders |

Monday, 22 October 2001 | Amit Sahai, Princeton University Zero Knowledge and Chosen-Ciphertext Security |

Tuesday, 23 October 2001 | Irit Dinur, IAS On the hardness of approximating vertex cover |

Wednesday, 24 October 2001 | David Galvin, Rutgers University Phase transition in the hard-core model on Z^d |

Monday, October 29 2001 | Andrew V. Goldberg, Reseaerch Fellow, InterTrust STAR Lab A Practical Shortest Path Algorithm with Linear Average Time |

Tuesday, October 30 2001 | Irit Dinur, IAS On the Hardness of Approximating Vertex Cover (Continued) |

Monday, November 5 2001 | Andrew Yao, Princeton University How to Generate a Random Polygon? |

Tuesday, November 6 2001 | Oded Regev, IAS The Unsplittable Flow Problem |

Monday, November 12 2001 | Amit Chakrabarti, Princeton University Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity |

Tuesday, November 13 2001 | Clifford Smyth, IAS Reimer's Inequality and Rudich's Conjecture |

Monday, November 19 2001 | Tim Gowers, Cambridge University and Princeton University A Tower-type Lower Bound for Szemer\'edi's Regularity Lemma |

Tuesday, November 20 2001 | Andris Ambainis, IAS Quantum Coin Flipping |

Monday, November 26 2001 | Sergei Konyagin, IAS Estimates for L Norms of Exponential Sums_{p} |

Tuesday, November 27 2001 | Clifford Smyth, IAS Reimer's Inequality and Rudich's Conjecture (Continued) |

Monday, December 3, 2001 | Amin Shokrollahi, Digital Fountain Capacity Achieving Sequences |

Monday, December 10, 2001 | Nicolas Sourlas, ENS, Paris On Statistical Mechanics and Cpacity Approaching Codes |

Tuesday, December 11, 2001 | Avi Wigderson, IAS Arithmetic Complexity - A Survey |

Monday, December 17, 2001 | Ilan Newman, NEC, Testing Monotonicity of Functions and Ruzsa-Szemer�di Type Graphs, |

Tuesday, December 18, 2001 | Avi Wigderson, IAS Do Algorithms Need Randomness? A Survey |

Monday, January 14, 2002 | Vladlen Koltun, Tel Aviv University Recent Developments Concerning Vertical Decompositions |

Tuesday, January 15, 2002 | Richard Beigel, IAS Learning a Hidden Matching |

Monday, January 21, 2002 | Avner Magen, NEC Research Institute Reduction of Dimensionality in Euclidean Space that Preserve Volumes, and Applications |

Monday, January 21, 2002 | Xiaodong Sun, Rutgers University Space Lower Bounds for Distance Approximation in the Data Stream Model |

Tuesday, January 22, 2002 | Richard Beigel, IAS and Noga Alon, IAS Learning a Hidden Matching |

Monday, January 28, 2002 | Alex Lubotzky, Hebrew University of Jerusalem Property 'Tau' and its Applications in Combinatorics, Computational Group Theory and Geometry, |

Tuesday, January 29, 2002 | Benjamin Sudakov, IAS Vertex List Coloring by Semirandom Method |

Monday, February 4, 2002 | Pavel Pudlak, Mathematical Institute, Academy of Sciences of the Czech Republic, Prague, Czech Republic An Application of Hindman's Theorem to a Problem on Communication Complexity |

Tuesday, February 5, 2002 | Noga Alon, Tel Aviv University and IAS Polynomials in Discrete Mathematics (A survey lecture) |

Thursday, February 7, 2002 | Mikkel Thorup, AT & T Research Compact Oracles for Reachability and Approximate Distances in Planar Digraphs |

Monday, February 11, 2002 | Vojta Rodl, Emory University Independent Deuber Sets in Graphs on the Natural Numbers |

Tuesday, February 12, 2002 | Noga Alon, Tel Aviv University and IAS Polynomials in Discrete Mathematics, II (A survey lecture) |

Monday, February 18, 2002 | Benjamin Sudakov, Princeton University and IAS Probabilistic Method and Ramsey Theory |

Monday, February 18, 2002 | Noga Alon, IASAddition, Codes and Subgraphs |

Tuesday, February 19, 2002 | Oded Regev, IAS Quantum Computation and Lattice Problems |

Monday, February 25, 2002 | Michael Krivelevich, Tel Aviv University Turan Numbers of Bipartite Graphs and Related Questions |

Tuesday, February 26, 2002 | Andris Ambainis, IAS Quantum Computing I (Survey Lecture) |

Monday, March 11, 2002 | Van H. Vu, University of California, SanDiego Generating Random Regular Graphs |

Tuesday, March 12, 2002 | Andris Ambainis, IAS Quantum Computing, Part II |

Monday, March 18, 2002 | Yi Zhao, Rutgers University Graph Tiling Problems |

Tuesday, March 19, 2002 | Andris Ambainis, IAS Quantum Computing, Part III |

Monday, March 25, 200 | Penny Haxell, University of Waterloo and Bell Labs Transverslas in Graphs |

Tuesday, March 26, 2002 | Alexander Razborov, IAS Proof Complexity, I (A Survey Lecture) |

Monday, April 1, 2002 | Kobbi Nissim, DIMACS and NEC Communication Complexity and Secure Function Evaluation |

Tuesday, April 2, 2002 | Alexander Razborov, IAS Proof Complexity, II (A Survey Lecture) |

Monday, April 8, 2002 | Alexei Kitaev, California Institute of Technology Quantum Interactive Proofs |

Tuesday, April 9, 2002 | Omer Reingold, IAS Randomness Conductors (A Survey Lecture) |

Monday, April 15, 2002 | Tibor Szabo, ETH Zurich Unique Sink Orientation of Cubes |

Tuesday, April 16, 2002 | Omer Reingold, IAS Randomness Conductors (Continued) |

Monday, April 22, 2002 | William Gasarch, University of Maryland Fault Diagnosis: What if the number of faulty processors is more than half? |

Tuesday, April 23, 2002 | Jozsef Balogh, IAS Monotone Graph Properties |

Friday, April 26, 2002 | Simon Kasif, Boston University Active Learning of Biological Systems |

Tuesday, April 30, 2002 | Michael Capalbo, IAS Explicity Unique-Neighbor Expanders |

Monday, May 6, 2002 | Tal Malkin, AT & T Labs - Research From Minicript to Cryptomania: Relationships among the Fundamental Cryptographic Primitives |

Tuesday, May 7, 2002 | Irit Dinur, Oded Regev and Clifford Smyth, IAS The Hardness of 3-Uniform Hypergraph Coloring |

Monday, May 13, 2002 | Frederic Green, Clark University and CWI The Correlation Between Parity and Quadratic Polynomials Mod 3 |

Tuesday, May 14, 2002 | Alexander Razborov, IAS Quantum Communication Complexity of Symmetric Predicates |

Monday, June 3, 2002 | Yaoyun Shi, California Institute of Technology Polynomial Approximations and Quantum Lower Bounds |

Monday, June 10, 2002 | Amir Amihood, AT & T Research Approximate Pattern Matching - The Hamming Distance Case |