New answers tagged randomized-algorithms
2
Chapter 10.5.1 of Oded Goldreich's Introduction to Property Testing (2017) discusses exactly that question. (See his website for an overview of the book, and (free) access to the drafts.)
Now, Theorem 10.15 states there are properties, for instance cycle-freeness, subgraph-freeness, and degree regularity, which have $O_\varepsilon(1)$-query testers in the ...
Top 50 recent answers are included