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.