Communication complexity : (Record no. 72949)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 03307nam a2200553 i 4500 |
| 001 - CONTROL NUMBER | |
| control field | 6267292 |
| 005 - DATE AND TIME OF LATEST TRANSACTION | |
| control field | 20220712204621.0 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 151229s1989 mau ob 001 eng d |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| ISBN | 9780262256490 |
| -- | electronic |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| -- | |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| -- | |
| 082 0# - CLASSIFICATION NUMBER | |
| Call Number | 511.3/24 |
| 100 1# - AUTHOR NAME | |
| Author | Karchmer, Mauricio, |
| 245 10 - TITLE STATEMENT | |
| Title | Communication complexity : |
| Sub Title | a new approach to circuit depth / |
| 300 ## - PHYSICAL DESCRIPTION | |
| Number of Pages | 1 PDF (68 pages). |
| 490 1# - SERIES STATEMENT | |
| Series statement | Acm doctoral dissertation award |
| 520 ## - SUMMARY, ETC. | |
| Summary, etc | 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.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. |
| 856 42 - ELECTRONIC LOCATION AND ACCESS | |
| Uniform Resource Identifier | https://ieeexplore.ieee.org/xpl/bkabstractplus.jsp?bkn=6267292 |
| 942 ## - ADDED ENTRY ELEMENTS (KOHA) | |
| Koha item type | eBooks |
| 264 #1 - | |
| -- | Cambridge, Massachusetts : |
| -- | MIT Press, |
| -- | c1989. |
| 264 #2 - | |
| -- | [Piscataqay, New Jersey] : |
| -- | IEEE Xplore, |
| -- | [1989] |
| 336 ## - | |
| -- | text |
| -- | rdacontent |
| 337 ## - | |
| -- | electronic |
| -- | isbdmedia |
| 338 ## - | |
| -- | online resource |
| -- | rdacarrier |
| 588 ## - | |
| -- | Description based on PDF viewed 12/29/2015. |
| 650 #0 - SUBJECT ADDED ENTRY--SUBJECT 1 | |
| -- | Algebra, Boolean. |
| 650 #0 - SUBJECT ADDED ENTRY--SUBJECT 1 | |
| -- | Logic circuits. |
| 650 #0 - SUBJECT ADDED ENTRY--SUBJECT 1 | |
| -- | Computational complexity. |
| 650 #0 - SUBJECT ADDED ENTRY--SUBJECT 1 | |
| -- | Automatic theorem proving. |
No items available.