Hostname: page-component-745bb68f8f-grxwn Total loading time: 0 Render date: 2025-02-07T01:15:39.310Z Has data issue: false hasContentIssue false
  • English
  • Français

Testing Odd-Cycle-Freeness in Boolean Functions

Published online by Cambridge University Press:  10 August 2012

ARNAB BHATTACHARYYA ,
ELENA GRIGORESCU ,
PRASAD RAGHAVENDRA  and
ASAF SHAPIRA
ARNAB BHATTACHARYYA
Affiliation:
Center for Computational Intractability, Olden Street, Princeton, NJ 08540, USA (e-mail: arnabb@princeton.edu)
ELENA GRIGORESCU
Affiliation:
College of Computing, Georgia Tech, 801 Atlantic Drive, Atlanta, GA 30332, USA (e-mail: elena_g@csail.mit.edu, raghavendra@cc.gatech.edu, asafico@math.gatech.edu
PRASAD RAGHAVENDRA
Affiliation:
College of Computing, Georgia Tech, 801 Atlantic Drive, Atlanta, GA 30332, USA (e-mail: elena_g@csail.mit.edu, raghavendra@cc.gatech.edu, asafico@math.gatech.edu
ASAF SHAPIRA
Affiliation:
College of Computing, Georgia Tech, 801 Atlantic Drive, Atlanta, GA 30332, USA (e-mail: elena_g@csail.mit.edu, raghavendra@cc.gatech.edu, asafico@math.gatech.edu School of Mathematical Sciences, Tel Aviv University, Ramat Aviv, Tel Aviv 69978, Israel
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A function f: 2n → {0,1} is odd-cycle-free if there are no x1,. . .,xk ∈ 2n 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. We give two proofs of this result, each shedding light on a different connection between testability of properties of Boolean functions and of dense graphs.

The first issue we study is directly reducing testing of linear-invariant properties of Boolean functions to testing associated graph properties. We show a black-box reduction from testing odd-cycle-freeness to testing bipartiteness of graphs. Such reductions have already been shown (Král’, Serra and Vena, and Shapira) for monotone linear-invariant properties defined by forbidding solutions to a finite number of equations. But for odd-cycle-freeness whose description involves an infinite number of forbidden equations, a reduction to graph property testing was not previously known. If one could show such a reduction more generally for any linear-invariant property closed under restrictions to subspaces, then it would likely lead to a characterization of the one-sided testable linear-invariant properties, an open problem raised by Sudan.

The second issue we study is whether there is an efficient canonical tester for linear-invariant properties of Boolean functions. A canonical tester for linear-invariant properties operates by picking a random linear subspace and then checking whether the restriction of the input function to the subspace satisfies a fixed property. The question is if, for every linear-invariant property, there is a canonical tester for which there is only a polynomial blow-up from the optimal query complexity. We answer the question affirmatively for odd-cycle-freeness. The general question remains open.

Keywords

Primary 68Q0168Q87
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 6 , November 2012 , pp. 835 - 855
Copyright
Copyright © Cambridge University Press 2012

References

[1]Alon, N. (2002) Testing subgraphs in large graphs. Random Struct. Alg. 21 359–370.Google Scholar
[2]Alon, N., Duke, R. A., Lefmann, H., Rödl, V. and Yuster, R. (1994) The algorithmic aspects of the regularity lemma. J. Algorithms 16 80–109.Google Scholar
[3]Alon, N., Fernandez de la Vega, W., Kannan, R. and Karpinski, M. (2003) Random sampling and approximation of MAX-CSPs. J. Comput. Syst. Sci. 67 212–243.CrossRefGoogle Scholar
[4]Alon, N., Fischer, E., Krivelevich, M. and Szegedy, M. (2000) Efficient testing of large graphs. Combinatorica 20 451–476.Google Scholar
[5]Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S. and Ron, D. (2005) Testing Reed–Muller codes. IEEE Trans. Inform. Theory 51 4032–4039.Google Scholar
[6]Alon, N. and Krivelevich, M. (2002) Testing k-colorability. SIAM J. Discrete Math. 15 211–227.Google Scholar
[7]Alon, N. and Shapira, A. (2008) A characterization of the (natural) graph properties testable with one-sided error. SIAM J. Comput. 37 1703–1727.CrossRefGoogle Scholar
[8]Austin, T. and Tao, T. (2010) Testability and repair of hereditary hypergraph properties. Random Struct. Alg. 36 373–463.CrossRefGoogle Scholar
[9]Bhattacharyya, A., Chen, V., Sudan, M. and Xie, N. (2011) Testing linear-invariant non-linear properties. Theory of Computing 7 75–99. Earlier version in STACS ‘09.Google Scholar
[10]Bhattacharyya, A., Grigorescu, E., Raghavendra, P. and Shapira, A. (2012) Testing odd-cycle-freeness in Boolean functions. In Proc. ACM–SIAM Symposium on Discrete Algorithms, pp. 1140–1149.CrossRefGoogle Scholar
[11]Bhattacharyya, A., Grigorescu, E. and Shapira, A. (2010) A unified framework for testing linear-invariant properties. In Proc. 51st Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, pp. 478–487.Google Scholar
[12]Bhattacharyya, A. and Xie, N. (2010) Lower bounds for testing triangle-freeness in Boolean functions. In Proc. 21st ACM–SIAM Symposium on Discrete Algorithms, pp. 87–98.Google Scholar
[13]Blum, M., Luby, M. and Rubinfeld, R. (1993) Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci. 47 549–595. Earlier version in STOC'90.CrossRefGoogle Scholar
[14]Bogdanov, A. and Trevisan, L. (2004) Lower bounds for testing bipartiteness in dense graphs. In Proc. 19th Annual IEEE Conference on Computational Complexity, IEEE Computer Society, pp. 75–81.Google Scholar
[15]Chen, V., Sudan, M. and Xie, N. (2011) Property testing via set-theoretic operations. In Proc. 2nd Innovations in Computer Science, pp. 211–222.Google Scholar
[16]Goldreich, O., Goldwasser, S. and Ron, D. (1998) Property testing and its connection to learning and approximation. J. Assoc. Comput. Mach. 45 653–750.Google Scholar
[17]Goldreich, O. and Ron, D. (2011) Algorithmic aspects of property testing in the dense graphs model. SIAM J. Comput. 40 376–445.Google Scholar
[18]Goldreich, O. and Trevisan, L. (2003) Three theorems regarding testing graph properties. Random Struct. Alg. 23 23–57.CrossRefGoogle Scholar
[19]Gopalan, P., O'Donnell, R., Servedio, R. A., Shpilka, A. and Wimmer, K. (2009) Testing Fourier dimensionality and sparsity. In Proc. 36th Annual International Conference on Automata, Languages, and Programming, Springer, pp. 500–512.Google Scholar
[20]Green, B. (2005) A Szemerédi-type regularity lemma in abelian groups. Geometric Funct. Anal. 15 340–376.Google Scholar
[21]Kaufman, T., Krivelevich, M. and Ron, D. (2004) Tight bounds for testing bipartiteness in general graphs. SIAM J. Comput. 33 1441–1483.Google Scholar
[22]Kaufman, T. and Sudan, M. (2008) Algebraic property testing: The role of invariance. In Proc. 40th Annual ACM Symposium on the Theory of Computing, pp. 403–412.Google Scholar
[23]Král’, D., Serra, O. and Vena, L. (2012) A removal lemma for systems of linear equations over finite fields. Israel J. Math. 187 193–207.CrossRefGoogle Scholar
[24]Nagle, B., Rödl, V. and Schacht, M. (2006) The counting lemma for regular k-uniform hypergraphs. Random Struct. Alg. 28 113–179.Google Scholar
[25]Parnas, M., Ron, D. and Rubinfeld, R. (2006) Tolerant property testing and distance approximation. J. Comput. Syst. Sci. 72 1012–1042.Google Scholar
[26]Rödl, V. and Schacht, M. (2009) Generalizations of the removal lemma. Combinatorica 29 467–502.Google Scholar
[27]Rödl, V. and Skokan, J. (2004) Regularity lemma for k-uniform hypergraphs. Random Struct. Alg. 25 1–42.Google Scholar
[28]Rubinfeld, R. and Sudan, M. (1996) Robust characterizations of polynomials with applications to program testing. SIAM J. Comput. 25 252–271.CrossRefGoogle Scholar
[29]Ruzsa, I. and Szemerédi, E. (1978) Triple systems with no six points carrying three triangles. In Combinatorics: Keszthely 1976, Vol. 18 of Colloq. Math. Soc. János Bolyai, North-Holland, pp. 939–945.Google Scholar
[30]Shapira, A. (2009) Green's conjecture and testing linear-invariant properties. In Proc. 41st Annual ACM Symposium on the Theory of Computing, pp. 159–166.Google Scholar
[31]Sudan, M. (2010) Invariance in property testing. In Property Testing: Current Research and Surveys (Goldreich, O., ed.), Vol. 6390 of Lecture Notes in Computer Science, Springer, pp. 211–227.Google Scholar