Combinatorics and Complexity Theory

The following is a list of seminars that were given in Term I and Term II:

• Monday, 28 September 1998
  Dana Ron, MIT
  A sublinear bipartite tester for bounded-degree graphs
  Abstract:

   

• Monday, 5 October 1998
  Luca Trevisan, Columbia University and DIMACS
  Construction of near-optimal extractors using pseudo-random generators
  Abstract:

   

• Monday, 12 October 1998
  Avi Wigderson, IAS/Hebrew University
  Resolution made simple
  Abstract:

   

• Monday, 19 October 1998
  Paul Seymour, Princeton University
  Digraph Minors
  Abstract:

   

• Monday, 26 October 1998
  Dmitry Kozlov, IAS
  On the action of the symmetric group on the selected-type
  partition lattices
  Abstract:

   

• Monday, 9 November 1998
  Michael Saks, Rutgers University
  Time-Space tradeoffs for Boolean branching programs
  Abstract:

   

• Monday, 16 November 1998
  Bela Bollobas, Memphis State University and Cambridge University
  Dependent percolation in two dimensions
  Abstract:

   

• Monday, 23 November 1998
  Dorit Aharonov, IAS
  Shor's Quantum Factorization Algorithm
  Abstract:

   

• Monday, 30 November 1998
  Vijay Vazirani, Georgia Tech
  On the Bidirected cut relaxation for the metric Steiner tree problem
  Abstract:

   

• Monday, 7 December 1998
  Jeff Kahn, Rutgers University
  Combinatorial uses of entropy
  Abstract:

   

• Monday, 14 December 1998
  Jean Bourgain, IAS
  Arithmetic progressions in finite sets
  Abstract:

   

• Monday, 18 January 1999
  Michael Krivelevich, DIMACS/Rutgers University
  Testing regular languages
  Abstract:

   

• Monday, 25 January 1999
  Miklos Bona, IAS
  A combinatorial proof of the log-concavity of the numbers of
  permutations with k runs
  Abstract:

   

• Monday, 1 February 1999
  Yehuda Shalom, Princeton University
  Groups and expanders
  Abstract:

   

• Monday, 8 February 1999
  Van Vu, IAS
  Small complete arcs in projective planes
  Abstract:

   

• Monday, 22 February 1999
  Meir Katchalski, Rutgers/Technion, Israel
  Touching and representing convex sets
  Abstract:

   

• Monday, 1 March 1999
  Avi Wigderson, IAS
  Some problems in algebraic complexity
  Abstract: