Noisy Information and Computational Complexity: A Short Survey
| Title | Noisy Information and Computational Complexity: A Short Survey |
| Publication Type | Technical Report |
| Year of Publication | 1995 |
| Authors | Plaskota, L. |
| Other Numbers | 995 |
| Abstract | 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. |
| URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1995/tr-95-055.pdf |
| Bibliographic Notes | ICSI Technical Report TR-95-055 |
| Abbreviated Authors | L. Plaskota |
| ICSI Publication Type | Technical Report |