On (Valiant's) Polynomial-Size Monotone Formula for Majority
On (Valiant's) Polynomial-Size Monotone Formula for Majority
复制标题
关于多数数的（Valiant）多项式大小单调公式
DOI：
10.1007/978-3-030-43662-9_3
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Oded Goldreich
中科院分区：
文献类型：
--
作者：
Oded Goldreich
这一论述提供了一个证明的存在性多项式大小的单调公式的多数。论述遵循Valiant的证明（J. Algorithms，1984）的主要原则，但在实际实现中偏离了它。具体来说，我们证明了，当树的每个叶子被随机分配n个值中的一个时，深度为\（2.71\log_2n\）的完整三元树以很高的概率计算n个值中的大多数。
This exposition provides a proof of the existence of polynomial-size monotone formula for Majority. The exposition follows the main principles of Valiant’s proof (J. Algorithms, 1984), but deviates from it in the actual implementation. Specifically, we show that, with high probability, a full ternary tree of depth \(2.71\log _2n\) computes the majority of n values when each leaf of the tree is assigned at random one of the n values.