Lower bounds for testing triangle-freeness in Boolean functions Conference

Bhattacharyya, A, Xie, N. (2010). Lower bounds for testing triangle-freeness in Boolean functions . 87-98. 10.1137/1.9781611973075.9

cited authors

  • Bhattacharyya, A; Xie, N

authors

abstract

  • Let f1, f2, f3 : F2n → {0,1} be three Boolean functions. We say a triple (x, y, x + y) is a triangle in the function-triple (f1, f2, f3) if f1(x) = f2(y) = f3 (x + y) = 1. (f 1, f2, f3) 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 f1(x) = f2 (y) = f3(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 no(ε) such that for all n ≥ no there exists a function-triple f1, f2, f3 : F 2n → {0, 1} depending on all the n variables which is ε-far from being triangle-free and requires (1/ε) 4.47⋯ queries for the canonical tester. For the single function case that f1 = f2 = f3, 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. Copyright © by SIAM.

publication date

  • January 1, 2010

Digital Object Identifier (DOI)

International Standard Book Number (ISBN) 13

start page

  • 87

end page

  • 98