Draft:Orthogonal vectors problem

Problem Definition

The input to the Orthogonal Vectors problem are two sets of ${\displaystyle n}$ binary vectors, each of some dimension ${\displaystyle d}$:

${\displaystyle A,B\subseteq \{0,1\}^{d},\quad |A|=|B|=n}$.

The Orthogonal Vectors problem asks whether there exists at least one pair of orthogonal vectors, one from each set. More formally, OV returns TRUE if and only if there exists some vectors ${\displaystyle a\in A}$ and ${\displaystyle b\in B}$ such that:

${\displaystyle a\cdot b=\sum _{i=1}^{d}a_{i}b_{i}=0.}$

Example

Consider the following input sets:

${\displaystyle A=\{(1,0,1),(1,1,0)\},\quad B=\{(0,1,0),(1,1,1)\}}$.

For all vectors ${\displaystyle a\in A}$ and ${\displaystyle b\in B}$, we check if the pair of vectors ${\displaystyle a}$ and ${\displaystyle b}$ are orthogonal by evaluating their dot products ${\displaystyle a\cdot b}$:

• ${\displaystyle (1,0,1)\cdot (0,1,0)=\mathbf {0} }$
• ${\displaystyle (1,0,1)\cdot (1,1,1)=2}$
• ${\displaystyle (1,1,0)\cdot (0,1,0)=1}$
• ${\displaystyle (1,1,0)\cdot (1,1,1)=2}$

There exists one pair of orthogonal vectors, so the solution for these particular input sets is TRUE.

Fine-Grained Complexity and SETH

The Orthogonal Vectors problem has an important role in fine-grained complexity, particularly in relation to the Strong Exponential Time Hypothesis (SETH). Specifically, if Orthogonal Vectors on ${\displaystyle n}$ vectors can be solved in time ${\displaystyle O(n^{2-\epsilon })}$ for some constant ${\displaystyle \epsilon >0}$, then SAT could be solved in time ${\displaystyle 2^{(1-\delta )n}}$ for some ${\displaystyle \delta >0}$, contradicting SETH. As a result, OV serves as a source of hardness in fine-grained complexity. Instead of reducing a problem directly from SAT, many problems are shown to be hard by reducing from OV, which allows establishing lower bounds for many different problems under the assumption that SETH holds.

References