Query-Complexity
- Sublinear Algorithms: Property Testing, Query Complexity, and the Power of Random Sampling
· 2019-07-07
An exploration of sublinear-time algorithms—property testing, the regularity lemma connection, and how random sampling reveals global structure without reading the whole input.