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, 01.12.2015, p. 1614-1622.

Research output: Contribution to journalArticle

Harvard

APA

Vancouver

Author

Bibtex

@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, ‘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.",
year = "2015",
month = "12",
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",

}

RIS

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

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 -