Combinatorics Seminar
When: Sunday, April 10, 10am
Where: Schreiber 309
Speaker: Dana Ron, Tel Aviv U.
Title: Distribution-Free Testing Algorithms for Monomials
with a Sublinear Number of Queries
Abstract:
We consider the problem of distribution-free testing
of the class of monotone monomials and the class of monomials
over $n$ variables. While there are very efficient algorithms
for testing a variety of functions classes when the underlying
distribution is uniform, designing distribution-free algorithms
(which must work under any arbitrary and unknown distribution),
tends to be a more challenging task. When the underlying
distribution
is uniform, Parnas et al. ({\em SIAM Journal on Discrete Math,
2002\/})
give an algorithm for testing (monotone) monomials whose query
complexity
does not depends on $n$, and whose dependence on the distance
parameter is (inverse) linear. In contrast, Glasner and Servedio
({\em Theory of Computing, 2009\/}) prove that every
distribution-free testing algorithm for monotone monomials as
well as for general monomials must have query
complexity $\tilde{\Omega}(n^{1/5})$ (for a constant
distance parameter $\epsilon$).
We present distribution-free testing algorithms
for these classes where the query complexity of the algorithms
is $\tilde{O}(n^{1/2}/\eps)$. We note that as opposed to previous
results for distribution-free testing, our algorithms do not
build on the algorithms that work under the uniform distribution.
Rather, we define and exploit certain structural properties of
monomials
(and functions that differ from them in a non-negligible manner),
which were not used in previous work on property testing.
Joint work with Elya Dolev