When Is Nonadaptive Information as Powerful as Adaptive Information?
Information based complexity is a unified treatment of problems where only partial or approximate information is available. In this approach one states how well a problem should be solved and indicates the type of information available. The theory then tells one optimal information and optimal algorithm and yields bounds on the problem complexity. In this paper we survey some recent results addressing one of the problems studied in information based complexity. The problem deals with nonadaptive and adaptive information both for the worst case and average case settings.
- cucs-149-84.pdf application/x-pdf 313 KB Download File
More About This Work
- Academic Units
- Computer Science
- Department of Computer Science, Columbia University
- Columbia University Computer Science Technical Reports, CUCS-149-84
- Published Here
- February 23, 2012