RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2024, том 36, выпуск 2, страницы 124–131 (Mi dm1821)

Линейное хеширование в булевом кубе с кластерами ограниченного размера

А. В. Чашкин

МГУ им. М. В. Ломоносова

Аннотация: Показано, что для произвольного подмножества $n$-мерного булева куба из $M$ элементов существует линейная хеш-функция, кластеры которой состоят не более чем из $a$ элементов, и ранг которой не превосходит ${2\log_2 M-2\log_2 a+\mathcal O(1)}$.

Ключевые слова: $n$-мерный булев куб, линейные булевы хеш-функции, кластер.

УДК: 519.714

Статья поступила: 15.03.2024

DOI: 10.4213/dm1821



© МИАН, 2024