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.

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

  Register online

 simonsevents@berkeley.edu, 510-664-9856