The 2-Orthogonal Vectors (2-OV) problem is the following: given two tuples $A$ and $B$ of $n$ vectors each of dimension $d$, decide if there exists a vector $u\in A$, and $v\in B$ such that $u$ and $v$ are orthogonal. This problem, and its generalization $k$-OV defined analogously for $k$ tuples, are central problems in the area of fine-grained complexity. Informally speaking, one of the major conjectures in fine-grained complexity is that deciding $k$-OV requires time $\Omega(n^k d)$. In this paper, we are interested in unconditional lower bounds against $k$-OV, but for weaker models of computation than the general Turing Machine. In particular, we are interested in circuit lower bounds to computing $k$-OV by Boolean circuit families of depth 3 of the form OR-AND-OR, or equivalently, a disjunction of CNFs. We show that for all $k\leq d$, any disjunction of $t$-CNFs computing $k$-OV requires size $\Omega((n/t)^k)$. In particular, when $k$ is a constant, any disjunction of $k$-CNFs computing $k$-OV needs to use $\Omega(n^k)$ CNFs. This matches the brute-force construction. Thus for each fixed $k\ge 2$, the complexity of computing $k$-OV as a disjunction of $k$-CNFs is $\Theta(n^k)$. Our results partially resolve a conjecture by Kane and Williams [16] (page 12, conjecture 10) about depth-3 $AC^0$ circuits computing 2-OV. As a secondary result, we show an exponential lower bound on the size of AND-OR-AND circuits computing 2-OV when $d$ is very large. Since 2-OV reduces to $k$-OV by projections trivially, this lower bound works against $k$-OV as well.

Kane and Williams[16]: The orthogonal vectors conjecture for branching programs and formulas (ITCS 2019)