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

共 20 条

[1]

Alon Noga, 2020, PMLR, V125, P119

[2]

Amano Kazuyuki, 2020, Language and Automata Theory and Applications. 14th International Conference, LATA 2020. Proceedings. Lecture Notes in Computer Science (LNCS 12038), P235, DOI 10.1007/978-3-030-40608-0_16

[3]

[Anonymous], 1994, Theoretical Advances in Neural Computation and Learning

[4] CLIQUE COVERINGS OF THE EDGES OF A RANDOM GRAPH [J].

BOLLOBAS, B ;

ERDOS, P ;

SPENCER, J ;

WEST, DB .

COMBINATORICA, 1993, 13 (01) :1-5

[5] REPRESENTATION OF A GRAPH BY SET INTERSECTIONS [J].

ERDOS, P ;

GOODMAN, AW ;

POSA, L .

CANADIAN JOURNAL OF MATHEMATICS, 1966, 18 (01) :106-&

[6] COVERING THE EDGES OF A RANDOM GRAPH BY CLIQUES [J].

FRIEZE, A ;

REED, B .

COMBINATORICA, 1995, 15 (04) :489-497

[7]

Ghazi Badih, 2021, ALGORITHMIC LEARNING, P686

[8] ADDRESSING PROBLEM FOR LOOP SWITCHING [J].

GRAHAM, RL ;

POLLAK, HO .

BELL SYSTEM TECHNICAL JOURNAL, 1971, 50 (08) :2495-+

[9] ON A CLIQUE COVERING PROBLEM OF ORLIN [J].

GREGORY, DA ;

PULLMAN, NJ .

DISCRETE MATHEMATICS, 1982, 41 (01) :97-99

[10] THRESHOLD CIRCUITS OF BOUNDED DEPTH [J].

HAJNAL, A ;

MAASS, W ;

PUDLAK, P ;

SZEGEDY, M ;

TURAN, G .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1993, 46 (02) :129-154

← 1 2 →