  The orthogonality dimension of a graph $G=(V,E)$ over a field $\mathbb{F}$ is
the smallest integer $t$ for which there exists an assignment of a vector $u_v
\in \mathbb{F}^t$ with $\langle u_v,u_v \rangle \neq 0$ to every vertex $v \in
V$, such that $\langle u_v, u_{v'} \rangle = 0$ whenever $v$ and $v'$ are
adjacent vertices in $G$. The study of the orthogonality dimension of graphs is
motivated by various applications in information theory and in theoretical
computer science. The contribution of the present work is two-fold.
  First, we prove that there exists a constant $c$ such that for every
sufficiently large integer $t$, it is $\mathsf{NP}$-hard to decide whether the
orthogonality dimension of an input graph over $\mathbb{R}$ is at most $t$ or
at least $3t/2-c$. At the heart of the proof lies a geometric result, which
might be of independent interest, on a generalization of the orthogonality
dimension parameter for the family of Kneser graphs, analogously to a
long-standing conjecture of Stahl (J. Comb. Theo. Ser. B, 1976).
  Second, we study the smallest possible orthogonality dimension over finite
fields of the complement of graphs that do not contain certain fixed subgraphs.
In particular, we provide an explicit construction of triangle-free $n$-vertex
graphs whose complement has orthogonality dimension over the binary field at
most $n^{1-\delta}$ for some constant $\delta >0$. Our results involve
constructions from the family of generalized Kneser graphs and they are
motivated by the rigidity approach to circuit lower bounds. We use them to
answer a couple of questions raised by Codenotti, Pudl\'{a}k, and Resta (Theor.
Comput. Sci., 2000), and in particular, to disprove their Odd Alternating Cycle
Conjecture over every finite field.
