On Blocky Ranks Of Matrices

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

On Blocky Ranks Of Matrices. / Avraham, Daniel; Yehudayoff, Amir.

In: Computational Complexity, Vol. 33, No. 1, 2, 2024.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Avraham, D & Yehudayoff, A 2024, 'On Blocky Ranks Of Matrices', Computational Complexity, vol. 33, no. 1, 2. https://doi.org/10.1007/s00037-024-00248-1

APA

Avraham, D., & Yehudayoff, A. (2024). On Blocky Ranks Of Matrices. Computational Complexity, 33(1), [2]. https://doi.org/10.1007/s00037-024-00248-1

Vancouver

Avraham D, Yehudayoff A. On Blocky Ranks Of Matrices. Computational Complexity. 2024;33(1). 2. https://doi.org/10.1007/s00037-024-00248-1

Author

Avraham, Daniel ; Yehudayoff, Amir. / On Blocky Ranks Of Matrices. In: Computational Complexity. 2024 ; Vol. 33, No. 1.

Bibtex

@article{fb5423d363a14c82a313f6ed826a433a,
title = "On Blocky Ranks Of Matrices",
abstract = "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.",
keywords = "68Q11, 68R10, Communication complexity, fat matchings, matrix rank, threshold circuits",
author = "Daniel Avraham and Amir Yehudayoff",
note = "Publisher Copyright: {\textcopyright} The Author(s) 2024.",
year = "2024",
doi = "10.1007/s00037-024-00248-1",
language = "English",
volume = "33",
journal = "Computational Complexity",
issn = "1016-3328",
publisher = "Birkhauser Verlag Basel",
number = "1",

}

RIS

TY - JOUR

T1 - On Blocky Ranks Of Matrices

AU - Avraham, Daniel

AU - Yehudayoff, Amir

N1 - Publisher Copyright: © The Author(s) 2024.

PY - 2024

Y1 - 2024

N2 - 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.

AB - 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.

KW - 68Q11

KW - 68R10

KW - Communication complexity

KW - fat matchings

KW - matrix rank

KW - threshold circuits

U2 - 10.1007/s00037-024-00248-1

DO - 10.1007/s00037-024-00248-1

M3 - Journal article

AN - SCOPUS:85186868964

VL - 33

JO - Computational Complexity

JF - Computational Complexity

SN - 1016-3328

IS - 1

M1 - 2

ER -

ID: 390410651