Lecture Notes in Computer Science 4123 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen UniversityofDortmund,Germany MadhuSudan MassachusettsInstituteofTechnology,MA,USA DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA MosheY.Vardi RiceUniversity,Houston,TX,USA GerhardWeikum Max-PlanckInstituteofComputerScience,Saarbruecken,Germany Rudolf Ahlswede Lars Bäumer Ning Cai Harout Aydinian Vladimir Blinovsky Christian Deppe Haik Mashurian (Eds.) General Theory of Information Transfer and Combinatorics 1 3 VolumeEditors Editedby: RudolfAhlswede UniversitätBielefeld,FakultätfürMathematik Universitätsstr.25,33615Bielefeld,Germany E-mail:[email protected] Assistedby: LarsBäumer NingCai UniversitätBielefeld,FakultätfürMathematik Universitätsstr.25,33615Bielefeld,Germany E-mail:{baeumer,cai}@math.uni-bielefeld.de Incooperationwith: HaroutAydinian VladimirBlinovsky* ChristianDeppe HaikMashurian UniversitätBielefeld,FakultätfürMathematik Universitätsstr.25,33615Bielefeld,Germany E-mail:{ayd,cdeppe,hmashur}@math.uni-bielefeld.de *RussianAcademyofSciences InstituteofProblemsofInformationTransmission Bol’shoiKaretnyiper.19,101447Moscow,Russia E-mail:[email protected] LibraryofCongressControlNumber:2006937883 CRSubjectClassification(1998):F.2,G.2-3,C.2,G.1.6,E.3-5 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ISSN 0302-9743 ISBN-10 3-540-46244-9SpringerBerlinHeidelbergNewYork ISBN-13 978-3-540-46244-6SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. SpringerisapartofSpringerScience+BusinessMedia springer.com ©Springer-VerlagBerlinHeidelberg2006 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SPIN:11889342 06/3142 543210 Preface The Center for Interdisciplinary Research (ZiF) of the University of Bielefeld hostedaresearchgroupunderthetitle“GeneralTheoryofInformationTransfer andCombinatorics,”abbreviatedasGTIT-C,fromOctober1,2001toSeptember 30, 2004. As head of the research group the editor shaped the group’s scientific directionsanditspersonalcomposition. He followed ideas, problems and results which had occupied him during the past decade and which seem to extend the frontiers of information theory in severaldirections.Themaincontributionsconcerninformationtransferbychan- nels. There are also new questions and some answers in new models of source coding. While many of the investigations are in an explorative state, there are alsohardcoresofmathematicaltheories.Inparticular,aunifiedtheoryofinfor- mation transfer was presented, which naturally incorporates Shannon’s Theory of Information Transmission and the Theory of Identification in the presence of noiseasextremalcases.Itprovidesseveralnovelcodingtheorems.Onthesource coding side the concept of identification entropy is introduced. Finally, beyond information theory new concepts of solutions for probabilistic algorithms arose. InadditiontothisbooktherewillbeaspecialissueofDiscreteApplied Math- ematics “General Theory of Information Transfer and Combinatorics” in three parts,whichcoversprimarilyworkwithastrongeremphasisonthesecondcom- ponent, combinatorics. It begins with an updated version of “General Theory of Information Transfer” in order to make the theory known to a broader au- dience and continues with other new directions such as bioinformatics, search, sorting and ordering, cryptology and number theory, and networks with many new suggestions for connections. It includes in a special volume works and abstracts of lectures devoted to the great Levon Khachatrian at the memorial held for him during the Opening Conference, November 4-9, 2002. In a preparatory year, October 1, 2001 – September 30, 2002, guided by the generalconceptsandideasindicatedanddescribedingreaterdetailinthepresent introduction,researchersandresearchinstitutionswereapproachedworldwidein order to find out which possible participants might be and which more concrete projects could be realized in the main researchyear,October 1, 2002to August 31, 2003. Central events in this phase were two weekly preparatory meetings in Febru- ary:GeneralTheoryofInformationTransfer,abbreviatedasGTIT,andInforma- tioninNaturalSciences,SocialSciences,HumanitiesandEngineering.Abstracts of the lectures can be found at http://www.math.uni-bielefeld.de/ahlswede/zif. The main goals were to test the applicability of the GTIT, particularly iden- tification, and to strive for new information phenomena in the sciences, which VI Preface can be modelled mathematically. Readers are strongly advised to read the In- troduction for guidance. Our special thanks go to the members of the administrationof the “Zentrum fu¨rinterdisziplina¨reForschung”(ZiF)inBielefeldforaverypleasantcooperation and, in particular, to Gertrude Lu¨bbe-Wolf, who as acting director authorized and generously supported this project, and to Ibke Wachsmuth, who continued herpolicy.Dr.Roggenho¨fer,whowasalwaysresponsivetonewideasandwishes is also thanked for his assistance. June 2006 Rudolf Ahlswede Table of Contents Introduction...................................................... 1 Rudolf Ahlswede – From 60 to 66 ................................... 45 Information Theory and Some Friendly Neighbors – Ein Wunschkonzert................................................ 49 I Probabilistic Models 1 Identification for Sources ....................................... 51 Rudolf Ahlswede, Bernhard Balkenhol, Christian Kleinewa¨chter 2 On Identification .............................................. 62 Christian Kleinew¨achter 3 Identification and Prediction .................................... 84 Lars Ba¨umer 4 Watermarking Identification Codes with Related Topics on Common Randomness....................................... 107 Rudolf Ahlswede, Ning Cai 5 Notes on Conditions for Successive Refinement of Information....... 154 Ashot N. Harutyunyan 6 Coding for the Multiple-Access Adder Channel .................... 165 Ba´lint Laczay 7 Bounds of E-Capacity for Multiple-Access Channel with Random Parameter .................................................... 196 Mariam E. Haroutunian 8 Huge Size Codes for Identification Via a Multiple Access Channel Under a Word-Length Constraint................................ 218 S´andor Csibi, Edward von der Meulen 9 CodeswiththeIdentifiableParentPropertyandtheMultiple-Access Channel...................................................... 249 Rudolf Ahlswede, Ning Cai VIII Table of Contents II Cryptology – Pseudo Random Sequences 10 Transmission, Identification and Common Randomness Capacities for Wire-Tape Channels with Secure Feedback from the Decoder ... 258 Rudolf Ahlswede, Ning Cai 11 A Simplified Method for Computing the Key Equivocation for Additive-Like Instantaneous Block Encipherers................ 276 Zhaozhi Zhang 12 SecrecySystemsforIdentificationViaChannelswithAdditive-Like Instantaneous Block Encipherer ................................ 285 Rudolf Ahlswede, Ning Cai, Zhaozhi Zhang 13 Large Families of Pseudorandom Sequences of k Symbols and Their Complexity – Part I..................................... 293 Rudolf Ahlswede, Christian Mauduit, Andra´s S´arko¨zy 14 Large Families of Pseudorandom Sequences of k Symbols and Their Complexity – Part II .................................... 308 Rudolf Ahlswede, Christian Mauduit, Andra´s S´arko¨zy 15 On a Fast Version of a Pseudorandom Generator ................. 326 Katalin Gyarmati 16 On PseudorandomSequences and Their Application .............. 343 Jo¨el Rivat, Andra´s S´arko¨zy 17 Authorship Attribution of Texts: A Review ...................... 362 Mikhail B. Malyutov III Quantum Models 18 Raum-Zeit und Quantenphysik – Ein Geburtstagssta¨ndchen fu¨r Hans-Ju¨rgen Treder........................................... 381 Armin Uhlmann 19 Quantum Information Transfer from One System to Another One .............................................. 394 Armin Uhlmann 20 On Rank Two Channels ....................................... 413 Armin Uhlmann 21 Universal Sets of Quantum Information Processing Primitives and Their Optimal Use........................................ 425 Jozef Gruska Table of Contents IX 22 An Upper Bound on the Rate of Information Transfer by Grover’s Oracle ...................................................... 452 Erdal Arikan 23 A Strong Converse Theorem for Quantum Multiple Access Channels .................................................... 460 Rudolf Ahlswede, Ning Cai 24 Identification Via Quantum Channels in the Presence of Prior Correlationand Feedback ..................................... 486 Andreas Winter 25 Additive Number Theory and the Ring of Quantum Integers ....... 505 Melvyn B. Nathanson 26 The Proper Fiducial Argument ................................. 512 Frank Hampel 27 On Sequential Discrimination Between Close Markov Chains ....... 527 Mikhail B. Malyutov, Dmitry M. Malyutov 28 Estimating with Randomized Encoding the Joint Empirical Distribution in a Correlated Source ............................. 535 Rudolf Ahlswede, Zhen Zhang 29 On Logarithmically Asymptotically Optimal Hypothesis Testing for Arbitrarily Varying Sources with Side Information............. 547 Rudolf Ahlswede, Ella Aloyan, Evgueni Haroutunian 30 OnLogarithmicallyAsymptoticallyOptimalTestingofHypotheses and Identification............................................. 553 Rudolf Ahlswede, Evgueni Haroutunian 31 Correlation Inequalities in Function Spaces ...................... 572 Rudolf Ahlswede, Vladimir Blinovsky 32 Lower Bounds for Divergence in the Central Limit Theorem........ 578 Peter Harremo¨es V Information Measures – Error Concepts – Performance Criteria 33 Identification Entropy......................................... 595 Rudolf Ahlswede 34 Optimal Information Measures for Weakly Chaotic Dynamical Systems..................................................... 614 Vieri Benci, Stefano Galatolo X Table of Contents 35 Report on Models of Write–Efficient Memories with Localized Errors and Defects............................................ 628 Rudolf Ahlswede, Mark S. Pinsker 36 Percolation on a k-Ary Tree.................................... 633 Kingo Kobayashi, Hiroyoshi Morita, Mamoru Hoshi 37 On Concepts of Performance Parameters for Channels............. 639 Rudolf Ahlswede 38 Appendix: On Common Information and Related Characteristics of Correlated Information Sources .............................. 664 Rudolf Ahlswede, Janos Ko¨rner VI Search – Sorting – Ordering – Planning 39 Q-Ary Ulam-Renyi Game with Constrained Lies.................. 678 Ferdinando Cicalese, Christian Deppe 40 Search with Noisy and Delayed Responses ....................... 695 Rudolf Ahlswede, Ning Cai 41 A Kraft–Type Inequality for d–Delay Binary Search Codes......... 704 Rudolf Ahlswede, Ning Cai 42 Threshold Group Testing ...................................... 707 Peter Damaschke 43 A Fast Suffix-Sorting Algorithm ................................ 719 Rudolf Ahlswede, Bernhard Balkenhol, Christian Deppe, Martin Fro¨hlich 44 Monotonicity Checking ........................................ 735 Marina Kyureghyan 45 Algorithmic Motion Planning: The Randomized Approach ......... 740 Stefano Carpin VII Language Evolution – Pattern Discovery – Reconstructions 46 Information Theoretic Models in Language Evolution ............. 769 Rudolf Ahlswede, Erdal Arikan, Lars Ba¨umer, Christian Deppe 47 Zipf’s Law, Hyperbolic Distributions and Entropy Loss............ 788 Peter Harremo¨es, Flemming Topsoe Table of Contents XI 48 Bridging Lossy and Lossless Compression by Motif Pattern Discovery.................................................... 793 Alberto Apostolico, Matteo Comin, Laxmi Parida 49 Reverse–Complement Similarity Codes .......................... 814 Arkadii D’yachkov, David Torney, Pavel Vilenkin, Scott White 50 On Some Applications of Information Indices in Chemical Graph Theory...................................................... 831 Elena V. Konstantinova 51 Largest Graphs of Diameter 2 and Maximum Degree 6 ............ 853 Sergey G. Molodtsov VIII Network Coding 52 An Outside Opinion .......................................... 858 Rudolf Ahlswede 53 Problems in Network Coding and Error Correcting Codes Appended by a Draft Version of S. Riis “Utilising Public Information in Network Coding” ............................... 861 Soren Riis, Rudolf Ahlswede IX Combinatorial Models Coverings 54 On the Thinnest Coverings of Spheres and Ellipsoids with Balls in Hamming and Euclidean Spaces.............................. 898 Ilya Dumer, Mark S. Pinsker, Viacheslav V. Prelov 55 Appendix: On Set Coverings in Cartesian Product Spaces.......... 926 Rudolf Ahlswede Partitions 56 Testing Sets for 1-PerfectCode ................................. 938 Sergey V. Avgustinovich, Anastasia Yu. Vasil’eva 57 On Partitions of a Rectangle into Rectangles with Restricted Number of Cross Sections ..................................... 941 Rudolf Ahlswede, Alexander A. Yudin Isoperimetry 58 On Attractive and Friendly Sets in Sequence Spaces............... 955 Rudolf Ahlswede, Levon Khachatrian