# Function with minimum sensitivity

Let sensitivity be defined as in Sensitivity and Block sensitivity

Is there an example of a boolean function in $n$ variables that depends on all $n$ inputs whose sensitivity is $O(\log n)$?

Is there an example of a boolean function in $n$ variables that depends on all $n$ inputs whose average sensitivity is $O(\log n)$?

Is there an example of a boolean function in $n$ variables that depends on all $n$ inputs whose sensitivity and average sensitivity is $O(\log n)$?

• Note that the average sensitivity is at most the sensitivity, so if a function has sensitivity $O(\log n)$ then it also has average sensitivity $O(\log n)$. – Yuval Filmus Dec 5 '14 at 5:10

## 1 Answer

The tribes function is the classical example of a transitive balanced function whose average sensitivity is $\Theta(\log n)$. Its maximal sensitivity is however $\Theta(n/\log n)$.

The addressing function is an example of a balanced function depending on all inputs which has sensitivity $\Theta(\log n)$ and average sensitivity $\Theta(\log n)$. It is simpler to describe this function as having an input of size $n + \log n$: the first $n$ bits describe a binary string $x$, and the last $\log n$ bits describe a number $i \in [1,n]$. The output of the function is $x_i$. At any point the function depends only on the $\log n$ bits of $i$ as well as the single bit $x_i$.

• are there any other functions whose maximum sensitivity is $O(\log n)$? – Bread Winner Dec 5 '14 at 5:25
• Yes. There is a function which has sensitivity $\tfrac{1}{2}\log n + O(\log\log n)$ in Wegener, The Complexity of Boolean functions, at least according to this paper: people.cs.uchicago.edu/~kutin/publications/sens.iandc.pdf (page 4 middle). – Yuval Filmus Dec 5 '14 at 5:27
• So are such functions rare? Say if I find an example(after some hard work), would there be any use? – Bread Winner Dec 5 '14 at 5:50
• Unless it satisfies other coveted properties, I don't think it will be very interesting. – Yuval Filmus Dec 5 '14 at 5:52
• You can ask a new question about it, and see what people have to say. – Yuval Filmus Dec 5 '14 at 5:56