A Nearly-Quadratic Gap Between Adaptive and Non-Adaptive Property Testers

Details A Nearly-Quadratic Gap Between Adaptive and Non-Adaptive Property Testers A Nearly-Quadratic Gap Between Adaptive and Non-Adaptive Property Testers

2011-02-25

arxiv.org/abs/1102.5309v3

Computer Science

Data Structures and Algorithms

Keywords: Sublinear-Time Algorithms, Property Testing, Dense-Graph Model, Adaptive vs Nonadaptive Queries, Hierarchy Theorem

Scientific paper

We show that for all integers $t\geq 8$ and arbitrarily small $\epsilon>0$, there exists a graph property $\Pi$ (which depends on $\epsilon$) such that $\epsilon$-testing $\Pi$ has non-adaptive query complexity $Q=\~{\Theta}(q^{2-2/t})$, where $q=\~{\Theta}(\epsilon^{-1})$ is the adaptive query complexity. This resolves the question of how beneficial adaptivity is, in the context of proximity-dependent properties (\cite{benefits-of-adaptivity}). This also gives evidence that the canonical transformation of Goldreich and Trevisan (\cite{canonical-testers}) is essentially optimal when converting an adaptive property tester to a non-adaptive property tester. To do so, we provide optimal adaptive and non-adaptive testers for the combined property of having maximum degree $O(\epsilon N)$ and being a \emph{blow-up collection} of an arbitrary base graph $H$.

Affiliated with

Also associated with

No associations

Rating

A Nearly-Quadratic Gap Between Adaptive and Non-Adaptive Property Testers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Nearly-Quadratic Gap Between Adaptive and Non-Adaptive Property Testers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Nearly-Quadratic Gap Between Adaptive and Non-Adaptive Property Testers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-710334