Abstract
A Boolean function \(f:\{0,1\}^n\rightarrow \{0,1\}\) is k-linear if it returns the sum (over the binary field \(F_2\)) of k coordinates of the input. In this paper, we study property testing of the classes k-Linear, the class of all k-linear functions, and k-Linear\(^*\), the class \(\cup _{j=0}^kj\)-Linear. We give a non-adaptive distribution-free two-sided \(\epsilon \)-tester for k-Linear that makes
queries. This matches the lower bound known from the literature.
We then give a non-adaptive distribution-free one-sided \(\epsilon \)-tester for k-Linear\(^*\) that makes the same number of queries and show that any non-adaptive uniform-distribution one-sided \(\epsilon \)-tester for k-Linear must make at least \( \tilde{\varOmega }(k)\log n+\varOmega (1/\epsilon )\) queries. The latter bound, almost matches the upper bound \(O(k\log n+1/\epsilon )\) known from the literature. We then show that any adaptive uniform-distribution one-sided \(\epsilon \)-tester for k-Linear must make at least \(\tilde{\varOmega }(\sqrt{k})\log n+\varOmega (1/\epsilon )\) queries.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The class of boolean functions that depends on at most k coordinates.
- 2.
w.r.t. the uniform distribution, i.e.,
where \(f_1\) and \(f_2\) are distinct linear functions. - 3.
That is, defining a function \(f(x_{\phi (1)},\ldots ,x_{\phi (n)})\) where \(\phi :[n]\rightarrow [r]\) is random uniform.
- 4.
We may assume that \(k\leqslant \sqrt{n}.\) This is because the one-sided non-adaptive testing in [13] asks \(O(k\log n+1/\epsilon )\) queries which is \(O(k\log k+1/\epsilon )\) queries for \(k>\sqrt{n}\).
- 5.
Coordinates that the function depends on.
where References
Blais, E.: Improved bounds for testing Juntas. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX/RANDOM -2008. LNCS, vol. 5171, pp. 317–330. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85363-3_26
Blais, E.: Testing juntas nearly optimally. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, 31 May–2 June 2009, pp. 151–158 (2009). https://doi.org/10.1145/1536414.1536437
Blais, E., Brody, J., Matulef, K.: Property testing lower bounds via communication complexity. In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, 8–10 June 2011, pp. 210–220 (2011). https://doi.org/10.1109/CCC.2011.31
Blais, E., Kane, D.M.: Tight bounds for testing k-linearity. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, 15–17 August 2012, Proceedings, pp. 435–446 (2012). https://doi.org/10.1007/978-3-642-32512-0_37
Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci. 47(3), 549–595 (1993). https://doi.org/10.1016/0022-0000(93)90044-W
Bshouty, N.J.: Almost optimal distribution-free junta testing. In: 34th Computational Complexity Conference, CCC 2019, 18–20 July 2019, New Brunswick, NJ, USA, pp. 2:1–2:13 (2019). https://doi.org/10.4230/LIPIcs.CCC.2019.2
Bshouty, N.H.: An optimal tester for \(k\)-linear. Electron. Colloquium Comput. Complex. 27, 123 (2020). https://eccc.weizmann.ac.il/report/2020/123
Buhrman, H., GarcÃa-Soriano, D., Matsliah, A., de Wolf, R.: The non-adaptive query complexity of testing k-parities. Chicago J. Theor. Comput. Sci. 2013, 1–11 (2013). http://cjtcs.cs.uchicago.edu/articles/2013/6/contents.html
Fischer, E., Kindler, G., Ron, D., Safra, S., Samorodnitsky, A.: Testing juntas. In: 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16–19 November 2002, Vancouver, BC, Canada, Proceedings, pp. 103–112 (2002). https://doi.org/10.1109/SFCS.2002.1181887
Goldreich, O.: On testing computability by small width OBDDs. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, 1–3 September 2010. Proceedings, pp. 574–587 (2010). https://doi.org/10.1007/978-3-642-15369-3_43
Goldreich, O. (ed.): Property Testing. LNCS, vol. 6390. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16367-8
Goldreich, O.: Introduction to Property Testing. Cambridge University Press, Cambridge (2017). http://www.cambridge.org/us/catalogue/catalogue.asp?isbn=9781107194052, https://doi.org/10.1017/9781108135252
Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. ACM 45(4), 653–750 (1998). https://doi.org/10.1145/285055.285060
Halevy, S., Kushilevitz, E.: Distribution-free property-testing. SIAM J. Comput. 37(4), 1107–1138 (2007). https://doi.org/10.1137/050645804
Hofmeister, T.: An application of codes to attribute-efficient learning. In: Fischer, P., Simon, H.U. (eds.) EuroCOLT 1999. LNCS (LNAI), vol. 1572, pp. 101–110. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-49097-3_9
Ron, D.: Property testing: a learning theory perspective. Found. Trends Mach. Learn. 1(3), 307–402 (2008). https://doi.org/10.1561/2200000004
Ron, D.: Algorithmic and analysis techniques in property testing. Found. Trends Theor. Comput. Sci. 5(2), 73–205 (2009). https://doi.org/10.1561/0400000029
Rubinfeld, R., Shapira, A.: Sublinear time algorithms. SIAM J. Discrete Math. 25(4), 1562–1588 (2011). https://doi.org/10.1137/100791075
Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM J. Comput. 25(2), 252–271 (1996). https://doi.org/10.1137/S0097539793255151
Saglam, M.: Near log-convexity of measured heat in (discrete) time and consequences. In: 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, 7–9 October 2018, pp. 967–978 (2018). https://doi.org/10.1109/FOCS.2018.00095
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Bshouty, N.H. (2022). An Optimal Tester for k-Linear. In: Mutzel, P., Rahman, M.S., Slamin (eds) WALCOM: Algorithms and Computation. WALCOM 2022. Lecture Notes in Computer Science(), vol 13174. Springer, Cham. https://doi.org/10.1007/978-3-030-96731-4_17
Download citation
DOI: https://doi.org/10.1007/978-3-030-96731-4_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-96730-7
Online ISBN: 978-3-030-96731-4
eBook Packages: Computer ScienceComputer Science (R0)