Thursday, March 4, 2010

The power of coding

The problem:
You have a bit vector $\langle a,b \rangle$, and I have another bit vector $\langle c,d \rangle$. We want to compute the scalar product of the two. Typically, we would need at least two multiplications and one addition ($\ell$ multiplications and $\ell-1$ additions for bit vectors of length $\ell$).
Using a certain algebraic property of some algebraic objects, we can do it using two additions and one multiplication ($2(\ell-1)$ additions and one multiplication).
We have reduced the number of computations. In cryptography, using homomorphic cryptsystems, multiplications is a big problem. So having reduced that to only one multiplication is big gain. Note also that you just add your vector locally and send me the result, so even less communication overhead.
I have got correctly working examples for vectors up to 6 items till now. I am working on increasing that number and getting to know the upper limit or any other limitations. So far it works for vectors over $\mathbb{R}$ not just bit vectors.

No comments: