#Property-Testing

2 posts in tag “Property-Testing”.

• 

  Additive Combinatorics: Szemerédi's Theorem, Sumset Inequalities, and Applications in Property Testing

  2022-10-25

  A rigorous exploration of additive combinatorics—Szemerédi's theorem on arithmetic progressions, Plünnecke-Ruzsa inequalities, the Balog-Szemerédi-Gowers theorem, and their applications in property testing and pseudorandomness.

• 

  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.