On Blocky Ranks Of Matrices

被引：1
作者：
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 条
[21]   ON EQUI-TRANSMITTING MATRICES [J].
Kurasov, Pavel ;
Ogik, Rao .
REPORTS ON MATHEMATICAL PHYSICS, 2016, 78 (02) :199-218
[22]   Conditional S-matrices [J].
Xu, GH ;
Shao, HY .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2004, 376 :187-206
[23]   Normal matrices subordinate to a graph [J].
Johnson, Charles R. ;
Turnansky, Morrison .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2017, 531 :54-63
[24]   On conjugate adjacency matrices of a graph [J].
Lepovic, Mirko .
DISCRETE MATHEMATICS, 2007, 307 (06) :730-738
[25]   Smith Normal Form and acyclic matrices [J].
Kim, In-Jae ;
Shader, Bryan L. .
JOURNAL OF ALGEBRAIC COMBINATORICS, 2009, 29 (01) :63-80
[26]   AN ALGORITHM TO RECOVER SHREDDED RANDOM MATRICES [J].
Atamanchuk, Caelan ;
Devroye, Luc ;
Vicenzo, Massimo .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2024, 38 (03) :2509-2529
[27]   ON A PARAMETRIZATION OF POSITIVE SEMIDEFINITE MATRICES WITH ZEROS [J].
Drton, Mathias ;
Yu, Josephine .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2010, 31 (05) :2665-2680
[28]   A new kind of Hermitian matrices for digraphs [J].
Mohar, Bojan .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2020, 584 :343-352
[29]   Inverse spectral problems for arrowhead matrices [J].
Fathi, Ferya ;
Araghi, Mohammad Ali Fariborzi ;
Fazeli, Seyed Abolfazl Shahzadeh .
JOURNAL OF MATHEMATICAL MODELING, 2022, 10 (02) :213-225
[30]   RANK FORMULAS FOR CERTAIN PRODUCTS OF MATRICES [J].
AHLSWEDE, R ;
CAI, N .
APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING, 1993, 4 (04) :253-261
12345