On XOR Lemma for Polynomial Threshold Weight and Length
On XOR Lemma for Polynomial Threshold Weight and Length
复制标题
关于多项式阈值权重和长度的异或引理
DOI：
10.1007/978-3-319-30000-9_20
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Kazuyuki Amano
中科院分区：
文献类型：
--
作者：
Masaki Nakanishi;Miki Matsuyama;and Yumi Yokoo;Kazuyuki Amano
设为布尔函数。我们说一个多线性多项式psign-表示fiffor all。本文研究了多项式符号表示布尔函数的长度和重量，其中每个函数都在一个不相交的变量集上。显然，如果psign-表示，则p（x）p（y）sign-表示。我们给出了一个建设性的证明，即当fis AND on n变量时，对于每个变量都有一个较短的多项式。此外，我们还引入了布尔函数的一个参数，并证明了一个多项式符号表示的最小权的k次根（k次）在到之间收敛到无穷大。
Letbe a Boolean function. We say that a multilinear polynomialpsign-representsfiffor all. In this paper, we consider the length and weight of polynomials sign-representing Boolean functions of the formwhere eachfis on a disjoint set of variables. Obviously, ifpsign-representsf, thenp(x)p(y) sign-represents. We give a constructive proof that there is a shorter polynomial whenfis AND onnvariables for every. In addition, we introduce a parameterof a Boolean function and show that thek-th root of the minimum weight of a polynomial sign-representing(ktimes) converges betweenandaskgoes to infinity.