Testing Odd-Cycle-Freeness in Boolean Functions
From MaRDI portal
Abstract: 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.
Recommendations
- Testing odd-cycle-freeness in Boolean functions
- scientific article; zbMATH DE number 3878850
- Verification, Model Checking, and Abstract Interpretation
- On testing repetition-free functions
- scientific article; zbMATH DE number 4172919
- On the sensitivity of cyclically-invariant Boolean functions
- Tests with respect to permutations of variables in Boolean functions
- On tests detecting certain faults of circuit inputs for almost all Boolean functions
- Distribution-Free Testing Lower Bounds for Basic Boolean Functions
- A canonical form for testing Boolean function properties
Cites work
- A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
- A removal lemma for systems of linear equations over finite fields
- A Szemerédi-type regularity lemma in abelian groups, with applications
- Algorithmic aspects of property testing in the dense graphs model
- Efficient testing of large graphs
- Generalizations of the removal lemma
- Invariance in property testing
- Property testing and its connection to learning and approximation
- Random sampling and approximation of MAX-CSPs
- Regularity Lemma for k-uniform hypergraphs
- Robust Characterizations of Polynomials with Applications to Program Testing
- Self-testing/correcting with applications to numerical problems
- Testing k-colorability
- Testing Fourier Dimensionality and Sparsity
- Testing Reed–Muller Codes
- Testing subgraphs in large graphs
- The Algorithmic Aspects of the Regularity Lemma
- The counting lemma for regular k‐uniform hypergraphs
- Three theorems regarding testing graph properties
- Tight Bounds for Testing Bipartiteness in General Graphs
- Tolerant property testing and distance approximation
Cited in
(7)- A polynomial bound for the arithmetic k-cycle removal lemma in vector spaces
- A tight bound for Green's arithmetic triangle removal lemma in vector spaces
- Testing linear-invariant non-linear properties
- A canonical form for testing Boolean function properties
- Testing linear-invariant non-linear properties
- Testing odd-cycle-freeness in Boolean functions
- Verification, Model Checking, and Abstract Interpretation
This page was built for publication: Testing Odd-Cycle-Freeness in Boolean Functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3168444)
