RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискрет. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискрет. матем., 1995, том 7, выпуск 3, страницы 129–145 (Mi dm594)  

Эта публикация цитируется в 9 научных статьях (всего в 9 статьях)

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

Б. В. Рязанов, С. И. Чечёта


Аннотация: Рассматривается задача о приближении случайной булевой функции (СБФ) множеством всех булевых функций (БФ) второй степени нелинейности, т.е. квадратичных форм (КФ). Под СБФ мы подразумеваем БФ $f$, выбираемую из множества $B_{n}$ всех БФ от $n$ переменных в соответствии с равномерным распределением на $B_{n}$. Ранее в работе [1] решалась аналогичная задача о приближении СБФ множеством всех линейных БФ. В §1 получена основная теорема 1 о дважды экспоненциальном предельном распределении расстояния Хэмминга $\rho_{n}=\rho(f,Q_{n})$ от СБФ $f$ до множества $Q_{n}$ всех КФ. Величину $\rho_{n}$ можно рассматривать как нижнюю оценку радиуса покрытия $t_{n}$ для кода Рида–Маллера второго порядка длины $2^{n}$ [2], и теорема 1 дает асимптотическую (при $n\to\infty$) оценку числа таких БФ $f$ из $B_{n}$, для которых $t_{n}\ge\rho(f,Q_{n})\ge y_{n}$, где $y_{n}$ — некоторая последовательность, $y_{n}\to\infty$. Теорема 1 в работе получена как следствие более общей теоремы 2 о пуассоновском предельном распределении расстояния Хэмминга от СБФ до $k$-й ближайшей КФ. Доказательство теоремы 2 основано на сведении к схеме суммирования зависимых индикаторов и использовании методики [3], проведение которой в нашем случае по существу опирается на новый вариант многомерной центральной предельной теоремы в области больших уклонений (ЦПТБУ) для схемы серий специального вида. Формулировка и доказательство указанной ЦПТБУ вынесены в §2.
Авторы благодарны В. М. Сидельникову за постановку задачи и А. А. Грушо за обсуждение результатов.

Полный текст: PDF файл (1295 kB)

Англоязычная версия:
Discrete Mathematics and Applications, 1995, 5:5, 473–489

Реферативные базы данных:
УДК: 519.1
Статья поступила: 09.07.1993

Образец цитирования: Б. В. Рязанов, С. И. Чечёта, “О приближении случайной булевой функции множеством квадратичных форм”, Дискрет. матем., 7:3 (1995), 129–145; Discrete Math. Appl., 5:5 (1995), 473–489

Цитирование в формате AMSBIB
\RBibitem{RyaChe95}
\by Б.~В.~Рязанов, С.~И.~Чечёта
\paper О приближении случайной булевой функции множеством квадратичных форм
\jour Дискрет. матем.
\yr 1995
\vol 7
\issue 3
\pages 129--145
\mathnet{http://mi.mathnet.ru/dm594}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1361500}
\zmath{https://zbmath.org/?q=an:0871.60007}
\transl
\jour Discrete Math. Appl.
\yr 1995
\vol 5
\issue 5
\pages 473--489


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm594
  • http://mi.mathnet.ru/rus/dm/v7/i3/p129

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. О. В. Денисов, “Локальная предельная теорема для распределения части спектра случайной двоичной функции”, Дискрет. матем., 12:1 (2000), 82–95  mathnet  crossref  mathscinet  zmath; O. V. Denisov, “A local limit theorem for the distribution of a part of the spectrum of a random binary function”, Discrete Math. Appl., 10:1 (2000), 87–101
    2. Н. Н. Токарева, “О квадратичных аппроксимациях в блочных шифрах”, Пробл. передачи информ., 44:3 (2008), 105–127  mathnet  mathscinet  zmath; N. N. Tokareva, “On Quadratic Approximations in Block Ciphers”, Problems Inform. Transmission, 44:3 (2008), 266–286  crossref  isi
    3. А. М. Зубков, А. А. Серов, “Оценка числа булевых функций, имеющих аффинные приближения заданной точности”, Дискрет. матем., 22:4 (2010), 3–19  mathnet  crossref  mathscinet  elib; A. M. Zubkov, A. A. Serov, “Bounds for the number of Boolean functions admitting affine approximations of a given accuracy”, Discrete Math. Appl., 20:5-6 (2010), 467–486  crossref
    4. А. А. Серов, “Предельное распределение расстояния между случайной булевой функцией и множеством аффинных функций”, Теория вероятн. и ее примен., 55:4 (2010), 791–795  mathnet  crossref  mathscinet; A. A. Serov, “Limit distribution of the distance between random Boolean function and affine functions set”, Theory Probab. Appl., 55:4 (2011), 717–722  crossref  isi
    5. Г. И. Ивченко, Ю. И. Медведев, “Спектр случайной булевой функции и его производящая функция”, Матем. вопр. криптогр., 2:2 (2011), 41–53  mathnet  crossref
    6. А. А. Серов, “Оценка числа булевых функций, имеющих квадратичные приближения заданной точности”, Дискрет. матем., 24:3 (2012), 90–107  mathnet  crossref  mathscinet  elib; A. A. Serov, “Bounds for the number of Boolean functions admitting quadratic approximations of given accuracy”, Discrete Math. Appl., 22:4 (2012), 455–475  crossref
    7. А. М. Зубков, А. А. Серов, “Оценки числа булевых функций, имеющих аффинные и квадратичные приближения заданной точности”, ПДМ. Приложение, 2012, № 5, 11–13  mathnet
    8. А. В. Черемушкин, “О распределении ранга и оценке уровня аффинности квадратичных форм”, ПДМ. Приложение, 2016, № 9, 36–38  mathnet  crossref
    9. А. В. Черемушкин, “Об оценке уровня аффинности квадратичных форм”, Дискрет. матем., 29:1 (2017), 114–125  mathnet  crossref  elib; A. V. Cheremushkin, “Estimating the level of affinity of a quadratic form”, Discrete Math. Appl., 27:6 (2017), 339–347  crossref  isi
  • Дискретная математика
    Просмотров:
    Эта страница:320
    Полный текст:129
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020