Показано, что для всех достаточно больших натуральных n относительная нелинейность произвольной булевой функции n переменных может быть статистически аппроксимирована относительной нелинейностью ее сужения на случайное подпространство (возможно, с выколотым нулевым вектором), размерность которого не зависит от n.
Скачать электронную версию публикации
Загружен, раз: 73
- Title О статистических свойствах нелинейности сужений булевых функций на случайно выбранное подпространство
- Headline О статистических свойствах нелинейности сужений булевых функций на случайно выбранное подпространство
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 1(15)
- Date:
- DOI
Ключевые слова
statistical estimation, random subspace, nonlinearity, Boolean functions, статистическая оценка, случайное подпространство, нелинейность, булева функцияАвторы
Ссылки
Bshouty N., Jackson J., and Tamon C. More efficient PAC-learning of DNF with membership queries under the uniform distribution // Proc. 12th Annual Conf. on Comput. Learning Theory. NY, USA: ACM,1999. P. 286-295.
Gopalan P., O'Donnell R., Servedio A., et al. Testing Fourier dimensionality and sparsity //SIAM J. Comput. 2011. V.40(4). P. 1075-1100.
Алексейчук А. Н., Шевцов А. С. Быстрый алгоритм статистического оценивания максимальной несбалансированности билинейных аппроксимаций булевых отображений // Прикладная дискретная математика. 2011. №3(13). С. 5-11.
Levin L. A. Randomness and non-determinism // J. Symbolic Logic. 1993. V. 58. No.3. P. 1102-1103.
Логачев О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2004. 470с.
О статистических свойствах нелинейности сужений булевых функций на случайно выбранное подпространство | Прикладная дискретная математика. 2012. № 1(15).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 181