PRIVATE VS COMMON RANDOM BITS IN COMMUNICATION COMPLEXITY

被引：175
作者：
NEWMAN, I
机构：
[1] Computer Science Department, Hebrew University, Jerusalem
来源：
INFORMATION PROCESSING LETTERS | 1991年 / 39卷 / 02期
关键词：
THEORY OF COMPUTATION; COMMUNICATION COMPLEXITY; RANDOMNESS;
D O I：
10.1016/0020-0190(91)90157-D
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We investigate the relative power of the common random string model vs. the private random string model in communication complexity. We show that the two model, are essentially equal.
引用
收藏
页码：67 / 71
页数：5
相关论文
共 13 条
[1]  
ADLEMAN L, 19TH P ANN IEEE S F, P75
[2]  
Babai L., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P337, DOI 10.1109/SFCS.1986.15
[3]  
CANETTI R, 1990, 31ST P ANN IEEE S F, P767
[4]  
HOEFFDING W, 1963, AM STAT ASS J, P13
[5]  
HOFRI M, 1987, PROBABILISTIC ANAL A, P104
[6]  
KARCHMER M, 1988, 20TH P ANN ACM S THE, P539
[7]  
KRIZANC D, 1988, 20TH P ANN ACM S THE, P93
[8]  
LOVASZ L, 1990, PATH FLOWERS VLSI
[9]  
RAZ R, 1989, 30TH P ANN IEEE S F, P562
[10]  
RAZ R, 1990, 22ND P ANN ACM S THE, P287
12