On Blocky Ranks Of Matrices
Research output: Contribution to journal › Journal article › Research › peer-review
Documents
- Fulltext
Final published version, 296 KB, PDF document
A matrix is blocky if it is a "blowup" of a permutation matrix. The blocky rank of a matrix M is the minimum number of blocky matrices that linearly span M. Hambardzumyan, Hatami and Hatami defined blocky rank and showed that it is connected to communication complexity and operator theory. We describe additional connections to circuit complexity and combinatorics, and we prove upper and lower bounds on blocky rank in various contexts.
Original language | English |
---|---|
Article number | 2 |
Journal | Computational Complexity |
Volume | 33 |
Issue number | 1 |
ISSN | 1016-3328 |
DOIs | |
Publication status | Published - 2024 |
Bibliographical note
Publisher Copyright:
© The Author(s) 2024.
- 68Q11, 68R10, Communication complexity, fat matchings, matrix rank, threshold circuits
Research areas
ID: 390410651