Communication complexity and orthogonal polynomials (Q2717211)

The communication complexity of certain functions defined on an association scheme is studied in this paper. Let \(\{D_0,\dots,D_n\}\) be a collection of matrices forming an association scheme. Let \(M_0(f)=\sum_{k \text{ even}}D_k\), \(M_1(f)=\sum_{k\text{ odd}}D_k\). If \(f=p_n\) is the Hamming distance modulo 2 for alphabet size \(q\geq 3\), then the communication complexity \(C(p_n)\) is that of the trivial protocol (corollary of Theorem 3.1). Theorem 3.2. Let \(f=g_n\) be defined by the matrices \(D_i\) in the Johnson scheme. Then the communication complexity \(C(g_n)\) is that of the trivial protocol, if for all \(i=1,\dots,n\) the Krawtchouk polynomials \(K_{n-i+1}(n-i+1,l+2i-2,2)\) are different from 0. The eigenvalues of the association scheme of bilinear forms over \(\text{GF}(q)\) have as parameters a prime power \(b=q\) and \(c=b^r\) for some nonnegative integer \(r\). The eigenvalues of the association scheme of alternating forms over \(\text{GF}(q)\) have as parameters \(b=p^2\) and \(c=p\) or \(c=1/p\) for some prime \(p\). Theorem 3.3. Let \(f\) be defined by the matrices \(D_i\) in the association scheme of bilinear forms over \(\text{GF}(b)\) or in the association scheme of alternating forms. If the prime \(p\) is odd and \(b-1\) is not a power of 2, then the trivial protocol is optimal for all such functions.NEWLINENEWLINEFor the entire collection see [Zbl 0960.00079].