Length of polynomials over finite groups

Gabor Horvath, C. L. Nehaniv

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
23 Downloads (Pure)

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

Keywords

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

Fingerprint

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

Cite this