Structure vs. Randomness

Workshop | April 10 – 14, 2017 every day |  Calvin Laboratory (Simons Institute for the Theory of Computing)

 Simons Institute for the Theory of Computing

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.

Madhur Tulsiani (Toyota Technological Institute at Chicago; chair), Jacob Fox (Stanford University), Shachar Lovett (UC San Diego), Tom Sanders (University of Oxford).

  Register online, 510-664-9856