Structure vs. Randomness 2017
2017-04-10..2017-04-14
Berkeley, United States
| title | author | length |
|---|---|---|
| Algorithmic Dense Model Theorems and Weak Regularity | Russell Impagliazzo | 34m |
Claims a tight equivalence between hardcore lemmas, dense model theorems, and weak regularity, and gives algorithmic dense model theorem and weak regularity… | ||
| Sum of Squares Lower Bounds for Refuting Any CSP | Ryan O'Donnell | 31m |
Proves tight lower bounds showing the Sum‑of‑Squares (SOS) hierarchy cannot refute random CSPs below the specific density thresholds it earlier achieves… | ||
| Large Deviations for Arithmetic Progressions | Yufei Zhao | 59m |
Proves the sharp upper-tail asymptotics for k-term AP counts when p does not decay too fast, solving the variational problem that gives an explicit constant… | ||
| Trading Information Complexity for Error | Hamed Hatami | 29m |
Paper proves that allowing error ε reduces information cost for AND by Θ(H(ε)) and for Disjointness the per-instance cost drops by about H(ε) (matching earlier… | ||
| Sparse Dense Dichotomy and Liquid Graphs | Jarik Nesetril | 26m |
Defines bounded expansion via shallow topological minors and degeneration and claims that planting any bounded‑degree graph then sprinkling random edges at… | ||
| The Entropy Decrement Method and the Erdos Discrepancy Problem | Terry Tao | 58m |
Claims that the Erdős discrepancy conjecture follows by converting the global problem to a model for the Liouville sequence, proving nontrivial logarithmic… | ||
| Vinogradov's Three Primes Theorem with Primes from Special Sets | Kaisa Matomäki | 01h 02m |
Shows that the only genuine obstruction to Vinogradov’s three‑prime conclusion for a subset of primes is concentration on small Bohr sets (a Boset… | ||
| Additive Structure of Sets of Fourier Coefficients | Thomas Bloom | 01h 03m |
Classifies what a large Fourier spectrum can actually look like and gives a way to extract a low‑dimensional large subset usable for density increments. Three… | ||
| On Structural Properties of Low Threshold Rank Graphs | Shayan Oveis Gharan | 35m |
Defines epsilon-threshold rank as the count of normalized-adjacency eigenvalues with |λ| ≥ ε and studies graphs where that rank is small. Proves any graph… | ||
| Hidden Irregularity Versus Hidden Structure: The Emergence of the Johnson Graphs | Laszlo Babai | 01h 07m |
Claim: a graph or relational structure with symmetry defect ≥10% yields, at quasi‑polynomial multiplicative cost, one of three canonical outcomes: a vertex… | ||
| Hidden Irregularity Versus Hidden Structure: The Emergence of the Johnson Graphs | Laszlo Babai | 44m |
Laszlo Babai, University of Chicago
Structure vs. Randomness
https://simons.berkeley.edu/talks/laszlo-babai-2017-4-12-2 | ||
| Random High-Dimensional Combinatorial Objects | Nati Linial | 01h 05m |
Nati Linial, Hebrew University of Jerusalem
https://simons.berkeley.edu/talks/nati-linial-2017-4-12
Structure vs. Randomness | ||
| Positional Games and Randomness | Michael Krivelevich | 01h 02m |
Michael Krivelevich, Tel Aviv University
https://simons.berkeley.edu/talks/michael-krivelevich-2017-4-13
Structure vs. Randomness | ||
| Labeling the Complete Bipartite Graph with No Zero Cycles | Shachar Lovett | 58m |
Shachar Lovett, UC San Diego
https://simons.berkeley.edu/talks/shachar-lovett-2017-4-13
Structure vs. Randomness | ||
| Unavoidable Patterns in Words | David Conlon | 57m |
Defines FN(q) as the least length forcing Zeeman word ZN in any q-letter string and proves concrete growth rates and constructions. Main claims: for fixed N… | ||
| True Complexity of Multilinear Systems | Freddie Manners | 01h 01m |
Proves two concrete things for six forms in three variables: first, there exist systems over Fp where the counting average stays large while all U2 norms stay… | ||
| nothing matches | ||