3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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