# About the sign-rank of the Minsky-Pappert function

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

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?

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})$
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.
• 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 for more info. – Robin Kothari Aug 3 '17 at 21:08