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

Автори:А.Н. Алексейчук, С.Н. Конюшок

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

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

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

References

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.

 

 

Сайт видання:http://journals.tsu.ru/pdm/