RUS  ENG
Полная версия
СЕМИНАРЫ
2024-арные квазигруппы и смежные вопросы
23 июня 2023 г., г. Новосибирск, Институт математики им. С.Л.Соболева СО РАН, ауд. 115

On the classification of perfect colorings of small degree in the hypercube

[О классификации совершенных раскрасок малой степени в гиперкубе]

Д. С. Кротов

Аннотация: Описаны результаты классификации совершенных раскрасок гиперкуба (двоичного графа Хэмминга) H(n,2) с собственными числами не меньше n-6. С точностью до эквивалентности, в H(10,2) таких раскрасок 103, не включая одноцветную. Максимальное число цветов - 8. (Совместная работа с А. Валюженичем)

Язык доклада: Русский или английский по выбору аудитории

Список литературы
  1. J. Chiarelli, P. Hatami, M. Saks. An asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function. Combinatorica, 40(2):237–244, 2020. https://doi.org/10.1007/s00493-019-4136-7
  2. D. P. Kirienko. On the number of correlation-immune and resilient functions of order $n-4$. In Proceedings of the VIII International Seminar “Discrete Mathematics and Its Applications” (2–6 Feb. 2004), pages 421–424, Москва, июнь 2004. MSU.
  3. D. Krotov. Perfect and related codes. IEEE DataPort, 2022–2023. https://doi.org/10.21227/w856-4b70
  4. I. Yu. Mogilnykh, A. A. Valyuzhenich. Equitable $2$-partitions of the Hamming graphs with the second eigenvalue. Discrete Math., 343(11):112039(1–9), Nov. 2020. https://doi.org/10.1016/j.disc.2020.112039
  5. N. Nisan, Szegedy M. On the degree of Boolean functions as real polynomials. Comput. Complexity, 4(4):301–313, Dec. 1994. https://doi.org/10.1007/BF01263419
  6. S. Rasoolzadeh. Classification of all $t$-resilient boolean functions with $t+4$ variables. Cryptology ePrint Archive 2023/638, 2023. https://eprint.iacr.org/2023/638
  7. Yu. Tarannikov, D. Kirienko. Spectral analysis of high order correlation immune functions. Cryptology ePrint Archive 2000/050, 2000. https://eprint.iacr.org/2000/050

© МИАН, 2024