Open Problems in Communication and Computation

1. Front Matter

   Pages i-viii

   PDF

2. Introduction

   1. Introduction

      • Thomas M. Cover, B. Gopinath

      Pages 1-2

3. FRACTRAN

   1. Front Matter

      Pages 3-3

      PDF

   2. FRACTRAN: A Simple Universal Programming Language for Arithmetic

      • J. H. Conway

      Pages 4-26

4. Problems in Communication

   1. Front Matter

      Pages 27-28

      PDF

   2. Some Basic Mathematical Problems of Multiuser Shannon Theory

      • I. Csiszár

      Pages 29-31

   3. The Information Theory of Perfect Hashing

      • János Körner

      Pages 32-34

   4. The Concept of Single-Letterization in Information Theory

      • János Körner

      Pages 35-36

   5. Is the Maximum Entropy Principle Operationally Justifiable?

      • I. Csiszár

      Pages 37-38

   6. Eight Problems in Information Theory

      • R. Ahlswede

      Pages 39-42

   7. Optimum Signal Set for a Poisson Type Optical Channel

      • A. D. Wyner

      Pages 43-45

   8. Spectra of Bounded Functions

      • A. D. Wyner

      Pages 46-48

   9. A Stochastic Decision Problem

      • H. S. Witsenhausen

      Pages 49-50

   10. Unsolved Problems Related to the Covering Radius of Codes

       • N. J. A. Sloane

       Pages 51-56

   11. A Complexity Problem

       • R. Ahlswede

       Pages 57-58

   12. Codes as Orbits

       • R. Ahlswede

       Pages 59-59

   13. Reliable Communication of Highly Distributed Information

       • Abbas El Gamal

       Pages 60-62

   14. Instability in a Communication Network

       • F. P. Kelly

       Pages 63-69

   15. Conjecture: Feedback doesn’t Help Much

       • Thomas M. Cover

       Pages 70-71

   16. The Capacity of the Relay Channel

       • Thomas M. Cover

       Pages 72-73

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.

• algorithms
• communication
• computer science
• information
• information theory

• Departments of Electrical Engineering and Statistics, Stanford University, Stanford, USA

  Thomas M. Cover

• Systems Principles Research, Bell Communications Research, Morristown, USA

  B. Gopinath

Policies and ethics