Length of polynomials over finite groups
作者:
Highlights:
•
摘要
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.
论文关键词:Length of polynomial functions,Simple non-Abelian groups,Nilpotent groups,Branching program,Permutation branching program
论文评审过程:Received 3 February 2014, Revised 15 September 2014, Accepted 13 May 2015, Available online 9 June 2015, Version of Record 25 August 2015.
论文官网地址:https://doi.org/10.1016/j.jcss.2015.05.002