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:

Date & Time

September 01, 1998 | 12:00am – September 01, 1999 | 12:00am

Categories