On Blocky Ranks Of Matrices

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningfagfællebedømt

Dokumenter

  • Fulltext

    Forlagets udgivne version, 296 KB, PDF-dokument

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.

OriginalsprogEngelsk
Artikelnummer2
TidsskriftComputational Complexity
Vol/bind33
Udgave nummer1
ISSN1016-3328
DOI
StatusUdgivet - 2024

Bibliografisk note

Publisher Copyright:
© The Author(s) 2024.

ID: 390410651