Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Kushilevitz E., Nisan N. — Communication Complexity
Kushilevitz E., Nisan N. — Communication Complexity



Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


Название: Communication Complexity

Авторы: Kushilevitz E., Nisan N.

Аннотация:

Many aspects of the internal and external workings of computers can be viewed, at different levels, as a series of communication processes. Communication complexity is the mathematical theory of such communication processes. It is also often used as an abstract model of other aspects of computation. It extends Shannon's information theory, allowing two-way communication and arbitrary processes. This book surveys this mathematical theory, concentrating on the question of how much communication is necessary for any particular process.
The first part of the book is devoted to the simple two-party model introduced by Yao in 1979, which is still the most widely studied model. The second part treats newer models, such as variable partition models, communication complexity of relations, and multiparty protocols, developed to deal with more complicated communication processes. Finally, applications of these models, including Turing machines, boolean circuits, computer net-works, VLSI circuits, pseudorandomness, and data structures, are treated in the third part of the book. In particular, communication arguments are used to prove lower bounds for many problems arising in these areas.
This is an essential resource for graduate students and researchers in theoretical computer science, circuits, networks, VLSI, and information theory.


Язык: en

Рубрика: Технология/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1997

Количество страниц: 189

Добавлена в каталог: 08.07.2006

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
$\textrm{ACC}^0$ circuits      93 136
$\textrm{SYM}^+$ circuits      136
$\varepsilon$-error protocol      29
Abelian group      163
ACC circuits      136
Associativity      163
Asymmetric communication      53
Best partition      99 144
Binomial coefficients      63 167
Binomial distribution      92
Boolean circuit      119 135
Branching program      143 158
Cauchy — Schwartz inequality      75 91 166
Center (of a star)      85
Chemoff inequality      30 34 65 73 166 169 171
Chromatic number      65
Circuit depth      74 120
Circuit size      134
CLIQUE      6
Coloring      65 87
Column rank      164
Commutativity      163
Completeness      58
Constant-depth circuits      128
Cover      11 16 19 21 22 24 59 126 169
Cover number      17 24
Cylinder      85
Cylinder intersection      85 89
Database      157
Decision tree      131
Deterministic communication complexity      4 9 13 20—22 25 30 31 34 42 46 49 71 73 74 97 126 140 142
Dimension (linear)      13 55 164
Direct-sum      42 66 82
Discrepancy      38 89 91 152
Disjointness function (DISJ)      11 14 26 37 54 56 58 59 73 76 78 102 175
Disjunctive normal form      120
distributed system      157
Distributional communication complexity      35 37 39 40 49 50 56 59 148
Distributive law      163
Duality theorem      45 171
Eigenvalues      39 57 166
Element distinctness function (ED)      101 146
entropy      63 95 167
Equality function (EQ)      11 13 14 19 24 30—33 41 43 47 49 54 58 73 84 89 98 102 133 141 143 158
Euclidean distance      159
Exactly-N function $(E^k_N)$      87 93
Expander graph      67
Fan-in (bounded)      128 135
Fan-in (unbounded)      128 136
Field      13 27 30 48 163
Finite automata      142
Finite control      139
Fooling set      11 19 47 170
Fooling set lower bound      25 47 54 72 74
Formal verification      144
Formula      119
Formula size      120 123 128
Gate $(\textrm{MOD}_m$      136
Gate (AND)      119 122 128
Gate (OR)      119 121 128
Generalized equality function $(\textrm{EQ}^k_n)$      83 84 187
Generalized inner product function $(\textrm{GIP}^k_n)$      83 90 134 137
Geometric rectangle      10 23
Graph      6 56 103 124 126 148 169 174
Graph (directed)      53 119 125 131
Graph (leveled)      143
Greater than function (GT)      11 14 19 32 35 54 98 132
Group      163
Hadamard matrix      40
Hamming distance      64 73 75 76
Hash function      65
Hoeffding inequality      73 166
Hypergraph      65
Identity element      163
Incidence matrix      56
Independent set      6 124 169
Index function (INDEX)      49 93
Information theory      64
Inner product function (IP)      12 14 25 27 33 39 44 48 54 76 84 90 115 133 134 150 154 165 174
Inverse      163
k-disjointness function $(\textrm{DISJ}_k)$      22 34 35
k-round protocol      49 59 64
k-round protocols      128
Kronecker product      47 165
Language      141 151
Las-Vegas protocol      28
Length (of a branching program)      144
linear combination      164
Linear independence      164
Linear programming      45 171
Linear span      12 55 164
List-non-equality function (LNE)      43 44 47 127
logic design      144
majority      84 124
Majority function $(\textrm{MAJ}_m)$      98 99 101 146
Majority relation $(\textrm{R}_{\textrm{MAJ}})$      76
Markov inequality      52 166
Matching      124 174
Matching function (MATCH)      124
Matrix-vector product      157
Median problem (MED)      6 168
Monochromatic rectangle      9 10 12 13 16 17 20 24 26 45 54 57 72 75 122 126 169 172
Monotone circuit      119 124 126 128
Monotone function      120 123—125 135
Monte-Carlo protocol      28
Multiparty communication complexity      84 89 92 133 134 137 141
n-best partition      101 145
NBA problem      64
Noisy channels      156
Non-equality function (NE)      24 31—33 46 47 74
Nondeterministic automaton      142
Nondeterministic communication complexity      18 20 21 24 26 31 32 45 46 59 71 74 89 126 169
Nondeterministic Turing machine      141 143
Norm      39 165
Norm (Euclidean)      165
NP      27 58 127
Number on the forehead model      83 98
One sided error protocol      29 34 35 46 55 170
One-round protocol      48 50 64 93
One-tape Turing machine      142
One-way communication      156
Ordered Binary Decision Diagram (OBDD)      144
Orthogonal spaces      12 165
Pair-disjointness relation      77 124
Palindrome      98 141 143
Palindrome function $(\textrm{PAL}_m)$      98 99
Parity      76 121 124 144
Parity relation $(\textrm{R}_\oplus)$      74
Partial functions      77
Partition      7 9 10 12 13 16 35 37 57 72 75 87 122 128
Partition number      17 25 75 172
Pointer jumping function $(\textrm{PJ}_k)$      53
Privacy      157
Probabilistic method      22 34 40 65 81 85 148 169
Product function (PROD)      100 174
Protocol      4 71 84
Protocol partition number      17 19 123 128
Protocol tree      4 7 17 19 28 32 84 87 122 156 158
Pseudorandom generator      56 150
Public coin      32 36 43 44 46 50 57 73 76 77 79 89 133 142 149 170
Quasirandom graphs      148
Ramanujan graphs      57
Ramsey theory      87
Random graph      148 188
Randomized communication complexity      30—32 37 40 43 48 49 59 73 76 79 89 92 103
Rank      13 18 22 164
Rank lower bound      13 22 24 25 47 54 63 74
rectangle      7 85
Rectangle size bound      24 45 172
Rectangle size lower bound      12 24 25 38 54 72 74
Rectangular (product) distribution      37 63
Reducibility      58
Relation      71 121
Richness      54
Ring      93
Row rank      164
s-t-connectivity function (STCON)      125
s-t-connectivity function (undirected) (USTCON)      103 174
Set-cover problem      127
Shifted equality function (SEQ)      99 101 145 174
Simultaneous protocols      49 92 135 137
SINDEX function      136
Slightly random sources      152
Space (of a processor)      156
Space (of a Turing machine)      139
Span function (SPAN)      55
Star      85
Statistical distance      148 150 152 154 167
Stirling formula      167
SUM-INDEX function      94 157
Support      167
Tape (of a Turing machine)      139
Threshold circuit      132
Threshold function $(\textrm{TH}^k_m)$      98
Threshold functions      134
Threshold gate      132 133
Time (of a Turing machine)      139 143
Time-space tradeoff      141
TRANSPOSE      166
Tree problem $(\textrm{T}_k)$      53 59 128
Turing machine      139
Two sided cards      158
Undirected s-t-connectivity function (USTCON)      126
Uniform distribution      12 24 37 38 148 149 152 165
Universal monotone relation $(\textrm{U}_m)$      76
Universal relation (U)      74 76
Variation distance      167
Vector space      55 163
VLSI      103
Width (of a branching program)      144
Width-length tradeoff      145 158
Worst partition      97 114 131
Zero error      143
Zero error protocol      29 34—36 44 76 142
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2024
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте