Lower bounds for testing triangle-freeness in Boolean functions

详细信息    查看全文

• 作者：Arnab Bhattacharyya ; Ning Xie
• 关键词：Property testing ; query lower bounds ; Boolean function triangles ; 68Q17 ; 68Q25 ; 68W20 ; 68W40
• 刊名：Computational Complexity
• 出版年：2015
• 出版时间：March 2015
• 年：2015
• 卷：24
• 期：1
• 页码：65-101
• 全文大小：498 KB
• 参考文献：1. Noga, Alon (2002) Testing subgraphs in large graphs. Random Structures and Algorithms 21: pp. 359-370 CrossRef
  2. Noga, Alon, Eldar, Fischer, Michael, Krivelevich, Mario, Szegedy (2000) Efficient testing of large graphs. Combinatorica 20: pp. 451-476
  3. Noga Alon, Eldar Fischer, Ilan Newman & Asaf Shapira (2006). A combinatorial characterization of the testable graph properties: it’s all about regularity. In / STOC-6: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 251-60.
  4. Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn & Dana Ron (2003). Testing low-degree polynomials over GF(2). In / Random-3: Proceedings of 7th International Workshop on Randomization and Computation, 188-99. URL citeseer.ist.psu.edu/article/alon03testing.htm.
  5. Noga Alon, Michael Krivelevich, Ilan Newman & Mario Szegedy (2000b). Regular Languages are Testable with a Constant Number of Queries. / SIAM Journal on Computing 30(6), 1842-862.
  6. Noga, Alon, Asaf, Shapira (2004) Testing subgraphs in directed graphs. Journal of Computer and System Sciences 69: pp. 354-382 CrossRef
  7. Noga Alon & Asaf Shapira (2005a). A Characterization of the (natural) Graph Properties Testable with One-Sided Error. In / FOCS-5: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 429-38. IEEE Computer Society. ISBN 0-7695-2468-0.
  8. Noga Alon & Asaf Shapira (2005b). Every monotone graph property is testable. In / STOC-5: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 128-37. ACM. ISBN 1-58113-960-8.
  9. Tim Austin & Terence Tao (2008). On the testability and repair of hereditary hypergraph properties. http://arxiv.org/abs/0801.2179.
  10. Thomas, Bailey, John, Cowles (1987) A convex hull inclusion test. IEEE Transactions on Pattern Analysis and Machine Intelligence 9: pp. 312-316
  11. Eli Ben-Sasson, Prahladh Harsha & Sofya Raskhodnikova (2005). Some 3CNF Properties Are Hard to Test. / SIAM Journal on Computing 35(1), 1-1. Early version in STOC-3.
  12. Arnab Bhattacharyya, Victor Chen, Madhu Sudan & Ning Xie (2009). Testing linear-invariant non-linear properties. In / STACS-9: Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 135-46.
  13. Arnab Bhattacharyya & Ning Xie (2010). Lower bounds on testing triangle-freeness in Boolean functions. In / SODA-0: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, 87-8.
  14. Christian Borgs, Jennifer T. Chayes, László Lovász, Vera T. Sós, Balázs Szegedy & Katalin Vesztergombi (2006). Graph limits and parameter testing. In / STOC-6: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 261-70.
  15. Henri Cohen (2000). / A Course in Computational Algebraic Number Theory. Springer.
  16. Henry Cohn, Robert Kleinbergy, Balázs Szegedy & Christopher Umans (2005). Group-theoretic algorithms for matrix multiplication. In / FOCS-5: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 379-88.
  17. Don Coppersmith & Shmuel Winograd (1990). Matrix Multiplication via Arithmetic Progressions. / Journal of Symbolic Computation 9, 251-80. Earlier version in STOC-7.
  18. Eric Domenjoud (1991). Solving Systems of Linear Diophantine Equations: an Algebraic Approach. In / In Proc. 16th Mathematical Foundations of Computer Science, Warsaw, LNCS 520, 141-50. Springer-Verlag.
  19. Jacob, Fox (2011) A new proof of the graph removal lemma. Annals of Mathematics 174: pp. 561-579 CrossRef
  20. Hu Fu & Robert Kleinberg (2013). Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication. http://arxiv.org/abs/1308.1643.
  21. Oded Goldreich, Shafi Goldwasser & Dana Ron (1998). Property testing and its connection to learning and approximation. / Journal of the ACM 45(4), 653-50. ISSN 0004-5411.
  22. Oded, Goldreich, Luca, Trevisan (2003) Three theorems regarding testing graph properties. Random Structures and Algorithms 23: pp. 23-57 CrossRef
  23. Ben Green (2005). A Szemeréd
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity
  Computational Mathematics and Numerical Analysis
  
• 出版者：Birkh盲user Basel
• ISSN：1420-8954

文摘

Given a Boolean function \({f : \mathbb{F}_{2}^{n} \to \{0,1\}}\) , we say a triple (x, y, x?+?y) is a triangle in f if \({f(x)\!=\!f(y)\!=\!f(x+y)\!=\!1}\) . A triangle-free function contains no triangle. If f differs from every triangle-free function on at least \({\epsilon \cdot 2^n}\) points, then f is said to be \({\epsilon}\) -far from triangle-free. In this work, we analyze the query complexity of testers that, with constant probability, distinguish triangle-free functions from those \({\epsilon}\) -far from triangle-free. Let the canonical tester for triangle-freeness denotes the algorithm that repeatedly picks x and y uniformly and independently at random from \({\mathbb{F}_2^n}\) , queries f(x), f(y) and f(x?+?y), and checks whether f(x)?=?f(y)?=?f(x?+?y)?=?1. Green showed that the canonical tester rejects functions \({\epsilon}\) -far from triangle-free with constant probability if its query complexity is a tower of 2’s whose height is polynomial in \({1/\epsilon}\) . Fox later improved the height of the tower in Green’s upper bound to \({O(\log{1/\epsilon})}\) . A trivial lower bound of \({\Omega(1/\epsilon)}\) on the query complexity is immediate. In this paper, we give the first non-trivial lower bound for the number of queries needed. We show that, for every small enough \({\epsilon}\) , there exists an integer \({n_{0}(\epsilon)}\) such that for all \({n\geq n_{0}}\) there exists a function \({f :\mathbb{F}_{2}^{n} \to \{0,1\}}\) depending on all n variables which is \({\epsilon}\) -far from being triangle-free and requires \({\Omega \left((\frac{1}{\epsilon})^{4.847\cdots}\right)}\) queries for the canonical tester. We also show that the query complexity of any general (possibly adaptive) one-sided tester for triangle-freeness is at least square root of the query complexity of the corresponding canonical tester. Consequently, this means that any one-sided tester for triangle-freeness must make at least \({\Omega\left((\frac{1}{\epsilon})^{2.423\cdots}\right)}\) queries.