Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR22-137 | 26th September 2022 17:18

On blocky ranks of matrices

RSS-Feed




TR22-137
Authors: Daniel Avraham , Amir Yehudayoff
Publication: 27th September 2022 15:24
Downloads: 466
Keywords: 


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.



ISSN 1433-8092 | Imprint