Super-logarithmic depth lower bounds via the direct sum in communication complexity

Mauricio Karchmer; Ran Raz; Avi Wigderson

doi:10.1007/BF01206317

Super-logarithmic depth lower bounds via the direct sum in communication complexity

Mauricio Karchmer, Ran Raz, Avi Wigderson

Research output: Contribution to journal › Article › peer-review

76 Scopus citations

Abstract

Is it easier to solve two communication problems together than separately? This question is related to the complexity of the composition of boolean functions. Based on this relationship, an approach to separating NC ¹ from P is outlined. Furthermore, it is shown that the approach provides a new proof of the separation of monotone NC ¹ from monotone P.

Original language	English (US)
Pages (from-to)	191-204
Number of pages	14
Journal	Computational Complexity
Volume	5
Issue number	3-4
DOIs	https://doi.org/10.1007/BF01206317
State	Published - Sep 1 1995
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Mathematics(all)
Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.1007/BF01206317

Cite this

@article{7cafc646194c475da6a3156b790e9554,

title = "Super-logarithmic depth lower bounds via the direct sum in communication complexity",

abstract = " Is it easier to solve two communication problems together than separately? This question is related to the complexity of the composition of boolean functions. Based on this relationship, an approach to separating NC 1 from P is outlined. Furthermore, it is shown that the approach provides a new proof of the separation of monotone NC 1 from monotone P.",

author = "Mauricio Karchmer and Ran Raz and Avi Wigderson",

year = "1995",

month = sep,

day = "1",

doi = "10.1007/BF01206317",

language = "English (US)",

volume = "5",

pages = "191--204",

journal = "Computational Complexity",

issn = "1016-3328",

publisher = "Birkhauser Verlag Basel",

number = "3-4",

}

TY - JOUR

T1 - Super-logarithmic depth lower bounds via the direct sum in communication complexity

AU - Karchmer, Mauricio

AU - Raz, Ran

AU - Wigderson, Avi

PY - 1995/9/1

Y1 - 1995/9/1

N2 - Is it easier to solve two communication problems together than separately? This question is related to the complexity of the composition of boolean functions. Based on this relationship, an approach to separating NC 1 from P is outlined. Furthermore, it is shown that the approach provides a new proof of the separation of monotone NC 1 from monotone P.

AB - Is it easier to solve two communication problems together than separately? This question is related to the complexity of the composition of boolean functions. Based on this relationship, an approach to separating NC 1 from P is outlined. Furthermore, it is shown that the approach provides a new proof of the separation of monotone NC 1 from monotone P.

UR - http://www.scopus.com/inward/record.url?scp=21344463185&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=21344463185&partnerID=8YFLogxK

U2 - 10.1007/BF01206317

DO - 10.1007/BF01206317

M3 - Article

AN - SCOPUS:21344463185

SN - 1016-3328

VL - 5

SP - 191

EP - 204

JO - Computational Complexity

JF - Computational Complexity

IS - 3-4

ER -

Super-logarithmic depth lower bounds via the direct sum in communication complexity

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this