<p>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.</p>

CC BY-SA 3.0
2015-01-26T07:13:44.383Z
2015-01-26T10:01:37.530Z
2015-01-26T10:01:37.530Z
Turbo
<p>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$?</p>

CC BY-SA 3.0
2015-01-21T19:46:06.950Z
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.
Huck Bennett
CC BY-SA 3.0
2015-01-22T03:28:42.203Z
@HuckBennett I do not see how you can represent $IP_n$ as a real degree $2$ polynomial. Over $\Bbb F_2$ this is clear.
Turbo
CC BY-SA 3.0
2015-01-22T03:45:20.307Z
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.
Huck Bennett
<boolean-functions><communication-complexity>
Real representation versus communication complexity
Turbo
# Real representation versus communication complexity

(Asked by: username_0 on 2015-01-21)

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$?

**Tags:** boolean-functions, communication-complexity

> **Comments:**
> **username_1**: 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.  
> **username_0**: @HuckBennett I do not see how you can represent $IP_n$ as a real degree $2$ polynomial. Over $\Bbb F_2$ this is clear.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_0 on 2015-01-26. Score: 1 | Accepted answer

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.


---

