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 Lp Norms of Exponential Sums
 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, IAS
Addition, 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