Revisions - MathOverflow

Return to Answer

deleted 1162 characters in body; deleted 96 characters in body

view source

edited Aug 25 2011 at 16:57

The following arose from joint work with Scott Aaronson. The first statement shows how one can do , and provides a converse reduction to get of the lattice problem back to the original boolean functions problem, and with the second is an improvement on Rubinstein's example for boolean functions and achieves sensitivity changed by a gap of $bs(f)=s(f)^2-s(f)$. certain factor.

This shows that $s(f) \leq s(C) \cdot \max_i b_i$.

For all $n$, there exists a boolean function $f$ on $2n^2-2n$ variables such that $bs(f)= s(f)^2-s(f)$.

Proof: For a fixed $n$, let $g(x)$ be a boolean function on $2n-2$ variables. We let $g(x)=1$ if there exists a $j$, $1 \leq j \leq n-1$, such that $x_{2j-1}=x_{2j}=1$ and $x_{2j+1},\ldots,x_{2j+n-2}=0$, where addition of coordinate indices is modulo $2n-2$. We have that $s^0(g)=1$ and $bs^0(g)=n-1$. We know that $s^0(g)=1$ because an input $x$ such that $g(x)=0$ and $g(x')=0$ where $x'$ is changed by one coordinate must contain either one 1 or three 1's, and both cases yield that $s(g,x)\leq 1$. Also, $bs^0(g)=n-1$ because one can take $n-1$ blocks of pairs ${x_{2j-1}, x_{2j}}$.

Let $f$ be a function on $2n^2-2n$ variables, defined by taking the exclusive or of $n$ copies of $g$. Then $bs^0(f) = n(n-1)$ and $s^0(f) = n$ since the 0-sensitivity is additive over the rows. Furthermore $bs^1(f)=2n-2 \leq bs^0(f)$ so $bs(f)=n(n-1)$. Also, $s^1(f)=n$ since there is at most one row $x$ such that $g(x)=1$ in the maximal input and $n$ coordinates can be changed in that row. Therefore, $s(f)=n$ and $bs(f) = s(f)^2-s(f)$.

added 1042 characters in body; deleted 46 characters in body; deleted 4 characters in body; deleted 3 characters in body; added 2 characters in body

view source

edited Jul 25 2011 at 15:37

Meena Boppana
71●1●3

UPDATE: The converse reduction allows us to translate Kenyon and Kutin's bound for $k$-block sensitivity into a polynomial lower bound on the sensitivity of the lattice in terms of $l$, where $l$ is the minimum number such that there is a blue point within $l$ units of the origin on each axis. Kenyon and Kutin's result is that there is at most a degree $k$ gap between $s(f)$ and $bs_k(f)$ ($k$-block sensitivity is block sensitivity where blocks are restricted to at most length $k$), so $bs_k(f) \leq c_k s(f)^k$, where $c_k < \frac{e}{(k-1)!}$. Take any lattice with $d$ dimensions and sensitivity $s$. Consider the finite lattice formed by cutting off each axis after the first blue point and apply the reduction below, so the maximum axis length is $l$. Then there exists a boolean function $f$ with $bs_l(f) \geq d$, since all blocks have length at most $l$, and $s(f) \leq ls$. Then $d \leq bs_l(f) \leq c_l(ls)^l$, and $s \geq \frac{1}{l} (\frac{d}{c_l})^{\frac{1}{l}}$.

The following arose from joint work with Scott Aaronson. The first statement shows how one can do a converse reduction to get back to the original boolean functions problem, and the second is an improvement on Rubinstein's example for boolean functions and achieves a gap of bs(f)=s(f)^2-s(f). $bs(f)=s(f)^2-s(f)$.

added 4 characters in body; deleted 4 characters in body

view source

edited Jul 15 2011 at 19:16

Meena Boppana
71●1●3

For a 2-coloring $C$ of a $d$-dimensional lattice of size $|S_1| \times |S_2| \ldots \times |S_d|$ such that the only axial blue points are $(0,\ldots,|S_i|,\ldots,0)$, where $|S_i|$ is the $i$th coordinate, there exists a boolean function with $bs(f) \geq d$ and $s(f) \leq \max_i{|S_i|} \cdot s(C)$.

Proof: We define a function $f$ on $n=|S_1|+|S_2|+\ldots+|S_d|$ bits as follows. Divide the bits into blocks $b_1, b_2, \ldots, b_n$, where $|b_i|=|S_i|$. For an input $y=(y_1,y_2,\ldots,y_n)$, let the number of 1's in set $b_i$ be $z_i$. Let $y$ correspond to the point $(z_1,z_2,\ldots,z_d)$, so $f(y)=0$ if $(z_1,z_2,\ldots,z_d)$ is red and $f(y)=1$ if it is blue. Each of the blocks $b_i$, $1 \leq i \leq d$, is sensitive on the $n$-bit input $(0,0,\ldots,0)$. This is because flipping the bits in block $b_i$ corresponds to the point $(0,\ldots,|S_i|,\ldots,0)$ where $|S_i|$ is the $i$th coordinate, which is blue, and so $f(y^{b_i})=1$ ($y$ with bits $b_i$ flipped). Thus $bs(f) \geq d$. Furthermore, moving one coordinate along the $i$th axis on the lattice corresponds to changing one of the bits in $b_i$ of the corresponding input. Therefore, for any point $x=(x_1,x_2,\ldots,x_n)$ where the set of coordinates $X \subseteq {1,\ldots,d}$ are sensitive, $|X| \leq s(C)$ and so the sensitivity of $f$ on the corresponding input is at most $\sum_{i \in X} b_i \leq s(C) \cdot \max_i b_i$. This shows that $s(f) \leq s(C) \cdot \max_i b_i$.

For all $n$, there exists a boolean function $f$ on $2n^2-2n$ variables such that $bs(f)= s(f)^2-s(f)$.

added 30 characters in body

view source

edited Jul 15 2011 at 19:10

Meena Boppana
71●1●3

Proof:

We define a function $f$ on $n=|S_1|+|S_2|+\ldots+|S_d|$ bits as follows. Divide the bits into blocks $b_1, b_2, \ldots, b_n$, where $|b_i|=|S_i|$. For an input $y=(y_1,y_2,\ldots,y_n)$, let the number of 1's in set $b_i$ be $z_i$. Let $y$ correspond to the point $(z_1,z_2,\ldots,z_d)$, so $f(y)=0$ if $(z_1,z_2,\ldots,z_d)$ is red and $f(y)=1$ if it is blue. Each of the blocks $b_i$, $1 \leq i \leq d$, is sensitive on the $n$-bit input $(0,0,\ldots,0)$. This is because flipping the bits in block $b_i$ corresponds to the point $(0,\ldots,|S_i|,\ldots,0)$ where $|S_i|$ is the $i$th coordinate, which is blue, and so $f(y^{b_i})=1$. f(y^{b_i})=1$ ($y$ with bits $b_i$ flipped). Thus $bs(f) \geq d$. Furthermore, moving one coordinate along the $i$th axis on the lattice corresponds to changing one of the bits in $b_i$ of the corresponding input. Therefore, for any point $x=(x_1,x_2,\ldots,x_n)$ where the set of coordinates $X \subseteq {1,\ldots,d}$ are sensitive, $|X| \leq s(C)$ and so the sensitivity of $f$ on the corresponding input is at most $\sum_{i \in X} b_i \leq s(C) \cdot \max_i b_i$. This shows that $s(f) \leq s(C) \cdot \max_i b_i$.

For all $n$, there exists a boolean function $f$ on $2n^2-2n$ variables such that $bs(f)= s(f)^2-s(f)$.

view source

answered Jul 15 2011 at 19:04

Meena Boppana
71●1●3

Proof:

We define a function $f$ on $n=|S_1|+|S_2|+\ldots+|S_d|$ bits as follows. Divide the bits into blocks $b_1, b_2, \ldots, b_n$, where $|b_i|=|S_i|$. For an input $y=(y_1,y_2,\ldots,y_n)$, let the number of 1's in set $b_i$ be $z_i$. Let $y$ correspond to the point $(z_1,z_2,\ldots,z_d)$, so $f(y)=0$ if $(z_1,z_2,\ldots,z_d)$ is red and $f(y)=1$ if it is blue. Each of the blocks $b_i$, $1 \leq i \leq d$, is sensitive on the $n$-bit input $(0,0,\ldots,0)$. This is because flipping the bits in block $b_i$ corresponds to the point $(0,\ldots,|S_i|,\ldots,0)$ where $|S_i|$ is the $i$th coordinate, which is blue, and so $f(y^{b_i})=1$. Thus $bs(f) \geq d$. Furthermore, moving one coordinate along the $i$th axis on the lattice corresponds to changing one of the bits in $b_i$ of the corresponding input. Therefore, for any point $x=(x_1,x_2,\ldots,x_n)$ where the set of coordinates $X \subseteq {1,\ldots,d}$ are sensitive, $|X| \leq s(C)$ and so the sensitivity of $f$ on the corresponding input is at most $\sum_{i \in X} b_i \leq s(C) \cdot \max_i b_i$. This shows that $s(f) \leq s(C) \cdot \max_i b_i$.

For all $n$, there exists a boolean function $f$ on $2n^2-2n$ variables such that $bs(f)= s(f)^2-s(f)$.