Constructive Relationships Between Algebraic Thickness and Normality

Abstract

We study the relationship between two measures of Boolean functions; \emph{algebraic thickness} and \emph{normality}. For a function $f$, the algebraic thickness is a variant of the \emph{sparsity}, the number of nonzero coefficients in the unique GF(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 $\Omega \left(n^{\frac{\epsilon }{2}}\right)$. Furthermore, we give an algorithm for finding such a subspace. We show that 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 $\Omega \left(2^{n^{1/6}}\right)$.

arXiv commentFinal version published in FCT'2015