General Theory of Information Transfer and Combinatorics (Lecture Notes in Computer Science, 4123)

✍ Scribed by Rudolf Ahlswede (editor), Lars Bäumer (editor), Ning Cai (editor), Harout Aydinian (editor), Vladimir Blinovsky (editor), Christian Deppe (editor), Haik Mashurian (editor)

• Publisher: Springer
• Year: 2006
• Tongue: English
• Leaves: 1138
• Category: Library

✦ Synopsis

This book collects 63 revised, full-papers contributed to a research project on the "General Theory of Information Transfer and Combinatorics" that was hosted from 2001-2004 at the Center for Interdisciplinary Research (ZIF) of Bielefeld University and several incorporated meetings. Topics covered include probabilistic models, cryptology, pseudo random sequences, quantum models, pattern discovery, language evolution, and network coding.

✦ Table of Contents

Frontmatter
Introduction
Rudolf Ahlswede --- From 60 to 66
Information Theory and Some Friendly Neighbors -- Ein Wunschkonzert
Probabilistic Models
Identification for Sources
On Identification
Identification and Prediction
Watermarking Identification Codes with Related Topics on Common Randomness
Notes on Conditions for Successive Refinement of Information
Coding for the Multiple-Access Adder Channel
Bounds of {\itshape E}-Capacity for Multiple-Access Channel with Random Parameter
Huge Size Codes for Identification Via a Multiple Access Channel Under a Word-Length Constraint
Codes with the Identifiable Parent Property and the Multiple-Access Channel
Cryptology -- Pseudo Random Sequences
Transmission, Identification and Common Randomness Capacities for Wire-Tape Channels with Secure Feedback from the Decoder
A Simplified Method for Computing the Key Equivocation for Additive-Like Instantaneous Block Encipherers
Secrecy Systems for Identification Via Channels with Additive-Like Instantaneous Block Encipherer
Large Families of Pseudorandom Sequences of {\itshape k} Symbols and Their Complexity -- Part I
Large Families of Pseudorandom Sequences of {\itshape k} Symbols and Their Complexity -- Part II
On a Fast Version of a Pseudorandom Generator
On Pseudorandom Sequences and Their Application
Authorship Attribution of Texts: A Review
Quantum Models
Raum-Zeit und Quantenphysik -- Ein Geburtstagsst\"{a}ndchen f\"{u}r Hans-J\"{u}rgen Treder
Quantum Information Transfer from One System to Another One
On Rank Two Channels
Universal Sets of Quantum Information Processing Primitives and Their Optimal Use
An Upper Bound on the Rate of Information Transfer by Grover's Oracle
A Strong Converse Theorem for Quantum Multiple Access Channels
Identification Via Quantum Channels in the Presence of Prior Correlation and Feedback
Additive Number Theory and the Ring of Quantum Integers
The Proper Fiducial Argument
On Sequential Discrimination Between Close Markov Chains
Estimating with Randomized Encoding the Joint Empirical Distribution in a Correlated Source
On Logarithmically Asymptotically Optimal Hypothesis Testing for Arbitrarily Varying Sources with Side Information
On Logarithmically Asymptotically Optimal Testing of Hypotheses and Identification
Correlation Inequalities in Function Spaces
Lower Bounds for Divergence in the Central Limit Theorem
Information Measures -- Error Concepts -- Performance Criteria
Identification Entropy
Optimal Information Measures for Weakly Chaotic Dynamical Systems
Report on Models of Write--Efficient Memories with Localized Errors and Defects
Percolation on a k-Ary Tree
On Concepts of Performance Parameters for Channels
Appendix: On Common Information and Related Characteristics of Correlated Information Sources
Search -- Sorting -- Ordering -- Planning
Q-Ary Ulam-Renyi Game with Constrained Lies
Search with Noisy and Delayed Responses
A Kraft--Type Inequality for d--Delay Binary Search Codes
Threshold Group Testing
A Fast Suffix-Sorting Algorithm
Monotonicity Checking
Algorithmic Motion Planning: The Randomized Approach
Language Evolution -- Pattern Discovery -- Reconstructions
Information Theoretic Models in Language Evolution
Zipf's Law, Hyperbolic Distributions and Entropy Loss
Bridging Lossy and Lossless Compression by Motif Pattern Discovery
Reverse--Complement Similarity Codes
On Some Applications of Information Indices in Chemical Graph Theory
Largest Graphs of Diameter 2 and Maximum Degree 6
Network Coding
An Outside Opinion
Problems in Network Coding and Error Correcting Codes Appended by a Draft Version of S. Riis ``Utilising Public Information in Network Coding''
Combinatorial Models
Coverings
On the Thinnest Coverings of Spheres and Ellipsoids with Balls in Hamming and Euclidean Spaces
Appendix: On Set Coverings in Cartesian Product Spaces
Partitions
Testing Sets for 1-Perfect Code
On Partitions of a Rectangle into Rectangles with Restricted Number of Cross Sections
Isoperimetry
On Attractive and Friendly Sets in Sequence Spaces
Remarks on an Edge Isoperimetric Problem
Appendix: On Edge--Isoperimetric Theorems for Uniform Hypergraphs
Isodiametry
Appendix: Solution of Burnashev's Problem and a Sharpening of the Erd\H{o}s/Ko/Rado Theorem
Networks
Realization of Intensity Modulated Radiation Fields Using Multileaf Collimators
Sparse Asymmetric Connectors in Communication Networks
Problem Section
Finding $C_{\text{NRI}}({\mathcal W})$, the Identification Capacity of the AVC ${\mathcal W}$, if Randomization in the Encoding Is Excluded
Intersection Graphs of Rectangles and Segments
Cutoff Rate Enhancement
Some Problems in Organic Coding Theory
Generalized Anticodes in Hamming Spaces
Two Problems from Coding Theory
Private Capacity of Broadcast Channels
A Short Survey on Upper and Lower Bounds for Multidimensional Zero Sums
Binary Linear Codes That Are Optimal for Error Correction
Capacity Problem of Trapdoor Channel
Hotlink Assignment on the Web
The Rigidity of Hamming Spaces
A Conjecture in Finite Fields
Multiparty Computations in Non-private Environments
Some Mathematical Problems Related to Quantum Hypothesis Testing
Designs and Perfect Codes
Backmatter