On Active and Passive Testing

Noga Alon, Rani Hod, Amit Weinstein

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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 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.

Original languageEnglish (US)
Pages (from-to)1-20
Number of pages20
JournalCombinatorics Probability and Computing
Volume25
Issue number1
DOIs
StatePublished - Jan 1 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'On Active and Passive Testing'. Together they form a unique fingerprint.

Cite this