On Blocky Ranks Of Matrices

Research output: Contribution to journalJournal articleResearchpeer-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 languageEnglish
Article number2
JournalComputational Complexity
Volume33
Issue number1
ISSN1016-3328
DOIs
Publication statusPublished - 2024

Bibliographical note

Publisher Copyright:
© The Author(s) 2024.

    Research areas

  • 68Q11, 68R10, Communication complexity, fat matchings, matrix rank, threshold circuits

ID: 390410651