Computer Science/Discrete Mathematics Seminar II

Submitted by admin on Wed, 02/27/2013 - 15:01
Sensitivity Versus Block Sensitivity, II
Series: 
Computer Science/Discrete Mathematics
Hao Huang
University of California, Los Angeles; Member, School of Mathematics
Date & Time: 
Tue, 03/19/2013 - 10:30 - 12:30
Location: 
S-101
Video Link: 

http://video.ias.edu/csdm/1213/0319-HaoHuang

There are two important measures of the complexity of a boolean function: the sensitivity and block sensitivity. Whether or not they are polynomial related remains a major open question. In this talk I will survey some known results on this conjecture, and its connection with various combinatorial problems.

terms: