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.