Lemma: Let $m=c n$ for some constant $0 < c \leq 0.01$, and $D$ a finite set of size $|D|\geq 3$. Suppose that a sensitive function $f:D^n\to\{0,1\}$ can be computed by a nondeterministic semantic read-once $D$-way branching program of size $s$. Suppose that $\ell$ satisfies \[ \ell\leq \frac{(1/2-c)^m|f^{-1}(1)|}{2s|D|^{n-m}}\,. \] Then $f^{-1}(1)$ contains an $m$-by-$4m$ rectangle with both legs of size $\ell$.Proof: Let $f:D^n\to\{0,1\}$ be our function, and $S=f^{-1}(1)$ be the set of its accepted inputs. Take a weakly read-once nondeterministic branching program for $f$. Since every two accepted inputs of $f$ must differ in at least two positions, every accepting $s$-$t$ path must test all $n$ variables. (This is the only place where we use the sensitivity of $f$; the authors do not use this property.) For every input $x\in S$, one $s$-$t$ path $p_x$ accepting $x$, and stop this path at a node $v_x$ after exactly $n/2$ variables are read. Let $v$ be the most common among the nodes $v_x$, and let $S_1=\{x\in A\colon v_x=v\}$ be the set of inputs whose paths were stopped at $v$. Then clearly $|S_1|\geq |S|/s$.
We now want to pick two disjoint sets $X$ and $Y$ of variables of sizes $|X|=m$ and $|Y|=4m$, and a subset $S_2\subseteq S_1$ of inputs with the property that the accepting paths of these inputs not only go through node $v$, but every variable in $X$ is read before node $v$, and every variable in $Y$ is read after $v$. We will first pick $X$ greedily.
For each input vector $x\in S_1$, at least $n/2$ of the $n$ variables are read before the node $v$. Thus there is some variable which is read for at least half of the inputs $x\in S_1$. Continue greedily until we pick $m$ variables in $X$, by always choosing the most popular variable which is read before $v$. By averaging, after $i$ variables are chosen, $i\leq m = cn$, the fraction of inputs that remain is at least \[ \frac{n/2-i}{n-i}\geq \frac{n/2-cn}{n-cn}\geq \frac{n/2-cn}{n} = \frac{1}{2} -c\,. \] Thus, \[ |S_2|\geq (1/2-c)^m|S_1|\geq (1/2-c)^m|S|/s\,. \] By the assumption of the Lemma, we have that $\ell$ satisfies \[ \ell\leq \frac{(1/2-c)^m|S|}{2s|D|^{n-m}}\ \ \ \mbox{ or equivalently }\ \ \ (1/2-c)^m|S|\geq 2\ell s |D|^{n-m} \,. \] This yields \[ |S_2|\geq 2\ell |D|^{n-m}\,. \] That is, the average number of extension of a vector $w\in D^{n-|X|}$ in $S_2$ is at least $2\ell$. We want to prune $S_2$ to a subset $S_3\subseteq S_2$ so that the projection onto $[n]=X$ of every vector of $S_3$ has at least $\ell$ extensions. We obtain $S_3$ by just removing all vectors $(\ast,w)$ from $S_2$ such that $w$ has less than $\ell$ extensions. Since we delete at most $r|D|^{n-m}$ vectors from $S_2$, and $|S_2|\geq 2\ell |D|^{n-m}$, it follows that \[ |S_3|\geq \ell|D|^{n-m}\,. \] We next choose the set $Y$ of $|Y|=4m$ variables in the same greedy fashion, and let $S_4$ denote the set of all vectors in $S_3$ such that all variables in $Y$ are read after reaching the node $v$. Again, by averaging, \[ |S_4|\geq (1/2-4c)^{4m}|S_3|\geq (1/2-4c)^{4m}\ell|D|^{n-m}\,. \] By the choice of $S_4$, every vector $x\in S_4$ has the following three properties:
Claim 1: $R_w$ is a rectangle.Proof: Take any vectors $a,a'\in A_w$ and $b,b'\in B_w$. Our goal is to show that then also vector $(a,w,b')$ must belong to $R_w$. The accepting paths for both vectors $(a,w,b)$ and $(a',w,b')$ go though the same node $v$. The $X$-bits of both vectors $a$ and $a'$ are read before $v$, and the $Y$-bits of both vectors $b$ and $b'$ are read after $v$. So, let $w_1$ be the part of the common vector $w$ read on input $(a,w,b)$ before $v$, and $w_2'$ the part of $w$ read on input $(a',w,b')$ after $v$. The combined input $(a,w,b')$ will follow the same path as $(a,w_1)$ until it reaches $v$. Since both $w_1$ and $w_2'$ are consistent with $w$ (are parts of the same vector $w$), the path then follows the path of $(w_2',b')$. Thus, the combined vector $(a,w,b')$ belongs to $R_w$, as desired. $\Box$
We now show that the size of the left leg of the rectangle $R_w$ must be at least $\ell$.
Claim 2: If $R_w\neq \emptyset$ then $|A_w|\geq r$.Proof: Since $R_w\neq \emptyset$, there is a vector $x=(a,w,b)\in R_w$. Since this vector belongs to $S_4$, the property (3) of $S_4$ above implies that the set $A_{w,b}:=\{a'\in D^X\colon (a',w,b)\in S_4\}$ has at least $\ell$ vectors. By the definition of $R_w$, all vectors of $A_{w,b}\times \{w\}\times{b}$ lie in $R_w$. Claim 1 actually shows that $A_{w,b}\times \{w\}\times b'\subseteq S_4$ holds for all vectors $b'\in B_w$. So, by the definition of $R_w$, the entire set $A_{w,b}\times \{w\}\times B$ must also lie in $R_w$. Hence, $A_{w,b}\subseteq A_w$, and $|A_w|\geq \ell$ follows. $\Box$
Let now $\ell_{avg}$ denote the average size of the right leg of a rectangle over all rectangles $R_w\subseteq S_4$. Then, since $|X|=m$ and $|Y|=4m$, we have \[ \ell_{avg}\geq \frac{|S_4|}{|D|^{n-|Y|}} \geq \frac{(1/2-4c)^{4m}\ell|D|^{n-m}}{|D|^{n-4m}} =\ell\cdot |D|^{3m}(1/2-4c)^{4m} =\ell\cdot t^m\qquad \mbox{ where }\qquad t=(1-8c)^{4}\cdot \frac{|D|^3}{2^4}\,. \] For $|D|\geq 3$ and $c\leq 0.01$, $t\geq (1-0.08)^4(27/16)$ is at least $1.2089>1$. Thus, $\ell_{avg}\geq r$, implying that there exists a vector $w$ such that $R_w=A_w\times \{w\}\times B_w$ is an $m$-by-$4m$ lying entirely in $f^{-1}(1)$, whose left and right legs have desired sizes $|A_w|,|B_w|\geq r$. This completes the proof of the lemma. $\Box$
Go back to the comment.