Average Case ϵ-Complexity in Computer Science: A Bayesian View
- Average Case ϵ-Complexity in Computer Science: A Bayesian View
- Kadane, Joseph B.
Wasilkowski, Grzegorz W.
- Technical reports
- Computer Science
- Persistent URL:
- Columbia University Computer Science Technical Reports
- Part Number:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- Relations between average case ϵ-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 ϵ-complexity theory corresponds to the concept of sequential experiment. Some results are reported, giving ϵ-complexity and minimax-Bayesian interpretations for factor analysis. Results from ϵ-complexity are used to establish that the optimal sequential design is no better than optimal nonsequential design for that problem.
- Computer science
- Item views
text | xml
- Suggested Citation:
- Joseph B. Kadane, Grzegorz W. Wasilkowski, 1983, Average Case ϵ-Complexity in Computer Science: A Bayesian View, Columbia University Academic Commons, http://hdl.handle.net/10022/AC:P:11553.