Нашли опечатку? Выделите ее мышкой и нажмите Ctrl+Enter
Название: Algorithmic and Analysis Techniques in Property Testing
Автор: Ron D.
Аннотация:
Property testing algorithms are "ultra"-efficient algorithms that decide whether a given object (e.g., a graph) has a certain property (e.g., bipartiteness), or is significantly different from any object that has the property. To this end property testing algorithms are given the ability to perform (local) queries to the input, though the decision they need to make usually concerns properties with a global nature. In the last two decades, property testing algorithms have been designed for many types of objects and properties, amongst them, graph properties, algebraic properties, geometric properties, and more.