On the complexity of linear Boolean operators with thin matrices

Gashkov, S.B.; Sergeev, I.S.

Авторы: Gashkov S.B., Sergeev I.S.
Журнал: Journal of Applied and Industrial Mathematics
Том: 5
Номер: 2
Год издания: 2011
Издательство: Maik Nauka/Interperiodica Publishing
Местоположение издательства: Russian Federation
Первая страница: 202
Последняя страница: 211
DOI: 10.1134/S1990478911020074
Аннотация: Abstract—Under consideration is the problem of constructing a square Boolean matrix A of order n without “rectangles” (it is a matrix whose every submatrix of the elements that are in any two rows and two columns does not consist of 1s). A linear transformation modulo two defined by A has complexity o(ν(A) − n) in the base {⊕}, where ν(A) is the weight of A, i.e., the number of 1s (the matrices without rectangles are called thin). Two constructions for solving this problem are given. In the first construction, n = p^2 where p is an odd prime. The corresponding matrix Hp has weight p^3 and generates the linear transformation of complexity O(p^2 log p log log p). In the second construction, the matrix has weight nk where k is the cardinality of a Sidon set in Z_n. We may assume that k = Θ(√n); there are examples of the sets of cardinality k ∼ √n for some n. The corresponding linear transformation has complexity O(n log n log log n). Some generalizations of this problem are considered. Keywords: Boolean circuit, complexity, linear Boolean operator, discrete Fourier transform, finite field, circulant matrix, Sidon set
Добавил в систему: Гашков Сергей Борисович

	ИСТИНА	Войти в систему Регистрация
	ИСТИНА ЦЭМИ РАН
	Главная Поиск Статистика О проекте Помощь

ИСТИНА

ИСТИНА ЦЭМИ РАН

On the complexity of linear Boolean operators with thin matricesстатья

Прикрепленные файлы