Threshold, Influence, Noise, and Discrete Harmonic Analysis

on YouTube ↗44m

" summary

Asks when near-equality in Harper’s edge-expansion bound actually forces structure: for muP(f) = T and P·I_P(f) within constant of the T·log_P(T) optimum, conjectures that one can fix a set S of size O(log(1/T)) that boosts the conditional density — a Bourgain-style inverse theorem upgrade used to locate sharp thresholds; proves a negative result for large-set influence showing mu(f) may need to be ≥ exp(−n^β) (tribes variant), and raises concrete questions on noise-stable vs noise-sensitive decomposition, K-wise independence improvements to KKL/Harper, and robustness of percolation crossings and random-matrix eigenvalue events.

AI-written summary · about

" chapters (6)

1. 0:00Introduction
2. 0:20Inverse theorems for Harper inequality
3. 14:20Large set influences and projections
4. 28:05Noise sensitivity in Boolean functions
5. 37:17Open questions
6. 43:19Q&A

" related talks

• 38mAn Information Theoretic View of HypercontractivityEhud Friedgut · Information Theory in Complexity Theory and Combinatorics 2015
• 45mThe lower tail: Poisson approximation revisitedLutz Warnke · Random Instances and Phase Transitions (Simons Institute, 2016)
• 56mSome Probabilistic Uses of Dirichlet EigenvectorsPersi Diaconis · Spectral Algorithms: From Theory to Practice 2014
• 01h 12mPedagogical Talk: Frameworks for Information-Computation TradeoffsTselil Schramm · Computational Phase Transitions (Simons Institute, 2020)
• 27mDetection and Estimation through an Information Theory LensSergio Verdú · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 11mSharp Threshold for the Planted Matching ProblemDana Yang · Meet the Fellows Welcome Event
• 01h 03mHigh Dimensional Geometry and Concentration IISantosh Vempala · Foundations of Data Science Boot Camp 2018
• 01h 00mLog-concave Polynomials and Spectral Independence 2Kuikui Liu · Analysis and TCS Boot Camp 2023