property_testing (1928B)
1 # Property testing 2 3 You have an object O and a property P, and you want to determine if O has property P via local queries. Further, you have the promise that O either has the property P, or is ε-far from the property, i.e., the distance from O to any object X having the property is at least ε |X|. You want to minimize the [query_complexity] 4 5 Examples: 6 7 - [property_testing_formal_language] 8 - you want to test membership to a [formal_language] 9 - you can test which letter is at a given position 10 - the promise is on some proportion of the letters in the word 11 - [property_testing_Boolean_function] 12 - you want to test if a [Boolean_function] has a certain property 13 - is it a [constant_boolean_function] 14 - is it a [dictatorship_boolean_function] 15 - you can evaluate the function at some point 16 - the promise is on some proportion of the values of the truth table 17 - [property_testing_graph] 18 - you want to test a [graph_property] 19 - you can test whether some edge exists (dense graphs) or find the i-th neighbor of a vertex (sparse graphs of bounded degree) 20 - the promise is in some proportion of the values of the [adjacency_matrix] (dense graphs) or edges (sparse graphs) 21 - [property_testing_CSP] 22 - [property_testing_databases] 23 24 Typical framework: 25 26 - local obstructions that justify that you don't have the property 27 - e.g., a [triangle] in a graph, when determining if the graph is [triangle_free] 28 - e.g., x and y such that f(x) \neq f(y), when determining if a function is constant 29 - lemma: ε-far => contains many obstructions 30 - e.g., a graph which is ε-far from a triangle-free graph contains many triangles 31 - [Szemerédi's_Regularity_Lemma] 32 - sampling algorithm to find a local obstruction whp 33 34 Property testing and [computational_complexity]: cf [ferreirapinto2026computational] 35 36 Up: [computational_problem] 37 38 See also: [model_checking], [Approximate_membership], [tolerant_property_testing]