论文标题
比较通信协议
Comparison communication protocols
论文作者
论文摘要
我们介绍了经典2方确定性通信协议的限制，其中爱丽丝和鲍勃仅限于使用比较功能。我们表明，模型中函数的复杂性是最高恒定因素，由类似于Yao的瓷砖数字的复杂度度量确定，我们称之为几何瓷砖数字，可以在多项式时间内计算出来。作为热身，我们考虑了一个类似的限制决策树模型，并观察到上述结果的一维类似物。
We introduce a restriction of the classical 2-party deterministic communication protocol where Alice and Bob are restricted to using only comparison functions. We show that the complexity of a function in the model is, up to a constant factor, determined by a complexity measure analogous to Yao's tiling number, which we call the geometric tiling number which can be computed in polynomial time. As a warm-up, we consider an analogous restricted decision tree model and observe a 1-dimensional analog of the above results.
