University of Hertfordshire

By the same authors

Length of polynomials over finite groups

Research output: Contribution to journalArticle

Documents

View graph of relations
Original languageEnglish
Pages (from-to)1614-1622
JournalJournal of Computer and System Sciences
Journal publication date1 Dec 2015
Volume81
Issue8
Early online date9 Jun 2015
DOIs
StatePublished - 1 Dec 2015

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.

Notes

This document is the Accepted Manuscript version of the following article: Gábor Horváth, and Chrystopher L. Nehaniv, ‘Length of polynomials over finite groups’, Journal of Computer and System Sicences, Vol. 81(8): 1614-1622, December 2015. The final, published version is available online at doi: https://doi.org/10.1016/j.jcss.2015.05.002.

Projects

ID: 8650087