Algebraic techniques in communication complexity

Bruno Codenotti; Giovanni Manzini; Luciano Margara

doi:10.1016/0020-0190(95)00158-9

Algebraic techniques in communication complexity

Bruno Codenotti
, Giovanni Manzini
, Luciano Margara

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper we study the gap between the logarithm of the rank of a matrix and its communication complexity. The main contribution of the paper relies on the algebraic interpretation of some methods which yield non constant gaps by combining, mainly via tensor products, matrices with constant gap.

Original language	English
Pages (from-to)	191-195
Number of pages	5
Journal	Information Processing Letters
Volume	56
Issue number	4
DOIs	https://doi.org/10.1016/0020-0190(95)00158-9
Publication status	Published - 24 Nov 1995
Externally published	Yes

Keywords

Communication complexity
Computational complexity
Gap
Rank of a matrix

Access to Document

10.1016/0020-0190(95)00158-9

Cite this

@article{ed1b3749fe784f4fb87aa17b73615df3,

title = "Algebraic techniques in communication complexity",

abstract = "In this paper we study the gap between the logarithm of the rank of a matrix and its communication complexity. The main contribution of the paper relies on the algebraic interpretation of some methods which yield non constant gaps by combining, mainly via tensor products, matrices with constant gap.",

keywords = "Communication complexity, Computational complexity, Gap, Rank of a matrix",

author = "Bruno Codenotti and Giovanni Manzini and Luciano Margara",

note = "Funding Information: * Corresponding author. Email: [email protected]. {\textquoteright} This work has been partially supported by EEC ESPRIT BRA Project 9072 GEPPCOM. * Email: [email protected]. 3 Email: [email protected].",

year = "1995",

month = nov,

day = "24",

doi = "10.1016/0020-0190(95)00158-9",

language = "English",

volume = "56",

pages = "191--195",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

T1 - Algebraic techniques in communication complexity

AU - Codenotti, Bruno

AU - Manzini, Giovanni

AU - Margara, Luciano

N1 - Funding Information: * Corresponding author. Email: [email protected]. ’ This work has been partially supported by EEC ESPRIT BRA Project 9072 GEPPCOM. * Email: [email protected]. 3 Email: [email protected].

PY - 1995/11/24

Y1 - 1995/11/24

N2 - In this paper we study the gap between the logarithm of the rank of a matrix and its communication complexity. The main contribution of the paper relies on the algebraic interpretation of some methods which yield non constant gaps by combining, mainly via tensor products, matrices with constant gap.

AB - In this paper we study the gap between the logarithm of the rank of a matrix and its communication complexity. The main contribution of the paper relies on the algebraic interpretation of some methods which yield non constant gaps by combining, mainly via tensor products, matrices with constant gap.

KW - Communication complexity

KW - Computational complexity

KW - Gap

KW - Rank of a matrix

UR - https://www.scopus.com/pages/publications/0346460374

U2 - 10.1016/0020-0190(95)00158-9

DO - 10.1016/0020-0190(95)00158-9

M3 - Article

SN - 0020-0190

VL - 56

SP - 191

EP - 195

JO - Information Processing Letters

JF - Information Processing Letters

IS - 4

ER -

Algebraic techniques in communication complexity

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this