期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Call a function f:Fn201 odd-cycle-free if there are no x1xkFn2 with k an odd integer such that f(x1)==f(xk)=1 and x1++xk=0. We show that one can distinguish odd-cycle-free functions from those -far from being odd-cycle-free by making poly(1) 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) queries, meaning that the testing algorithm operates by picking a random linear subspace of dimension O(log1) 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.
