Testing Odd-Cycle-Freeness in Boolean Functions

Details Testing Odd-Cycle-Freeness in Boolean Functions Testing Odd-Cycle-Freeness in Boolean Functions

2011-05-06

arxiv.org/abs/1105.1325v1

Computer Science

Data Structures and Algorithms

18 pages

Scientific paper

Call a function f : F_2^n -> {0,1} odd-cycle-free if there are no x_1, ..., x_k in F_2^n with k an odd integer such that f(x_1) = ... = f(x_k) = 1 and x_1 + ... + x_k = 0. We show that one can distinguish odd-cycle-free functions from those eps-far from being odd-cycle-free by making poly(1/eps) 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/eps) queries, meaning that the testing algorithm operates by picking a random linear subspace of dimension O(log 1/eps) 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.

Affiliated with

Also associated with

No associations

Rating

Testing Odd-Cycle-Freeness in Boolean Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Testing Odd-Cycle-Freeness in Boolean Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Testing Odd-Cycle-Freeness in Boolean Functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-576823