Published: August 4, 2015
Author(s)
Joan Boyar, Magnus Find
Conference
Name: 20th International Symposium on Fundamentals of Computation Theory (FCT 2015)
Dates: 08/17/2015 - 08/19/2015
Location: Gdansk, Poland
Citation: Fundamentals of Computation Theory, vol. 9210, pp. 106-117
We study the relationship between two measures of Boolean functions; "algebraic thickness" and "normality". For a function f, the algebraic thickness is a variant of the "sparsity", the number of nonzero coefficients in the unique F_2 polynomial representing f, and the normality is the largest dimension of an affine subspace on which f is constant. We show that for 0 < epsilon<2, any function with algebraic thickness n^{3-\epsilon} is constant on some affine subspace of dimension O(n^(epsilon/2). Furthermore, we give an algorithm for finding such a subspace. This is at most a factor of \Theta(sqrt{n}) from the best guaranteed, and when restricted to the technique used, is at most a factor of Theta(sqrt{\log n}) from the best guaranteed. We also show that a concrete function, majority, has algebraic thickness O(2^{n^{1/6}}).
We study the relationship between two measures of Boolean functions; "algebraic thickness" and "normality". For a function f, the algebraic thickness is a variant of the "sparsity", the number of nonzero coefficients in the unique F_2 polynomial representing f, and the normality is the largest...
See full abstract
We study the relationship between two measures of Boolean functions; "algebraic thickness" and "normality". For a function f, the algebraic thickness is a variant of the "sparsity", the number of nonzero coefficients in the unique F_2 polynomial representing f, and the normality is the largest dimension of an affine subspace on which f is constant. We show that for 0 < epsilon<2, any function with algebraic thickness n^{3-\epsilon} is constant on some affine subspace of dimension O(n^(epsilon/2). Furthermore, we give an algorithm for finding such a subspace. This is at most a factor of \Theta(sqrt{n}) from the best guaranteed, and when restricted to the technique used, is at most a factor of Theta(sqrt{\log n}) from the best guaranteed. We also show that a concrete function, majority, has algebraic thickness O(2^{n^{1/6}}).
Hide full abstract
Keywords
affine subspace; algebraic thickness; cryptographic measures; normality
Control Families
None selected
