Редкие циркулянтные матрицы и нижние оценки сложности некоторых булевых операторов

Авторы: Гринчук М.И., Сергеев И.С.
Журнал: Дискретный анализ и исследование операций
Том: 18
Номер: 5
Год издания: 2011
Издательство: Изд-во Ин-та математики
Местоположение издательства: Новосибирск
Первая страница: 38
Последняя страница: 53
Аннотация: В работе доказывается нижняя оценка Ω ( (k+l)/(k^2l^2) N^{2-(k+l+2)/(kl)} ) максимально возможного веса (k,l)-редкой (т.е. не содержащей единичных подматриц размера k x l) циркулянтной матрицы порядка N. Эта оценка близка к известной оценке для класса всех (k,l)-редких матриц. В качестве следствия получены новые нижние оценки для нескольких мер сложности систем булевых сумм и нижняя оценка Ω(N^2 log^{-6} N) монотонной сложности булевой свертки порядка N.
Добавил в систему: Сергеев Игорь Сергеевич

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

ИСТИНА