✦ LIBER ✦

Matrix rank and communication complexity

✍ Scribed by Bruno Codenotti; Gianna Del Corso; Giovanni Manzini

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 76 KB
Volume: 304
Category: Article
ISSN: 0024-3795
DOI: 10.1016/s0024-3795(99)00226-8

No coin nor oath required. For personal study only.

✦ Synopsis

The rank of a matrix seems to play a role in the context of communication complexity, a framework developed to analyze basic communication requirements of computational problems. We present some issues and open problems arising in this area, and put forward a number of research subjects in linear algebra, whose investigation would shed new lights into the intriguing relationship between communication complexity and matrix rank. We also mention the related problem of the accuracy of bounds on the chromatic number of a graph given in terms of the rank of its adjacency matrix.

📜 SIMILAR VOLUMES

The communication complexity of several

The communication complexity of several problems in matrix computation

✍ Jeff I Chu; Georg Schnitger 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 747 KB

The communication complexity of a function f measures the communication resources required for computingf. In the design of VLSI systems, where savings on the chip area and computation time are desired, this complexity dictates an area x time\* lower bound. We investigate the communication complexit

Quantum communication and complexity

✍ Ronald de Wolf 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 182 KB

In the setting of communication complexity, two distributed parties want to compute a function depending on both their inputs, using as little communication as possible. The required communication can sometimes be signiÿcantly lowered if we allow the parties the use of quantum communication. We surv

Complexity and rank of homogeneous space

Complexity and rank of homogeneous spaces

✍ D. I. Panyushev 📂 Article 📅 1990 🏛 Springer 🌐 English ⚖ 917 KB

We study an algebraic varieties with the action ofa reductive group G. The relation is elucidated between the notions of complexity and rank of an arbitrary G-variety and the structure of stabilizers of general position of some actions of G itself and its Borel subgroup. The application of this theo

Recognition problems and communication c

Recognition problems and communication complexity

✍ Gábor Wiener 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 248 KB

A special case of combinatorial search, the recognition problem is examined in this article. (H; A; f) is a recognition problem if H is a set, A is a set system on H and f : H → {0; 1} is a function. Someone chooses an arbitrary x ∈ H and instead of determining x itself (which is the case in most of

Still another rank determination of set

Still another rank determination of set intersection matrices with an application in communication complexity

✍ U. Tamm 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 415 KB

The set-intersection function gives the cardinality of the intersection of two sets. In order to obtain a lower bound for the communication complexity of this function, the rank of the corresponding characteristic function-value matrices was calculated in [l] and [Z]. In this note, the rank of these

Spectral Methods for Matrix Rigidity wit

Spectral Methods for Matrix Rigidity with Applications to Size–Depth Trade-offs and Communication Complexity

✍ Satyanarayana V. Lokam 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 210 KB

The rigidity of a matrix measures the number of entries that must be changed in order to reduce its rank below a certain value. The known lower bounds on the rigidity of explicit matrices are very weak. It is known that stronger lower bounds would have important consequences in complexity theory. We