Length of polynomials over finite groups

Gabor Horvath; C. L. Nehaniv

doi:10.1016/j.jcss.2015.05.002

Length of polynomials over finite groups

Gabor Horvath
, C. L. Nehaniv

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

47 Downloads (Pure)

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.

Original language	English
Pages (from-to)	1614-1622
Journal	Journal of Computer and System Sciences
Volume	81
Issue number	8
Early online date	9 Jun 2015
DOIs	https://doi.org/10.1016/j.jcss.2015.05.002
Publication status	Published - 1 Dec 2015

Keywords

Length of polynomial functions, Simple non-Abelian groups, Nilpotent groups, Branching program, Permutation branching program

Access to Document

10.1016/j.jcss.2015.05.002

Accepted ManuscriptAccepted author manuscript, 723 KBLicence: CC BY-NC-ND

Cite this

@article{956de9f2e3974bcebcd13d93cd4a847d,

title = "Length of polynomials over finite groups",

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.",

keywords = "Length of polynomial functions, Simple non-Abelian groups, Nilpotent groups, Branching program, Permutation branching program",

author = "Gabor Horvath and Nehaniv, \{C. L.\}",

note = "This document is the Accepted Manuscript version of the following article: G{\'a}bor Horv{\'a}th, and Chrystopher L. Nehaniv, {\textquoteleft}Length of polynomials over finite groups{\textquoteright}, 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. ",

year = "2015",

month = dec,

day = "1",

doi = "10.1016/j.jcss.2015.05.002",

language = "English",

volume = "81",

pages = "1614--1622",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "8",

}

TY - JOUR

T1 - Length of polynomials over finite groups

AU - Horvath, Gabor

AU - Nehaniv, C. L.

N1 - 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.

PY - 2015/12/1

Y1 - 2015/12/1

N2 - 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.

AB - 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.

KW - Length of polynomial functions, Simple non-Abelian groups, Nilpotent groups, Branching program, Permutation branching program

U2 - 10.1016/j.jcss.2015.05.002

DO - 10.1016/j.jcss.2015.05.002

M3 - Article

SN - 0022-0000

VL - 81

SP - 1614

EP - 1622

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 8

ER -

Length of polynomials over finite groups

Abstract

Keywords

Access to Document

Fingerprint

Cite this