Academic Commons

Reports

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.

Subjects

Files

More About This Work

Academic Units
Computer Science
Publisher
Department of Computer Science, Columbia University
Series
Columbia University Computer Science Technical Reports, CUCS-149-84
Published Here
February 23, 2012
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.