3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – gradstudent Aug 3 '17 at 16:10
  • 1
    $\begingroup$ 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. $\endgroup$ – Robin Kothari Aug 3 '17 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.