Average case optimality

G. W. Wasilkowski

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


Information-based complexity studies problems where only partial and contaminated information is available. One simply states how well a problem should be solved and indicates the type of information available. The theory then yields the optimal information, the optimal algorithm, and bounds on the problem complexity. In this paper we discuss some recent results dealing with the average case setting, i.e., the setting where both the cost and the error are measured on the average.

Original languageEnglish
Pages (from-to)107-117
Number of pages11
JournalJournal of Complexity
Issue number1
StatePublished - Oct 1985

Bibliographical note

Funding Information:
* Presented at the Symposium on Complexity of Approximately Solved Problems, April 17, 1985. ‘This research was supported in part by the National Science Foundation under Grant JXR-82-14322.

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Statistics and Probability
  • Numerical Analysis
  • General Mathematics
  • Control and Optimization
  • Applied Mathematics


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

Cite this