|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Lower bounds for additive complexity of linear operators and bilinear algorithms for matrix and polynomial multiplication over GF(2)статья
- Автор: Sergeev I.S.
- Журнал: Mathematical Notes
- Том: 118
- Номер: 4
- Год издания: 2025
- Издательство: Pleiades Publishing, Ltd
- Местоположение издательства: Road Town, United Kingdom
- Первая страница: 848
- Последняя страница: 862
- Аннотация: We establish a lower bound 5n–o(n) on the complexity of an explicit boolean n×n matrix with respect to implementation by additive circuits over GF(2). Also we obtain complexity lower bounds 3n–o(n) for an explicit n×n circulant matrix, and for the Sierpiński matrix of the same size. Along the way, we prove lower bounds on the additive complexity of bilinear algorithms: (4–o(1))n2 for multiplication of n×n matrices, 5n–o(n) for multiplication of degree n–1 polynomials, and 4n–o(n) for the cyclic convolution of order n over GF(2).
- Добавил в систему: Сергеев Игорь Сергеевич