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

82 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 1995
Externally published	Yes

All Science Journal Classification (ASJC) codes

Computational Mathematics
Theoretical Computer Science
Computational Theory and Mathematics
General Mathematics

Keywords

Lower-bound
Subject classifications: 68Q15, 68Q25
circuit
complexity
direct-sum

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 NC1 from P is outlined. Furthermore, it is shown that the approach provides a new proof of the separation of monotone NC1 from monotone P.",

keywords = "Lower-bound, Subject classifications: 68Q15, 68Q25, circuit, complexity, direct-sum",

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

year = "1995",

month = sep,

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

Y1 - 1995/9

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 NC1 from P is outlined. Furthermore, it is shown that the approach provides a new proof of the separation of monotone NC1 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 NC1 from P is outlined. Furthermore, it is shown that the approach provides a new proof of the separation of monotone NC1 from monotone P.

KW - Lower-bound

KW - Subject classifications: 68Q15, 68Q25

KW - circuit

KW - complexity

KW - direct-sum

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

Keywords

Access to Document

Other files and links

Fingerprint

Cite this