Length of polynomials over finite groups

Horvath, Gabor and Nehaniv, C. L. (2015) Length of polynomials over finite groups. Journal of Computer and System Sciences, 81 (8). pp. 1614-1622. ISSN 0022-0000
Copy

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.
Item Type Article
Additional information 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.
Keywords length of polynomial functions, simple non-abelian groups, nilpotent groups, branching program, permutation branching program
Date Deposited 15 May 2025 12:55
Last Modified 04 Jun 2025 17:03

Explore Further

visibility_off picture_as_pdf
picture_as_pdf
FiniteGroups.pdf
subject
Published Version
lock
Restricted to Repository staff only
Request Copy
picture_as_pdf
Submitted Version

Atom BibTeX OpenURL ContextObject in Span OpenURL ContextObject Dublin Core MPEG-21 DIDL Data Cite XML EndNote HTML Citation METS MODS RIOXX2 XML Reference Manager Refer ASCII Citation
Export

Downloads