Average case Optimality for Linear Problems

acknowledge the sunport of the Advanced Research ~rojects Agency under Contract N00039-82-C-0427. We introduce an average case ~odel and define general notions of optimal algorithm and optLmal info~.ation. t~e prove that the same algorithm and information are optimal in the ~'orst and average cases and that adaptive information is not r.ore powerful than non-adaptive information