Revision #3 Authors: Tameem Choudhury, Karteek Sreenivasaiah

Accepted on: 30th September 2023 08:23

Downloads: 176

Keywords:

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)

Revision #2 Authors: Tameem Choudhury, Karteek Sreenivasaiah

Accepted on: 30th September 2023 08:21

Downloads: 133

Keywords:

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)

Revision #1 Authors: Tameem Choudhury, Karteek Sreenivasaiah

Accepted on: 30th September 2023 08:18

Downloads: 130

Keywords:

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.

TR23-014 Authors: Tameem Choudhury, Karteek Sreenivasaiah

Publication: 20th February 2023 08:52

Downloads: 446

Keywords:

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)