UC San Diego

This dissertation involves the interplay between structure, randomness, and pseudorandomness in theoretical computer science and additive combinatorics. Such interplay in particular materializes when one is extracting algebraic structure in scenarios where only weak combinatorial information is available. We develop new tools to address some problems of this type where the objects are sumsets and its bilinear generalizations, set of large Fourier spectra, and protocols in communication complexity. Later we move on to constructions of objects with certain pseudorandom properties. We construct a highly irregular set showing the limits of regularity lemma in the algebraic setting which is a major tool in pseudorandomness. Moreover, we introduce a new framework to construct pseudorandom generators and give some applications