**Published:** August 04, 2015

#### Author(s)

**Joan Boyar, Magnus Find**

#### Conference

**Name:** 20th International Symposium on Fundamentals of Computation Theory (FCT 2015)

**Dates:** August 17-19, 2015

**Location:** Gdansk, Poland

**Citation:** Fundamentals of Computation Theory, *Lecture Notes in Computer Science* 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