Past Combinatorics and Complexity Theory Seminars for 2001 - 2002
| 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 |