Suppose that Alice and Bob communicate to compute a function $f:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$. Does the minimal degree of a real polynomial/rational representation of $f$ play a role for upper and/or lower bounds on the deterministic, non-deterministic, randomized or quantum communication complexity of computing $f$?

  • 1
    $\begingroup$ If you're working mod 2 I guess the answer is no: the inner product function provably has linear communication complexity but can be represented by a degree 2 polynomial. $\endgroup$ – Huck Bennett Jan 21 '15 at 19:46
  • $\begingroup$ @HuckBennett I do not see how you can represent $IP_n$ as a real degree $2$ polynomial. Over $\Bbb F_2$ this is clear. $\endgroup$ – 1.. Jan 22 '15 at 3:28
  • $\begingroup$ Yes, I agree. I thought it was worth noting that we can say something in the $\mathbb{F}_2$ case even though it doesn't answer your question. $\endgroup$ – Huck Bennett Jan 22 '15 at 3:45

The minimal degree of a real polynomial representing the parity function of $n$ variables is $n$. However, the deterministic communication complexity is at most $2$ bits.


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.