*
*

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 |