| 000 | 03307nam a2200553 i 4500 | ||
|---|---|---|---|
| 001 | 6267292 | ||
| 003 | IEEE | ||
| 005 | 20220712204621.0 | ||
| 006 | m o d | ||
| 007 | cr |n||||||||| | ||
| 008 | 151229s1989 mau ob 001 eng d | ||
| 010 | _z 89034499 (print) | ||
| 016 | _z 900034262 (print) | ||
| 020 |
_a9780262256490 _qelectronic |
||
| 020 |
_z9780262611886 _qprint |
||
| 020 |
_z0262111438 _qprint |
||
| 035 | _a(CaBNVSL)mat06267292 | ||
| 035 | _a(IDAMS)0b000064818b4286 | ||
| 040 |
_aCaBNVSL _beng _erda _cCaBNVSL _dCaBNVSL |
||
| 050 | 4 |
_aQA10.3 _b.K37 1989eb |
|
| 082 | 0 |
_a511.3/24 _220 |
|
| 100 | 1 |
_aKarchmer, Mauricio, _eauthor. _921974 |
|
| 245 | 1 | 0 |
_aCommunication complexity : _ba new approach to circuit depth / _cMauricio Karchmer. |
| 264 | 1 |
_aCambridge, Massachusetts : _bMIT Press, _cc1989. |
|
| 264 | 2 |
_a[Piscataqay, New Jersey] : _bIEEE Xplore, _c[1989] |
|
| 300 | _a1 PDF (68 pages). | ||
| 336 |
_atext _2rdacontent |
||
| 337 |
_aelectronic _2isbdmedia |
||
| 338 |
_aonline resource _2rdacarrier |
||
| 490 | 1 | _aAcm doctoral dissertation award | |
| 502 | _aThesis (doctoral)--Hebrew University, 1988. | ||
| 504 | _aIncludes bibliographical references (p. )[65]-66. | ||
| 506 | 1 | _aRestricted to subscribers or individual electronic text purchasers. | |
| 520 | _aCommunication 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.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 gives simpler proofs to old results and demonstrates the usefulness of the approach by presenting a depth lower bound for st-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. | ||
| 530 | _aAlso available in print. | ||
| 538 | _aMode of access: World Wide Web | ||
| 588 | _aDescription based on PDF viewed 12/29/2015. | ||
| 650 | 0 |
_aAlgebra, Boolean. _921975 |
|
| 650 | 0 |
_aLogic circuits. _93501 |
|
| 650 | 0 |
_aComputational complexity. _93729 |
|
| 650 | 0 |
_aAutomatic theorem proving. _921976 |
|
| 655 | 0 |
_aElectronic books. _93294 |
|
| 710 | 2 |
_aIEEE Xplore (Online Service), _edistributor. _921977 |
|
| 710 | 2 |
_aMIT Press, _epublisher. _921978 |
|
| 776 | 0 | 8 |
_iPrint version: _z9780262611886 |
| 830 | 0 |
_aAcm doctoral dissertation award _921979 |
|
| 856 | 4 | 2 |
_3Abstract with links to resource _uhttps://ieeexplore.ieee.org/xpl/bkabstractplus.jsp?bkn=6267292 |
| 942 | _cEBK | ||
| 999 |
_c72949 _d72949 |
||