On Active and Passive Testing
From MaRDI portal
Publication:5364269
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
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
