5 added 6 characters in body

There's been some discussion of searching for improvements to Rubinstein's example, i.e., much larger gaps between sensitivity and block sensitivity. I will argue that any such improvement would have to make a significant departure from the original example, and deviate from a natural approach one would be tempted to follow. This observation has surely been made by others who've worked on the problem. [Note: the argument I'll give can be summarized by the relation $bs_0(f) = O(s_0(f)C_1(f))$. Probably one of the early known facts (?), references would be appreciated...), and if so I probably read the proof at some point; I'll check in the morning.point.]

I'll be talking about the original, Boolean-functions problem. Say we want the sensitivity to be at most $m$, and the block sensitivity to be at least $k \gg m$. (Don't worry about their relation to $n$, the input length.)

Recall that $s_0(f)$ is the maximum over all 0-inputs $x$ to $f$, of the number of sensitive coordinates of $x$. Similarly, $s_1(f)$ is max over all 1-inputs. A natural way to try to make $s(f) \leq m$ hold is to define $f$ as an OR over a collection $\mathcal{G}$ of functions $g_t$, each of which depends on at most $m$ variables. This way, we are at least ensured $s_1(f) \leq m$.
(An equivalent assumption is that $f$ is an $m$-DNF. Another equivalent rephrasing in terms of certificate complexity is that $C_1(f) \leq m$.) Rubinstein's function is easily seen to be of this type. Now I'll argue that for any $m$-DNF $f$, we have $s_0(f) = \Omega(k/m)$. If $s_1(f) = \Theta(m)$ as our approach leads us to expect, then combining we conclude that $s(f) = \Omega(\sqrt{k})$. (But note, this falls short of being a proof of this relation for all $m$-DNFs, since by a more refined approach one could hope to have $s_1(f) \ll m$.)

OK, let's prove that for $f = \bigvee_{g_t \in \mathcal{G}}g_t$ as above, $s_0(f) = \Omega(k/m)$.

Assume WLOG that the all-zeroes input $0$ satisfies $f(0) = 0$, and has $k$ disjoint, minimal sensitive blocks $B_1, \ldots, B_k$. Let $0^{(B_j)}$ denote the all-zero input with bits in $B_j$ flipped to 1, so that $f(0^{(B_j)}) = 1$.

For each block $B_j$, there is a function $g_j \in \mathcal{G}$ that equals 1 on input $0^{(B_j)}$. Let $u^j \in (0, 1, *)^n$ be the restriction of $0^{(B_j)}$ to $S_j := dom(g_j) \subset [n]$, the set of $\leq m$ inputs on which $g_j$ depends. By minimality of $B_j$, we have $B_j \subseteq S_j$; the containment may be proper.

Say that $a, b \in (0, 1, *)$ disagree if they're both Boolean and distinct; otherwise say they agree. Say that strings $u, u' \in (0, 1, *)^n$ are compatible if there's no coordinate $i \in [n]$ for which $u_i, u'_i$ disagree.

Claim 1: There is a set $A \subseteq [k]$ of size $\Omega(k/m)$, such that $u^j, u^\ell$ are compatible for all $j, \ell \in A$.

Proof: For $i \in [n]$, let $\sharp (i)$ denote the number of pairs $j, \ell \in [k]$ such that $u^j, u^\ell$ disagree on the $i$-th coordinate.

Note that if $u^j_i = 0$, then there is at most one $\ell \in [k]$ for which $u^j, u^\ell$ disagree on the $i$-th coordinate. (This is because the sets $B_\ell$ are pairwise disjoint.) Thus, $\sum_i \sharp (i)$ is at most the number of 0's in the strings $u^1, \ldots, u^k$; this is at most $mk$. Then by averaging, there exists $j \in [k]$ such that $\sum_{i \in B_j} \sharp (i) \leq m$; again we're using disjointness of the $B_\ell$'s.

Add this index $j$ to $A$, and delete' $j$ along with all indices $\ell \in [k]$ for which $u^j, u^\ell$ are incompatible. By our choice of $j$, there are at most $m$ indices $\ell \in [k]$ for which $u^j, u^\ell$ disagree somewhere on $B_j$. Also, our earlier observations tell us that at most one $u^\ell$ disagrees with $u^j$ on each coordinate in $S_j \setminus B_j$. Thus we only delete at most $m+m = 2m$ indices $\ell$ along with $j$.

Now repeat the same procedure on the remaining indices. Continuing in this fashion, we build up a set $A$ of at least $k/(2m+1) = \Omega(k/m)$ indices; by construction $u^j, u^\ell$ are consistent for $j, \ell \in A$, as desired. $\clubsuit$

The rest of the proof follows a familiar pattern. Initialize $x := 0^n$ (so $f(x) = 0$). Repeatedly flip bits of $\bigcup_{j \in A} B_j$ to 1, while preserving the property $f(x) = 0$. The strings $u^j$, $j \in A$ are mutually compatible, so our flips never increase the disagreement between $x$ and any $u^j$, $j \in A$. If $x$ ever becomes compatible with any $u^j$, then $f(x) = g_j(x) = 1$, so eventually our flipping process gets stuck at some value $x$; it follows that $x$ has a sensitive coordinate on $B_j$ for each $j \in A$. Thus $s_0(f) \geq |A| = \Omega(k/m)$, as we wanted to show.

4 edited body

There's been some discussion of searching for improvements to Rubinstein's example, i.e., much larger gaps between sensitivity and block sensitivity. I will argue that any such improvement would have to make a significant departure from the original example, and deviate from a natural approach one would be tempted to follow. This observation has surely been made by others who've worked on the problem. [Note: the argument I'll give can be summarized by the relation $bs_0(f) \leq s_0(f)C_1(f)$= O(s_0(f)C_1(f))$. Probably one of the early known facts (?), and if so I probably read the proof at some point; I'll check in the morning.] I'll be talking about the original, Boolean-functions problem. Say we want the sensitivity to be at most$m$, and the block sensitivity to be at least$k \gg m$. (Don't worry about their relation to$n$, the input length.) Recall that$s_0(f)$is the maximum over all 0-inputs$x$to$f$, of the number of sensitive coordinates of$x$. Similarly,$s_1(f)$is max over all 1-inputs. A natural way to try to make$s(f) \leq m$hold is to define$f$as an OR over a collection$\mathcal{G}$of functions$g_t$, each of which depends on at most$m$variables. This way, we are at least ensured$s_1(f) \leq m$. (An equivalent assumption is that$f$is an$m$-DNF. Another equivalent rephrasing in terms of certificate complexity is that$C_1(f) \leq m$.) Rubinstein's function is easily seen to be of this type. Now I'll argue that for any$m$-DNF$f$, we have$s_0(f) = \Omega(k/m)$. If$s_1(f) = \Theta(m)$as our approach leads us to expect, then combining we conclude that$s(f) = \Omega(\sqrt{k})$. (But note, this falls short of being a proof of this relation for all$m$-DNFs, since by a more refined approach one could hope to have$s_1(f) \ll m$.) OK, let's prove that for$f = \bigvee_{g_t \in \mathcal{G}}g_t$as above,$s_0(f) = \Omega(k/m)$. Assume WLOG that the all-zeroes input$0$satisfies$f(0) = 0$, and has$k$disjoint, minimal sensitive blocks$B_1, \ldots, B_k$. Let$0^{(B_j)}$denote the all-zero input with bits in$B_j$flipped to 1, so that$f(0^{(B_j)}) = 1$. For each block$B_j$, there is a function$g_j \in \mathcal{G}$that equals 1 on input$0^{(B_j)}$. Let$u^j \in (0, 1, *)^n$be the restriction of$0^{(B_j)}$to$S_j := dom(g_j) \subset [n]$, the set of$ \leq m$inputs on which$g_j$depends. By minimality of$B_j$, we have$B_j \subseteq S_j$; the containment may be proper. Say that$a, b \in (0, 1, *)$disagree if they're both Boolean and distinct; otherwise say they agree. Say that strings$u, u' \in (0, 1, *)^n$are compatible if there's no coordinate$i \in [n]$for which$u_i, u'_i$disagree. Claim 1: There is a set$A \subseteq [k]$of size$\Omega(k/m)$, such that$u^j, u^\ell$are compatible for all$j, \ell \in A$. Proof: For$i \in [n]$, let$\sharp (i)$denote the number of pairs$j, \ell \in [k]$such that$u^j, u^\ell$disagree on the$i$-th coordinate. Note that if$u^j_i = 0$, then there is at most one$\ell \in [k]$for which$u^j, u^\ell$disagree on the$i$-th coordinate. (This is because the sets$B_\ell$are pairwise disjoint.) Thus,$\sum_i \sharp (i)$is at most the number of 0's in the strings$u^1, \ldots, u^k$; this is at most$mk$. Then by averaging, there exists$j \in [k]$such that$\sum_{i \in B_j} \sharp (i) \leq m$; again we're using disjointness of the$B_\ell$'s. Add this index$j$to$A$, and delete'$j$along with all indices$\ell \in [k]$for which$u^j, u^\ell$are incompatible. By our choice of$j$, there are at most$m$indices$\ell \in [k]$for which$u^j, u^\ell$disagree somewhere on$B_j$. Also, our earlier observations tell us that at most one$u^\ell$disagrees with$u^j$on each coordinate in$S_j \setminus B_j$. Thus we only delete at most$m+m = 2m$indices$\ell$along with$j$. Now repeat the same procedure on the remaining indices. Continuing in this fashion, we build up a set$A$of at least$k/(2m+1) = \Omega(k/m)$indices; by construction$u^j, u^\ell$are consistent for$j, \ell \in A$, as desired.$\clubsuit$The rest of the proof follows a familiar pattern. Initialize$x := 0^n$(so$f(x) = 0$). Repeatedly flip bits of$\bigcup_{j \in A} B_j$to 1, while preserving the property$f(x) = 0$. The strings$u^j$,$j \in A$are mutually compatible, so our flips never increase the disagreement between$x$and any$u^j$,$j \in A$. If$x$ever becomes compatible with any$u^j$, then$f(x) = g_j(x) = 1$, so eventually our flipping process gets stuck at some value$x$; it follows that$x$has a sensitive coordinate on$B_j$for each$j \in A$. Thus$s_0(f) \geq |A| = \Omega(k/m)$, as we wanted to show. 3 added 61 characters in body There's been some discussion of searching for improvements to Rubinstein's example, i.e., much larger gaps between sensitivity and block sensitivity. I will argue that any such improvement would have to make a significant departure from the original example, and deviate from a natural approach one would be tempted to follow. This observation has surely been made by others who've worked on the problem. [Note: the argument I'll give can be summarized by the relation$bs(f) bs_0(f) \leq s_0(f)C_1(f)$. Probably one of the early known facts due to Nisan(?), and if so I probably read the proof at some point; I'll check in the morning.] I'll be talking about the original, Boolean-functions problem. Say we want the sensitivity to be at most$m$, and the block sensitivity to be at least$k \gg m$. (Don't worry about their relation to$n$, the input length.) Recall that$s_0(f)$is the maximum over all 0-inputs$x$to$f$, of the number of sensitive coordinates of$x$. Similarly,$s_1(f)$is max over all 1-inputs. A natural way to try to make$s(f) \leq m$hold is to define$f$as an OR over a collection$\mathcal{G}$of functions$g_t$, each of which depends on at most$m$variables. This way, we are at least ensured$s_1(f) \leq m$. (An equivalent assumption is that$f$is an$m$-DNF. Another equivalent rephrasing in terms of certificate complexity is that$C_1(f) \leq m$.) Rubinstein's function is easily seen to be of this type. Now I'll argue that for any$m$-DNF$f$, we have$s_0(f) = \Omega(k/m)$. If$s_1(f) = \Theta(m)$as our approach leads us to expect, then combining we conclude that$s(f) = \Omega(\sqrt{k})$. (But note, this falls short of being a proof of this relation for all$m$-DNFs, since by a more refined approach one could hope to have$s_1(f) \ll m$.) OK, let's prove that for$f = \bigvee_{g_t \in \mathcal{G}}g_t$as above,$s_0(f) = \Omega(k/m)$. Assume WLOG that the all-zeroes input$0$satisfies$f(0) = 0$, and has$k$disjoint, minimal sensitive blocks$B_1, \ldots, B_k$. Let$0^{(B_j)}$denote the all-zero input with bits in$B_j$flipped to 1, so that$f(0^{(B_j)}) = 1$. For each block$B_j$, there is a function$g_j \in \mathcal{G}$that equals 1 on input$0^{(B_j)}$. Let$u^j \in (0, 1, *)^n$be the restriction of$0^{(B_j)}$to$S_j := dom(g_j) \subset [n]$, the set of$ \leq m$inputs on which$g_j$depends. By minimality of$B_j$, we have$B_j \subseteq S_j$; the containment may be proper. Say that$a, b \in (0, 1, *)$disagree if they're both Boolean and distinct; otherwise say they agree. Say that strings$u, u' \in (0, 1, *)^n$are compatible if there's no coordinate$i \in [n]$for which$u_i, u'_i$disagree. Claim 1: There is a set$A \subseteq [k]$of size$\Omega(k/m)$, such that$u^j, u^\ell$are compatible for all$j, \ell \in A$. Proof: For$i \in [n]$, let$\sharp (i)$denote the number of pairs$j, \ell \in [k]$such that$u^j, u^\ell$disagree on the$i$-th coordinate. Note that if$u^j_i = 0$, then there is at most one$\ell \in [k]$for which$u^j, u^\ell$disagree on the$i$-th coordinate. (This is because the sets$B_\ell$are pairwise disjoint.) Thus,$\sum_i \sharp (i)$is at most the number of 0's in the strings$u^1, \ldots, u^k$; this is at most$mk$. Then by averaging, there exists$j \in [k]$such that$\sum_{i \in B_j} \sharp (i) \leq m$; again we're using disjointness of the$B_\ell$'s. Add this index$j$to$A$, and `delete'$j$along with all indices$\ell \in [k]$for which$u^j, u^\ell$are incompatible. By our choice of$j$, there are at most$m$indices$\ell \in [k]$for which$u^j, u^\ell$disagree somewhere on$B_j$. Also, our earlier observations tell us that at most one$u^\ell$disagrees with$u^j$on each coordinate in$S_j \setminus B_j$. Thus we only delete at most$m+m = 2m$indices$\ell$along with$j$. Now repeat the same procedure on the remaining indices. Continuing in this fashion, we build up a set$A$of at least$k/(2m+1) = \Omega(k/m)$indices; by construction$u^j, u^\ell$are consistent for$j, \ell \in A$, as desired.$\clubsuit$The rest of the proof is simplefollows a familiar pattern. Initialize$x := 0^n$(so$f(x) = 0$). Repeatedly flip bits of$\bigcup_{j \in A} B_j$to 1, while preserving the property$f(x) = 0$. The strings$u^j$,$j \in A$are mutually compatible, so our flips never increase the disagreement between$x$and any$u^j$,$j \in A$. If$x$ever becomes compatible with any$u^j$, then$f(x) = g_j(x) = 1$, so eventually our flipping process gets stuck at some value$x$; it follows that$x$has a sensitive coordinate on$B_j$for each$j \in A$. Thus$s_0(f) \geq |A| = \Omega(k/m)\$, as we wanted to show.

2 added 177 characters in body
1