Boolean Functions: Degree and Support

Please use this identifier to cite or link to this item: http://hdl.handle.net/10045/79229

Información del item - Informació de l'item - Item information
Title:	Boolean Functions: Degree and Support
Authors:	Climent, Joan-Josep \| García García, Francisco Jesús \| Requena Arévalo, Verónica
Research Group/s:	Grupo de Álgebra y Geometría (GAG)
Center, Department or Service:	Universidad de Alicante. Departamento de Matemáticas
Keywords:	Boolean function \| Support \| Weight \| Algebraic normal form \| Degree \| Linear space
Knowledge Area:	Álgebra
Issue Date:	Sep-2018
Publisher:	Springer International Publishing
Citation:	Mathematics in Computer Science. 2018, 12(3): 349-369. doi:10.1007/s11786-018-0350-8
Abstract:	In this paper we establish some properties about Boolean functions that allow us to relate their degree and their support. These properties allow us to compute the degree of a Boolean function without having to calculate its algebraic normal form. Furthermore, we introduce some linear algebra properties that allow us to obtain the degree of a Boolean function from the dimension of a linear or affine subspace. Finally we derive some algorithms and compute the average time to obtain the degree of some Boolean functions from its support.
URI:	http://hdl.handle.net/10045/79229
ISSN:	1661-8270 (Print) \| 1661-8289 (Online)
DOI:	10.1007/s11786-018-0350-8
Language:	eng
Type:	info:eu-repo/semantics/article
Rights:	© Springer International Publishing AG, part of Springer Nature 2018
Peer Review:	si
Publisher version:	https://doi.org/10.1007/s11786-018-0350-8
Appears in Collections:	INV - GAG - Artículos de Revistas

Files in This Item:

Files in This Item:
File	Description	Size	Format
2018_Climent_etal_MathComputSci_final.pdf	Versión final (acceso restringido)	400,19 kB	Adobe PDF	Open Request a copy