On Active and Passive Testing

DOI10.1017/S0963548315000292zbMath1371.68319arXiv1307.7364OpenAlexW1653844607MaRDI QIDQ5364269

Rani Hod, Noga Alon, 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

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

Related Items

Sunflowers and testing triangle-freeness of functions, Sample-Based High-Dimensional Convexity Testing., A characterization of constant‐sample testable properties

Cites Work

• Unnamed Item
• Random low-degree polynomials are hard to approximate
• Testing juntas
• Non-deterministic exponential time has two-prover interactive protocols
• Property testing lower bounds via communication complexity
• Cutoff phenomena for random walks on random regular graphs
• Self-testing/correcting with applications to numerical problems
• Concentration of measure and isoperimetric inequalities in product spaces
• A lower bound for testing juntas
• Linearity testing in characteristic two
• Property testing and its connection to learning and approximation
• Tight Bounds for Testing k-Linearity
• Intersection Theorems for Systems of Sets
• Improved Bounds for Testing Juntas
• A theory of the learnable
• Robust Characterizations of Polynomials with Applications to Program Testing
• Optimal Testing of Reed-Muller Codes
• Testing juntas nearly optimally
• Partially Symmetric Functions Are Efficiently Isomorphism Testable
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Testing problems with sublearning sample complexity
• Graph colouring and the probabilistic method