On the Theory of Average Case Complexity

Shai Ben-David Benny Chor Oded Goldreich Michael Luby

Published in: STOC (1989)

Keyphrases

average case complexity
theoretical framework
orders of magnitude
average case
computational complexity
lower bound
query language
image compression