2
$\begingroup$

The Eulidean distance function $d$ of $x$ and $y$ is given by:

$ d(x,y)=\sqrt{x^2-y^2} $

Let us assume that $x$ and $y$ are fixed-point numbers, or $x,y$ are element of some subfield $f_n$ of $F_p$. We could even assume that $x,y$ have precision $n$ decimal digits. Any facilitating representations of rational or real values $x,y$ that carries "enough" information is good. $x,y$ could also be assumed to be only positive.

Can the Euclidean distance function be computed using only XOR's? If this cannot be achieved, what other boolean functions would be needed?

$\endgroup$
  • $\begingroup$ Intuition tell me it's not possible with only Boolean functions, simply from the fact that a bit-wise operation treats a number as a vector of bits. With that in mind, it's impossible to have a function as simple as successors, so exponentiation is out of the way. What's your take on this? $\endgroup$ – ZeroUltimax Aug 11 '14 at 2:33
  • $\begingroup$ You'd certainly have to restrict yourself to finite precision in the result, otherwise you have no chance for any computation. $\endgroup$ – Raphael Aug 11 '14 at 7:07
5
$\begingroup$

No. It's not possible. Any function that can be computed using just XOR's is affine over $GF(2)$. However, the Euclidean distance is not affine over $GF(2)$, so there is no hope of representing it with just XOR's.

Recall that $GF(2)$ denotes the finite field with two elements; you might also see it indicated by $\mathbb{F}_2$, and it is the field $(\{0,1\},\oplus,\times)$, where $\oplus$ represents the XOR operation (i.e., addition modulo two) and $\times$ represents the AND operation (i.e., multiplication modulo two).

Recall that a function $f$ is linear if it can be expressed as a linear map, i.e., $f(x+y)=f(x)+f(y)$ holds. More specifically, suppose we have a function $f:GF(2)^n \to GF(2)^m$ that maps from a vector space over $GF(2)$ to a vector space over $GF(2)$. Then $f$ is linear if $f(x \oplus y)=f(x) \oplus f(y)$ for all $x,y$, where $\oplus$ denotes element-wise XOR. Equivalently, $f$ is linear if there is a $m\times n$ matrix $M$ whose elements are in $GF(2)$ (i.e., all of whose elements are 0 or 1), such that $f(x) = Mx$.

A function $g$ is affine if it is of the form $g(x)=f(x)+c$, where $f$ is linear and $c$ is an arbitrary constant. In our case, $g$ is affine if there is a $m\times n$ matrix $M$ whose elements are in $GF(2)$ (i.e., all of whose elements are 0 or 1) and a constant $c \in GF(2)^n$, such that $g(x) = Mx+c$. See, e.g., this Wikipedia article for more.

The XOR operation is linear. Also, because the set of $GF(2)$-affine transformations is closed under composition (this follows because $(\{0,1\},\oplus)$ is a group), it is easy to see that any circuit built solely out of XOR's must be $GF(2)$-affine. (Why affine, rather than linear? Because a circuit can contain constants: it can take an input and XOR it with the constant 1. That makes it affine, rather than linear.)

Now it is easy to verify that the Euclidean distance is not $GF(2)$-affine, just by looking at a few values: e.g., you can look at $d(0,0)$, $d(0,1)$, $d(1,0)$, $d(1,1)$. If $d$ were affine, we would have the relationship

$$d(0,0) \oplus d(0,1) \oplus d(1,0) \oplus d(1,1) = 0.$$

Since this relationship does not in fact hold, $d$ is not $GF(2)$-affine.

And since $d$ is not an affine function of its inputs, this means it cannot be expressed using only XORs.

Certainly NAND gates would be sufficient, as they are universal. It could also be expressed using just XORs and ANDs, as those two are also universal. There are many other options.

$\endgroup$
  • $\begingroup$ Ah, I see; "of course" I knew this stuff but we call(ed) it $\mathbb{F}_2$, so it was indeed a notational issue. Thanks for expanding the answer, though, it's definitely self-contained now and should be accessible enough! $\endgroup$ – Raphael Aug 15 '14 at 15:37

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.