Sunflowers and Testing Triangle-Freeness of Functions
Ishay Haviv, Ning Xie · 2015
A function f : Fn/2 → {0,1} is triangle-free if there are no x1, x2, x3 ∈ Fn/2 satisfying x1 + x2 + x3 --0 and f(x1) -- f(x2) -- f(x3) -- 1. In testing triangle freeness, the goal is to distinguish with high probability triangle-free functions from those which are ε-far from being triangle-free. It was shown by Green that the query complexity of the canonical tester for the problem is upper bounded by a function that depends only on ε (GAFA, 2005), however the best known upper bound is a tower type function of 1/ε. The best known lower bound on the query complexity of the canonical tester is 1/ε13.239 (Fu and Kleinberg, RANDOM, 2014).