# Randomized and Deterministic Communication Complexity of a function

I have a problem I'm trying to answer for my homework. The question is:

Let $p$ be a prime number and let $GF(p)$ denote the finite field of size $p$. Suppose that A has input $x∈GF(p)$ encoded with $⌈log2p⌉$ bits and B has input $y∈GF(p)$ encoded with $⌈log2p⌉$ bits. Let $f:GF(p)×GF(p)→\{0,1\}$ be the function defined as $$f(x,y)= \begin{cases} 0& \text{if}& x+y+xy=0\\ 1& \text{if}& x+y+xy≠0 \end{cases}$$ for all $x,y∈GF(p)$. Show that the randomized communication complexity of $f$ is $O(log\text{ } log\text{ } p)$ bits. Can you prove a lower bound on the deterministic communication complexity of $f$?

I've been thinking about using a random element $r∈GF(p)$ and make A calculate $f$ using $x$ and $r$ and sending the answer $r$ to B, but this doesn't seem to work as there are no general trend using such an protocol. For example that when A and B get the same answer, the function is $0$ or if they get different answers, the function is $1$.

Anyone have any idea how this protocol can look like? For example what kind of random input should be used?

Hint: The condition $x + y + xy = 0$ is equivalent to the condition $1 + x + y + xy = 1$, i.e. $(1 + x)(1 + y) = 1$, or in other words, $$(1+x)^{-1} = 1+y.$$