The 2-Orthogonal Vectors (2-OV) problem is the following: given two tuples $A$ and $B$ of $n$ Boolean vectors, each of dimension $d$, decide if there exist vectors $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. One of the major conjectures in fine-grained complexity is that $k$-OV cannot be solved by a randomised algorithm in $n^{k-\epsilon}poly(d)$ time for any constant $\epsilon > 0$.
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 \emph{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, and for each fixed $k>2$, this is the first unconditional $\Omega(n^k)$ lower bound against $k$-OV for a computation model that can compute it in size $O(n^k)$. Our results partially resolve a conjecture by Kane and Williams[16] (page12, 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 $\ANDORAND$ 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)

The 2-Orthogonal Vectors (2-OV) problem is the following: given two tuples $A$ and $B$ of $n$ Boolean vectors, each of dimension $d$, decide if there exist vectors $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. One of the major conjectures in fine-grained complexity is that $k$-OV cannot be solved by a randomised algorithm in $n^{k-\epsilon}poly(d)$ time for any constant $\epsilon > 0$.
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 \emph{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, and for each fixed $k>2$, this is the first unconditional $\Omega(n^k)$ lower bound against $k$-OV for a computation model that can compute it in size $O(n^k)$. Our results partially resolve a conjecture by Kane and Williams[16] (page12, 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 $\ANDORAND$ 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)

The 2-Orthogonal Vectors (2-OV) problem is the following: given two tuples $A$ and $B$ of $n$ Boolean vectors, each of dimension $d$, decide if there exist vectors $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. One of the major conjectures in fine-grained complexity is that $k$-OV cannot be solved by a randomised algorithm in $n^{k-\epsilon}poly(d)$ time for any constant $\epsilon > 0$.
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 \emph{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, and for each fixed $k>2$, this is the first unconditional $\Omega(n^k)$ lower bound against $k$-OV for a computation model that can compute it in size $O(n^k)$. Our results partially resolve a conjecture by Kane and Williams \cite{kane2019orthogonal} (page12, 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 $\ANDORAND$ 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.

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)