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