Document Open Access Logo

Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication

Authors Hu Fu, Robert Kleinberg

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.669.pdf
  • Filesize: 456 kB
  • 8 pages

Document Identifiers

Author Details

Hu Fu
Robert Kleinberg

Cite As Get BibTex

Hu Fu and Robert Kleinberg. Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 669-676, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.669

Abstract

Understanding the query complexity for testing linear-invariant properties has been a central open problem in the study of algebraic property testing. Triangle-freeness in Boolean functions is a simple property whose testing complexity is unknown. Three Boolean functions f1, f2 and f3, mapping {0,1}^k to {0,1}, are said to be triangle free if there is no x, y in {0,1}^k such that f1(x) = f2(y) = f3(x + y) = 1.  This property is known to be strongly testable (Green 2005), but the number of queries needed is upper-bounded only by a tower of twos whose height is polynomial in 1 / epsislon, where epsislon is the distance between the tested function triple and triangle-freeness, i.e., the minimum fraction of function values that need to be modified to make the triple triangle free. A lower bound of (1 / epsilon)^2.423 for any one-sided tester was given by Bhattacharyya and Xie (2010). In this work we improve this bound to (1 / epsilon)^6.619. Interestingly, we prove this by way of a combinatorial construction called uniquely solvable puzzles that was at the heart of Coppersmith and Winograd's renowned matrix multiplication algorithm.

Subject Classification

Keywords
  • Property testing
  • linear invariance
  • fast matrix multiplication
  • uniquely solvable puzzles

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon. Testing subgraphs in large graphs. Random Struct. Algorithms, 21(3-4):359-370, 2002. Google Scholar
  2. Noga Alon, Eldar Fischer, Ilan Newman, and Asaf Shapira. A combinatorial characterization of the testable graph properties: it’s all about regularity. In STOC, pages 251-260, 2006. Google Scholar
  3. Noga Alon and Asaf Shapira. Testing subgraphs in directed graphs. J. Comput. Syst. Sci., 69(3):354-382, 2004. Google Scholar
  4. Noga Alon and Asaf Shapira. A characterization of the (natural) graph properties testable with one-sided error. In FOCS, pages 429-438, 2005. Google Scholar
  5. Noga Alon, Amir Shpilka, and Christopher Umans. On sunflowers and matrix multiplication. Computational Complexity, 22(2):219-243, 2013. Google Scholar
  6. Tim Austin and Terence Tao. Testability and repair of hereditary hypergraph properties. Random Struct. Algorithms, 36(4):373-463, 2010. Google Scholar
  7. Felix A. Behrend. On sets of integers which contain no three terms in arithmetical progression. Proc. Nat. Acad. Sci., 32:331-332, 1946. Google Scholar
  8. Arnab Bhattacharyya, Victor Chen, Madhu Sudan, and Ning Xie. Testing linear-invariant non-linear properties. Theory of Computing, 7(1):75-99, 2011. Google Scholar
  9. Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, and Asaf Shapira. Testing odd-cycle-freeness in boolean functions. Combinatorics, Probability & Computing, 21(6):835-855, 2012. Google Scholar
  10. Arnab Bhattacharyya, Elena Grigorescu, and Asaf Shapira. A unified framework for testing linear-invariant properties. In FOCS, pages 478-487, 2010. Google Scholar
  11. Arnab Bhattacharyya and Ning Xie. Lower bounds for testing triangle-freeness in boolean functions. In SODA, pages 87-98, 2010. Google Scholar
  12. Henry Cohn, Robert D. Kleinberg, Balázs Szegedy, and Christopher Umans. Group-theoretic algorithms for matrix multiplication. In FOCS, pages 379-388, 2005. Google Scholar
  13. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. J. Symbolic Computation, 9(3):250-280, 1990. Google Scholar
  14. Michael Elkin. An improved construction of progression-free sets. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '10, pages 886-905, Philadelphia, PA, USA, 2010. Society for Industrial and Applied Mathematics. Google Scholar
  15. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, 1998. Google Scholar
  16. Ben Green. A Szemerédi-type regularity lemma in abelian groups, with applications. Geom. Funct. Anal. , 15(2):340-376, 2005. Google Scholar
  17. Ishay Haviv and Ning Xie, 2014. Private communication. Google Scholar
  18. Tali Kaufman and Madhu Sudan. Algebraic property testing: the role of invariance. In STOC, pages 403-412, 2008. Google Scholar
  19. Daniel Král, Oriol Serra, and Lluís Vena. On the removal lemma for linear systems over abelian groups. Eur. J. Comb., 34(2):248-259, 2013. Google Scholar
  20. Vojtech Rödl and Mathias Schacht. Generalizations of the removal lemma. Combinatorica, 29(4):467-501, 2009. Google Scholar
  21. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252-271, 1996. Google Scholar
  22. R. Salem and D. Spencer. On sets of integers which contain no three in arithmetic progression. Proc. Nat. Acad. Sci., 28:561-563, 1942. Google Scholar
  23. Asaf Shapira. Green’s conjecture and testing linear-invariant properties. In STOC, pages 159-166, 2009. Google Scholar
  24. Andrew James Stothers. On the Complexity of Matrix Multiplication. PhD thesis, University of Edinburgh, 2010. Google Scholar
  25. Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In STOC, pages 887-898, 2012. Google Scholar
  26. Ning Xie, 2010. Private communication. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact