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

Risultato della ricerca: Contributo su rivista › Articolo in rivista › 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.

Lingua originale	Inglese
pagine (da-a)	191-195
Numero di pagine	5
Rivista	Information Processing Letters
Volume	56
Numero di pubblicazione	4
DOI	https://doi.org/10.1016/0020-0190(95)00158-9
Stato di pubblicazione	Pubblicato - 24 nov 1995
Pubblicato esternamente	Sì

Accesso al documento

10.1016/0020-0190(95)00158-9

Altri file e collegamenti

Link to publication in Scopus

Cita questo

@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

Accesso al documento

Altri file e collegamenti

Fingerprint

Cita questo