Notions of pseudorandomness and (implicitly) of indistinguishability arise in several key results in additive combinatorics. In this expository talk, we will show how to translate between the analytic language of norms, decompositions, and transference and the computer science language of indistinguishability, simulations and pseudoentropy.
Up to translations and generalizations, we shall see that the Weak Regularity Lemma of Frieze and Kannan;a key step in the Green-Tao transference theorem for dense subsets of pseudorandom integers; and the main result needed to analyze the Dziembowski-Pietrzak leakage-resilient encryption scheme, are all essentially the same result.
Copyright. All Rights Reserved.