Homogeneous Formulas and Symmetric Polynomials
Homogeneous Formulas and Symmetric Polynomials
复制标题
齐次公式和对称多项式
DOI：
10.1007/s00037-011-0007-3
复制
发表时间：
2009
影响因子：
1.4
通讯作者：
A. Yehudayoff
中科院分区：
文献类型：
--
作者：
P. Hrubes;A. Yehudayoff
我们研究了基本对称多项式的算术公式复杂性$$ {s^k_n} $$。我们表明，每个多线性均质公式计算$$ {s^k_n} $$的大小至少$$ {k^{k^{\ omega（\ log k）} n} $$，以及该产品深度depth d depth d depth d depth d多线性同质配方$$ {s^k_n} $$至少有大小$$ {2^{\ omega（k^{1/d}）} n} $$。由于$$ {s^{n} _ {2n}} $$具有大小O（n2）的多线性公式，因此我们获得了多线性和多线性均匀公式之间的超级单位分离。我们还表明，$$ {s^k_n} $$可以通过大小$$ {k^{o（\ log k）} n} $$的均质公式计算，回答了Nisan和Wigderson的问题。最后，我们在非共同环境中提出了单调和非单调公式之间的超级单位分离，回答了Nisan的问题。
We investigate the arithmetic formula complexity of the elementary symmetric polynomials $${S^k_n}$$ . We show that every multilinear homogeneous formula computing $${S^k_n}$$ has size at least $${k^{\Omega(\log k)}n}$$ , and that product-depth d multilinear homogeneous formulas for $${S^k_n}$$ have size at least $${2^{\Omega(k^{1/d})}n}$$ . Since $${S^{n}_{2n}}$$ has a multilinear formula of size O(n2), we obtain a superpolynomial separation between multilinear and multilinear homogeneous formulas. We also show that $${S^k_n}$$ can be computed by homogeneous formulas of size $${k^{O(\log k)}n}$$ , answering a question of Nisan and Wigderson. Finally, we present a superpolynomial separation between monotone and non-monotone formulas in the noncommutative setting, answering a question of Nisan.