University of Hertfordshire

By the same authors

Length of polynomials over finite groups

Research output: Contribution to journalArticle

Standard

Length of polynomials over finite groups. / Horvath, Gabor; Nehaniv, C. L.

In: Journal of Computer and System Sciences, Vol. 81, No. 8, 12.2015, p. 1614-1622.

Research output: Contribution to journalArticle

Harvard

APA

Vancouver

Author

Horvath, Gabor; Nehaniv, C. L. / Length of polynomials over finite groups.

In: Journal of Computer and System Sciences, Vol. 81, No. 8, 12.2015, p. 1614-1622.

Research output: Contribution to journalArticle

Bibtex

@article{956de9f2e3974bcebcd13d93cd4a847d,
title = "Length of polynomials over finite groups",
keywords = "Length of polynomial functions, Simple non-Abelian groups, Nilpotent groups, Branching program, Permutation branching program",
author = "Gabor Horvath and Nehaniv, {C. L.}",
note = "Date of Acceptance: 13/05/2015",
year = "2015",
month = "12",
doi = "10.1016/j.jcss.2015.05.002",
volume = "81",
pages = "1614--1622",
journal = "Journal of Computer and System Sciences",
issn = "0022-0000",
publisher = "Academic Press Inc.",
number = "8",

}

RIS

TY - JOUR

T1 - Length of polynomials over finite groups

AU - Horvath,Gabor

AU - Nehaniv,C. L.

N1 - Date of Acceptance: 13/05/2015

PY - 2015/12

Y1 - 2015/12

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

VL - 81

SP - 1614

EP - 1622

JO - Journal of Computer and System Sciences

T2 - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

IS - 8

ER -