Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-066 | 13th August 2009 20:23

Lower Bounds for Testing Triangle-freeness in Boolean Functions


Authors: Arnab Bhattacharyya, Ning Xie
Publication: 14th August 2009 15:41
Downloads: 4216


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.

ISSN 1433-8092 | Imprint