On the sensitivity complexity of Boolean functions

Xiaoming Sun
CAS

Time: 11am, Aug 15, 2013
Venue: Room 3501

Abstract:

Decision tree is an important and well-studied computational model,
especially used in quantum computing. Sensitivity and block sensitivity are
two important complexity measures of Boolean functions in Decision Tree
theory. A longstanding open problem in decision tree complexity, the
“Sensitivity versus Block Sensitivity” conjecture, proposed by Nisan and
Szegedy in 1992, is whether these two complexity measures are polynomially
related. In this talk I will present some new results related to this
conjecture. I will also discuss the sensitivity complexity of some special
functions, for example graph properties, cyclically invariant functions etc.

Base on joint work with Andris Ambainis, Yihan Gao, Jieming Mao and Song
Zuo.