Combinatorics and Complexity Theory

Wednesday, September 1, 1999 (All day) to Friday, June 30, 2000 (All day)
(1999-2000)

The seminar on Combinatorics and Theoretical Computer Science at the Institute for Advanced Study will take place every
Monday at 11 a.m. in room 101, the seminar room in Simonyi Hall.

 

  • Monday, 27 September 1999
    Michael Saks, Rutgers University
    An Improved Exponential-time Algorithm for k CNF Satisfiability
    Abstract:

 

 

  • Monday, 4 October 1999
    Leonid Gurvits, NECI
    Operator Scaling and Approximating the Mixed Discriminant
    Abstract:

 

  • Monday, 11 October 1999
    Ran Raz, The Weizmann Institute of Science, Israel
    Exponential Separation of Quantum and Classical Communication Complexity,
    and some Geometrical Properties of the Sphere S^n

    Abstract:

 

  • Monday, 18 October 1999
    There is no talk scheduled for this date

 

  • Monday, 25 October 1999
    Eldar Fischer, Tel Aviv University
    Graph embeddings via the Regularity Lemma
    Abstract:

 

  • Monday, 8 November 1999
    Eli Ben-Sasson, Hebrew University
    Many Hard Examples for the Polynomial Calculus
    Joint Work with Russell Impagliazzo, from UCSD

    Abstract:

 

  • Monday, 15 November 1999
    Jeff Kahn, Rutgers University
    Entropy, Independent Sets and Antichains
    Abstract:

 

  • Monday, 22 November 1999
    Luca Trevisan, Columbia University
    A PCP Characterization of NP with Optimal Amortized
    Query Complexity
    Abstract:

 

  • Monday, 29 November 1999
    Leslie G. Valiant, Harvard University
    Robust Logic
    Abstract:

 

  • Monday, 6 December 1999
    Ehud Friedgut, MSRI and UC Berkeley
    Projections of Subsets of the Discrete and Continuous Cube
    Abstract:

 

  • Monday, 13 December 1999
    Dorit Aharonov, UC Berkeley
    A Quantum to Classical Phase Transition in Noisy Quantum Computers
    Abstract:

 

  • Monday, 17 January 2000
    Jozsef Beck, Rutgers University
    The Erdos-Szekeres Game
    Abstract:

 

  • Monday, 24 January 2000
    Alex Samorodnitsky, IAS
    On the optimum of Delsarte's linear program
    Abstract:

 

  • Monday, 31 January 2000
    Yuval Peres, Hebrew University
    Two Erdos problems on lacunary sequences: Chromatic
    number and diophantine approximation

    Abstract:

 

  • Monday, 7 February 2000
    Seminar will be held at 2:00 p.m., this week only
    Noga Alon, Tel Aviv University
    Economical covers with geometric applications
    Abstract:

 

  • Monday, 14 February 2000
    Madhu Sudan, MIT
    List decoding of error-correcting codes
    Abstract:

 

  • ADDITIONAL SEMINAR
    Tuesday, 15 February 2000
    2:00 p.m.
    Johan Hastad, Royal Institute of Technology
    Some optimal inapproximability results
    Abstract:
  • NO SEMINAR MONDAY, FEBRUARY 21, 2000 DUE TO
    DIMACS WORKSHOP AT PRINCETON UNIVERSITY

 

  • Monday, 28 February 2000
    Ronen Shaltiel, IAS
    Extracting Randomness via Repeated Condensing
    Abstract:

 

  • Monday, 06 March 2000
    Peter Winkler, Bell Labs
    Percolation and Collision
    Abstract:

 

  • Monday, 13 March 2000
    Benny Sudakov, IAS/Princeton University
    Max Cut and the Smallest Eigenvalue
    Abstract:

 

  • Monday, 27 March 2000
    Andrew Yao, Princeton University
    On Quantum Complexity of Graph Properties
    Abstract:

 

  • Monday, 03 April 2000
    Russell Impagliazzo, UC San Diego
    Convex complexity measures
    THIS SEMINAR TO BE HELD IN THE WEST BUILDING
    LECTURE HALL

    Abstract:

 

  • NO SEMINAR MONDAY, APRIL 10, 2000 DUE TO
    DIMACS WORKSHOP

 

  • Monday, 17 April 2000
    Alexander Razborov, IAS/Princeton University
    Pseudorandom Generators in Propositional Proof Complexity
    Abstract:

 

  • Monday, 24 April 2000
    Bela Bollobas, Memphis and Cambridge
    Polynomial Invariants of Graphs On Surfaces
    Abstract:

 

  • Monday, 01 May 2000
    Gregory Freiman, Tel Aviv University
    Analytical Methods in Integer Programming
    Abstract:

 

  • Monday, 08 May 2000
    Omer Reingold, AT&T and IAS
    Selective Decommitment, Magic Functions and 3-Round
    Zero-Knowledge

    Abstract:
events: