The Taub Faculty of Computer Science Events and Talks

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 among the three functions. The distance between a function triple and triangle-free functions is the minimum fraction of the function values one needs to modify in order to make the function triple triangle-free. A canonical tester for triangle-freeness is to pick x and y uniformly at random and check if f_{1}(x)=f_{2}(y)=f_{3}(x+y)=1.

Based on a regularity lemma for Boolean functions, Ben Green showed a tower type upper bound on the number of queries for the canonical testing algorithm. In this talk, we discuss 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 a 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 conjecture that our approach may lead to super-polynomial query complexity lower bounds for testing triangle-freeness. We also prove a Goldreich-Trevisan type theorem for Boolean functions, showing that the query complexities of a canonical tester and that of a general one-sided tester are polynomially related.

Joint work with Ning Xie.