Average case optimality for linear problems

J. F. Traub, G. W. Wasilkowski, H. Woźniakowski

Research output: Contribution to journalArticlepeer-review

18 Scopus citations


We introduce an average case model and define general notions of optimal algorithm and optimal information. We prove that the same algorithm and information are optimal in the worst and average cases and that adaptive information is not more powerful than non-adaptive information.

Original languageEnglish
Pages (from-to)1-25
Number of pages25
JournalTheoretical Computer Science
Issue number1-2
StatePublished - 1984

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Average case optimality for linear problems'. Together they form a unique fingerprint.

Cite this