Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-23T12:32:09.901Z Has data issue: false hasContentIssue false
  • English
  • Français

On Active and Passive Testing

Published online by Cambridge University Press:  04 January 2016

NOGA ALON ,
RANI HOD  and
AMIT WEINSTEIN
NOGA ALON
Affiliation:
Sackler School of Mathematics and Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel and School of Mathematics, Institute for Advanced Study, Princeton, NJ 08540, USA (e-mail: [email protected])
RANI HOD
Affiliation:
School of Mathematics, Georgia Tech, 686 Cherry St., Atlanta, GA 30332, USA (e-mail: [email protected])
AMIT WEINSTEIN
Affiliation:
Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Given a property of Boolean functions, what is the minimum number of queries required to determine with high probability if an input function satisfies this property or is ‘far’ from satisfying it? This is a fundamental question in property testing, where traditionally the testing algorithm is allowed to pick its queries among the entire set of inputs. Balcan, Blais, Blum and Yang have recently suggested restricting the tester to take its queries from a smaller random subset of polynomial size of the inputs. This model is called active testing, and in the extreme case when the size of the set we can query from is exactly the number of queries performed, it is known as passive testing.

We prove that passive or active testing of k-linear functions (that is, sums of k variables among n over $\mathbb{Z}$2) requires Θ(k log n) queries, assuming k is not too large. This extends the case k = 1, (that is, dictator functions), analysed by Balcan, Blais, Blum and Yang.

We also consider other classes of functions including low-degree polynomials, juntas, and partially symmetric functions. Our methods combine algebraic, combinatorial, and probabilistic techniques, including the Talagrand concentration inequality and the Erdős–Rado theorem on Δ-systems.

Keywords

Primary 68Q17Secondary 68R05
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 1: Oberwolfach Special Issue Part 2 , January 2016 , pp. 1 - 20
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S. and Ron, D. (2003) Testing low-degree polynomials over GF(2). In Proc. 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 7th International Workshop on Randomization and Approximation Techniques in Computer Science: RANDOM–APPROX '03, pp. 188–199.CrossRefGoogle Scholar
[2]Alon, N. and Spencer, J. H. (2008) The Probabilistic Method, third edition, Wiley.Google Scholar
[3]Babai, L., Fortnow, L. and Lund, C. (1991) Nondeterministic exponential time has two-prover interactive protocols. Comput. Complexity 1 3–40.Google Scholar
[4]Balcan, M.-F., Blais, E., Blum, A. and Yang, L. (2012) Active property testing. In Proc. 53rd Annual IEEE Symposium on Foundations of Computer Science: FOCS '12, pp. 21–30.CrossRefGoogle Scholar
[5]Bellare, M., Coppersmith, D., Håstad, J., Kiwi, M. and Sudan, M. (1996) Linearity testing in characteristic two. IEEE Trans. Inform. Theory 42 1781–1796.Google Scholar
[6]Ben-Eliezer, I., Hod, R. and Lovett, S. (2012) Random low-degree polynomials are hard to approximate. Comput. Complexity 21 63–81.CrossRefGoogle Scholar
[7]Bhattacharyya, A., Kopparty, S., Schoenebeck, G., Sudan, M. and Zuckerman, D. (2010) Optimal testing of Reed–Muller codes. In Proc. 51st Annual IEEE Symposium on Foundations of Computer Science: FOCS '10, pp. 488–497.Google Scholar
[8]Blais, E. (2008) Improved bounds for testing juntas. In Proc. 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 12th International Workshop on Randomization and Approximation Techniques in Computer Science: RANDOM–APPROX '08, pp. 317–330.Google Scholar
[9]Blais, E. (2009) Testing juntas nearly optimally. In Proc. 41st Annual ACM Symposium on Theory of Computing: STOC '09, pp. 151–158.Google Scholar
[10]Blais, E., Brody, J. and Matulef, K. (2012) Property testing lower bounds via communication complexity. Comput. Complexity 21 311–358.CrossRefGoogle Scholar
[11]Blais, E. and Kane, D. (2012) Tight bounds for testing k-linearity. In Proc. 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 16th International Workshop on Randomization and Approximation Techniques in Computer Science: RANDOM–APPROX '12, pp. 435–446.CrossRefGoogle Scholar
[12]Blais, E., Weinstein, A. and Yoshida, Y. (2012) Partially symmetric functions are efficiently isomor-phism-testable. In Proc. 53rd Annual IEEE Symposium on Foundations of Computer Science: FOCS '12, pp. 551–560. Also SIAM J. Computing 44 (2015) 411–432.Google Scholar
[13]Blum, M., Luby, M. and Rubinfeld, R. (1993) Self-testing/correcting with applications to numerical problems. In J. Comput. System Sci. 47 549–595.Google Scholar
[14]Chakraborty, S., Fischer, E., García–Soriano, D. and Matsliah, A. (2012) Junto-symmetric functions, hypergraph isomorphism, and crunching. In Proc. 27th Annual IEEE Conference on Computational Complexity: CCC '12, pp. 148–158.CrossRefGoogle Scholar
[15]Chockler, H. and Gutfreund, D. (2004) A lower bound for testing juntas. Inform. Process. Lett 90 301–305.Google Scholar
[16]Cohn, D., Atlas, L. and Ladner, R. (1994) Improving generalization with active learning. In Proc. 15th International Conference on Machine Learning: ICML '94, pp. 201–221.Google Scholar
[17]Diakonikolas, I., Lee, H., Matulef, K., Onak, K., Rubinfeld, R., Servedio, R. and Wan, A. (2007) Testing for concise representations. In Proc. 48th Annual IEEE Symposium on Foundations of Computer Science: FOCS '07, pp. 549–558.CrossRefGoogle Scholar
[18]Erdős, P. and Rado, R. (1960) Intersection theorems for systems of sets. J. London Math. Soc. 35 85–90.Google Scholar
[19]Fischer, E., Kindler, G., Ron, D., Safra, S. and Samorodnitsky, A. (2004) Testing juntas. J. Comput. System Sci. 68 753–787.Google Scholar
[20]Goldreich, O., Goldwasser, S. and Ron, D. (1998) Property testing and its connection to learning and approximation. J. Assoc. Comput. Mach. 45 653–750.Google Scholar
[21]Kearns, M. and Ron, D. (2000) Testing problems with sublearning sample complexity. J. Comput. System Sci. 61 428–456.CrossRefGoogle Scholar
[22]Lubetzky, E. and Sly, A. (2010) Cutoff phenomena for random walks on random regular graphs. Duke Math. J. 153 475–510.CrossRefGoogle Scholar
[23]Molloy, M. and Reed, B. (2002) Graph Colouring and the Probabilistic Method, Springer.Google Scholar
[24]Rubinfeld, R. and Sudan, M. (1996) Robust characterizations of polynomials with applications to program testing. SIAM J. Comput. 25 252–271.Google Scholar
[25]Shannon, C. E. (1949) The synthesis of two-terminal switching circuits. Bell System Tech. J. 28 59–98.Google Scholar
[26]Talagrand, M. (1995) Concentration of measure and isoperimetric inequalities in product spaces. Publications Mathématiques de l'IHÉS 81 73–203.Google Scholar
[27]Valiant, L. G. (1984) A theory of the learnable. Comm. Assoc. Comput. Mach. 27 1134–1142.Google Scholar