Length of polynomials over finite groups
View/ Open
Author
Horvath, Gabor
Nehaniv, C. L.
Attention
2299/16399
Abstract
We study the length of polynomials over finite simple non-Abelian groups needed to realize Boolean functions. We apply the results for bounding the length of 5-permutation branching programs recognizing a Boolean set. Moreover, for Boolean and general functions on these groups, we present upper bounds on the length of shortest polynomials computing an arbitrary n-ary Boolean or general function, or a function given by another polynomial.