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$
3
-
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 BennettJan 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$– TurboJan 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$– Huck BennettJan 22, 2015 at 3:45
Add a comment
|
1 Answer
$\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.