An official website of the United States government
Here’s how you know
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
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)