Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
复制标题
通信复杂性高或从两个通信半随机源生成准随机序列
DOI：
--
复制
发表时间：
1987
期刊：
影响因子：
--
通讯作者：
U. Vazirani
中科院分区：
文献类型：
--
作者：
U. Vazirani
半随机源由S和瓦齐拉尼定义，是不完美的和相关的随机源(物理源，如噪声码元)的一般数学模型。本文提出了一种从两个独立的半随机信源高效地产生“高质量”随机序列(准随机比特序列)的算法。提取“高质量”比特的一般问题与通信复杂性理论有关，由此引出了布尔函数强通信复杂性的定义。证明了强通信复杂性类的一个层次定理，这使得以前的算法被推广到可以从两个通信半随机源产生准随机序列的算法
The semi-random source, defined by Sántha and Vazirani, is a general mathematical mode for imperfect and correlated sources of randomness (physical sources such as noise dicdes). In this paper an algorithm is presented which efficiently generates “high quality” random sequences (quasirandom bit-sequences) from two independent semi-random sources. The general problem of extracting “high quality” bits is shown to be related to communication complexity theory, leading to a definition of strong communication complexity of a boolean function. A hierarchy theorem for strong communication complexity classes is proved; this allows the previous algorithm to be generalized to one that can generate quasi-random sequences from two communicating semi-random sources