Constructive Relationships Between Algebraic Thickness and Normality

Published

August 4, 2015

Author(s)

Joan Boyar, Magnus G. Find

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 Ω(n^(epsilon/2). Furthermore, we give an algorithm for finding such a subspace. This is at most a factor of \Theta(sqrtn}) 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, PL

Conference Title

20th International Symposium on Fundamentals of Computation Theory

Pub Type

Conferences

Download Paper

https://doi.org/10.1007/978-3-319-22177-9_9

Local Download

Keywords

Cryptographic measures, algebraic thickness, normality, affine subspace

Citation

Boyar, J. and Find, M. (2015), Constructive Relationships Between Algebraic Thickness and Normality, Fundamentals of Computation Theory (LNCS), Gdansk, PL, [online], https://doi.org/10.1007/978-3-319-22177-9_9, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=918805 (Accessed May 2, 2026)

Additional citation formats