Communication Complexity: A New Approach To Circuit Depth (acm Doctoral Dissertation Award)
by Mauricio Karchmer /
1989 / English / PDF
4.3 MB Download
Communication Complexity
Communication Complexity describes a new intuitive model for
studying circuit networks that captures the essence of circuit
depth. Although the complexity of boolean functions has been
studied for almost 4 decades, the main problems the inability to
show a separation of any two classes, or to obtain nontrivial lower
bounds remain unsolved. The communication complexity approach
provides clues as to where to took for the heart of complexity and
also sheds light on how to get around the difficulty of proving
lower bounds.
describes a new intuitive model for
studying circuit networks that captures the essence of circuit
depth. Although the complexity of boolean functions has been
studied for almost 4 decades, the main problems the inability to
show a separation of any two classes, or to obtain nontrivial lower
bounds remain unsolved. The communication complexity approach
provides clues as to where to took for the heart of complexity and
also sheds light on how to get around the difficulty of proving
lower bounds.
Karchmer's approach looks at a computation device as one that
separates the words of a language from the non-words. It views
computation in a top down fashion, making explicit the idea that
flow of information is a crucial term for understanding
computation. Within this new setting,
Karchmer's approach looks at a computation device as one that
separates the words of a language from the non-words. It views
computation in a top down fashion, making explicit the idea that
flow of information is a crucial term for understanding
computation. Within this new setting,Communication
Complexity
Communication
Complexity gives simpler proofs to old results and demonstrates
the usefulness of the approach by presenting a depth lower bound
for
gives simpler proofs to old results and demonstrates
the usefulness of the approach by presenting a depth lower bound
forst
st-connectivity. Karchmer concludes by proposing open
problems which point toward proving a general depth lower
bound.
-connectivity. Karchmer concludes by proposing open
problems which point toward proving a general depth lower
bound.
Mauricio Karchmer received his doctorate from Hebrew University and
is currently a Postdoctoral Fellow at the University of Toronto.
Communication Complexity received the 1988 ACM Doctoral
Dissertation Award.
Mauricio Karchmer received his doctorate from Hebrew University and
is currently a Postdoctoral Fellow at the University of Toronto.
Communication Complexity received the 1988 ACM Doctoral
Dissertation Award.
