# Minimize collision of bit strings

I'm sorry, if I got the wrong expressions, I'm gonna describe it:

I got bit-strings of n bits with k ones and want to minimize "collision" The collision count of two strings $a=(a_1,...,a_n), b=(b_1,...,b_n)$ is defined by $$Coll(a,b):=\sum_{i=1}^n a_i b_i$$ and $a,b$ are said to "collide", if $Coll(a,b)>0$. Of course this can be generalized to higher number of strings.

Now I'm looking for a "shift" $s$ (depending on $a$), that minimizes the shifted self-collision $$\sum_{i=1}^n a_{i+s}a_i$$ and (if possible) the $m$-fold shifted self-collision $$\sum_{i=1}^n\prod_{j=1}^m a_{i+js}$$ ($i+s>n$ may be replaced by $i^\prime\in\{1,...,n\}$ with $i^\prime\equiv i+s$ (mod n))

Now my questions are:

1. Is this solvable faster than $O(n²)$? (computing the collision count for a shift needs $O(n)$ and there are at most $n$ shifts
2. I'm coding my bit-strings by length of consecutive 0s between two 1s $(10011 \rightsquigarrow 200 )$. Does this help to compute the collision count without translating back to the bit-string?
3. Is there already any theory on that?
-
On 2.: Yes, it helps if the bit strings are sparse; you can just keep track of the numbers of zeros left in the current run in both strings, and when they reach $0$ simultaneously you have a collision. If they're not sparse, this will be inefficient compared to just ANDing them a word at a time and looking up the bit counts in a table. – joriki Aug 10 '12 at 13:12

For the first question: Your "shifted self collision" is the same as a circular autocorrelation, so it can be computed using Fourier transform, which is $O(n \log(n))$
 x=[1, 1, 0, 1, 0 ,0  ,0 ,0 ];