ECCC-Report TR11-075https://eccc.weizmann.ac.il/report/2011/075Comments and Revisions published for TR11-075en-usSat, 07 May 2011 01:24:45 +0300
Paper TR11-075
| Testing Odd-Cycle-Freeness in Boolean Functions |
Arnab Bhattacharyya,
Elena Grigorescu,
Prasad Raghavendra,
Asaf Shapira
https://eccc.weizmann.ac.il/report/2011/075Call a function $f: \mathbb{F}_2^n \to \{0,1\}$ odd-cycle-free if there are no $x_1, \dots, x_k \in \mathbb{F}_2^n$ with $k$ an odd integer such that $f(x_1) = \cdots = f(x_k) = 1$ and $x_1 + \cdots + x_k = 0$. We show that one can distinguish odd-cycle-free functions from those $\epsilon$-far from being odd-cycle-free by making poly$(1/\epsilon)$ queries to an evaluation oracle. To obtain this result, we use connections between basic Fourier analysis and spectral graph theory to show that one can reduce testing odd-cycle-freeness of Boolean functions to testing bipartiteness of dense graphs. Our work forms part of a recent sequence of works that shows connections between testability of properties of Boolean functions and of graph properties.
We also prove that there is a canonical tester for odd-cycle-freeness making poly$(1/\epsilon)$ queries, meaning that the testing algorithm operates by picking a random linear subspace of dimension $O(\log 1/\epsilon)$ and then checking if the restriction of the function to the subspace is odd-cycle-free or not. The test is analyzed by studying the effect of random subspace restriction on the Fourier coefficients of a function. Our work implies that testing odd-cycle-freeness using a canonical tester instead of an arbitrary tester incurs no more than a polynomial blowup in the query complexity. The question of whether a canonical tester with polynomial blowup exists for all linear-invariant properties remains an open problem.Sat, 07 May 2011 01:24:45 +0300https://eccc.weizmann.ac.il/report/2011/075