Open Problems in Communication and Computation

Open Problems in Communication and Computation

Paperback(Softcover reprint of the original 1st ed. 1987)

View All Available Formats & Editions
Choose Expedited Shipping at checkout for guaranteed delivery by Thursday, January 24

Product Details

ISBN-13: 9781461291626
Publisher: Springer New York
Publication date: 12/21/2011
Edition description: Softcover reprint of the original 1st ed. 1987
Pages: 236
Product dimensions: 6.10(w) x 9.25(h) x 0.02(d)

Table of Contents

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.

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews