Simons Institute Workshop: Structure vs. Randomness Apr. 10 – Apr. 14

Seminar | April 11 | 9:05 a.m.-1:05 p.m. | Simons Institute, Auditorium | Note change in date and location

 Various, Various

 Department of Mathematics

This workshop will focus on a phenomenon observed in harmonic analysis, ergodic theory, analytic number theory, graph theory, complexity theory, additive combinatorics and cryptography, according to which arbitrary objects can be well approximated by a combination of a small number of pseudorandom objects. In the study of higher-order Fourier analysis, this corresponds to approximating every function by a combination of structured functions plus a function of small Gowers norm; in graph theory it corresponds to Szemeredi’s regularity lemma; in cryptography it corresponds to approximating distributions dominated by a pseudorandom distribution by distributions of high min-entropy; and so on.

The workshop will bring together researchers working on such decomposition results in different areas and with different motivations, who often use technically similar methods.

 nikhil@math.berkeley.edu