Upper bounds on the Boolean rank of Kronecker products

DOI10.1016/j.dam.2022.04.001zbMath1497.15033arXiv2102.07486OpenAlexW3130137236MaRDI QIDQ2146742

Ishay Haviv, Michal Parnas

Publication date: 21 June 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2102.07486

zbMATH Keywords

Kronecker productBoolean rankbiclique edge covernon-deterministic communication complexity

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Information theory (general) (94A15) Vector spaces, linear dependence, rank, lineability (15A03) Canonical forms, reductions, classification (15A21) Communication theory (94A05) Boolean and Hadamard matrices (15B34)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fractional biclique covers and partitions of graphs
• Nearly Tight Approximability Results for Minimum Biclique Cover and Partition
• Privacy and Communication Complexity
• Fractional Covers and Communication Complexity
• Amortized Communication Complexity
• Communication Complexity
• Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs
• Secure Frameproof Code Through Biclique Cover
• Boolean rank of Kronecker products