Testing Boolean Functions
summary
Overview of concrete results and algorithms: property testing of Boolean functions centers on very low-query testers. The BLR linearity tester checks f(x)+f(y)=f(x+y) over F2 using O(1/ε) random triples and proves closeness via a voting/self-correction function and two lemmas. Monotonicity gets an edge tester n/ε (one-sided, non-adaptive) with structural proofs; path testers and later work reduce the cost toward ~2√n regimes. Junta testing achieves complexity independent of n (e.g., k log k + k/ε or 2^{√k} non-adaptive bounds) and tolerant variants remain harder.
AI-written summary · about
chapters (6)
- 0:00Property testing of Boolean functions
- 1:14Core definitions in property testing
- 13:57Linearity testing and BLR algorithm
- 34:46Testing monotonicity
- 50:23Juntas and k-junta testing
- 1:00:04Open problems in property testing
related talks
10m“Essential Mathematics for Testers”
14mVerify, but test: extracting property-based tests from F* specifications
47mProperty-Based Testing
51mProperty-Based Testing
44mHow to specify it! A guide to writing properties of pure functions
23mLogarithm and Program Testing
44mTypes and Property Tests for Software Resiliency
18mType-Based Incorrectness Reasoning