Next: The Best of Both
Up: The Technion Period (1986-94)
Previous: Hard-core Predicates for any
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
- Proc. of the 21st STOC, pp. 204-216, 1989.
- Journal
of Computer and system Sciences,
Vol. 44, No. 2, April 1992, pp. 193-219.
Oded Goldreich
2003-07-30