1
$\begingroup$

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)$?

$\endgroup$
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Yuval Filmus Dec 5 '14 at 5:10
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ are there any other functions whose maximum sensitivity is $O(\log n)$? $\endgroup$ – Turbo Dec 5 '14 at 5:25
  • 1
    $\begingroup$ 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). $\endgroup$ – Yuval Filmus Dec 5 '14 at 5:27
  • $\begingroup$ So are such functions rare? Say if I find an example(after some hard work), would there be any use? $\endgroup$ – Turbo Dec 5 '14 at 5:50
  • 1
    $\begingroup$ Unless it satisfies other coveted properties, I don't think it will be very interesting. $\endgroup$ – Yuval Filmus Dec 5 '14 at 5:52
  • 1
    $\begingroup$ You can ask a new question about it, and see what people have to say. $\endgroup$ – Yuval Filmus Dec 5 '14 at 5:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.