论文标题
多党Karchmer-Wigderson游戏和阈值电路
Multiparty Karchmer-Wigderson Games and Threshold Circuits
论文作者
论文摘要
我们建议将Karchmer-Wigderson通信游戏概括为多方设置。事实证明，我们的概括与由阈值大门组成的电路紧密连接。这使我们能够为多种功能获得此类电路的新构造。特别是，我们为多数功能提供了明确的（多项式时间计算）对数深度单调公式，仅由3位多数门和变量组成。这解决了Cohen等人的猜想。 （加密2013）。
We suggest a generalization of Karchmer-Wigderson communication games to the multiparty setting. Our generalization turns out to be tightly connected to circuits consisting of threshold gates. This allows us to obtain new explicit constructions of such circuits for several functions. In particular, we provide an explicit (polynomial-time computable) log-depth monotone formula for Majority function, consisting only of 3-bit majority gates and variables. This resolves a conjecture of Cohen et al. (CRYPTO 2013).
