Communication complexity (for algorithm designers)
By: Roughgarden, Tim
Language: English Publisher: United States of America -- Now Publishers -- 2016Description: xii, 193pISBN: 9781680831146Subject(s): Computer science | Computer algorithms Design | Design and analysis of algorithmsDDC classification: 004.6 ROU/C Summary: The two primary goals of the text are to learn several canonical problems in communication complexity that are useful for proving lower bounds for algorithms (Disjointness, Index, Gap-Hamming, and so on); and to learn how to reduce lower bounds for fundamental algorithmic problems to communication complexity lower bounds.
| Item type | Current location | Collection | Call number | Status | Date due | Barcode |
|---|---|---|---|---|---|---|
Book
|
Central Library General Stack (Nila Campus) | 004.6 ROU/C | Available | 07975 | ||
|
Book
|
Central Library General Stack (Nila Campus) | 004.6 ROU/C | Available | 07973 | ||
|
Book
|
Central Library General Stack (Nila Campus) | 004.6 ROU/C | Available | 07972 | ||
|
Book
|
Central Library General Stack (Nila Campus) | 004.6 ROU/C | Available | 07974 | ||
Reference
|
Central Library Reference (Sahyadri Campus) | Reference | 004.6 ROU/C | Not for loan | 07971 |
Preface1: Data Streams: Algorithms and Lower Bounds2: Lower Bounds for One Way Communication: Disjointness, Index, and Gap-Hamming3: Lower Bounds for Compressive Sensing4: Boot Camp on Communication Complexity5: Lower Bounds for the Extension Complexity of Polytopes6: Lower Bounds for Data Structures7: Lower Bounds in Algorithmic Game Theory8: Lower Bounds in Property TestingReferences
The two primary goals of the text are to learn several canonical problems in communication complexity that are useful for proving lower bounds for algorithms (Disjointness, Index, Gap-Hamming, and so on); and to learn how to reduce lower bounds for fundamental algorithmic problems to communication complexity lower bounds.