next up previous
Next: The Best of Both Up: The Technion Period (1986-94) Previous: Hard-core Predicates for any

On the Theory of Average Case Complexity

This paper takes the next step in developing the theory of average case complexity initiated by Levin, by investigating basic computational questions such as the equivalence of search and decision problems in the context of average case complexity. In addition, we consider average case complexity with respect to efficiently sampleable distributions (rather than distributions with an efficiently computable accomulative function as considered by Levin).


Comments: Authored by S. Ben-David, B. Chor, O. Goldreich and M. Luby. Appeared in



Oded Goldreich
2003-07-30