## Keywords (6)

Publications
Lower Bounds for Testing Triangle-freeness in Boolean Functions

# Lower Bounds for Testing Triangle-freeness in Boolean Functions,Arnab Bhattacharyya,Ning Xie

Lower Bounds for Testing Triangle-freeness in Boolean Functions
Letf1,f2,f3 : Fn 2 ! {0,1} be three Boolean functions. We say a triple (x,y,x+y) is a triangle in the function-triple (f1,f2,f3) iff1(x) = f2(y) = f3(x +y) = 1. (f1,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 iff1(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 n0( ) such that for all n n0 there exists a function-triple f1,f2,f3 : Fn 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 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.
View Publication
 The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
 ( portal.acm.org ) ( portal.acm.org ) ( www.siam.org )
More »

## Citation Context (4)

• ...Of course, despite all this progress, this area abounds with questions with some basic ones being: Which subclass of locally characterizaed affine-invariant properties are locally testable? When can the rejection probability of the test be lower bounded by a polynomial in the distance to the property? Some progress in this direction is reported in Bhattacharyya and Xing [17]...

### Madhu Sudan. Invariance in Property Testing

• ...This question was raised by Green [24]; see [44] for current best bounds...

### Arnab Bhattacharyya, et al. A Unified Framework for Testing Linear-Invariant Properties

• ...Partial progress in this direction is reported in the work of Bhattacharyya and Xie [BX10]...

### Arnab Bhattacharyya, et al. Testing Linear-Invariant Non-linear Properties: A Short Report

• ...is super-polynomial. The only result in this direction was obtained recently by Bhattacharyya and Xie [8] who showed that this relation is super-linear...

Sort by:

## Citations (5)

### Invariance in Property Testing(Citations: 6)

Published in 2010.

### A Unified Framework for Testing Linear-Invariant Properties(Citations: 3)

Published in 2010.

### Testing Linear-Invariant Non-linear Properties: A Short Report(Citations: 1)

Published in 2010.

### A Proof of Green's Conjecture Regarding the Removal Properties of Sets of Linear Equations(Citations: 6)

Published in 2008.