Length of polynomials over finite groups

Gabor Horvath, C. L. Nehaniv

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
35 Downloads (Pure)


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 languageEnglish
Pages (from-to)1614-1622
JournalJournal of Computer and System Sciences
Issue number8
Early online date9 Jun 2015
Publication statusPublished - 1 Dec 2015


  • Length of polynomial functions, Simple non-Abelian groups, Nilpotent groups, Branching program, Permutation branching program


Dive into the research topics of 'Length of polynomials over finite groups'. Together they form a unique fingerprint.

Cite this