Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank

Dror Chawin, Ishay Haviv

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…