Home »

Dec 11, 2020

Resolution of the Sensitivity Conjecture: where linear algebra meets combinatorics

Hao Huang 黄皓, Emory University

 

Abstract:

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 (known as the Sensitivity Conjecture) had remained a mystery for almost three decades until July 2019. In this talk, I will explain the background and history of the Sensitivity Conjecture, and walk through a very short proof based on undergraduate level linear algebra and combinatorics.

 

Recorded video for the talk (click)

Activities Calendar

March 2023
M T W T F S S
 12345
6789101112
13141516171819
20212223242526
2728293031