## 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.