SENSITIVITY VS BLOCK SENSITIVITY OF BOOLEAN FUNCTIONS

被引：30

作者：

RUBINSTEIN, D

机构：

来源：

COMBINATORICA | 1995年 / 15卷 / 02期

关键词：

D O I：

10.1007/BF01200762

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Sensitivity and block sensitivity are important measures of complexity of Boolean functions. In this note we exhibit a Boolean function of n variables that has sensitivity O(root n) and block sensitivity Omega(n). This demonstrates a quadratic separation of the two measures.

引用

页码：297 / 299

页数：3