Property Testing with Incomplete or Manipulated Inputs

on YouTube ↗44m

" summary

Introduces an online erasure/corruption oracle that, after each query, can erase or corrupt up to t input locations; uses Fourier analysis and affine-subspace sampling to prove concrete complexity changes. Concretely, linearity remains testable with the usual 1/ε dependence plus a small (provably necessary) overhead in t (polylogarithmic), low-degree testing requires polylog(t) overhead, while sortedness becomes untestable and Lipschitz arrays are likewise impossible even for t=1. Shows separations (an artificial property testable online but not offline), phase transitions with batched queries, and links to Maker–Breaker games.

AI-written summary · about

" chapters (18)

1. 0:00Introduction
2. 1:47Sublinear algorithms motivation
3. 3:11Erasure and corruption oracles
4. 6:02Property testing model overview
5. 7:53Adversarial models comparison
6. 8:35Talk plan and extreme properties
7. 9:02Linearity and low-degree results
8. 12:03Why linearity testing works
9. 17:29Low-degree testing generalization
10. 27:50Impossibility of online sortedness
11. 30:01Online versus offline separations
12. 32:14Query complexity separations
13. 33:26Randomness separation
14. 34:55Batch queries and strategies
15. 36:22Local properties and transitions
16. 39:02Maker-Breaker connection
17. 41:10Open questions
18. 42:58Closing