  A $t$-dimensional orthogonal representation of a hypergraph is an assignment
of nonzero vectors in $\mathbb{R}^t$ to its vertices, such that every hyperedge
contains two vertices whose vectors are orthogonal. The orthogonality dimension
of a hypergraph $H$, denoted by $\overline{\xi}(H)$, is the smallest integer
$t$ for which there exists a $t$-dimensional orthogonal representation of $H$.
In this paper we study computational aspects of the orthogonality dimension of
graphs and hypergraphs. We prove that for every $k \geq 4$, it is
$\mathsf{NP}$-hard (resp. quasi-$\mathsf{NP}$-hard) to distinguish $n$-vertex
$k$-uniform hypergraphs $H$ with $\overline{\xi}(H) \leq 2$ from those
satisfying $\overline{\xi}(H) \geq \Omega(\log^\delta n)$ for some constant
$\delta>0$ (resp. $\overline{\xi}(H) \geq \Omega(\log^{1-o(1)} n)$). For
graphs, we relate the $\mathsf{NP}$-hardness of approximating the orthogonality
dimension to a variant of a long-standing conjecture of Stahl. We also consider
the algorithmic problem in which given a graph $G$ with $\overline{\xi}(G) \leq
3$ the goal is to find an orthogonal representation of $G$ of as low dimension
as possible, and provide a polynomial time approximation algorithm based on
semidefinite programming.
