When Is Nonadaptive Information as Powerful as Adaptive Information?

Traub, Joseph F.; Wasilkowski, Grzegorz W.; Wozniakowski, Henryk

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.



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