Sunflowers and Testing Triangle-Freeness of Functions

Understand

A function $f: \mathbb{F}_2^n \rightarrow \{0,1\}$ is triangle-free if there are no $x_1,x_2,x_3 \in \mathbb{F}_2^n$ satisfying $x_1+x_2+x_3=0$ and $f(x_1)=f(x_2)=f(x_3)=1$.

• In testing triangle-freeness, the goal is to distinguish with high probability triangle-free functions from those that are $\varepsilon$-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 $\varepsilon$ (GAFA, 2005), however the best known upper bound is a tower type function of $1/\varepsilon$.
• The best known lower bound on the query complexity of the canonical tester is $1/\varepsilon^{13.239}$ (Fu and Kleinberg, RANDOM, 2014).