dc.contributor.author | Horvath, Gabor | |
dc.contributor.author | Nehaniv, C. L. | |
dc.date.accessioned | 2015-09-08T09:43:42Z | |
dc.date.available | 2015-09-08T09:43:42Z | |
dc.date.issued | 2015-12-01 | |
dc.identifier.citation | Horvath , G & Nehaniv , C L 2015 , ' Length of polynomials over finite groups ' , Journal of Computer and System Sciences , vol. 81 , no. 8 , pp. 1614-1622 . https://doi.org/10.1016/j.jcss.2015.05.002 | |
dc.identifier.issn | 0022-0000 | |
dc.identifier.uri | http://hdl.handle.net/2299/16399 | |
dc.description | 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. | |
dc.description.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. | en |
dc.format.extent | 740233 | |
dc.language.iso | eng | |
dc.relation.ispartof | Journal of Computer and System Sciences | |
dc.subject | Length of polynomial functions, Simple non-Abelian groups, Nilpotent groups, Branching program, Permutation branching program | |
dc.title | Length of polynomials over finite groups | en |
dc.contributor.institution | School of Computer Science | |
dc.contributor.institution | Centre for Computer Science and Informatics Research | |
dc.contributor.institution | Adaptive Systems | |
dc.description.status | Peer reviewed | |
dc.date.embargoedUntil | 2016-06-09 | |
rioxxterms.versionofrecord | 10.1016/j.jcss.2015.05.002 | |
rioxxterms.type | Journal Article/Review | |
herts.preservation.rarelyaccessed | true | |