On XOR Lemmas for the Weight of Polynomial Threshold Functions
On XOR Lemmas for the Weight of Polynomial Threshold Functions
复制标题
多项式阈值函数权重的异或引理
DOI：
10.1016/j.ic.2019.104439
复制
发表时间：
2019
影响因子：
1
通讯作者：
Kazuyuki Amano and Shoma Tate
中科院分区：
文献类型：
--
作者：
Gima Tatsuya;Hanaka Tesshu;Kiyomi Masashi;Kobayashi Yasuaki;Otachi Yota;Kazuyuki Amano and Shoma Tate
如果对于所有 x∈{− 1, 1} n，f (x)= s g n (p (x))，则多重线性多项式 p 被称为符号表示布尔函数 f:{− 1, 1} n→{− 1, 1}。在本文中，我们考虑形式为⊕ k f 的多项式符号表示布尔函数的长度和权重，即 f 的 k 个副本在不相交变量集上的异或。首先，我们证明对于无限族函数 f，简单的构造不会产生最短多项式符号表示⊕ k f。更准确地说，对于除 k= n= 2 之外的每个 k≥ 2 和 n≥ 2，我们给出了符号表示的多项式⊕ k AND n 的构造，其长度严格小于符号表示的多项式 AND n 的最小长度的 k 次方。以前，此类多项式仅在 n= 2 时已知（Sezener 和 Oztop，2015）。还提供了类似的重量结果。其次，我们引入布尔函数 f 的参数 v f⁎ 并证明当 k 趋向无穷大时，表示多项式符号的最小权重⊕ k f 的 k 次根收敛于 v f⁎ 和 (v f⁎) 2 之间。
A multilinear polynomial p is said to sign-represent a Boolean function f:{− 1, 1} n→{− 1, 1} if f (x)= s g n (p (x)) for all x∈{− 1, 1} n. In this paper, we consider the length and weight of polynomials sign-representing Boolean functions of the form⊕ k f, the XOR of k copies of f on disjoint sets of variables. Firstly, we show that for an infinite family of functions f, a naive construction does not yield a shortest polynomial sign-representing⊕ k f. More precisely, we give a construction of polynomials sign-representing⊕ k AND n whose length is strictly smaller than the k-th power of the minimum length of a polynomial sign-representing AND n, for every k≥ 2 and n≥ 2 except for k= n= 2. Previously, such polynomials were known only for n= 2 (Sezener and Oztop, 2015). A similar result for the weight is also provided. Secondly, we introduce a parameter v f⁎ of a Boolean function f and show that the k-th root of the minimum weight of a polynomial sign-representing⊕ k f converges between v f⁎ and (v f⁎) 2 as k goes to infinity.