Bounds on Certain Multiplications of Affine Combinations
Joan Boyar, Faith Fich, Kim S. Larsen
Discrete Applied Mathematics, 52(2):155-167, 1994.

Let A and B be n x n matrices the entries of which are affine combinations of the variables a_1, .., a_m, b_1, .., b_m over GF(2). Suppose that, for each i, 1 <= i <= m, the term a_i b_i is an element of the product matrix C = A x B. What is the maximum value that m can have as a function of n? This question arises from a recent technique for improving the communication complexity of zero-knowledge proofs.

The obvious upper bound of n^2 is improved to n^2 / cubicroot(3) + O(n). Tighter bounds are obtained for smaller values of n. The bounds for n = 2, n = 3, and n = 4 are tight.


Last modified: April 6, 1997.
Kim Skak Larsen (kslarsen@imada.sdu.dk)