bathie2021property (646B)
1 # bathie2021property 2 3 by [gabriel] and [tatiana_starikovskaya] 4 5 - Shows that there is a "hard" [regular_language] for which [property_testing_formal_language] requires Omega(log(1/ε)/ε) 6 - There are "easy" [regular_languages] needing Theta(1/ε) queries 7 - e.g., a^* 8 - There are "trivial" [regular_languages] where 0 queries are needed for large enough n 9 - any sufficiently long [word] cannot be [epsilon_far] from the [formal_language] 10 11 Uses the notion of [blocking_factor]: they sample random [factors] and check if they are [blocking_factors] 12 13 Follow-up: [bathie2025trichotomy] 14 15 Up: [academic_paper] on [property_testing_formal_language]