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$ Jan 21, 2015 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$
    – Turbo
    Jan 22, 2015 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$ Jan 22, 2015 at 3:45

1 Answer 1


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 and acknowledge you have read our privacy policy.

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