User andy drucker - MathOverflow

Answer by Andy Drucker for The "sensitivity" of 2-colorings of the d-dimensional integer lattice

2010-07-15T03:24:00Z

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

Answer by Andy Drucker for The "sensitivity" of 2-colorings of the d-dimensional integer lattice

2010-07-13T15:41:04Z

(Note: I'm new here; I don't mean to 'answer' Scott's question, but somehow I'm not seeing how to just leave a comment.)

I think an approach that uses (d-dimensional) Sperner's Lemma is definitely worth looking for, since anyone who has tried to directly find a sensitive input from a block-sensitive one knows it's a hard road.

http://en.wikipedia.org/wiki/Sperner%27s_lemma

A possible sketch 'proof' of sensitivity conjecture with gaps (I'll discuss what needs fixing after):

Let $C_0$ denote the 2-coloring of the $d$-lattice. suppose for concreteness that $C_0(0, 0, ... 0) =$ blue and $C_0(0, 0, ... k_i, ... 0) =$ red for each $i \leq d$. (that's $k_i$ in the $i$-th coordinate, 0 elsewhere).

Form a topological simplex with vertices $(0, .., 0)$ and ${(0, 0, ... k_i, ... 0)}$ (for all ${i <= d}$), by joining each pair of vertices with a lattice walk. This gives you the skeleton of a d-dimensional solid consisting of a bunch of unit cubes. Triangulate each of these cubes in some fashion, without adding new vertices.

Now we give a new coloring $Col$: a $(d+1)$-coloring of the vertices of this solid:
$Col(0, 0, ... ,0) := 0$,

$Col(v) := 0$ for any other $v$ colored blue in $C_0$,

$Col(0, 0, ... k_i, ... 0) := i$,

and... $Col(v') \in { 1, 2, ... ,d}$ for other $v'$, in some clever way I haven't determined yet.

Now use Sperner's Lemma (+) to find a panchromatic simplex in the triangulation. This, we hope (++), is the sensitive point we were looking for.

Gaps: (+) we need $Col$ to be defined to satisfy the consistency requirements over faces. (see the Lemma's statement on wiki.)

(++) an edge of the panchromatic simplex found will be a sensitive edge iff:

(i) it goes from color $Col = 0$ to a color $Col = i \neq 0$;

(ii) it is an actual lattice edge.

The gap (+) may be impossible to rectify as stated: consider the case where the only points colored red in $C_0$ are the hypothesized points $(0, ... k_i, ... 0)$. But in this case the sensitivity at red points is high. To fill (+), we'd need to give an argument saying that WLOG the red points have a high degree of connectivity. We may also wish to jettison some of the red points and introduce more blue vertices which take on distinct colors in $Col$.

To fil (++), an 'ideal' situation would one in which all simplicial edges in our triangulation are in fact lattice edges. Then (i), (ii) would be satisfied on all edges issuing from the $Col = 0$ vertex in the panchromatic simplex, and we'd get sensitivity $d$.

This is impossible (and we can't hope for sensitivity $d$); however, perhaps there are triangulations of the d-cube in which all simplices have 'enough' lattice edges at each vertex. (I think this is false too, but I don't have a better idea yet.)

Comment by Andy Drucker

2010-07-13T20:22:37Z

Thanks Daniel--that's a good example. It demonstrates that if gap (+) is to be filled, the shape of the simplex would in general have to 'adapt' to the coloring. In this case, if we let the 'outermost' (d - 1)-face (the one not containing the origin) 'balloon outwards', it could be all-red. Then the coloring $Col$ could satisfy Sperner's condition, and the point $(k -1 , ... k -1)$ would lie in the simplex waiting to be found. (We'd still have gap (++) to fill, though.)

Comment by Andy Drucker

2010-07-13T16:20:28Z

Thanks Scott M... Before trying to see if this approach could work, we'd need to understand why it wouldn't work in a different set of initial conditions: suppose instead that the coloring is a threshold function $C_0(x) =$ red, if $x_i > 1$, else $C_0(x) =$ blue. Then there is no sensitive point to find. Say the $d$ red vertices of our initial simplex are chosen from anywhere on the red side of the threshold. Connect the vertices as before. What useful condition fails in this setup, yet holds in the original setup?