|
5
|
|
edited Jul 16 2010 at 3:18 |
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 Jul 15 2010 at 15:08 |
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
|
|
edited Jul 15 2010 at 5:27 |
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
|
|
edited Jul 15 2010 at 4:59 |
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) \leq s_0(f)C_1(f)$. Probably one of the early known facts due to Nisan; 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 simple. 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.
|
|
|
|
|
1
|
|
answered Jul 15 2010 at 3:24 |
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.
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 simple. 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.
|
|
|
