5 citations · 16 across the 14 of their papers we have counts for
10 papers · 1 filter
Notes on the complexity of coverings for Kronecker powers of symmetric matrices
Igor S. Sergeev
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…
Some comments on the structure of the best known networks sorting 16 elements
Igor S. Sergeev
We propose an explanation of the structure of the best known sorting networks for 16 elements with respect to the complexity and to the depth due to Green and van Voorhis.
On the complexity of computing prime tables on a Turing machine
Igor S. Sergeev
We prove that the complexity of computing the table of primes between and on a multitape Turing machine is .
On the circuit complexity of the standard and the Karatsuba methods of multiplying integers
Igor S. Sergeev
We provide accurate upper bounds on the Boolean circuit complexity of the standard and the Karatsuba methods of integer multiplication
Implementation of linear maps with circulant matrices via modulo 2 rectifier circuits of bounded depth
Igor S. Sergeev
In the present note we show that for any positive integer k an arbitrary Boolean circulant matrix can be implemented via modulo 2 rectifier circuit of depth 2k-1 and complexity O(n…
A relation between additive and multiplicative complexity of Boolean functions
Igor S. Sergeev
In the present note we prove an asymptotically tight relation between additive and multiplicative complexity of Boolean functions with respect to implementation by circuits over th…