通信复杂性简介

文艺复兴以来，源远流长的科学精神和逐步形成的科学规范，使西方国家在自然科学的各个领域取得了垄断性的优势；也正是这样的优势，使美国在信息技术发展的六十多年间名家辈出、独领风骚。
-----机械工业出版社

一.双方通信复杂性

以确定性协议为例：
A protocol $\pi$π ==> a rooted binary tree
协议在输入(x,y)上的输出结果对应二叉树上的叶子

树的长度：根节点到叶子结点的最长路径。
函数g的通信复杂性：计算g的协议树的最小长度。

二.单色矩形

协议树中的所有叶子结点对应的矩形形成了一个$X \times Y$X×Y的划分。
定理：如果g的通信复杂性为$c$c,则$X \times Y$X×Y被划分成最多$2^c$2c个单色矩形。

三.Communication Complexity and Rank

居中并且带尺寸的图片:

函数g对应一个矩阵

Theorem. The communication complexity of $M$M is at most $rank(M) + 1$rank(M)+1.

Theorem. If M is not the all 1’s matrix, then the communication complexity of $M$M is at least $\log(rank(M) + 1)$log(rank(M)+1).

四.The Lifting Theorem

决策树复杂性（即查询复杂性）：
A decision tree is an extremely simple model of computation. It captures the complexity of an algorithm that reads the input bit by bit. The only cost paid is the number of bits read by the algorithm.

The Lifting Theorem：基于决策树复杂性的下界得到通信复杂性的下界。