General Theory of Information Transfer and Combinatorics

Rudolf Ahlswede (auth.), Rudolf Ahlswede, Lars Bäumer, Ning Cai, Harout Aydinian, Vladimir Blinovsky, Christian Deppe, Haik Mashurian (eds.)3540462449, 9783540462446

This book constitutes the thoroughly refereed research 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 also papers of several incorporated meetings.

The 63 revised, full-papers presented were carefully reviewed and selected for inclusion in the book. The papers are organized in topical sections on probabilistic models, cryptology, pseudo random sequences, quantum models, statistics, probability theory, information measures, error concepts, performance criteria, search, sorting, ordering, planning, language evolution, pattern discovery, reconstructions, network coding, combinatorial models, and a problem section.

---

Table of contents :
Front Matter….Pages –
Introduction….Pages 1-44
Rudolf Ahlswede — From 60 to 66….Pages 45-48
Information Theory and Some Friendly Neighbors – Ein Wunschkonzert….Pages 49-50
Identification for Sources….Pages 51-61
On Identification….Pages 62-83
Identification and Prediction….Pages 84-106
Watermarking Identification Codes with Related Topics on Common Randomness….Pages 107-153
Notes on Conditions for Successive Refinement of Information….Pages 154-164
Coding for the Multiple-Access Adder Channel….Pages 165-195
Bounds of E -Capacity for Multiple-Access Channel with Random Parameter….Pages 196-217
Huge Size Codes for Identification Via a Multiple Access Channel Under a Word-Length Constraint….Pages 218-248
Codes with the Identifiable Parent Property and the Multiple-Access Channel….Pages 249-257
Transmission, Identification and Common Randomness Capacities for Wire-Tape Channels with Secure Feedback from the Decoder….Pages 258-275
A Simplified Method for Computing the Key Equivocation for Additive-Like Instantaneous Block Encipherers….Pages 276-284
Secrecy Systems for Identification Via Channels with Additive-Like Instantaneous Block Encipherer….Pages 285-292
Large Families of Pseudorandom Sequences of k Symbols and Their Complexity – Part I….Pages 293-307
Large Families of Pseudorandom Sequences of k Symbols and Their Complexity – Part II….Pages 308-325
On a Fast Version of a Pseudorandom Generator….Pages 326-342
On Pseudorandom Sequences and Their Application….Pages 343-361
Authorship Attribution of Texts: A Review….Pages 362-380
Raum-Zeit und Quantenphysik – Ein Geburtstagsständchen für Hans-Jürgen Treder….Pages 381-393
Quantum Information Transfer from One System to Another One….Pages 394-412
On Rank Two Channels….Pages 413-424
Universal Sets of Quantum Information Processing Primitives and Their Optimal Use….Pages 425-451
An Upper Bound on the Rate of Information Transfer by Grover’s Oracle….Pages 452-459
A Strong Converse Theorem for Quantum Multiple Access Channels….Pages 460-485
Identification Via Quantum Channels in the Presence of Prior Correlation and Feedback….Pages 486-504
Additive Number Theory and the Ring of Quantum Integers….Pages 505-511
The Proper Fiducial Argument….Pages 512-526
On Sequential Discrimination Between Close Markov Chains….Pages 527-534
Estimating with Randomized Encoding the Joint Empirical Distribution in a Correlated Source….Pages 535-546
On Logarithmically Asymptotically Optimal Hypothesis Testing for Arbitrarily Varying Sources with Side Information….Pages 547-552
On Logarithmically Asymptotically Optimal Testing of Hypotheses and Identification….Pages 553-571
Correlation Inequalities in Function Spaces….Pages 572-577
Lower Bounds for Divergence in the Central Limit Theorem….Pages 578-594
Identification Entropy….Pages 595-613
Optimal Information Measures for Weakly Chaotic Dynamical Systems….Pages 614-627
Report on Models of Write–Efficient Memories with Localized Errors and Defects….Pages 628-632
Percolation on a k-Ary Tree….Pages 633-638
On Concepts of Performance Parameters for Channels….Pages 639-663
Appendix: On Common Information and Related Characteristics of Correlated Information Sources….Pages 664-677
Q-Ary Ulam-Renyi Game with Constrained Lies….Pages 678-694
Search with Noisy and Delayed Responses….Pages 695-703
A Kraft–Type Inequality for d–Delay Binary Search Codes….Pages 704-706
Threshold Group Testing….Pages 707-718
A Fast Suffix-Sorting Algorithm….Pages 719-734
Monotonicity Checking….Pages 735-739
Algorithmic Motion Planning: The Randomized Approach….Pages 740-768
Information Theoretic Models in Language Evolution….Pages 769-787
Zipf’s Law, Hyperbolic Distributions and Entropy Loss….Pages 788-792
Bridging Lossy and Lossless Compression by Motif Pattern Discovery….Pages 793-813
Reverse–Complement Similarity Codes….Pages 814-830
On Some Applications of Information Indices in Chemical Graph Theory….Pages 831-852
Largest Graphs of Diameter 2 and Maximum Degree 6….Pages 853-857
An Outside Opinion….Pages 858-860
Problems in Network Coding and Error Correcting Codes Appended by a Draft Version of S. Riis “Utilising Public Information in Network Coding”….Pages 861-897
On the Thinnest Coverings of Spheres and Ellipsoids with Balls in Hamming and Euclidean Spaces….Pages 898-925
Appendix: On Set Coverings in Cartesian Product Spaces….Pages 926-937
Testing Sets for 1-Perfect Code….Pages 938-940
On Partitions of a Rectangle into Rectangles with Restricted Number of Cross Sections….Pages 941-954
On Attractive and Friendly Sets in Sequence Spaces….Pages 955-970
Remarks on an Edge Isoperimetric Problem….Pages 971-978
Appendix: On Edge–Isoperimetric Theorems for Uniform Hypergraphs….Pages 979-1005
Appendix: Solution of Burnashev’s Problem and a Sharpening of the Erdős/Ko/Rado Theorem….Pages 1006-1009
Realization of Intensity Modulated Radiation Fields Using Multileaf Collimators….Pages 1010-1055
Sparse Asymmetric Connectors in Communication Networks….Pages 1056-1062
Finding $C_{text{NRI}}({mathcal W})$ , the Identification Capacity of the AVC ${mathcal W}$ , if Randomization in the Encoding Is Excluded….Pages 1063-1063
Intersection Graphs of Rectangles and Segments….Pages 1064-1065
Cutoff Rate Enhancement….Pages 1066-1068
Some Problems in Organic Coding Theory….Pages 1069-1072
Generalized Anticodes in Hamming Spaces….Pages 1073-1074
Two Problems from Coding Theory….Pages 1075-1075
Private Capacity of Broadcast Channels….Pages 1076-1078
A Short Survey on Upper and Lower Bounds for Multidimensional Zero Sums….Pages 1079-1080
Binary Linear Codes That Are Optimal for Error Correction….Pages 1081-1083
Capacity Problem of Trapdoor Channel….Pages 1084-1087
Hotlink Assignment on the Web….Pages 1088-1092
The Rigidity of Hamming Spaces….Pages 1093-1094
A Conjecture in Finite Fields….Pages 1095-1096
Multiparty Computations in Non-private Environments….Pages 1097-1099
Some Mathematical Problems Related to Quantum Hypothesis Testing….Pages 1100-1103
Designs and Perfect Codes….Pages 1104-1105
Back Matter….Pages –