6533b7dafe1ef96bd126f5d8

RESEARCH PRODUCT

Tighter Relations between Sensitivity and Other Complexity Measures

Xiaoming SunMohammad BavarianSong ZuoYihan GaoJieming MaoAndris Ambainis

subject

CombinatoricsComplexity indexDiscrete mathematicsConjecture010201 computation theory & mathematics0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processing0102 computer and information sciences02 engineering and technologySensitivity (control systems)Boolean function01 natural sciencesMathematics

description

The sensitivity conjecture of Nisan and Szegedy [12] asks whether the maximum sensitivity of a Boolean function is polynomially related to the other major complexity measures of Boolean functions. Despite major advances in analysis of Boolean functions in the past decade, the problem remains wide open with no positive result toward the conjecture since the work of Kenyon and Kutin from 2004 [11].

yearjournalcountryeditionlanguage
2014-07-08
https://doi.org/10.1007/978-3-662-43948-7_9