Distribution-Free Testing Algorithms for Monomials with a Sublinear Number of Queries

by Elya Dolev and Dana Ron.

Oded's comments

When Dana, Shafi and me were working on what became [GGR], our starting point was the distribution-free setting (which is the main setting of computational learning theory). (Our actual focus on the uniform distribution was rather a consequence of the positive results that we were able to prove and viewed as a "proof of concept" (for property testing).) Indeed, the distribution-free setting turned out very hard to handle, and the current work present -- in my opinion -- to most impressive positive result to date.

Prior work established an $Omega(n^{0.2-o(1)})$ lower bound for (distribution-free) testing the properties being considered here, and so any (distribution-free) tester of $o(n)$ query complexity is of interest. The current work establishes a $O(n^{0.5+o(1)})$ upper bound, and leaves open the question of closing the gap. Another important challenge is extending the positive results to other properties (for which lower bounds are known).

The original abstract

See RANDOM'10 proceedings (LNCS 6302).


Back to list of Oded's choices.