@TechReport{Dartmouth:TR2010-673,
author = {Karn Seth},
title = {{Block Sensitivity versus Sensitivity}},
institution = {Dartmouth College, Computer Science},
address = {Hanover, NH},
number = {TR2010-673},
year = {2010},
month = {June},
URL = {http://www.cs.dartmouth.edu/reports/TR2010-673.pdf},
comment = {
Senior Honours Thesis Advisor: Amit Chakrabarti
},
abstract = {
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.
}
}