AVERAGE CASE E-COMPLEXITY IN COMPUTER SCIENCE: A BAYESIAN VIEW
Original Publication Date: 1983-Jul-31
Included in the Prior Art Database: 2007-Mar-29
Software Patent Institute
Kadane, J.B.: AUTHOR [+3]
AVERAGE CASE €-COMPLEXITY IN COMPUTER, SCIENCE : A BAYESIAN VIEW
AVERAGE CASE €-COMPLEXITY
IN COMPUTER, SCIENCE :
A BAYESIAN VIEW
J. 8. Kadane Carnegle-Mellon Unlvers~ty
G. W. Wasilkowski Columb~a University
TABLE OF CONTENTS
1 Worst Case Analysis
2 Averagc Case Anaysis
3 A Bayesian Interpretation of the Average Case Model
4 An Application to Factor Analysis
Tht authors are grateful to H. T, Kung, M. I. Shainos and J. F. Traub for the~r roles In bringing them together. Joseph B. Kadane was supported in part by ONR Contract 014-82- K-0622 and G. W. Wasilkowski was supported in part by the National Science Foundat~on under Grant MCS-7823676.
Relations between average case t -complexity and Bayesian statistics are discussed. An algorithm corresponds to a decision function. and the choice of information to the choice of an experiment. Adaptive information in 6-complexity theory corresponds to the concept of sequential experiment. Some results are reported, giving 6-complexity and minimax-Bayesian interpretations for factor analysis. Results from 6-complexity are used to establish that t k optimal sequential design is no better than optimal nonsequential design for that problem.
This paper shows that average case analysis of algorithms and Information in c-complexity theory is related to to optimal decisions and experiments, respectively. in Bayesian Theory. Finding such relations betwwn problems in previously disjoint literatures is exciting both because one discovers a new set of colleagues and because results obtained in each literature can illuminate the other.
Sections 1 and 2 explain, respectively. the worst-case and averagccase analysls of algorithms. Section 3 establishes t h correspondence mentioned abave. Finally, Sectlon 4 hscusses some results from the average case c-complexity literature, and ~ t s mterpretation for Bayesians. We hope that the relatlon reported here can lead to further fruitful results for both fields.
1 Worst Case Analysis
in ths section we briefly present some major quest~ons addressed tn c-complexity theory. We
first ducuss the worst case model wkch is concr?ptually simpler than tbc average case model, discussed ln Sectlon 2.
An expository account of c -complexity theory (wtuch ~s also known as informat~on-centered
theory) may be found m Traub and ~oz'ntakowski (1983). T k general worst case model u
presented u two research monographs: Traub and ~oz&rakowski
( 1980) and Traub, Was~lkowsk~ and ~o&akowski (1983). T k first of these has an extensive annotated blbllography. Reports
on the average case model are cited in Section 2.