Combinatorics Seminar
When: Sunday, December 6, 10am
Where: Schreiber 309
Speaker: Ning Xie, MIT
Title: Lower Bounds for Testing Triangle-freeness in
Boolean Functions
Abstract:
Let f_1,f_2, f_3:F_2^{n}->{0,1} be three Boolean functions.
We say a triple (x,y,x+y) is a 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 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 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>n_0 there exists
a function-triple f_1,f_2, f_3:F_2^{n}->{0,1} depending on all
the n variables which is \epsilon-far from being triangle-free and
requires (1/\epsilon)^{4.847...} queries for the canonical
tester.
For the single function case that f_1=f_2=f_3, we obtain a
weaker lower bound of (1/\epsilon)^{3.409...}. 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...} and (1/\epsilon)^{1.704...}
query complexity lower bounds for multi-function and
single-function
triangle-freeness respectively, with respect to general one-sided
testers.
Joint work with Arnab Bhattacharyya.