Let’s Try and Be More Tolerant: On Tolerant Property Testing and Distance Approximation
summary
Gives concrete algorithms and separations: monotonicity over [1..n] is distance-approximated by estimating the size of a maximal matching in the violation graph and maximal matching (this yields a factor-2 reduction from vertex-cover; initial polylog^7 n dependence on log n is later reduced to log n and Saks removes the factor-2 tradeoff); graph connectivity in the sparse incidence-list model is approximated by sampling O(1/δ^2) vertices and doing BFS up to size r≈1/δ to estimate component count; subsequence-freeness is sample-testable with Θ(k/ε) samples and tolerant testing needs ~Õ(k^2/δ^2) samples with 1/δ^2 necessary (sample-based k/ε bound).
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:03Talk overview
- 2:12Property testing definitions
- 4:05Tolerant testing and distance
- 8:44Monotonicity testing improvements
- 21:18Monotonicity over hypercube
- 26:20Graph connectivity in sparse model
- 39:23k-edge connectivity and subgraph-freeness
- 44:19Dense model tolerant results
- 49:48Subsequence freeness in samples
- 56:42Open problems and summary