Lesson 4

In the orthogonal vectors problem two sets of \(d\)-dimensional binary vectors of size \(n\) are given: \(A,B \subseteq \{0,1\}^{d}\), \(|A|=|B|=n\). It is required to check whether there exist two vectors \(a \in A, b \in B\) whose dot product is zero: \(\sum_{i=1}^{d}a_{i}b_{i}=0\). The naive algorithm for this problem has running time \(O(dn^{2})\). It turns out that speeding up such exhaustive search is a major open problem.

Theorem (Williams, 2005). If for the orthogonal vectors problem there is an algorithm with running time \(O(n^{2-\varepsilon}\operatorname{poly}(d))\), then for the satisfiability problem there is an algorithm with running time \(O^{*}((2-\delta(\varepsilon))^{n})\).

Proof. Let \(F\) be a formula over \(n\) variables and \(m\) clauses. We split the variables into two parts of sizes \(n_{1}=\lfloor n/2\rfloor\) and \(n_{2}=\lceil n/2\rceil\). The set \(A \subseteq \{0,1\}^{m}\) will consist of \(2^{n_1}\) vectors, one vector for each assignment \(u\) of the first part: \(a_{u}[i]=0\) if and only if assignment \(u\) satisfies the \(i\)-th clause of the formula. The set \(B\) consists similarly of \(2^{n_2}\) vectors, one for each assignment of the second part. It is easy to see that sets \(A\) and \(B\) have an orthogonal pair of vectors if and only if the formula \(F\) is satisfiable.◼