Horváth, Gábor and Nehaniv, Chrystopher L. (2015) Length of polynomials over finite groups. Journal of Computer and System Sciences, 81 (8). pp. 16141622. ISSN 00220000
This is the latest version of this item.

Text
pollength.pdf  Accepted Version Download (335kB)  Preview 
Official URL: http://authors.elsevier.com/a/1RbPE509754EN
Abstract
We study the length of polynomials over finite simple nonAbelian groups needed to realize Boolean functions. We apply the results for bounding the length of 5permutation 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 nary 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)
Edit Item 