Green's conjecture and testing linear-invariant properties

ABSTRACT

Given a set of linear equations Mx=b, we say that a set of integers S is (M,b)-free if it contains no solution to this system of equations. Motivated by questions related to testing linear-invariant properties of boolean functions, as well as recent investigations in additive number theory, the following conjecture was raised (implicitly) by Green and by Bhattacharyya, Chen, Sudan and Xie: we say that a set of integers S ⊆ [n], is ε-far from being (M,b)-free if one needs to remove at least ε n elements from S in order to make it (M,b)-free. The above conjecture states that for any system of homogenous linear equations Mx=0 and for any ε >0 there is a constant time algorithm that can distinguish with high probability between sets of integers that are (M,0)-free from sets that are ε-far from being (M,0)-free. Or in other words, that for any M there is an efficient testing algorithm for the property of being (M,0)-free. In this paper we confirm the above conjecture by showing that such a testing algorithm exists even for non-homogenous linear equations. As opposed to most results on testing boolean functions, which rely on algebraic and analytic arguments, our proof relies on results from extremal hypergraph theory, such as the recent removal lemmas of Gowers, Rodl et al. and Austin and Tao.

REFERENCES

• 1: Noga Alon, Testing subgraphs in large graphs, Random Structures & Algorithms, v.21 n.3-4, p.359-370, October 2002 [doi>10.1002/rsa.10056]
• 2: N. Alon , R. A. Duke , H. Lefmann , V. Rödl , R. Yuster, The algorithmic aspects of the regularity lemma, Journal of Algorithms, v.16 n.1, p.80-109, Jan. 1994 [doi>10.1006/jagm.1994.1005]
• 3: N. Alon, E. Fischer, M. Krivelevich and M. Szegedy, Efficient testing of large graphs, Proc. of 40th FOCS, New York, NY, IEEE(1999), 656--666. Also: Combinatorica 20 (2000), 451--476.
• 4: Noga Alon , Eldar Fischer , Ilan Newman , Asaf Shapira, A combinatorial characterization of the testable graph properties: it's all about regularity, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132555]
• 5: N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn and D. Ron, Testing low-degree polynomials over GF(2), Proc. of RANDOM 2003, 188--199.
• 6: Noga Alon , Asaf Shapira, Testing subgraphs in directed graphs, Journal of Computer and System Sciences, v.69 n.3, p.354-382, November 2004 [doi>10.1016/j.jcss.2004.04.008]
• 7: Noga Alon , Asaf Shapira, Testing subgraphs in directed graphs, Journal of Computer and System Sciences, v.69 n.3, p.354-382, November 2004 [doi>10.1016/j.jcss.2004.04.008]
• 8: Noga Alon , Asaf Shapira, A Characterization of Easily Testable Induced Subgraphs, Combinatorics, Probability and Computing, v.15 n.6, p.791-805, November 2006 [doi>10.1017/S0963548306007759]
• 9: Noga Alon , Asaf Shapira, A Characterization of the (Natural) Graph Properties Testable with One-Sided Error, SIAM Journal on Computing, v.37 n.6, p.1703-1727, March 2008 [doi>10.1137/06064888X]
• 10: T. Austin and T. Tao, On the testability and repair of hereditary hypergraph properties, manuscript, 2008.
• 11: Ilya Baran , Erik D. Demaine , Mihai Pǎtraşcu, Subquadratic Algorithms for 3SUM, Algorithmica, v.50 n.4, p.584-596, March 2008 [doi>10.1007/s00453-007-9036-3]
• 12: F. A. Behrend, On sets of integers which contain no three terms in arithmetic progression, Proc. National Academy of Sciences USA 32(1946), 331--332.
• 13: Eli Ben-Sasson , Prahladh Harsha , Sofya Raskhodnikova, Some 3CNF Properties Are Hard to Test, SIAM Journal on Computing, v.35 n.1, p.1-21, 2005 [doi>10.1137/S0097539704445445]
• 14: A. Bhattacharyya, V. Chen, M. Sudan and N. Xie, Testing linear-invariant non-linear properties, Electronic Colloquium on Computational Complexity, Report TR08--088, 2008.
• 15: Manuel Blum , Michael Luby , Ronitt Rubinfeld, Self-testing/correcting with applications to numerical problems, Journal of Computer and System Sciences, v.47 n.3, p.549-595, Dec. 1993 [doi>10.1016/0022-0000(93)90044-W]
• 16: Andrej Bogdanov , Kenji Obata , Luca Trevisan, A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.93-102, November 16-19, 2002
• 17: P. Candela, On systems of linear equations and uniform hypergraphs, manuscript, 2008.
• 18: A. Czumaj and C. Sohler, Sublinear-time algorithms, Bulletin of the EATCS, 89 (2006) 23--47.
• 19: Jeff Erickson, Lower bounds for linear satisfiability problems, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.388-395, January 22-24, 1995, San Francisco, California, United States
• 20: Eldar Fischer , Ilan Newman, Testing versus Estimation of Graph Properties, SIAM Journal on Computing, v.37 n.2, p.482-501, May 2007 [doi>10.1137/060652324]
• 21: Peter Frankl , Vojtech Rödl, Extremal problems on set systems, Random Structures & Algorithms, v.20 n.2, p.131-164, March 2002 [doi>10.1002/rsa.10017.abs]
• 22: H. Furstenberg and Y. Katznelson, An ergodic Szemerédi theorem for commuting transformations, J. Analyse Math. 34 (1978), 275--291.
• 23: Anka Gajentaan , Mark H. Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry: Theory and Applications, v.5 n.3, p.165-185, Oct. 1995 [doi>10.1016/0925-7721(95)00022-2]
• 24: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 25: T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, Ann. of Math. Volume 166, Number 3 (2007),897--946.
• 26: W. T. Gowers, Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs, Combinatorics, Probability and Computing, v.15 n.1-2, p.143-184, January 2006 [doi>10.1017/S0963548305007236]
• 27: B. Green, A Szemerédi-type regularity lemma in a belian groups, GAFA 15 (2005), 340--376.
• 28: Y. Ishigami, A simple regularization of hypergraphs, available athttp://arxiv.org/abs/math/0612838.
• 29: Charanjit S. Jutla , Anindya C. Patthak , Atri Rudra , David Zuckerman, Testing Low-Degree Polynomials over Prime Fields, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.423-432, October 17-19, 2004 [doi>10.1109/FOCS.2004.64]
• 30: Tali Kaufman , Simon Litsyn, Almost Orthogonal Linear Codes are Locally Testable, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.317-326, October 23-25, 2005 [doi>10.1109/SFCS.2005.16]
• 31: Tali Kaufman , Dana Ron, Testing Polynomials over General Fields, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.413-422, October 17-19, 2004 [doi>10.1109/FOCS.2004.65]
• 32: Tali Kaufman , Madhu Sudan, Algebraic property testing: the role of invariance, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374434]
• 33: Y. Kohayakawa, B. Nagle, V. Rödl, M. Schacht and J. Skokan, The hypergraph regularity method and its applications, Proceedings of the National Academy of Sciences USA, 102(23): 8109--8113.
• 34: J. Komlós and M. Simonovits, Szemerédi's Regularity Lemma andits applications in graph theory. In: Combinatorics, PaulErdös is Eighty, Vol II (D. Miklós, V. T. Sós, T. Szönyieds.), János Bolyai Math. Soc., Budapest (1996), 295--352.
• 35: D. Král', O. Serra and L. Vena, A combinatorial proof of theremoval lemma for groups, arXiv:0804.4847v1.
• 36: D. Král', O. Serra and L. Vena, A removal lemma for linear systems over finite fields, Jornadas de Matematica Discreta y algortimica, 2008.
• 37: Kevin Matulef , Ryan O'Donnell , Ronitt Rubinfeld , Rocco A. Servedio, Testing halfspaces, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.256-264, January 04-06, 2009, New York, New York
• 38: Brendan Nagle , Vojtěch Rödl , Mathias Schacht, The counting lemma for regular k-uniform hypergraphs, Random Structures & Algorithms, v.28 n.2, p.113-179, March 2006 [doi>10.1002/rsa.v28:2]
• 39: Vojtěch Rödl , Jozef Skokan, Regularity lemma for k-uniform hypergraphs, Random Structures & Algorithms, v.25 n.1, p.1-42, August 2004 [doi>10.1002/rsa.20017]
• 40: K.F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 104--109.
• 41: Ronitt Rubinfeld , Madhu Sudan, Robust Characterizations of Polynomials withApplications to Program Testing, SIAM Journal on Computing, v.25 n.2, p.252-271, February 1996 [doi>10.1137/S0097539793255151]
• 42: I. Z. Ruzsa, Solving a linear equation in a set of integers I, Acta Arithmetica 65 (1993), 259--282.
• 43: I. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles, in Combinatorics (Keszthely, 1976), Coll.Math. Soc. J. Bolyai 18, Volume II, 939--945.
• 44: E. Szemerédi, Integer sets containing no k elements in arithmetic progression, Acta Arith. 27 (1975), 299--345.
• 45: . Szemerédi,Regular partitions of graphs, In: Proc. Colloque Inter. CNRS (J. C. Bermond, J. C. Fournier, M. Las Vergnas andD. Sotteau, eds.), 1978, 399--401.
• 46: Terence Tao, A variant of the hypergraph removal lemma, Journal of Combinatorial Theory Series A, v.113 n.7, p.1257-1280, October 2006 [doi>10.1016/j.jcta.2005.11.006]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
boolean functions, hypergraphs removal lemma, property testing