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$?
$\begingroup$
$\endgroup$
-
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$ – T.... 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
$\begingroup$
$\endgroup$
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.
