Bounds on certain multiplications of affine combinations
type: Item
instance of: scholarly article
title: Bounds on certain multiplications of affine combinations
zbMATH Open document ID: 0804.05013
DOI: 10.1016/0166-218X(94)90079-5
author: Kim S. Larsen
author: Joan Boyar
author: Faith E. Fich
published in: Discrete Applied Mathematics
publication date: 1995-01-09T00:00:00Z
review text: Let \(A\) and \(B\) be \(n \times n\) matrices the entries of which are affine combinations of the variables \(a_ 1, \dots, a_ m\), \(b_ 1, \dots, b_ m\) over GF(2). Suppose that for each \(i\), \(1 \leq i \leq m\), the term \(a_ i b_ i\) is an element of the product matrix \(C = A \cdot B\). For a given \(n\), let \(M(n)\) denote the maximum value that \(m\) can have. This question arises from a recent technique for improving the communication complexity of zero-knowledge proofs. Let \(u = {1 \over 2} (\lceil n/3 \rceil - 1) (n - 1) (n - 2)\) and \(v = \sqrt {u^ 2 - {1 \over 27}}\). In this paper it is shown that for \(n \geq 4\), \[ M(n) \leq n(1 + \root 3\of {u + v} + \root 3\of {u - v}) = n^ 2/ {\root 3 \of {3}} + O(n) \] and \(M(2) = 2\), \(M(3) = 6\), and \(M(4) = 9\). Note that this problem has some connections with the so-called Zarankiewicz problem.
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 626258
zbMATH Keywords: encryption scheme
zbMATH Keywords: affine combinations
zbMATH Keywords: product matrix
zbMATH Keywords: Zarankiewicz problem
Wikidata QID: Q114215017
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
cites work: Q4773298
cites work: Q5592261
cites work: Q3257129
cites work: On a problem of K. Zarankiewicz
cites work: A problem of Zarankiewicz
cites work: On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
cites work: On the number of multiplications necessary to compute certain functions
description: scientific article; zbMATH DE number 626258