A general 4-words inequality with consequences for 2-way communication complexity
type: Item
instance of: scholarly article
title: A general 4-words inequality with consequences for 2-way communication complexity
zbMATH Open document ID: 0668.94007
DOI: 10.1016/0196-8858(89)90004-3
author: Ning Cai
author: Zhen Zhang
author: Rudolf Ahlswede
published in: Advances in Applied Mathematics
publication date: 1989-01-01T00:00:00Z
full work available at URL: https://pub.uni-bielefeld.de/record/1780500
review text: We describe the main result. Let \({\mathcal X}\) and \({\mathcal Y}\) be two finite sets. We consider functions \(f: {\mathcal X}\times {\mathcal Y}\to {\mathbb{Z}},\) where \({\mathbb{Z}}\) is the ring of integers. With f we associate the ``sum- type function'' \(f_ n: {\mathcal X}^ n\times {\mathcal Y}^ n\to {\mathbb{Z}}\) defined by \(f_ n(x^ n,y^ n)=\sum^{n}_{t=1}f(x_ t,y_ t).\) Let \({\mathcal P}(f,{\mathcal R},n)\) be the set of pairs (A,B), \(A\subset {\mathcal X}^ n\) and \(B\subset {\mathcal Y}^ n\), with the \({\mathcal R}\)-4-words property \[ f_ n(a^ n,b^ n)-f_ n(a^ n,b^{'n})+f_ n(a^{'n},b^{'n})-f_ n(a^{'n},b^ n)\in {\mathcal R}. \] For M(f,\({\mathcal R},n)=\max \{| A| | B|:(A,B)\in {\mathcal P}(f,{\mathcal R},n)\}\) we have the General 4-words inequality: For any \({\mathcal R}\subset {\mathbb{Z}},\) \(M(f,{\mathcal R},n)\leq M(f,{\mathcal R},1)^ n.\) Furthermore, if \(0\in {\mathcal R}\) and \(M(f,\{0\},1)=M(f,{\mathcal R},1),\) then equality holds. This inequality is much more general than its predecessors [\textit{R. Ahlswede}, \textit{A. El Gamal}, \textit{K. F. Pang}, Discrete Math. 49, 1-5 (1984; Zbl 0532.94013); \textit{R. Ahlswede}, \textit{M. Moers}, Eur. J. Comb. 9, No.2, 175-181 (1988; Zbl 0549.05007)]. The \({\mathcal R}\)-4-words property extends Yao's [\textit{A. Yao}, Proc. 11th Ann. ACM Sympos. Theory of Computing 1979, 209-219] notion of monochromatic rectangles and the inequality is a key tool in deriving (often asymptotically optimal) bounds on 2-way communication complexity.
Mathematics Subject Classification ID: 94A99
zbMATH DE Number: 4095373
zbMATH Keywords: General 4-words inequality
zbMATH Keywords: monochromatic rectangles
zbMATH Keywords: 2-way communication complexity
MaRDI profile type: Publication
OpenAlex ID: W2012121115
cites work: A two-family extremal problem in Hamming space
cites work: An extension of an inequality by Ahlswede, El Gamal and Pang for pairs of binary codes
cites work: Q3705357
cites work: Communication Complexity of Computing the Hamming Distance
cites work: Q3030262
cites work: Q4206689
cites work: Q3895387
description: scientific article; zbMATH DE number 4095373