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 条
  • [11] On the critical group of matrices
    Corrales, Hugo
    Valencia, Carlos E.
    BULLETIN MATHEMATIQUE DE LA SOCIETE DES SCIENCES MATHEMATIQUES DE ROUMANIE, 2011, 54 (03): : 213 - 236
  • [12] Graphs whose normalized Laplacian matrices are separable as density matrices in quantum mechanics
    Wu, Chai Wah
    DISCRETE MATHEMATICS, 2016, 339 (04) : 1377 - 1381
  • [13] Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks
    Korda, Milan
    Laurent, Monique
    Magron, Victor
    Steenkamp, Andries
    MATHEMATICAL PROGRAMMING, 2024, 205 (1-2) : 703 - 744
  • [14] ON ORTHOGONAL MATRICES WITH ZERO DIAGONAL
    Bailey, R. F.
    Craigen, R.
    ELECTRONIC JOURNAL OF LINEAR ALGEBRA, 2019, 35 : 307 - 318
  • [15] On superalgebras of matrices with symmetry properties
    Hill, S. L.
    Lettington, M. C.
    Schmidt, K. M.
    LINEAR & MULTILINEAR ALGEBRA, 2018, 66 (08) : 1538 - 1563
  • [16] RANK DROPS OF RECURRENCE MATRICES
    Bozlee, Sebastian J.
    ELECTRONIC JOURNAL OF LINEAR ALGEBRA, 2015, 30 : 422 - 436
  • [17] ON EUCLIDEAN DISTANCE MATRICES OF GRAPHS
    Jaklic, Gasper
    Modic, Jolanda
    ELECTRONIC JOURNAL OF LINEAR ALGEBRA, 2013, 26 : 574 - 589
  • [18] QUANTUM SYMMETRIES OF HADAMARD MATRICES
    Gromada, Daniel
    TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2024, 377 (09) : 6341 - 6377
  • [19] ON THE MINIMUM RANK OF DISTANCE MATRICES
    Gachkooban, Zahra
    Alizadeh, Rahim
    MATHEMATICAL INEQUALITIES & APPLICATIONS, 2024, 27 (01): : 185 - 191
  • [20] Schur decomposition of several matrices
    Dmytryshyn, Andrii
    LINEAR & MULTILINEAR ALGEBRA, 2024, 72 (08) : 1346 - 1355
12345