Theory Reading Seminar

Fall 2004:

Thursdays, 15:00-17:00, Ross 79.

Organizer: Dorit Aharonov

Semester's Topic: Average case complexity




Date	Paper	Speaker
4-11-04	Russell's paper from 1995: "A personal view of Average case complexity", which can be downloaded from Russell Impagliazzo's homepage.	Dorit Aharonov
11-11-04	Levin's complete problem (1986) for distributional NP, from Oded Goldreich's Notes on Levin's Theory of Average-Case Complexity from 1997.	Elan Pavlov
18-11-04	The paper by Impagliazzo and Levin, showing the surprising result that No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random. from 1990.	Adin Rosenberg
25-11-04	The equivalence of search and decision problems for Average case complexity, S. Ben-David, B. Chor, O. Goldreich and M. Luby, On the Theory of Average Case Complexity, 1989 Plus a continuation of last time's paper.	Adin and Dorit
2-12-04	Ajtai's worst case to average case reductions on lattice problems, 1996. Generating Hard instances of lattice problems See also: Complexity of SVP---A reader's digest by Kumar and Sivakumar. See also this short description . A reference to Cai's paper will be added.	Irit Dinur
9-12-04	Regev and Miccianco's recent paper (2004) Worst-case to Average-case Reductions based on Gaussian Measure improving on Ajtai's result.	Alex Samorodnitsky
16-12-04	Continuation of Previous talk	Alex Samorodnitsky
23-12-04	Regev's paper from 2002, providing a public key cryptosystem based on the assumption that a lattice problem is hard in the worst case: New lattice based cryptographic constructions.	Elon Portugali
30-12-04	No meeting: School Retreat	-
6-01-05	Miklós Ajtai: Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties. FOCS 2002: 733-742	Michael Ben-Or
13-01-05	No meeting	-
20-01-05	Ryen O'Donnel's paper	Katerina Shechtman
24-01-05?	Uri Feige's paper, Relations between average case complexity and approximation complexity. Proceedings of 34th STOC, 2002, 534--543.	Ran Shallom