%T Block Sensitivity versus Sensitivity
%A Karn Seth
%R Technical Report TR2010-673
%I Dartmouth College, Computer Science
%C Hanover, NH
%D June 2010
%U http://www.cs.dartmouth.edu/reports/TR2010-673.pdf
%X
Sensitivity and block sensitivity are useful and well-studied measures of computational
complexity, but in spite of their similarities, the largest possible gap between
them is still unknown. Rubinstein showed that this gap must be at least quadratic,
and Kenyon and Kutin showed that it is at worst exponential, but many strongly
suspect that the gap is indeed quadratic, or at worst polynomial.
Our work shows that for a large class of functions, which includes Rubinstein's
function, the quadratic gap between sensitivity and block sensitivity is the best
we can possibly do.
%Z
Senior Honours Thesis Advisor: Amit Chakrabarti