<p>There's the Minsky-Papert function, which is a depth-two formula, OR composed with AND, where the OR is of size $n^{1/3}$ and the AND is of size $n^{2/3}$. I.e., it's $OR_{n^{1/3}}\circ AND_{n^{2/3}}$. </p>

<p>Then there's the particular communication complexity problem studied in the papers you linked, which is now a function of 2 $n$-bit strings $x$ and $y$, where $x$ is given to Alice and $y$ to Bob. This function is $OR_{n^{1/3}}\circ AND_{n^{2/3}} \circ (x \vee y)$, maybe more clearly expressed as</p>

<blockquote>
  <p>$\bigvee _{i=1}^{n^{1/3}}\circ \bigwedge_{j=1}^{n^{2/3}} \circ (x_{ij} \vee y_{ij})$</p>
</blockquote>

<p>This is the communication problem for which both papers you linked to prove a sign rank lower bound. If you look at Corollary 1.1, they're talking about this function, not the Minsky-Papert DNF.</p>

<p>Note that any communication problem can be represented as a matrix, by having $x$ index rows and $y$ index columns. The papers prove lower bounds on the sign rank of this matrix for the above communication problem. (Rank and sign rank being measures that make sense for matrices.) What Minsky and Papert showed was a sign degree (or threshold degree) lower bound on the Minsky-Papert DNF. Degree (and sign degree) are measures of Boolean functions.</p>

CC BY-SA 3.0
2017-08-03T16:10:22.103Z
Thanks! I was reading the Bun-Thaler statement wrong! Its not a sign-rank lowerbound for MP but for this "communication version of MP". BTW I was curious to know if you think this is just a coincidence or do you think there is a reason for it that the degree and sign-degree are exponential for MP and sign-rank is also exponential for the communication version of MP. A priori was there an implication expected between these two seemingly different properties?
gradstudent
CC BY-SA 3.0
2017-08-03T21:08:42.737Z
There is an expectation that for most reasonable measures and good enough gadget $G$ in communication complexity, the communication measure of $f \circ G$ is lower bounded by the analogous query measure of $f$. This should hold generally for "analogous" measures in both models, like degree/rank, or sign-degree/sign-rank, approx-degree/approx-rank, randomized/randomized, deterministic/deterministic, etc. These results are called lifting theorems or simulation theorems. See [this](https://doi.org/10.1109/FOCS.2015.70) for more info.
Robin Kothari
CC BY-SA 3.0
2017-08-03T03:30:44.393Z
2017-08-03T03:30:44.393Z
Robin Kothari
<p>Apologies this might be a very trivial thing I am getting confused by!</p>

<ul>
<li>Firstly in corollary 1.1 (page 3) in this paper, <a href="https://eccc.weizmann.ac.il/report/2016/075/" rel="nofollow noreferrer">https://eccc.weizmann.ac.il/report/2016/075/</a> the authors claim that they have given a new proof of the apparently well-known fact that the Minsky-Pappert DNF has an exponentially high sign-rank. They claim that this was previously also proven in this paper by Razborov and Sherstov, <a href="http://people.cs.uchicago.edu/~razborov/files/sign.pdf" rel="nofollow noreferrer">http://people.cs.uchicago.edu/~razborov/files/sign.pdf</a>. </li>
</ul>

<p>But in the Razborov-Sherstov paper I am unable to locate any such claim or proof. 
What am I missing? Is this somehow implicit? </p>

<ul>
<li><p>The high sign-rank function that Razborov-Shertov display is in their theorem $1.1$ called the "Main Result" on page $2$. This is a depth $3$ $AC^0$ function and not a depth $2$ one like Minsky-Pappert is. </p></li>
<li><p>Also on page $2$ a few lines below the statement of Theorem $1.1$ Razborov-Sherstov seem to say that depth $1$ and $2$ $AC^0$ function can only have polynomial sign-rank. This if I am reading correctly implies that the Minsky-Pappert function does not have an exponentially large sign-rank since it is depth $2$ $AC^0$. What is going on? </p></li>
<li><p>If true, could anyone kindly link to any reference which gives a pedagogic exposition of the proof that the Minsky-Pappert function has a high sign-rank? </p></li>
</ul>

<hr>

<p>The Razborov-Sherstov paper does use the Minsky-Pappert function as a tool in their final proof on page $16$ whereby they use its pattern matrix to create another matrix which is a submatrix of high sign-rank sitting inside the pattern matrix of their hard function from the "Main Result" quoted above. Its not clear to me if this is somehow implicitly also proving a high sign-rank for the Minsky-Pappert function itself. Is it? </p>

<circuit-complexity><linear-algebra><linear-programming><circuit-families><circuit-depth>
About the sign-rank of the Minsky-Pappert function
gradstudent
# About the sign-rank of the Minsky-Pappert function

(Asked by: username_0 on 2017-08-02)

Apologies this might be a very trivial thing I am getting confused by!

* Firstly in corollary 1.1 (page 3) in this paper, <https://eccc.weizmann.ac.il/report/2016/075/> the authors claim that they have given a new proof of the apparently well-known fact that the Minsky-Pappert DNF has an exponentially high sign-rank. They claim that this was previously also proven in this paper by Razborov and Sherstov, <http://people.cs.uchicago.edu/~razborov/files/sign.pdf>.

But in the Razborov-Sherstov paper I am unable to locate any such claim or proof.
What am I missing? Is this somehow implicit?

* The high sign-rank function that Razborov-Shertov display is in their theorem $1.1$ called the "Main Result" on page $2$. This is a depth $3$ $AC^0$ function and not a depth $2$ one like Minsky-Pappert is.
* Also on page $2$ a few lines below the statement of Theorem $1.1$ Razborov-Sherstov seem to say that depth $1$ and $2$ $AC^0$ function can only have polynomial sign-rank. This if I am reading correctly implies that the Minsky-Pappert function does not have an exponentially large sign-rank since it is depth $2$ $AC^0$. What is going on?
* If true, could anyone kindly link to any reference which gives a pedagogic exposition of the proof that the Minsky-Pappert function has a high sign-rank?

---

The Razborov-Sherstov paper does use the Minsky-Pappert function as a tool in their final proof on page $16$ whereby they use its pattern matrix to create another matrix which is a submatrix of high sign-rank sitting inside the pattern matrix of their hard function from the "Main Result" quoted above. Its not clear to me if this is somehow implicitly also proving a high sign-rank for the Minsky-Pappert function itself. Is it?

**Tags:** circuit-complexity, linear-algebra, linear-programming, circuit-families, circuit-depth

---

## 1 answers

### Answer by username_1 on 2017-08-03. Score: 2

There's the Minsky-Papert function, which is a depth-two formula, OR composed with AND, where the OR is of size $n^{1/3}$ and the AND is of size $n^{2/3}$. I.e., it's $OR\_{n^{1/3}}\circ AND\_{n^{2/3}}$.

Then there's the particular communication complexity problem studied in the papers you linked, which is now a function of 2 $n$-bit strings $x$ and $y$, where $x$ is given to Alice and $y$ to Bob. This function is $OR\_{n^{1/3}}\circ AND\_{n^{2/3}} \circ (x \vee y)$, maybe more clearly expressed as

> $\bigvee \_{i=1}^{n^{1/3}}\circ \bigwedge\_{j=1}^{n^{2/3}} \circ (x\_{ij} \vee y\_{ij})$

This is the communication problem for which both papers you linked to prove a sign rank lower bound. If you look at Corollary 1.1, they're talking about this function, not the Minsky-Papert DNF.

Note that any communication problem can be represented as a matrix, by having $x$ index rows and $y$ index columns. The papers prove lower bounds on the sign rank of this matrix for the above communication problem. (Rank and sign rank being measures that make sense for matrices.) What Minsky and Papert showed was a sign degree (or threshold degree) lower bound on the Minsky-Papert DNF. Degree (and sign degree) are measures of Boolean functions.

> **Comments:**
> **username_0**: Thanks! I was reading the Bun-Thaler statement wrong! Its not a sign-rank lowerbound for MP but for this "communication version of MP". BTW I was curious to know if you think this is just a coincidence or do you think there is a reason for it that the degree and sign-degree are exponential for MP and sign-rank is also exponential for the communication version of MP. A priori was there an implication expected between these two seemingly different properties?  
> **username_1**: There is an expectation that for most reasonable measures and good enough gadget $G$ in communication complexity, the communication measure of $f \circ G$ is lower bounded by the analogous query measure of $f$. This should hold generally for "analogous" measures in both models, like degree/rank, or sign-degree/sign-rank, approx-degree/approx-rank, randomized/randomized, deterministic/deterministic, etc. These results are called lifting theorems or simulation theorems. See [this](https://doi.org/10.1109/FOCS.2015.70) for more info.  

---

