Lower Bounds for Testing Triangle-freeness in Boolean Functions
Arnab Bhattacharyya, Ning Xie · NOT FOUND REPOSITORY (Indian Institute of Science Bangalore) · 2009
Given a Boolean function f: Fn2 → {0, 1}, we say a triple (x, y, x + y) is a triangle in f if f(x) = f(y) = f(x + y) = 1. A triangle-free function contains no triangle. If f differs from every triangle-free function on at least ·2n points, then f is said to be -far from triangle-free. In this work, we analyze the query complexity of testers that, with constant probability, distinguish triangle-free functions from those -far from triangle-free. Let the canonical tester for triangle-freeness denote the algorithm that repeatedly picks x and y uniformly and independently at random from Fn2, queries f(x), f(y) and f(x+ y), and checks whether f(x) = f(y) = f(x + y) = 1. Green showed that the canonical tester rejects functions -far from triangle-free with constant probability if its query complexity is a tower of 2’s whose height is polynomial in 1/. Fox later improved the height of the tower in Green’s upper bound to O(log 1/). A trivial lower bound of Ω(1/) on the query complexity is immediate. In this paper, we give the first non-trivial lower bound for the number of queries needed. We show that, for every small enough , there exists an integer n0() such that for all n ≥ n0 there exists a function f: Fn2 → {0, 1} depending on all n variables which is -far from being triangle-free and requires Ω (1/)4.847··· queries for the canonical tester. 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 means that any one-sided tester for triangle-freeness must make at least Ω (1/)2.423··· queries.