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 F2 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 ns 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 Θ(√(logn)) from the best guaranteed. We also show that a concrete function, majority, has algebraic thickness Ω(2n1/6).


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