In defining what it means to be a tester for property , I wrote: if satisfies then Pr[ accepts] and if is -far from satisfying then Pr[ accepts] . I then added that the and here is "arbitrary" and could be "boosted".
This phrasing is pretty imprecise, and an anonymous commenter asked what exactly I meant. What's meant is this: Suppose you have a tester making queries that satisfies the given definition. Then for any constant , there is another tester making queries that satisfies the definition with and in place of and . So if you don't care about constant factors in the number of queries, then the choice of and is arbitrary. In "testing" we don't usually care about constant factors on the number of queries, although in "local testing" we often do.
The way to get from is to just run it many times independently and then accept iff at least half of the runs accepted. Then the Chernoff bound implies the claim.
Tuesday, January 30, 2007
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment