Sensitivity Conjecture and Its Applications

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


Duration: 55:57
1,044 views
18

Hao Huang (Emory University) & Avishay Tal (UC Berkeley)
Advances in Boolean Function Analysis
https://simons.berkeley.edu/events/boolean-3

Many complexity measures of Boolean functions have been well studied in theoretical computer science. These include sensitivity, block sensitivity, degree, approximate degree, certificate complexity, decision-tree complexity, among many others. It has been long known that almost all these measures are polynomially related to each other, yet whether sensitivity belongs to the same class (a.k.a. the Sensitivity Conjecture of Nisan and Szegedy) has remained a mystery for almost three decades until last July.

In this talk, we will explain some background, walk through a linear algebraic proof of the Sensitivity Conjecture based on the Gotsman-Linial reduction to an extremal combinatorial problem on discrete cubes, and discuss the remaining challenges.



Other Videos By Simons Institute for the Theory of Computing


2020-08-04From Chaos to Information - Communication in a Crowd of Bats
2020-08-04Foundations of Early Human Learning
2020-08-04Interpreting Natural Language Processing Models
2020-08-03Sperm Whale Communication: What we know so far/ Understanding Whale Communication: First steps
2020-08-03Is Life All About Communication? A Theoretical Perspective
2020-08-03Project CETI Next Steps: Industrial-Scale Whale Bioacoustic Data Collection and Analysis
2020-08-03Improved Bounds for the Sunflower Lemma
2020-08-03What Information Do the Voices of African Savanna Elephants Communicate?
2020-07-30The Mathematical Essence of Aging | Theoretically Speaking
2020-07-23Berkeley in the 80s, Episode 3: Silvio Micali
2020-07-22Sensitivity Conjecture and Its Applications
2020-07-22Sensitivity Conjecture and Its Applications
2020-07-21Computing and Data Science for Human Welfare and Social Justice
2020-07-21Roles for Computing in Social Justice
2020-07-20Nowcasting COVID-19
2020-07-20Presentations & Reflections
2020-07-20Perspectives on Digital Contact Tracing
2020-07-15Advances in Boolean Function Analysis — On the Fourier-Entropy Influence Conjecture
2020-07-15Advances in Boolean Function Analysis — On the Fourier-Entropy Influence Conjecture
2020-06-29Berkeley in the 80s, Episode 2: Manuel Blum
2020-06-25Computational and Statistical Tools to Control a Pandemic | Theoretically Speaking Series


Tags:
Simons Institute
Theory of Computing
Theory of Computation
Theoretical Computer Science
Computer Science
UC Berkeley
Avishay Tal
Advances in Boolean Function Analysis