机构名称：
¥ 2.0
通信复杂性研究计算一个函数所需的通信量，该函数的值取决于分布在多个实体之间的信息。姚期智 [Yao79] 于 40 多年前发起了通信复杂性研究，如今它已成为理论计算机科学的核心领域，在数据结构、流算法、属性测试、近似算法、编码理论和机器学习等不同领域都有广泛应用。教科书 [KN06,RY20] 对该理论及其应用进行了出色的概述。在通信复杂性的基本版本中，两个玩家，分别称为 Alice 和 Bob，希望计算一个函数 F : X × Y →{ 0 , 1 }，其中 X 和 Y 是一些有限集。Alice 持有一个输入 x ∈ X，Bob 持有一个输入 y ∈ Y，他们希望通过按照某种协议来回发送消息来计算 F(x, y)。重要的是，Alice 和 Bob 具有任意的计算能力，因为我们只关心计算该函数需要交换多少信息。目标是设计低成本协议，以 Alice 和 Bob 交换的位数来衡量（在最坏情况下），理想情况下，我们会显示感兴趣的通信问题的通信复杂度的严格上限和下限。让 D cc ( F ) 表示确定性协议在所有输入上正确计算 F 的最低可实现成本。
嘉宾专栏：决策树与通信之间的计算模型 1
主要关键词
相关文件推荐
