Open Problems in Communication and Computation

ISBN-13: 9781461291626 / Angielski / Miękka / 2011 / 236 str.

Thomas M. Cover; B. Gopinath

Opis

Thomas M. Cover and B. Gopinatb 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 lems 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. Beyond these well-defined problems are certain grand research goals. What is the general theory of information flow in stochastic networks? What is a comprehensive theory of computational complexity? What about a unification of algorithmic complexity and computational complex ity? Is there a notion of energy-free computation? And if so, where do information theory, communication theory, computer science, and physics meet at the atomic level? Is there a duality between computation and communication? Finally. what is the ultimate impact of algorithmic com plexity on probability theory? And what is its relationship to information theory? The idea was to present problems on the first day. try to solve them on the second day, and present the solutions on the third day. In actual fact, only one problem was solved during the meeting -- El Gamal's prob. lem on noisy communication over a common line."

Spis treści

I. Introduction.- II. Fractran: A Simple Universal Programming Language for Arithmetic.- III. Problems in Communication.- 3.1 Some Basic Mathematical Problems of Multiuser Shannon Theory.- 3.2 The Information Theory of Perfect Hashing.- 3.3 The Concept of Single-Letterization in Information Theory.- 3.4 Is the Maximum Entropy Principle Operationally Justifiable?.- 3.5 Eight Problems in Information Theory.- 3.6 Optimum Signal Set for a Poisson Type Optical Channel.- 3.7 Spectra of Bounded Functions.- 3.8 A Stochastic Decision Problem.- 3.9 Unsolved Problems Related to the Covering Radius of Codes.- 3.10 A Complexity Problem.- 3.11 Codes as Orbits.- 3.12 Reliable Communication of Highly Distributed Information.- 3.13 Instability in a Communication Network.- 3.14 Conjecture: Feedback Doesn’t Help Much.- 3.15 The Capacity of the Relay Channel.- 3.16 Simplex Conjecture.- 3.17 Essential Average Mutual Information.- 3.18 Pointwise Universality of the Normal Form.- 3.19 On Classification with Partial Statistics and Universal Data Compression.- 3.20 Are Bayes Rules Consistent in Information?.- 3.21 On Finding Maximally Separated Signals for Digital Communications.- 3.22 Frequency Assignment in Cellular Radio.- IV. Problems in Computation.- 4.1 In Search of a One-Way Function.- 4.2 Average Case Complete Problems.- 4.3 Does a Single Bit Accumulate the Hardness of the Inverting Problem?.- 4.4 Computing the Busy Beaver Function.- 4.5 The Complexity of Computing Discrete Logarithms and Factoring Integers.- 4.6 Knapsack Used in Factoring.- 4.7 Reliable Computation with Asynchronous Cellular Arrays.- 4.8 Finite Memory Clocks.- 4.9 Distributed Shortest Path Algorithms.- 4.10 The Scope Problem.- 4.11 A Conjectured Generalized Permanent Inequality and a Multiaccess Problem.- 4.12 Rotation Distance.- 4.13 Efficient Digital Signature Schemes Based on Multivariate Polynomial Equations.- 4.14 Some Results for the Problem “Waiting for Godot”.- 4.15 Problems on Tiling, Independent Sets, and Trigonometric Polynomials.- 4.16 Communication Complexity of Shifts.- 4.17 A Coding Problem Concerning Simultaneous Threshold Detection.- 4.18 Cooling Schedules for Optimal Annealing.- V. Problems in the Cracks.- 5.1 Pick the Largest Number.- 5.2 Ergodic Process Selection.- 5.3 Finding the Oldest Person.- 5.4 Gambler’s Ruin: A Random Walk on the Simplex.- 5.5 Linear Separability.- 5.6 The Generic Rank of A2.- 5.7 The Stability of the Products of a Finite Set of Matrices.- 5.8 Electrical Tomography.- 5.9 Figure-Ground Problem for Sound.- 5.10 The Entropy Power Inequality and the Brunn- Minkowski Inequality.- 5.11 The Weird and Wonderful Chemistry of Audioactive Decay.- VI. Solutions to Six of the Problems.- 6.1 On the Spectral Density of Some Stochastic Processes.- 6.2 Ergodic Process Selection.- 6.3 Gambler’s Ruin: A Random Walk on the Simplex.- 6.4 Finding Parity in a Broadcast Network.- 6.5 An Optimal Strategy for a Conflict Resolution Problem.- 6.6 Coordination Complexity and the Rank of Boolean Functions.- List of Contributors.