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?