Constructive Relationships Between Algebraic Thickness and Normality

Published: August 04, 2015


Joan Boyar, Magnus G. Find


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 Ω(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 Ω(2^{n^{1/6}}).
Proceedings Title: Fundamentals of Computation Theory (LNCS)
Volume: 9210
Conference Dates: August 17-19, 2015
Conference Location: Gdansk, -1
Conference Title: 20th International Symposium on Fundamentals of Computation Theory
Pub Type: Conferences


Cryptographic measures, algebraic thickness, normality, affine subspace
Created August 04, 2015, Updated November 10, 2018