**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)