It is shown that for all sufficiently large natural n, the relativenonlinearity of any Boolean function in n variables can be statistically approximated bythe relative nonlinearity of its restriction on a random subspace (possibly without the zerovector), whose dimension is independent on n.
Download file
Counter downloads: 73
- Title Nonlinearity statistical properties ofBoolean function restrictions on a randomly chosen subspace
- Headline Nonlinearity statistical properties ofBoolean function restrictions on a randomly chosen subspace
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 1(15)
- Date:
- DOI
Keywords
statistical estimation, random subspace, nonlinearity, Boolean functions, статистическая оценка, случайное подпространство, нелинейность, булева функцияAuthors
References
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с.
Nonlinearity statistical properties ofBoolean function restrictions on a randomly chosen subspace | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2012. № 1(15).
Download full-text version
Download fileCounter downloads: 181