5 citations · 16 across the 14 of their papers we have counts for
14 papers
An explicit finite -sequence
Igor S. Sergeev
For any and , we provide an explicit (that is, computable in polynomial time) example of integer -sequence of size consisting of elements bounded by .
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…
On the monotone complexity of the shift operator
Igor S. Sergeev
We show that the complexity of minimal monotone circuits implementing a monotone version of the permutation operator on boolean vectors of length is . In parti…
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.
Thin circulant matrices and lower bounds on the complexity of some Boolean operators
M. I. Grinchuk, I. S. Sergeev
We prove a lower bound on the maximal possible weight of a -free (that is, free of all-ones submatrices)…
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 .