Back to Search
Start Over
Notes on the complexity of coverings for Kronecker powers of symmetric matrices
- Publication Year :
- 2022
-
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\times N$ Kneser-Sierpinski matrices is improved to $O(N^{1.251})$.<br />Comment: 13 pages (in English); 14 pages (in Russian)
- Subjects :
- Computer Science - Data Structures and Algorithms
Subjects
Details
- Language :
- English
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2212.01776
- Document Type :
- Working Paper