Notes on the complexity of coverings for Kronecker powers of symmetric matrices

2022/12/04 by Igor S. Sergeev, Sergeev, Igor S. · 1 citation
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph theory and applications #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2212.01776

openalex publication_date 2022/12/04 · openalex created_date 2022/12/18 · openalex updated_date 2026/07/28

Abstract

In the present note, we study a new method of constructing efficient coverings for Kronecker powers of matrices, recently proposed by J. Alman, Y. Guan, A. Padaki [arXiv, 2022]. We provide an alternative proof for the case of symmetric matrices in a stronger form. As a consequence, the previously known upper bound on the depth-2 additive complexity of the boolean N× N Kneser-Sierpinski matrices is improved to O(N^1.251).

Cited by

• Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum

Related

• Explicit Lower Bounds via Geometric Complexity Theory
• Smaller Low-Depth Circuits for Kronecker Powers
• A remark on the quantum complexity of the Kronecker coefficients
• Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra
• Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum