期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2009
卷号：2009
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Let f 1 f 2 f 3 : F n 2 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 . A trivial query complexity lower bound of (1 ) 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 there exists an integer n 0 ( ) such that for all n n 0 there exists a function-triple f 1 f 2 f 3 : F n 2 0 1 depending on all the n variables which is -far from being triangle-free and requires ( 1 ) 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 ) 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 ) 2 423 and (1 ) 1 704 query complexity lower bounds for multi-function and single-function triangle-freeness respectively, with respect to general one-sided testers.
f 2 
