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.
|
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 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)
 |
Edit Item |
