TR09-066 Authors: Arnab Bhattacharyya, Ning Xie

Publication: 14th August 2009 15:41

Downloads: 4117

Keywords:

Let $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.