Noisy Information and Computational Complexity: A Short Survey

TitleNoisy Information and Computational Complexity: A Short Survey
Publication TypeTechnical Report
Year of Publication1995
AuthorsPlaskota, L.
Other Numbers995

In the modern world, the importance of information can be hardly overestimated. Information also plays a prominent role in scientific computations. A branch of computational complexity which deals with problems for which information is partial, noisy, and priced is called information-based complexity.In most of the work on information-based complexity, the emphasis was on partial and exact information. We concentrate our attention on noisy information. We consider deterministic and random noise. The analysis of noisy information leads to a variety of new algorithms and complexity results.This short survey has a reach extension in the form of a monograph 'Noisy Information and Computational Complexity', to be published in Cambridge University Press.

Bibliographic Notes

ICSI Technical Report TR-95-055

Abbreviated Authors

L. Plaskota

ICSI Publication Type

Technical Report