Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Constructive Relationships Between Algebraic Thickness and Normality

Published

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

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 October 16, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created August 3, 2015, Updated October 12, 2021