А.Н.Алексейчук, С.Н. Конюшок
Показано, что для всех достаточно больших натуральных относительная нелинейность произвольной булевой функции переменных может быть статистически аппроксимирована относительной нелинейностью ее сужения на случайное продпространство (возможно, с выколотым нулевым вектором), размерность которого не зависит от .
Ключевые слова: булева функция, нелинейность, случайное подпространство, статистическая оценка.
1. Логачев О.А., Сальников А.А., Ященко В.В. Булевы функции в теории кодирования и криптологии. – М.: МЦНМО, 2004. – 470 с.
2. Levin L.A. Randomness and non-determinism // J. of Symbolic Logic. – 1993. – Vol. 58. – № 3. – P. 1102 – 1103.
3. Bshouty N., Jackson J., Tamon C. More efficient PAC-learning of DNF with membership queries under the uniform distribution // Proc. 12th Annual Conf. on Comput. Learning Theory, 1999. – P. 286 – 295.
4. Gopalan P., O’Donnell R., Servedio A., Shpilka A., Wimmer K. Testing Fourier dimensionality and sparsity // SIAM J. on Computing. – 2011. – Vol. 40(4). – P. 1075 – 1100.
5. Алексейчук А.Н., Шевцов А.С. Быстрый алгоритм статистического оценивания максимальной несбалансированности билинейных аппроксимаций булевых отображений // Прикладная дискретная математика. – 2011. – № 3(13). – С. 5 – 11.
