Thursday
August 25 2005 |
Topic: Min-wise perumatutions
Eric Skaug will lead the discussion.
1:00pm, 4397 CS.
|
Thursday
August 18 2005 |
Topic:
Irit Dinur's proof of the PCP Theorem
3:30pm, 4397 CS.
|
Thursday
August 4 2005 |
Topic: Metric Embeddings (Including
Bourgain's Theorem)
Eric Skaug will lead the discussion.
1:00pm, 4397 CS.
|
Thursday
July 14 2005 |
Topic: Random walks and circuit resistance.
Michael Kowalczyk will lead the discussion.
1:00pm, 4397 CS.
|
Thursday
June 30 2005 |
Paper presentation:
Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized
Machines by Scott Diehl and Dieter van Melkebeek.
Scott will present his recent research.
4:00pm, 3331 CS.
|
Wednesday
June 8 2005 |
Topic: average case complexity.
References:
notes on Levin's Theory of Average-Case Complexity,
A Personal View of Average-Case Complexity,
On the Theory of Average Case Complexity.
Jeff will lead the discussion.
1:00-2:30, 4397 CS.
|
Friday
June 3 2005 |
Topic: time hierarchies for semantic classes.
Reference:
Time Hierarchies for Computations with a Bit of Advice by
Konstantin Pervyshev.
Bess will lead the discussion.
12:00-1:30, 4397 CS.
|
Thursday
May 26 2005 |
Topic: If P!=NP, there are
NP-intermediate problems.
Reference: Ladner's theorem.
1:00-2:00, 4397 CS.
|
