Communication Complexity: And Applications
暫譯: 通訊複雜度及其應用

Rao, Anup, Yehudayoff, Amir

Communication Complexity: And Applications
  • 出版商: Cambridge
  • 出版日期: 2020-03-26
  • 售價: $2,400
  • 貴賓價: 9.5 折 $2,280
  • 語言: 英文
  • 頁數: 266
  • 裝訂: Hardcover - also called cloth, retail trade, or trade
  • ISBN: 1108497985
  • ISBN-13: 9781108497985

    • 立即出貨 (庫存=1)

買這商品的人也買了...

相關主題

商品描述

Communication complexity is the mathematical study of scenarios where several parties need to communicate to achieve a common goal, a situation that naturally appears during computation. This introduction presents the most recent developments in an accessible form, providing the language to unify several disjoint research subareas. Written as a guide for a graduate course on communication complexity, it will interest a broad audience in computer science, from advanced undergraduates to researchers in areas ranging from theory to algorithm design to distributed computing. The first part presents basic theory in a clear and illustrative way, offering beginners an entry into the field. The second part describes applications including circuit complexity, proof complexity, streaming algorithms, extension complexity of polytopes, and distributed computing. Proofs throughout the text use ideas from a wide range of mathematics, including geometry, algebra, and probability. Each chapter contains numerous examples, figures, and exercises to aid understanding.

  •  
  • Offers a modern guide to a growing, interdisciplinary field
  • Includes numerous illustrations, examples, and end-of-chapter exercises
  • Comments and notes provide context and pointers to further reading

商品描述(中文翻譯)

通訊複雜度是數學上研究多方需要溝通以達成共同目標的情境，這種情況在計算過程中自然會出現。本書的介紹以易於理解的形式呈現最新的發展，提供統一多個不相干研究子領域的語言。作為一門關於通訊複雜度的研究生課程指南，它將吸引廣泛的計算機科學讀者，從高年級本科生到研究理論、演算法設計及分散式計算等領域的研究人員。第一部分以清晰且具說明性的方式介紹基本理論，為初學者提供進入該領域的途徑。第二部分描述了包括電路複雜度、證明複雜度、串流演算法、多面體的擴展複雜度以及分散式計算等應用。全書的證明使用了來自廣泛數學領域的概念，包括幾何、代數和概率。每章包含大量的例子、圖形和練習題以幫助理解。

- 提供一個現代化的指南，涵蓋一個不斷增長的跨學科領域
- 包含大量插圖、例子和章末練習
- 評論和註釋提供背景資訊及進一步閱讀的指引

作者簡介

Anup Rao, University of Washington
Anup Rao is an Associate Professor at the School of Computer Science, University of Washington. He received his Ph.D. in Computer Science from the University of Texas, Austin, and was a researcher at the Institute for Advanced Study, Princeton. His research interests are primarily in theoretical computer science.

Amir Yehudayoff, Technion - Israel Institute of Technology, Haifa
Amir Yehudayoff is Associate Professor of Mathematics at Technion – Israel Institute of Technology, Haifa. He is interested in mathematical questions that are motivated by theoretical computer science and machine learning. He was a member of the Institute for Advanced Study in Princeton, and served as the secretary of the Israel Mathematical Union. He has won several prizes, including the Cooper Prize and the Krill Prize for excellence in scientific research, and the Kurt Mahler Prize for excellence in mathematics.

作者簡介(中文翻譯)

阿努普·拉奧，華盛頓大學

阿努普·拉奧是華盛頓大學計算機科學學院的副教授。他在德克薩斯大學奧斯汀分校獲得計算機科學博士學位，並曾在普林斯頓高等研究院擔任研究員。他的研究興趣主要集中在理論計算機科學。

阿米爾·耶胡達約夫，以色列理工學院，海法

阿米爾·耶胡達約夫是以色列理工學院（Technion）數學系的副教授。他對由理論計算機科學和機器學習所激發的數學問題感興趣。他曾是普林斯頓高等研究院的成員，並擔任以色列數學聯盟的秘書。他獲得過多個獎項，包括庫珀獎（Cooper Prize）和克里爾獎（Krill Prize）以表彰其在科學研究方面的卓越表現，以及庫爾特·馬勒獎（Kurt Mahler Prize）以表彰其在數學方面的卓越成就。

目錄大綱

Preface
Conventions and preliminaries
Introduction
Part I. Communication:
1. Deterministic protocols
2. Rank
3. Randomized protocols
4. Numbers on foreheads
5. Discrepancy
6. Information
7. Compressing communication
8. Lifting
Part II. Applications:
9. Circuits and proofs
10. Memory size
11. Data structures
12. Extension Complexity of Polytopes
13. Distributed computing.

目錄大綱(中文翻譯)

Preface

Conventions and preliminaries

Introduction

Part I. Communication:

1. Deterministic protocols

2. Rank

3. Randomized protocols

4. Numbers on foreheads

5. Discrepancy

6. Information

7. Compressing communication

8. Lifting

Part II. Applications:

9. Circuits and proofs

10. Memory size

11. Data structures

12. Extension Complexity of Polytopes

13. Distributed computing.

類似商品

最後瀏覽商品 (10)