Constructive Relationships Between Algebraic Thickness and Normality

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