  The orthogonality dimension of a graph $G$ over $\mathbb{R}$ is the smallest
integer $k$ for which one can assign a nonzero $k$-dimensional real vector to
each vertex of $G$, such that every two adjacent vertices receive orthogonal
vectors. We prove that for every sufficiently large integer $k$, it is
$\mathsf{NP}$-hard to decide whether the orthogonality dimension of a given
graph over $\mathbb{R}$ is at most $k$ or at least $2^{(1-o(1)) \cdot k/2}$. We
further prove such hardness results for the orthogonality dimension over finite
fields as well as for the closely related minrank parameter, which is motivated
by the index coding problem in information theory. This in particular implies
that it is $\mathsf{NP}$-hard to approximate these graph quantities to within
any constant factor. Previously, the hardness of approximation was known to
hold either assuming certain variants of the Unique Games Conjecture or for
approximation factors smaller than $3/2$. The proofs involve the concept of
line digraphs and bounds on their orthogonality dimension and on the minrank of
their complement.
