Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR23-014 | 30th September 2023 08:23

Depth-3 Circuit Lower Bounds for k-OV

RSS-Feed




Revision #3
Authors: Tameem Choudhury, Karteek Sreenivasaiah
Accepted on: 30th September 2023 08:23
Downloads: 118
Keywords: 


Abstract:

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 to TR23-014 | 30th September 2023 08:21

Depth-3 Circuit Lower Bounds for k-OV





Revision #2
Authors: Tameem Choudhury, Karteek Sreenivasaiah
Accepted on: 30th September 2023 08:21
Downloads: 94
Keywords: 


Abstract:

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 to TR23-014 | 30th September 2023 08:18

Depth-3 Circuit Lower Bounds for k-OV





Revision #1
Authors: Tameem Choudhury, Karteek Sreenivasaiah
Accepted on: 30th September 2023 08:18
Downloads: 85
Keywords: 


Abstract:

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.


Paper:

TR23-014 | 16th February 2023 19:52

Depth-3 Circuit Lower Bounds for k-OV





TR23-014
Authors: Tameem Choudhury, Karteek Sreenivasaiah
Publication: 20th February 2023 08:52
Downloads: 368
Keywords: 


Abstract:

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)



ISSN 1433-8092 | Imprint