Noise Stability - Beyond the Boolean cube

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,600
Published on ● Video Link: https://www.youtube.com/watch?v=DZvP5MaRhFI


Duration: 59:26
308 views
7

Dan Mikulincer (MIT)
https://simons.berkeley.edu/talks/dan-mikulincer-mit-2023-06-29
Beyond the Boolean Cube

We revisit the notion of noise stability in the hypercube and show how one can replace the usual heat semigroup with more general stochastic processes. We will then introduce a re-normalized Brownian motion, embedding the discrete hypercube into the Wiener space, and analyze the noise stability along its paths. Our approach leads to a new quantitative form of the 'Majority is Stablest' theorem from Boolean analysis and to progress on the 'most informative bit' conjecture of Courtade and Kumar.



Other Videos By Simons Institute for the Theory of Computing


2023-07-11A Phase Transition in Linear Cross-Entropy Benchmarking
2023-07-11Validated Quantum Advantage via Bell Sampling
2023-07-11Verifiable Quantum Supremacy: What I Hope Will Be Done
2023-07-01Representation Theory in TCS and Extremal Combinatorics
2023-07-01On Perfectly Friendly Bisections of Random Graphs
2023-07-01Localization Schemes
2023-07-01Linearity Testing over the Biased Cube
2023-06-30Sparsifying Sums of Norms
2023-06-30It ain't over till it's over
2023-06-30Separating Quantum from Classical with k-fold Forrelation and Friends
2023-06-29Noise Stability - Beyond the Boolean cube
2023-06-29Erdős and Shannon: A Story of Probability, Communication, and Combinatorics
2023-06-29Fractional Pseudorandom Generators
2023-06-29Strong Bounds for 3-Progressions
2023-06-28Parallel Discrete Sampling via Continuous Walks
2023-06-28Unique Games and Expansion
2023-06-28Small-Set Expansion in the 2-Degree Short-Code Graph, the Easier Version
2023-06-27Product Mixing, Quantum Separation, and Comfortable Juntas
2023-06-27Explicit SoS Lower Bounds from (Small-Set) High Dimensional Expanders
2023-06-27Hypercontractivity Inequality on $\varepsilon$-product Spaces
2023-06-27Reverse Hypercotractivity and Improved Sampling in High Dimensional Expanders


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Beyond the Boolean Cube
Dan Mikulincer