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.