On Blocky Ranks Of Matrices

被引：0
|
作者：
Avraham, Daniel [1 ]
Yehudayoff, Amir [1 ,2 ]
机构：
[1] Technion IIT, Dept Math, Hefa, Israel
[2] Univ Copenhagen, Dept Comp Sci, Copenhagen, Denmark
来源：
COMPUTATIONAL COMPLEXITY | 2024年 / 33卷 / 01期
关键词：
Communication complexity; matrix rank; threshold circuits; fat matchings; THRESHOLD CIRCUITS; GRAPH; DEPTH-2; EDGES;
D O I：
10.1007/s00037-024-00248-1
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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.
引用
收藏
页数：18
相关论文
共 50 条
  • [1] Sums of rank-one matrices and ranks of principal submatrices
    Fallat, Shaun M.
    Tifenbach, Ryan M.
    LINEAR & MULTILINEAR ALGEBRA, 2021, 69 (01): : 9 - 18
  • [2] A remark on ranks of sign patterns
    Shitov, Yaroslav
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2020, 593 : 150 - 151
  • [3] Inequalities for the ranks of multipartite quantum states
    Cadney, Josh
    Huber, Marcus
    Linden, Noah
    Winter, Andreas
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2014, 452 : 153 - 171
  • [4] A SEPARATION BETWEEN TROPICAL MATRIX RANKS
    Shitov, Yaroslav
    PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 2023, 151 (02) : 489 - 499
  • [5] On idempotent ranks of semigroups of partial transformations
    Barnes, G
    Levi, I
    SEMIGROUP FORUM, 2005, 70 (01) : 81 - 96
  • [6] Nilpotent ranks of semigroups of partial transformations
    Levi, Inessa
    SEMIGROUP FORUM, 2006, 72 (03) : 459 - 476
  • [7] Boolean circuits, tensor ranks, and communication complexity
    Pudlak, P
    Rodl, V
    Sgall, J
    SIAM JOURNAL ON COMPUTING, 1997, 26 (03) : 605 - 633
  • [8] Halfspace matrices
    Sherstov, Alexander A.
    COMPUTATIONAL COMPLEXITY, 2008, 17 (02) : 149 - 178
  • [9] Halfspace Matrices
    Alexander A. Sherstov
    computational complexity, 2008, 17 : 149 - 178
  • [10] Sign pattern matrices that admit P0-matrices
    Mendes Araujo, C.
    Torregrosa, Juan R.
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2011, 435 (08) : 2046 - 2053
12345