Combinatorics and Complexity Theory

The seminar on Combinatorics and Theoretical Computer Science at the Institute for Advanced Study took 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, 1 November 1999
  Because of a DIMACS Workshop on Probabilistic Analysis
  there is no talk scheduled for this date
  For more information see:
  http://dimacs.rutgers.edu/Workshops/ProbAnal/program.html

 

• 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, 20 March 2000
  Because of a DIMACS Workshop at Rutgers University
  there is no seminar scheduled for this date.
  For more information see:
  http://dimacs.rutgers.edu/archive/Workshops/CryptIntract/

 

• 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: