REAL

Length of polynomials over finite groups

Horváth, Gábor and Nehaniv, Chrystopher L. (2015) Length of polynomials over finite groups. Journal of Computer and System Sciences, 81 (8). pp. 1614-1622. ISSN 0022-0000

This is the latest version of this item.

[img]
Preview
Text
pollength.pdf - Accepted Version

Download (327Kb) | Preview

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.

Item Type: Article
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA72 Algebra / algebra
Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Depositing User: Dr Gábor Horváth
Date Deposited: 25 Sep 2015 11:35
Last Modified: 26 Feb 2016 00:15
URI: http://real.mtak.hu/id/eprint/28036

Available Versions of this Item

  • Length of polynomials over finite groups. (deposited 25 Sep 2015 11:35) [Currently Displayed]

Actions (login required)

View Item View Item