most recent 30 from http://mathoverflow.net 2013-05-24T00:44:22Z http://mathoverflow.net/feeds/user/16122 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/31482/the-sensitivity-of-2-colorings-of-the-d-dimensional-integer-lattice/70455#70455 Meena Boppana 2011-07-15T19:04:54Z 2011-08-25T16:57:35Z

<p>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 &lt; \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}}$.</p> <p>The following arose from joint work with Scott Aaronson, and provides a reduction of the lattice problem back to the original boolean functions problem, with the sensitivity changed by a certain factor.</p> <p>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)$. </p> <p>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$.</p>

http://mathoverflow.net/questions/31482/the-sensitivity-of-2-colorings-of-the-d-dimensional-integer-lattice/69831#69831 Meena Boppana 2011-07-08T21:15:12Z 2011-07-15T18:53:25Z

<p>The following is a generalization of domotorp's construction for $r_6=2$, which constructs a coloring on a $d$-dimensional lattice with $d=2s^2-s$.</p> <p>We can construct the following $(2s-1)s$-dimensional certificates which we will color blue, each divided into $s$ groups of $2s-1$ coordinates each. We define the $s(2s-1)$ coordinates $x_{{i,j}}$, where $1 \leq i \leq s$ and $1 \leq j \leq 2s-1$. The certificate $S_{{i,j}}$ consists of those vectors for which $x_{{i,j}}=3$ and $x_{{i,j+1}},\ldots, x_{{i,j+s-1}}=0$, where addition of coordinates is modulo $2s-1$, allowing for wraparound. </p> <p>We can now define a coloring where a point is colored blue if it is in a certificate $S_{{i,j}}$ and red otherwise. This satisfies the non-triviality condition because for any coordinate $x_{{i,j}}$, the certificate $S_{{i,j}}$ contains the point along the coordinate axis in that direction with $x_{{i,j}}=3$ and $x_{{a,b}}=0$ for all $(a,b)\neq(0,0)$. </p> <p>The blue to red sensitivity of this coloring, which is the maximum sensitivity of blue points, is $s$ because for any point in a certificate $S_{{i,j}}$, only changing one of the $s$ coordinates $x_{{i,j}}, x_{{i,j+1}},\ldots, x_{{i,j+s-1}}$ yields an adjacent red point. Furthermore, the red to blue sensitivity is also $s$. For a point $p$ and a certificate $S_{{i,j}}$, if $p$ is adjacent to $S_{{i,j}}$ then $2 \leq x_{{i,j}} \leq 4$ and $-1 \leq x_{{i,j+1}},\ldots, x_{{i,j+s-1}} \leq 1$. So for a point $p$ and a fixed index $a$, $1 \leq a \leq s$, $p$ can be adjacent to at most one certificate of the form $S_{{a,j}}$ because two of these strings of $s$ coordinates cannot fit in $2s-1$ coordinates. Ranging over all $a$, a point can be adjacent to at most $s$ certificates, and so the red to blue sensitivity is at most $s$. </p> <p>Therefore the coloring has sensitivity $s$, and $d=(2s-1)s=2s^2-s$. </p>

http://mathoverflow.net/questions/31482/the-sensitivity-of-2-colorings-of-the-d-dimensional-integer-lattice/69831#69831 Meena Boppana 2011-07-21T20:50:12Z 2011-07-21T20:50:12Z

Nice! Last year you said that you have an argument for why with $d$ affine subspaces, the maximum dimension is $d=2s^2-s$. Would you mind explaining that? I'm interested now that I have a construction with affine subspaces satisfying the exact bound.