**Constructive Relationships Between Algebraic Thickness and Normality**
*Joan Boyar, Magnus Gausdal Find*

FCT 2015.

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 *s*<3, any function with algebraic thickness
*n*^{s} is constant
on some affine subspace of dimension Ω(n^{(3-s)/2}).
Furthermore, we give an algorithm for finding such a subspace.
We show that this is at most a factor of Θ(√n) from the best
guaranteed, and when restricted to the technique used, is at most a factor
of Θ(√(log*n*)) from the best guaranteed. We also show
that a concrete function,
majority, has algebraic thickness Ω(2^{n1/6}).

Last modified: Tue Jun 4 16:48:05 CEST 2015