Abstract
In this paper, we study linear and quadratic Boolean functions in the context of property testing. We do this by observing that the query complexity of testing properties of linear and quadratic functions can be characterized in terms of complexity in another model of computation called parity decision trees.
The observation allows us to characterize testable properties of linear functions in terms of the approximate l 1 norm of the Fourier spectrum of an associated function. It also allows us to reprove the Ω(k) lower bound for testing k-linearity due to Blais et al [8]. More interestingly, it rekindles the hope of closing the gap of Ω(k) vs O(klogk) for testing k-linearity by analyzing the randomized parity decision tree complexity of a fairly simple function called E k that evaluates to 1 if and only if the number of 1s in the input is exactly k. The approach of Blais et al. using communication complexity is unlikely to give anything better than Ω(k) as a lower bound.
In the case of quadratic functions, we prove an adaptive two-sided Ω(n 2) lower bound for testing affine isomorphism to the inner product function. We remark that this bound is tight and furnishes an example of a function for which the trivial algorithm for testing affine isomorphism is the best possible. As a corollary, we obtain an Ω(n 2) lower bound for testing the class of Bent functions.
We believe that our techniques might be of independent interest and may be useful in proving other testing bounds.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alon, N., Fischer, E., Newman, I., Shapira, A.: A combinatorial characterization of the testable graph properties: It’s all about regularity. SIAM J. Comput. 39(1), 143–167 (2009)
Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S.N., Ron, D.: Testing low-degree polynomials over GF(2). In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) APPROX 2003 + RANDOM 2003. LNCS, vol. 2764, pp. 188–199. Springer, Heidelberg (2003)
Bhattacharyya, A., Fischer, E., Hatami, H., Hatami, P., Lovett, S.: Every locally characterized affine-invariant property is testable. In: Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing, STOC 2013, pp. 429–436. ACM Press, New York (2013), http://doi.acm.org/10.1145/2488608.2488662
Bhattacharyya, A., Grigorescu, E., Shapira, A.: A unified framework for testing linear-invariant properties. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 478–487 (2010)
Bhrushundi, A.: On testing bent functions. Electronic Colloquium on Computational Complexity (ECCC) 20, 89 (2013)
Bhrushundi, A., Chakraborty, S., Kulkarni, R.: Property testing bounds for linear and quadratic functions via parity decision trees. Electronic Colloquium on Computational Complexity (ECCC) 20, 142 (2013)
Blais, E.: Testing juntas nearly optimally. In: Proc. ACM Symposium on the Theory of Computing, pp. 151–158. ACM, New York (2009)
Blais, E., Brody, J., Matulef, K.: Property testing via communication complexity. In: Proc. CCC (2011)
Blais, E., Kane, D.: Tight bounds for testing k-linearity. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX/RANDOM 2012. LNCS, vol. 7408, pp. 435–446. Springer, Heidelberg (2012)
Blais, E., Weinstein, A., Yoshida, Y.: Partially symmetric functions are efficiently isomorphism-testable. In: FOCS, pp. 551–560 (2012)
Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting with applications to numerical problems. In: STOC, pp. 73–83 (1990)
Buhrman, H., García-Soriano, D., Matsliah, A., de Wolf, R.: The non-adaptive query complexity of testing k-parities. CoRR abs/1209.3849 (2012)
Chakrabarty, D., Seshadhri, C.: A o(n) monotonicity tester for boolean functions over the hypercube. CoRR abs/1302.4536 (2013)
Chakraborty, S., Fischer, E., García-Soriano, D., Matsliah, A.: Junto-symmetric functions, hypergraph isomorphism and crunching. In: IEEE Conference on Computational Complexity, pp. 148–158 (2012)
Chen, V., Sudan, M., Xie, N.: Property testing via set-theoretic operations. In: ICS, pp. 211–222 (2011)
Fischer, E.: The art of uninformed decisions: A primer to property testing. Science 75, 97–126 (2001)
Fischer, E., Kindler, G., Ron, D., Safra, S., Samorodnitsky, A.: Testing juntas. Journal of Computer and System Sciences 68(4), 753–787 (2004), Special Issue on FOCS 2002
Fischer, E., Lehman, E., Newman, I., Raskhodnikova, S., Rubinfeld, R., Samorodnitsky, A.: Monotonicity testing over general poset domains. In: STOC, pp. 474–483 (2002)
Goldreich, O.: On testing computability by small width obdds. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX 2010. LNCS, vol. 6302, pp. 574–587. Springer, Heidelberg (2010)
Grigorescu, E., Wimmer, K., Xie, N.: Tight lower bounds for testing linear isomorphism. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) RANDOM 2013 and APPROX 2013. LNCS, vol. 8096, pp. 559–574. Springer, Heidelberg (2013)
Huang, W., Shi, Y., Zhang, S., Zhu, Y.: The communication complexity of the hamming distance problem. Inf. Process. Lett. 99(4), 149–153 (2006)
Kaufman, T., Sudan, M.: Algebraic property testing: the role of invariance. In: STOC, pp. 403–412 (2008)
Lee, T., Shraibman, A.: Lower bounds in communication complexity. Foundations and Trends in Theoretical Computer Science 3(4), 263–398 (2009)
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes (North-Holland Mathematical Library). North Holland Publishing Co. (June 1988), http://www.worldcat.org/isbn/0444851933
Neumann, T.: Bent functions, Master’s thesis (2006)
O’Donnell, R.: Analysis of boolean functions (2012), http://www.analysisofbooleanfunctions.org
Rothaus, O.: On bent functions. Journal of Combinatorial Theory, Series A 20(3), 300–305 (1976), http://www.sciencedirect.com/science/article/pii/0097316576900248
Rubinfeld, R., Shapira, A.: Sublinear time algorithms. Electronic Colloquium on Computational Complexity (ECCC) 11(013) (2011)
Sun, X., Wang, C.: Randomized communication complexity for linear algebra problems over finite fields. In: STACS, pp. 477–488 (2012)
Wimmer, K., Yoshida, Y.: Testing linear-invariant function isomorphism. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 840–850. Springer, Heidelberg (2013)
Zhang, Z., Shi, Y.: On the parity complexity measures of boolean functions. Theor. Comput. Sci. 411(26-28), 2612–2618 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Bhrushundi, A., Chakraborty, S., Kulkarni, R. (2014). Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees. In: Hirsch, E.A., Kuznetsov, S.O., Pin, JÉ., Vereshchagin, N.K. (eds) Computer Science - Theory and Applications. CSR 2014. Lecture Notes in Computer Science, vol 8476. Springer, Cham. https://doi.org/10.1007/978-3-319-06686-8_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-06686-8_8
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06685-1
Online ISBN: 978-3-319-06686-8
eBook Packages: Computer ScienceComputer Science (R0)