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.
Original language | English |
---|---|
Pages (from-to) | 1614-1622 |
Journal | Journal of Computer and System Sciences |
Volume | 81 |
Issue number | 8 |
Early online date | 9 Jun 2015 |
DOIs | |
Publication status | Published - 1 Dec 2015 |
Keywords
- Length of polynomial functions, Simple non-Abelian groups, Nilpotent groups, Branching program, Permutation branching program