Boolean Functions: Degree and Support |
| |
Authors: | Joan-Josep Climent Francisco J García Verónica Requena |
| |
Institution: | 1.Departament de Matemàtiques,Universitat d’Alacant,Sant Vicent del Raspeig,Spain;2.Departament de Fonaments de l’Anàlisi Econòmica,Universitat d’Alacant,Sant Vicent del Raspeig,Spain |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|