Cover T.M., Gopinath B. — Open problems in communication and computation :: Электронная библиотека попечительского совета мехмата МГУ

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

Авторизация

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

Cover T.M., Gopinath B. — Open problems in communication and computation

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

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

Название: Open problems in communication and computation

Авторы: Cover T.M., Gopinath B.

Аннотация:

The papers in this volume are the contributions to a special workshop on problems in communication and computation conducted in the summers of 1984 and 1985 in Morristown, New Jersey, and the summer of 1986 in Palo Alto, California. The structure of this workshop was unique: no recent results, no surveys. Instead, we asked for outstanding open prob- problems in the field. There are many famous open problems, including the question P = NP?, the simplex conjecture in communication theory, the capacity region of the broadcast channel, and the two-helper problem in information theory.

Язык:

Рубрика: Computer science/Теория информации/

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

ed2k: ed2k stats

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

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

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

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

Abnormal linear code      54
Additive Gaussian noise channel      70
Algorithmic information content      see “Program-size complexity”
Algorithmic information theory      108
Alphabet      50 84
Amplitude-constrained pulse      46
Asynchronous cellular arrays      120—121
Asynchronous computation      161—162
Average case complete problems      106
Average mutual information      75—76
Bayes rules      85—91
Berlekamp — Massey algorithm      114—115
Berlekamp's light-bulb game      51—55
Berry paradox      110—111
Binary decision trees      145—146
Binary questions      154 210—216
Binary trees      130—137
Boolean functions      57—58 77—82 217—219
Bounded functions      32—34 46—48 191—198
Boxcar spectrum      47—48 191—193
Broadcast channel, capacity region      39
Broadcast networks      60—62 208—209
Brownian motion      155 204—207
Brunn — Minkowski inequality      172
Busy Beaver function      108—111
Call attempts      64—68
Call rearrangement      100
Cantor's diagonal construction      109
Catalan numbers      131—132
Cayley — Hamilton theorem      114—115
Cellular arrays      120—121
Cellular Automata Machine simulator      120
Cellular radio      100—101
Cesaro convergence      194
Channel input/output      93—94
Circuit simulation      80—82
Circuit switching      63
Circuit-switched network      68
clocks      122
codes      51—55 59 145—146
Collatz problems      25—26
Combinatorial complexity      77—78
Communication complexity      123—124 144
Complexity problems      57—58
Compositional complexity      78
concurrency control      63
conflict resolution      210—216
Conjugate gradient      114
Continued fraction algorithm      115
Coordination complexity      217—218
Coppersmith, Odlyzko, and Schroeppel algorithm      115
Correlation inequalities      40
Cost      78—79
Covering radii      50—55
Cryptography      106
Cryptosystems      113
Cyclic codes      55
Data processing inequality      75
decision-making      49—50 77 78
Digital signature schemes      138
Discrete logarithms      113—116
Discrete memoryless channel (DMC)      29 59 72—73
Discrete memoryless models      32
Distributed shortest path algorithms      123—124
Divergence characterization      30
Dynamic programming      154
Dynamic routing      63
Electrical conductivity      164
Electrical tomography      see “Tomography”
entropy      77—78 79 82
Entropy characterization      29 30
Entropy power inequality      172
Equidistribution      41
Ergodic convergence theorem      201
Ergodic process selection      153 199—203
Ergodic processes      38 192
Factorization      113—119
Fast algorithms      107 113
Faster binary signaling (FBS)      98
Feedback      40 70—71
Fermat's conjecture      109—110
Figure-ground problem      171
Filter transfer function      46
First-order Reed — Muller codes      55
Flip distance      132—133
Flow patterns      165
Fourier transform      46
FRACTRAN      3—26
Fredman — Komlos proof      32 33
Frequency assignment, cellular radio      100—101
Frobenius — Perron theorem      184
Fuch's inequality      129
Gacs — Reif model      120
Gaussian channels      44 70—71
Gaussian elimination      113
Gaussian random process      48
Generic rank      158—159
Gibbs random fields      38
Goedel's incompleteness theorem      110—111
Goldbach conjecture      109—110
Graph entropy      32 33
Graph theory      49—50
Halting problem      109 110—111
Hamming weight      145
Hardness      106 107
Highly distributed information      60—62
Image size characterization      29 30
Independent sets      142—143
Information divergence      85—91
Information rate      96—98
Interacting particle systems      63
Inverting      107
Irrationality measure for $\pi$       20
Jamming      30
Justesen code      107
Klawe's configuration      101
Kleene's normal form theorem      25
Knapsacks      113 117—119
Kolmogorov forward equation      148
Kolmogorov — Chaitin complexity      78
Kullback — Leibler divergence      30 37 85—91
Lanczos algorithms      114
Laplace's equation      167
Light-bulb game      51—55
Linear programming (LP)      96 101
Linear separability      156—157
Lyapunov stability, time-varying linear systems      161
Magnetic media storage      46
Markov processes      64 66 122 148
Martingale convergence theorem      201
Martingales      87 201
Matrices, stability of products      161—163

Maximally separated signals      92—98
Maximum entropy (ME) principle      37—38
Maximum matching problem      147—150
MEX machines      217—218
Microwave radio links      46
Minimum discrimination principle      see “Maximum entropy (ME) principle”
Minimum hop problem      123—124
Moment constraints      153n.
Monotone Boolean functions      57—58
Morrison — Brillhart algorithms      118
Multilevel Nyquist signaling (MNS)      97—98
Multiple access protocols      210—211
Multiuser information theory      29—30 39—40 60
Multivariate polynomial equations      138
networks      60—62 63—68
Networks, flow      158—159
Networks, in tomography      164—170
Networks, instability      63—68
Noise      60—62 144 208—209
Noiseless coding      40
Nonprobabilistic channels      39
Normal form      77—82
NP-complete problems      106
Nyquist rate      97—98
One-dimensional network      64—66
One-way functions      104—105
Optical communication channels      43—45
Optimum pulse shaping      95—96
Optimum sequence of questions      154 210—216
Optimum signaling rate      96—98
Optional sampling theorem      204
Orbital codes      59
Packet-Switched Network      68
Partial statistics      84
Pattern recognition      77—82
Perfect cubes      117
Perfect hashing      32—34 127n
Permanent inequality      127—129
Phase transition      63
Poisson kernel      205
Poisson process      43
Pomerance quadratic sieve      115
Predictive density      89—90
Probability density functions      85—91
probability distribution      155
Program-size complexity      108—111
Pulse amplitude modulated (PAM) signals      95—96
Queueing      68 139—141
Random access strategies      127—129
Random pairs      156
random selection      41
Random walks      155 204—207
Rate-Distortion function      59
Read/write complexities      145—146
Receiver noise model      61
Reed — Muller codes      55
Relative entropy      see “Kullback — Leibler divergence”
Relay channel capacity      72—73
Reliable communication      60—62 208—209
Reliable computation      120—121
resistors      165—167
Reyneri cubic sieve      118
Rhythm      171
Riemann hypothesis      109—110
Ring networks      62
Rotation distance      130—137
RSA Signature Scheme      113 138
Rudin — Shapiro polynomials      143
Sample partitioning      154 210—216
Saturation      125
Schnorr — Lenstra algorithm      115
Schroeppel linear sieve      115
Schwartz — Christoffel formula      205
Scope      125—126
Secretary problem      152
Selection functions      153
Selection strategies      199—203
Self-adjusting search trees      133
Shannon's entropy      78 79
Shannon's Information Theory      29—30 60
Shifts      144
Shortest path problem      123—124
Signal sets      43—45
Simplex conjecture      74 155 204—207
Simulated annealing      147—150
Single-letterization      29 35—36 39
Small primes      117—118
Smooth integers      117—118
Sound      171
Sparse systems      114
Spectral density      46—48 191—198
Splitting numbers      152
State trajectories      140
Stationary distributions      63—68
Stationary random process      46 47
Statistical mechanics      149—150
Stochastic decision problems      49—50
Stochastic processes      191 —198
Stochastic relaxation      147—150
Straight-line (SL) algorithms      104—105
Strassen' s algorithm      113
Strings, derivation, generation, and parsing      173—188
Structurally fixed modes      158—160
Structured matrices      158—160
Team decision problem      49—50
Threshold detection system      145—146
Tiling      106 142—143
Time complexity      124
Time-varying linear systems      161
Tomography      164—168
Toom's rule      121
Transmitter noise model      61—62
Transversals      40
Trapdoor functions      107
Tree network      62 67
Triangulation      132—136
Trigonometric polynomials      142—143
Turing Machines      79 104—105 108—111
Two-dimensional network      67—68
Universal data compression      84
Universal discriminant function      84
Universal gates      78 80—81
Wallis' product      19
waveforms      46—47
White Gaussian noise      71 94
Work factor      104—105
Write complexities      see “Read/write complexities”
Wyner's wiretap channel      30
X-ray tomography      see “Tomography”
Zarankiewic's problem      58
“Lacunary” information pattern      50
“Move-alon” policy      139—141

О проекте