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

April 2024
M T W T F S S
1234567
891011121314
15161718192021
22232425262728
2930