On active and passive testing

DOI10.1017/S0963548315000292MaRDI QIDQ5364269zbMATH OpenOpenAlexFDO

Authors Noga Alon, Rani Hod, Amit Weinstein

Publication date 4 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.7364

Mathematics Subject Classification ID

Symmetric functions and generalizations (05E05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorics in computer science (68R05) Randomized algorithms (68W20)

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 to restrict 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 Z_2) requires Theta(k*log n) queries, assuming k is not too large. This extends the case k=1, (that is, dictator functions), analyzed by Balcan et. al. 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 Erdos--Rado theorem on Delta-systems.

Recommendations

• Tight bounds for testing k-linearity
• An optimal tester for k-Linear
• Testing piecewise functions
• Property testing bounds for linear and quadratic functions via parity decision trees
• Property testing lower bounds via communication complexity

Cites work

• A lower bound for testing juntas
• A theory of the learnable
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Concentration of measure and isoperimetric inequalities in product spaces
• Cutoff phenomena for random walks on random regular graphs
• Graph colouring and the probabilistic method
• Improved Bounds for Testing Juntas
• Intersection Theorems for Systems of Sets
• Linearity testing in characteristic two
• Non-deterministic exponential time has two-prover interactive protocols
• Optimal testing of Reed-Muller codes
• Partially symmetric functions are efficiently isomorphism testable
• Property testing and its connection to learning and approximation
• Property testing lower bounds via communication complexity
• Random low-degree polynomials are hard to approximate
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Testing juntas
• Testing juntas nearly optimally
• Testing problems with sublearning sample complexity
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Tight bounds for testing k-linearity

Cited in

(4)

• Testing piecewise functions
• An optimal tester for k-Linear
• Sample-based high-dimensional convexity testing
• A characterization of constant-sample testable properties

This page was built for publication: On active and passive testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5364269)