  After Bob sends Alice a bit, she responds with a lengthy reply. At the cost
of a factor of two in the total communication, Alice could just as well have
given the two possible replies without listening and have Bob select which
applies to him. Motivated by a conjecture stating that this form of "round
elimination" is impossible in exact quantum communication complexity, we study
the orthogonal rank and a symmetric variant thereof for a certain family of
Cayley graphs. The orthogonal rank of a graph is the smallest number $d$ for
which one can label each vertex with a nonzero $d$-dimensional complex vector
such that adjacent vertices receive orthogonal vectors.
  We show an exp$(n)$ lower bound on the orthogonal rank of the graph on
$\{0,1\}^n$ in which two strings are adjacent if they have Hamming distance at
least $n/2$. In combination with previous work, this implies an affirmative
answer to the above conjecture.
