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. 12Rotation 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. Language: English