## Keywords (1)

Publications
Sensitivity vs. Block Sensitivity of Boolean Functions

# Sensitivity vs. Block Sensitivity of Boolean Functions,10.1007/BF01200762,Combinatorica,David Rubinstein

Sensitivity vs. Block Sensitivity of Boolean Functions
Senstivity and block sensitivity are important measures of complexity of Boolean functions. In this note we exhibit a Boolean function ofn variables that has sensitivity <img src="/fulltext-image.asp?format=htmlnonpaginated&src=Q0303V260357H2H7_html\493_2005_Article_BF01200762_TeX2GIFIE1.gif" border="0" alt=" $$O(\sqrt n )$$ " /> and block sensitivity Ω(n). This demonstrates a quadratic separation of the two measures.
Journal: Combinatorica , vol. 15, no. 2, pp. 297-299, 1995
View Publication
 The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
More »

## Citation Context (5)

• ...The query complexity of Boolean functions, also called black-box or decision-tree complexity, has been well studied for years [3,5,13,14,16,17]...

### Scott Aaronson. Algorithms for Boolean Function Query Properties

• ...The relation between sensitivity and block sensitivity has been studied in 128, 17, 32, 191...

### Anna Gál, et al. A Theorem on Sensitivity and Applications in Private Computation

• ...Since l(f ) gives an equivalent definition for the log-sensitivity of f ,w e may obtain a new approach to the sensitivity versus block-sensitivity question of Linial and Rubinstein [15]...

### Mario Szegedy, et al. Computing Boolean Functions from Multiple Faulty Copies of Input Bits

• ...Rubinstein [10] exhibits a family of functions where the gap is quadratic, and this is the largest known separation...
• ...The largest known gap between sensitivity and block sensitivity is due to Rubinstein [10]:...
• ...Remark. As we mentioned in Section 2.2, Rubinstein [10] exhibits a quadratic gap between sensitivity and block sensitivity...

### Claire Kenyon, et al. Sensitivity, block sensitivity, and � -block sensitivity of boolean fu...

• ...The relation between sensitivity and block sensitivity has been studied in a number of papers [28, 17, 32, 20]...

Sort by: