Structure vs. Randomness (Simons Institute)

# click the upper-left icon to select videos from the playlist

source: Simons Institute     2017年4月10日
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.
For more information, please visit https://simons.berkeley.edu/workshops/pseudorandomness2017-3
These presentations were supported in part by an award from the Simons Foundation.

Algorithmic Dense Model Theorems and Weak Regularity 34:13 Russell Impagliazzo, UC San Diego https://simons.berkeley.edu/talks/rus...
Sum of Squares Lower Bounds for Refuting Any CSP 30:31
Large Deviations for Arithmetic Progressions 58:51
Trading Information Complexity for Error 29:05
Sparse Dense Dichotomy and Liquid Graphs 25:39
The Entropy Decrement Method and the Erdos Discrepancy Problem 57:37
Vinogradov's Three Primes Theorem with Primes from Special Sets 1:01:44
Additive Structure of Sets of Fourier Coefficients 1:02:35
On Structural Properties of Low Threshold Rank Graphs 35:01
Hidden Irregularity Versus Hidden Structure: The Emergence of the Johnson Graphs 1:06:48
Hidden Irregularity Versus Hidden Structure: The Emergence of the Johnson Graphs 44:26
Random High-Dimensional Combinatorial Objects 1:04:52
Positional Games and Randomness 1:02:09
Labeling the Complete Bipartite Graph with No Zero Cycles 58:07
Unavoidable Patterns in Words 57:05
True Complexity of Multilinear Systems 1:00:50

No comments: