The art of uninformed decisions: a primer to property testing. (English) Zbl 1082.68123
Păun, G. (ed.) et al., Current trends in theoretical computer science. The challenge of the new century. Vol. 1: Algorithms and complexity. River Edge, NJ: World Scientific (ISBN 981-238-966-0/hbk; 981-238-783-8/set). 229-263 (2004).
Summary: Property testing is a new field in computational theory that deals with the information that can be deduced from the input where the number of allowable queries (reads from the input) is significantly smaller than the input size. This survey provides an introduction and reference to this exciting field.
For the entire collection see [Zbl 1047.68163].
For the entire collection see [Zbl 1047.68163].
MSC:
| 68W20 | Randomized algorithms |
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
