Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > TAMEEM CHOUDHURY:
All reports by Author Tameem Choudhury:

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