LOWER BOUNDS ON COMMUNICATION COMPLEXITY

被引：29
|
作者：
DURIS, P
GALIL, Z
SCHNITGER, G
机构：
[1] COLUMBIA UNIV,NEW YORK,NY 10027
[2] TEL AVIV UNIV,IL-69978 TEL AVIV,ISRAEL
[3] PENN STATE UNIV,UNIVERSITY PK,PA 16802
来源：
INFORMATION AND COMPUTATION | 1987年 / 73卷 / 01期
关键词：
* Research supported by National Science Foundation Grants MCS-83-03139 and DCR-85-11713. ’ All logarithms;
D O I：
10.1016/0890-5401(87)90037-X
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
引用
收藏
页码：1 / 22
页数：22
相关论文
共 50 条
  • [1] Lower Bounds in Communication Complexity
    Lee, Troy
    Shraibman, Adi
    FOUNDATIONS AND TRENDS IN THEORETICAL COMPUTER SCIENCE, 2007, 3 (04): : 263 - 399
  • [2] Lower bounds for quantum communication complexity
    Klauck, H
    42ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2001, : 288 - 297
  • [3] Lower bounds on the multiparty communication complexity
    Duris, P
    Rolim, JDP
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1998, 56 (01) : 90 - 95
  • [4] Communication complexity lower bounds by polynomials
    Buhrman, H
    de Wolf, R
    16TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2000, : 120 - 130
  • [5] Lower bounds for quantum communication complexity
    Klauck, Hartmut
    SIAM JOURNAL ON COMPUTING, 2007, 37 (01) : 20 - 46
  • [6] Communication complexity and lower bounds on multilective computations
    Hromkovic, J
    RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 1999, 33 (02): : 193 - 212
  • [7] Lower bounds on quantum multiparty communication complexity
    Lee, Troy
    Schechtman, Gideon
    Shraibman, Adi
    PROCEEDINGS OF THE 24TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, 2009, : 254 - +
  • [8] Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness
    Rao, Anup
    Yehudayoff, Amir
    30TH CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC 2015), 2015, 33 : 88 - 101
  • [9] Hadamard tensors and lower bounds on multiparty communication complexity
    Ford, Jeff
    Gal, Anna
    COMPUTATIONAL COMPLEXITY, 2013, 22 (03) : 595 - 622
  • [10] Hadamard tensors and lower bounds on multiparty communication complexity
    Jeff Ford
    Anna Gál
    computational complexity, 2013, 22 : 595 - 622
12345