ECCC-Report TR09-066https://eccc.weizmann.ac.il/report/2009/066Comments and Revisions published for TR09-066en-usFri, 14 Aug 2009 15:41:30 +0300
Paper TR09-066
| Lower Bounds for Testing Triangle-freeness in Boolean Functions |
Arnab Bhattacharyya,
Ning Xie
https://eccc.weizmann.ac.il/report/2009/066Let $f_{1},f_{2}, f_{3}:\mathbb{F}_{2}^{n} \to \{0,1\}$ be three Boolean functions.
We say a triple $(x,y,x+y)$ is a \emph{triangle} in the function-triple $(f_{1}, f_{2}, f_{3})$ if $f_{1}(x)=f_{2}(y)=f_{3}(x+y)=1$.
$(f_{1}, f_{2}, f_{3})$ is said to be \emph{triangle-free} if there is no triangle in the triple. The distance between a function-triple
and triangle-freeness is the minimum fraction of function values one needs to modify in order to make the function-triple triangle-free.
A \emph{canonical tester} for triangle-freeness repeatedly picks $x$ and $y$ uniformly and independently at random and checks
if $f_{1}(x)=f_{2}(y)=f_{3}(x+y)=1$. Based on an algebraic regularity lemma, Green showed that the number of queries for the canonical
testing algorithm is upper-bounded by a tower of $2$'s whose height is polynomial in $1/\epsilon$. A trivial query complexity
lower bound of $\Omega(1/\epsilon)$ is straightforward to show. In this paper, we give the first non-trivial query complexity
lower bound for testing triangle-freeness in Boolean functions. We show that, for every small enough $\epsilon$ there exists
an integer $n_{0}(\epsilon)$ such that for all $n\geq n_{0}$ there exists a function-triple
$f_{1},f_{2}, f_{3}:\mathbb{F}_{2}^{n} \to \{0,1\}$ depending on all the $n$ variables which
is $\epsilon$-far from being triangle-free and requires $(\frac{1}{\epsilon})^{4.847\cdots}$ queries for the canonical tester.
For the single function case that $f_{1}=f_{2}=f_{3}$, we obtain a weaker lower bound of $(\frac{1}{\epsilon})^{3.409\cdots}$.
We also show that the query complexity of any general (possibly adaptive) one-sided tester for triangle-freeness is at least
square-root of the query complexity of the corresponding canonical tester.
Consequently, this yields $(1/\epsilon)^{2.423\cdots}$ and $(1/\epsilon)^{1.704\cdots}$ query complexity lower bounds
for multi-function and single-function triangle-freeness respectively, with respect to general one-sided testers.Fri, 14 Aug 2009 15:41:30 +0300https://eccc.weizmann.ac.il/report/2009/066