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

ПДМ, 2012, номер 1(15), страницы 5–10 (Mi pdm354)

Эта публикация цитируется в 1 статье

Теоретические основы прикладной дискретной математики

О статистических свойствах нелинейности сужений булевых функций на случайно выбранное подпространство

А. Н. Алексейчук, С. Н. Конюшок

Институт специальной связи и защиты информации Национального технического университета Украины "Киевский политехнический институт", г. Киев, Украина

Аннотация: Показано, что для всех достаточно больших натуральных $n$ относительная нелинейность произвольной булевой функции $n$ переменных может быть статистически аппроксимирована относительной нелинейностью ее сужения на случайное подпространство (возможно, с выколотым нулевым вектором), размерность которого не зависит от $n$.

Ключевые слова: булева функция, нелинейность, случайное подпространство, статистическая оценка.

УДК: 631.391+519.2



© МИАН, 2025