Open AccessBounds on Certain Multiplications of Affine Combinations
Author(s) -
Joan Boyar,
Faith E. Fich,
Kim S. Larsen
Publication year - 1992
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v21i408.6721
Subject(s) - combinatorics , mathematics , affine transformation , product (mathematics) , function (biology) , upper and lower bounds , matrix (chemical analysis) , value (mathematics) , discrete mathematics , arithmetic , pure mathematics , statistics , mathematical analysis , chemistry , geometry , evolutionary biology , biology , chromatography
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 € 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 sqrt[3] 3 + O(n). Tighter bounds are obtained for smaller values of n. The bounds for n = 2, n = 3, and n = 4 are tight.