Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > FINE GRAINED COMPLEXITY:
Reports tagged with fine grained complexity:
TR23-014 | 16th February 2023
Tameem Choudhury, Karteek Sreenivasaiah

Depth-3 Circuit Lower Bounds for k-OV

Revisions: 3

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, ... more >>>




ISSN 1433-8092 | Imprint