General Theory of Information Transfer

The talk will present work that has been done in our group in recent years on comparison and matching of shapes with methods from computational geometry. We assume that planar shapes are represented by polygonal curves and consider several distance measures to describe similarity between shapes, in particular the Hausdorff- and the Frechet- distance. Algorithms for measuring the distance between two shapes will be presented. Also the problem of matching shapes optimally with respect to a given distance measure will be considered. There are different variants of this problem depending on the set of allowable transformations, like translations, rigid motions, similarities etc. Also a few generalizations to three and higher dimensions will be presented.

Stochastic resonance is the name given to the phenomenon, in several physical systems, whereby noise or deliberate randomization can enhance the ability to perceive the influence of an external driving signal. We propose an information theoretic model within the context of which this phenomenon can be studied. When distributed agents are attempting jointly to use deliberate randomization to extract the characteristics of an underlying natural source that drives the observations of each of the agents, common randomness plays a natural role, which is highlighted.

R. Apfelbach and Nina Y. Vasilieva: Molecules, Chemical Signals, Information Transfer and Behavior

Chemical messengers operate at all levels of biological organization from subcellular to interorganismal. Chemical regulation of cellular processes can be found in even the most primitive plants and animal species; chemical regulatory agents include relatively nonspecific molecules (e.g., , , , ), and those, like cyclic adenosine 3',-5'-monophosphate (cAMP), that are more complex. Some animal species utilize chemical messengers as means of communication between individuals of that species. In this case we call chemical messengers as pheromones (exocrine secretions). In many invertebrates the pheromone consists of only one molecule type, like in the silk moth ( Bombyx mori) where bombykol has been identified as the male attracting substance emitted by the female. In vertebrates, especially in mammals, pheromones typically consist of a mixture of different odorants. In Dwarf hamsters (genus Phodopus) chemical messengers released together with urine serve to identify family or group members, individuals, and also play an important role in the reproduction for these species. In search of compounds releasing behavior in another animals, mass spectometry and gas chromatography techniques were used. In urinary profiles the presence of pyrazines was a dominating factor: six pyrazines indicated strong changes within gender and age.

The notion of motif, interpreted here as a string of intermittently solid and don't care characters recurring more or less frequently in a sequence or sequence family, emerged in the area of computational biology and has been studied primarily in connection with problems of pattern discovery in that domain. More recenlty, this notion has been applied successfully to other endeavors, notably, of structure inference and data compression. This talk highlights some of the combinatorial, analytical and algorithmic issues that arised in this process, and attempts an outline of directions for future developments.

R. Ahlswede, H. Aydinian, L.H. Khachatrian, and L. Tolhuizen: On q-ary Codes Correcting All Unidirectional Errors of a Limited Magnitude

We consider codes over the alphabet intended for the control of unidirectional errors of level . That is, the transmission channel is such that the received word cannot contain both a component larger than the transmitted one and a component smaller than the transmitted one. Moreover, the absolute value of the difference between a transmitted component and its received version is at most .

We study -ary codes capable of correcting all unidirectional errors of level . Lower and upper bounds for the maximal size of those codes are presented.

We also study codes for this aim that are defined by a single equation on the codeword coordinates (similar to the Varshamov-Tenengolts codes for correcting binary asymmetric errors). We finally consider the problem of detecting all unidirectional errors of level .

In the system-level diagnosis model introduced by Preparata, Metze and Chien (1967) processors perform tests on one another via links in the system. Fault-free testers (processors) correctly identify the status of tested processors, while the faulty testers can give arbitrary test results. The goal is to identify correctly all faulty processors based on the test results (syndrom). A system is said to be -diagnosable if all faulty units can be identified provided the number of faulty units present does not exceed .

Later Friedman introduced the notion of -diagnosability, where for given syndrom the faulty units can be isolated to within a set of at most units (provided the number of faulty units ).

Here we explore the -diagnosability of -cube multiprocessor systems. In particular we determine the degree of -diagnosability of the -cube, for .

A. Bergeron, J. Mixtacki, and J. Stoye: The reversal distance without hurdles and fortresses

This paper presents an elementary proof of the Hannenhalli-Pevzner theorem on the reversal distance of two signed permutations. It uses a single PQ-tree to encode the various features of a permutation. The parameters called hurdles and fortresses are replaced by a single one, whose value is computed by a simple and efficient algorithm.

We give a survey of known generalizations of LYM inequality from extremal set theory. Among the new results presented is a quadratic LYM-type inequality for cross t-intersecting set families.

The continuous space-time limit of the Quantum Random Walk will be discussed. For the case of the Hadamard coin it is possible to obtain an analytic expression for the probability to find the QRW in at time .

V. Blinovsky: Number of Shapes of Young Diagrams with Restrictions on the Length and Height of Steps

We consider the set of non increasing step functions with the nodes in the lattice such that they begin in some node and end in some point . Also we suppose that the area under these step functions is . W.l.o.g. we assume that the step functions are continuous from the right. At last (and most important in this work) is the condition that the length of the steps belong to some set and heights of the steps are from the set . The problem is to find the logarithmic asymptotic of the number of such step functions i.e. the value

There is connecteion between this problem and the problem of large deviations for the shape of random Young diagram with the restrictions on the length and height of steps. We also formulate the solution of this problem and write the explicit formulae for the rate function.

A multiplicity vector (or compomer) is obtained from a string by counting the number of occurrences of each character. Though the set of multiplicity vectors has a simple structure, several interesting questions arise from the implicit connection to strings.

Our interest in compomers stems from the analysis of mass spectrometry data. Using mass spectrometry, one can determine the weight (or molecular mass) of a sample molecule with unequaled accuracy. These sample molecules are in fact strings over an alphabet where every character has some known weight. Clearly, the order of characters in the sample molecule cannot be determined from its weight. We want to find efficient algorithms for determining all or some compomers with masses sufficiently close to the measured mass, the number of such compomers, and related questions.

Finally, we demonstrate how mass spectrometry (and compomers) can be used for DNA de-novo sequencing.

R. Ahlswede and N. Cai: Transmission, identification and common randomness capacities for wire-tape channels with secure feedback from the decoder (see [B10])

The subword complexity function of a finite word over a finite alphabet with is defined by , , where represents the set of all the subwords or factors of .

The function defined as for has values greater than or equal to those of the complexity function for any , i.e., for all . As a first result regarding , we prove that for each there exist words of length for which the maximum of their complexity function is equal to the maximum of the function ; a way to construct such words is described. This result gives rise to a further question: for a given , is there a word of length whose complexity function coincides with for each ? The problem is answered in affirmative, with different constructive proofs for binary alphabets () and for those with . This means that for each , there exist words of length whose complexity function is equal to the function . Such words are constructed using de Bruijn graphs. When for some , these words are known as de Bruijn words: they are the shortest words that contain as a factor one occurrence of every word of length .

R. Ahlswede, F. Cicalese, C. Deppe, and D. Mundici: Optimal strategies for fault-tolerant search over an arbitrary channel with an arbitrary error-distance

We consider a variant of the so called Ulam-Renyi problem. This is a classical model for the problem of finding the fewest number of questions necessary to find an unknown element in a finite set with membership tests, were some of the tests can be faulty, i.e., not give the exact result.

We consider the case in which tests may have different outcomes, typically , and the errors may only follow some patterns which are fixed in advance. A typical -ary test is a -tuple of disjoint subsets of the search space, which cover the search space. The outcome of the queries is the index of the set in this -tuple which contains the unknown element.

By constrained error patterns, we mean, e.g., the case that a test whose correct outcome is 1, can only produce a faulty outcome in the set , i.e., it either gives the correct outcome ``1'' or otherwise it gives one of the values in , but it never gives the incorrect value ``3''.

We also consider the case that the different possible errors have different weights, and the total error weight, during the entire search process is bounded by a constant .

In the previous example, it could be the case that the transformation of the outcome 1 into its faulty version costs 1 when , it costs 2 when and it costs 4 when .

This problem is strongly related to the one of finding shortest error correcting codes for a channel that for each given input symbol can only produce a subset of the output alphabet , and for each symbol , there exists an error cost that the channel incurs when is transformed into . It is assumed that the channel can at most incur a cost of per codeword (block of symbols transmitted at once), where the value is fixed in advance. A famous special case of this problem is the one of finding error-correcting codes for the -channel. In this case we have and the cost function is 0 for the case when there is no error and 1 for the case when a 1 is transformed into a 0.

In our present scenario we look for asymmetric error correcting codes when the channels error dynamics can have an arbitrary, though fixed, form and errors can have different weights, but for each codeword the total error weight is bounded. One could think of a sort of maximum amount of errors that the channel has and can spread over the codeword producing errors of different intensity over the different symbols.

Given integers, and a function we shall provide matching upper and lower bounds for the maximum integer , such that there exists a search strategy with -ary queries, to find a number in the set when

Notwithstanding an extensive literature on decision-making by animals acting alone, group decision-making processes have been largely neglected. Two extreme mechanisms whereby a group could in principle reach communal decisions are (i)despotically, where a dominant decides; and (ii) democratically, where a majority of group members decides. Many authors have made the assumption of despotic groupdecisions without testing, because the feasibility of democracy in non-humans is not immediately obvious. It requires the ability to vote and to count votes. I examine therelative fitness consequences of the two extreme mechanisms of communal decision making, investigate how different mechanisms of communal decision making could evolve and give empirical examples of democratic decision making in animals.

A. De Bonis: New results on Superimposed codes (and Related Combinatorial Structures) with Applications to Group Testing

Let s be the number of unknown positive elements in a population of members, . We aim at finding all the s positive elements by testing group of members of the population, under the constraint that a group tests positive if and only if it contains exactly one positive element. The above variant of the group testing problem has been introduced in the framework of the design of efficient algorithms for random multiple-access communication systems in which the receiver cannot distinguish between channel noise and collision noise. The talk will present tight upper and lower bounds on the optimal number of tests needed to solve the above group testing problem. In particular, we provide new and improved bounds on the minimum number of tests required by one-stage strategies, that is strategies that perform all tests in parallel. Instrumental to our results is the relation between one-stage algorithms for our group testing problem and a certain generalization of classical superimposed codes for which we provide improved bounds. We also present algorithms for our group testing problem which proceed in more than one stage, and that use a much smaller number of tests than one-stage algorithms.

R. Ahlswede, F. Cicalese, and C. Deppe: Searching with lies under error transition cost constraints (see [D10])

M. Drmota and W. Szpankowski: Applications of number theoretic methods in coding theory

The purpose of this talk is to present some unexpected applications of Diophantine approximation techniques in coding theory.

Let be the binary alphabet with probability distribution and . One problem in coding theory is to consider an optimal (prefix) code on the set of words of length . Since the entropy is a lower bound for the average code length a perfect code should have the property , where denotes the length of the encoded word and the probability of with and . Since is usually not an integer one has to try to approximate the linear forms by integers. Therefore one is confronted with an Diophantine approximation problem.

We present applications to Huffmann codes, to (generalized) Shannon codes and to variable-to-variable codes, where metric Diophantine approximation on manifolds can be applied.

M. Dutour: Filling of a given boundary by -gons and related problems (see [D13])

We discuss the distance concepts between two -ary -sequences, , called a partition distance. This distance is a metric in the space of unordered partitions of a finite -set, where each partition contains disjoint subsets of the -set. For the metric, we study codes called -partition codes and work out their application to the statistical analysis of psychological or sociological tests using questionnaires. An example of 3-partition code based on conventional linear codes for the Hamming distance is given. Bounds on the rate of -partition codes are obtained. A general construction of -partition codes based on the first order Reed-Muller codes is presented.

A.R. Ghazaryan and E.C. van der Meulen: New Results in Hierarchical Guessing

We consider a natural interesting extension of the guessing problem - hierarchical guessing, which takes advantage of the distortion information obtained at each step. This search model was first studied by Merhav, Roth and Arikan in [2]. In this paper we investigate this guessing problem from the point of view of optimality at both steps. The scheme of two-stage hierarchical guessing consists of first approximating the value of a random vector within distortion level , using an initial number of guesses; then, after the first success, of iteratively improving this approximation for distortion level , by adding new guesses to the previous guessing list. The guesser can make the first step (for achieving ) as efficient as possible, i.e., with the best attainable guessing exponent given by (see [1]) = the one-stage guessing exponent function . Later, if the source message needs to be guessed more accurately, he can provide to the original guessing list an addendum, thereby achieving distortion . It is interesting to determine whether this refinement can be done as efficient as if he had directed his guesses immediately to , i.e., with the best attainable one-stage guessing exponent given by for the overall procedure. In this paper we prove as a first result that for a finite-alphabet memoryless source, distortion measure , distortion levels and , optimal (in the noted sense) guessing from a coarse guess within distortion level to a finer guess within distortion level can be achieved. For the case of a discrete memoryless source, two finite reproduction alphabets, two distortion measures and and distortion levels and , Merhav, Roth and Arikan derived a lower bound on the best attainable two-stage guessing exponent, i.e., the asymptotically minimal exponential growth rate of the -th moment of the number of required guesses associated with intermediate distortion level and target distortion level , and demonstrated its achievability under the assumption that the guesser knows in advance the type class of the given source vector . As a second result, we demonstrate the achievability of without knowing the type class information. As a consequence, we provide a single-letter characterization of the best attainable twostage guessing exponent given by .

P. Ferragina, R. Giancarlo, G. Manzini, and M. Sciortino: Boosting textual compression in optimal linear time

We provide a general boosting technique for Textual Data Compression. Qualitatively, it takes a good compression algorithm and turns it into an algorithm with a better compression performance guarantee. It displays the following remarkable properties: (a) it can turn any memoryless compressor into a compression algorithm that uses the ``best possible'' contexts; (b) it is very simple and optimal in terms of time; (c) it admits a decompression algorithm again optimal in time. To the best of our knowledge, this is the first boosting technique displaying these properties.

Technically, our boosting technique builds upon three main ingredients: the Burrows-Wheeler Transform, the Suffix Tree data structure, and a greedy algorithm to process them. Specifically we show that there exists a proper partition of the Burrows-Wheeler Transform of a string that shows a deep combinatorial relation with the -th order entropy of . That partition can be identified via a greedy processing of the suffix tree of with the aim of minimizing a proper objective function over its nodes. The final compressed string is then obtained by compressing individually each substring of the partition by means of the base compressor we wish to boost.

Our boosting technique is inherently combinatorial because it does not need to assume any prior probabilistic model about the source emitting , and it does not deploy any training, parameter estimation and learning. Various corollaries are derived from this main achievement. Among the others, we show analytically that using our booster we get better compression algorithms than some of the best existing ones, i.e., LZ77, LZ78, PPMC and the ones derived from the Burrows-Wheeler Transform. Further, we settle analytically some long standing open problems about the algorithmic structure and the performance of BWT-based compressors. Namely, we provide the first family of BWT algorithms that do not use Move-To-Front or Symbol Ranking as a part of the compression process.

J. Gruska: Quantum information processing primitives (Universal sets of quantum information processing primitives and their optimal use) (see also [B21])

On one side, nature offers many ways - let us call them technologies - various quantum information processing primitives can be exhibited, realized and utilized. This fact has been fully realized. On the other side, quite different primitives are usually desirable when ``user or theory point of view'' of quantum information processing is pursued. Experiences from the development of classical computers and computing show, on one side, that both technology offers and users/theory requirements are important, but finally those primitives that best serve theory and users dominate in long terms.

Since it appears to be very difficult to exploit potential of nature for QIP, it is of large importance to explore which quantum primitives form universal sets of primitives, and are (quite) easy to implement. At the same way it is important to explore, using abstract models of quantum computation, which primitives are really handy and allow to develop quantum computing theory in most convenient way.

Since designing of (small) quantum processors is becoming an agenda in quantum computing the search for quantum primitives and their optimal use is becoming of large practical importance. At the same time this search brings a lot of fundamental, motivating and stimulating problems.

The talk deals with several concepts of universality in quantum information processing and with various (sometimes surprising) universal sets of (often surprising) quantum primitives.

In the talk we also deal with recent developments concerning an optimal use of some quantum primitives.

C. Mauduit and A. Sárközy introduced new measures of pseudorandomness of finite binary sequences . The most important pseudorandom measures among these are the well-distribution measure and the correlation measure of order ().

Y. Kohayakawa, C. Mauduit, C. G. Moreira and V. Rödl proved that always holds. In the case of odd order the correlation measure can be small, e.g. for the sequence we have , but in this case we have . C. Mauduit conjectured that always holds with some constant . In this paper it is shown that this is true for , more exactly if for a sequence we have then . Finally, an inequality of C. Mauduit and A. Sárközy involving and to correlation measures of higher even order will be generalized.

In this talk we plan to show some evidences of the close relation of graphs, designs and hypergraphs to each other by discussing some extreme hypergraph problems what can be reduced to graph theoretical problems and what special graph techniques are applied to and the extreme constructions involve designs or graphs too. We are going to speak of the subjects as follows.

R. Ahlswede and E. Haroutunian: On Logarithmically Asymptotically Optimal Testing of Hypotheses and Identification (see [B30])

The information projection of a distribution into a convex set is the distribution, which minimizes the information divergence. If the infimum over divergences does not exist the information projection should be replaced by the generalized information. If is a continuous distribution and is a set of discrete (empirical) distributions then the divergence from a distribution in to is always infinite and even the generalized information divergence is not defined. In this case there still exist an optimal way to compress data with as prior distribution given that we are provided with the extra information that the empirical distribution belongs to . This leads to the definition of the weak information. No convexity conditions are required. Inequalities for the generalized information divergence can be generalized to the weak information projection. If is convex and the divergence from any distribution in to is finite then the two constructions coincide. The weak information projection leads to new results on the conditional limit theorem.

The talk will treat the error exponent in arbitrary vaying source coding problems mostly inspired by Ahlswede's ``Coloring hypergraphs''.

For a permutation of , an interval of is a set of the form for . Given a family of two or more such permutations, a common interval of is a subset of such that is an interval in each permutation.

Common intervals have applications in different fields. Some genetic algorithms using subtour exchange crossover based on common intervals have been proposed for sequencing problems such as the traveling salesman problem or the single machine scheduling problem. In a bioinformatical context, common intervals are used to detect possible functional associations between genes, to compute the reversal distance between genomes, and to define a similarity measure for gene order permutations.

Uno and Yagiura (2000) presented an optimal time and space algorithm for finding all common intervals of two permutations. In Heber and Stoye (2001) this algorithm was generalized to find the common intervals in a family of two or more permutations. Here, we further generalize the above approaches to find common intervals in a family of labeled trees. The notion of intervals in permutations is replaced by connected components (subtrees) in trees. While in permutations there are at most common intervals, now there might be up to common subtrees. Despite this difference, we show that given a family of labeled trees on vertices, we can compute in time and space a set of at most irreducible common intervals which form a generating set for the (possibly exponentially large) set of all common intervals.

C.K. Hemelrijk and H. Kunz: Pecularities of fish schools: an agent-based model

Fish schools have many peculiarities: For instance, larger schools are denser, schools are usually oblong, their centre of gravity is located at the front, and fish of different sizes cluster together to different degrees. It is, however, difficult to understand how such collective phenomena may relate to behavioural rules at the level of the individual.

To study this, we use an agent-based model (called SchoolingWorld) in which artificial fish are equipped with simple rules: to group, to align and to avoid others if these come to close. We will show that, unexpectedly, all these characteristics of schools may emerge as collective phenomena among these simple, artificial fish. We will explain the emergent phenomena in detail and indicate how these results may guide empirical studies.

O. Hirota: Secure quantum communication protocol based on Quantum communication theory

Abstract:

In 2000, an attractive new quantum cryptography was discovered by H.P.Yuen based on quantum communication theory, which can realize secure communication with high speeds and at long distance by conventional optical devices. We give a brief introduction of the general logic for the security of Y-00 as direct encryption and also for key generation. In addition, we show some examples of its concrete performance.

A quantum key generation scheme for two legitimate users(Alice and Bob) is one of the most interesting subjects in quantum information science, which was pioneered by C.Bennett and G.Brassard in 1984. We emphasize that such results are great achievement and open a new science. Many researchers believe that the key distribution by single photon is on the verge of commercial application. However we should take into account the fact that the societies of electronics and communication, and of cryptography are basically not interested in the practical use of quantum cryptography based on single photon schemes, because of extremely low performance in the sense of communication science. Although there is no means of solving such a serious argument, we would like to make the following comment. The key generation is a very important, but it is very narrow sense that one defines quantum cryptography by only BB-84 and similar principle. Yuen, Kumar, and their group have pointed out that the quantum cryptography should involve other aspects, and called quantum information scientist's attention to quantum cryptography based on another principle. The research like Gisin's work and coherent state based BB-84 to cope with the low performance should be encouraged, and also research like Northwestern University's group to investigate another scheme for achieving the same function should be welcome. In this review, we would like to introduce a new quantum cryptography which is called Yuen protocol. The fundamental structure of Yuen protocol(Y-00) is organized by a shared initial key like symmetric key scheme in the conventional cryptography, but it is constructed as a physical cryptography. In addition, this gives a generalization of conventional unconditional secure key generation based on Maurer and similar theory, in which the shared seed key is used to establish an advantage distillation. After such an introduction, I will give some concrete performance of Y-00.

Let us introduce Y-00 in the following. First we assume that Alice and Bob share a seed key . The key is stretched by a pseudo random number generator to . The data bit is modulated by -ary keying driven by pseudo random number: with the seed key . The -ary keying has different basis based on coherent states. So the data bit is mapped into one of coherent states randomly. Let us mention first what is basic principle to guarantee the security. There are many fundamental theorems in quantum information theory. The most important theorem for information processing of classical information by quantum states is the following:

Theorem 1:Signals with non-orthogonal states cannot be distinguished without error and optimum lower bounds for error rate exist.

This means that if we assign non-orthogonal states for bit values 1 and 0, then one cannot distinguish 1 and 0 without error. When the error probability is 1/2 based on quantum noise, there is no way to distinguish them, from quantum signal detection theory. On the other hand, in the quantum case, one has to take a quantum attack into account. So one needs the well known quantum no-cloning theorem.

The application of Y-00 is, first, a direct encryption stream cipher in conventional cryptography, and then it is extended to key generation, but not one-time pad which is very inefficient. Here we emphasize that one should employ different security criteria for direct encryption and key generation. For direct encryption, the criteria are given as follows.

In the conventional theory, we have known as Shannon bound for ciphertext only attack. In addition, for known plaintext attack, we have which means a computational complexity based security. In the following, we will show that one can overcome such limitations in the conventional direct encryption by Y-00. A fundamental requirement of secure communication is, first, to establish that the channel between Alice and Eve is very noisy, but the channel of Alice and Bob is kept as a normal communication channel by physical structure. To realize it, Yuen employed a combination of a shared short key for the legitimate users and a kind of stream cipher with specific modulation scheme, following the above two theorems. We note that a main idea in his protocol is the explicit use of a shared short key and physical nature of scheme for cryptographic ob jective of secure communication and key generation. And also, one can say that the origin of security comes from receiver performance with versus without key. In general, the quantum information system is described by a density operator. The density operator of the output of the coding/modulation system of Y-00 as seen by the attack for ciphertext-only individual attack is

The probability depends on the statistics of the data, and depend on the pseudo random number with , and being even and odd number, for example. Eve has to extract the data from the quantum system with such a density operator. However, according to one of the most fundamental theorem (Theorem 1) in quantum information theory, the accuracy of Eve's measurement is limited. For ciphertext only attack, the best way of Eve is of course given by the quantum optimum detection for two mixed states : and . That is, the accuracy of measurement of Eve is given by Helstrom bound as follows:

where is POVM. The error probability of Eve as determined by the quantum limit is 1/2 from the appropriate choice of the number and signal energy. It means that Eve's data is completely inaccurate. In addition, a Overlap Selection Keying:OSK was proposed. By such a randomization, the density operators of 1 and 0 for Eve are . So Eve cannot completely estimate information bits. For known/chosen plaintext attack, Eve knows the input data. So the best way for Eve is to detect pure coherent states which convey directly running key sequence : . In this case, the accuracy of the data is also given by the quantum detection for pure coherent states and the measured data on the running key involve unavoidable error given by

For appropriate and signal energy, we have . As a result, Eve's data involves error by irreducible noise. Thus, Y-00 is a new type of quantum cryptography based on quantum detection theory. That is, the security is guaranteed by quantum noise, but the system can be implemented by conventional devices. As quantum advantage, Y-00 provides secrecy against quantum computer and quantum attacks. We can summarize the property of Y-00 as follows: In the cipher-text only attack, Y-00 may exceed the classical Shannon limit. That is,

where is information, is ciphertext as ``measured value'' for Eve, and is initial seed key. Even with , intuitively, the search complexity is between and in Y-00, . For known plaintext attack, it will be expected that

which corresponds to information-theoretic security. If one has , then it is full security. If there are some algorithm for computing to find the key based on the measured data including error, then . Even so, the system may be secure in the sense of high search complexity. Fortunately, by introducing several new randomizations(for example, DSR: deliberate signal randomization), Y-00 may provides information-theoretically secure scheme with very efficient performance for direct encryption.

In the case of key generation protocol, data is a true random number sequence. So there is no criterion like known plaintext attack. In the conventional theory of key generation, if one has

then key generation is possible. That is, under this condition, an information-theoretic existence proof is given. Then an asymptotic key generation rate is as follows:

under the condition of no public discussion. However, so far there was no theoretical discussion on scheme with shared seed key between Alice and Bob. In the above subsection, we explained a basic scheme of Y-00. By this scheme, we can also make a key generation scheme. As we mentioned, the use of shared seed key between Alice and Bob that determine the quantum states generated for the data bit sequences in a detection/coding scheme between Alice and Bob that gives them a better error performance over Eve who does not know . Based on the above scheme, the conditions were generalized to include the use of a shared seed key. Let us introduce the basic result here.

Remark: For the scheme with the seed key, one has to make sure that the generated key: between Alice and Bob is fresh. That is, the generated key is independent of the initial seed key, and .

In order to characterize this situation, we allow that Eve can know the key only after she has made her measurement. So her information is described by . As a result, the condition for secure key generation is

where is Bob's observation with knowledge of the seed key. The above result means that Eve can get the key after Eve's measurement as a kind of side information. In the quantum signal detection theory, the difference between ``before measurement'' and ``after measurement'' on the knowledge of key which control the quantum measurement is essential. In the classical channel, there may be no difference for the order of the knowledge of key. That is,

By choosing a rate below the key rate, one may be able to force the Eve's information to be zero as a consequence of the well known coding theorem. However, finally, this new quantum key generation is unconditionally secure without the use of further channel coding, which means that it is realizable in the sense of practical use.

In this review, we have introduced the basic structure of Yuen's new quantum cryptography as an application of quantum communication theory. In my lecture, we will give some concrete performance of Y-00.

A.S. Holevo: An exactly solvable model related to the additivity problem for quantum channels

We give a direct proof of the additivity of the minimum output entropy of a particular quantum channel which breaks the multiplicativity conjecture. This yields additivity of the classical capacity of this channel, a result obtained by a different method by Nagaoka and Yura. Our proof relies heavily upon certain concavity properties of the output entropy which are of independent interest.

The pseudorandom properties of finite binary sequences have been studied recently intensively by Mauduit and Sárközy. In the papers written on this subject the two distinct elements of the sequences are chosen equally with probability . In this paper the authors extend the work to the more general case when the two elements are chosen with probability , resp. .

Network theory, used to describe local and global properties of many interconnected agents, is highly interdisciplinary, attracting the attention of, among others, mathematicians, sociologists, and physicists. Perhaps surprisingly, very little use has been made of the network approach in the study of social interactions between wild animals, despite the potential to make predictions regarding both the ecological (e.g. the transmission of information and disease) and evolutionary (e.g. the potential for reciprocal altruism) properties of populations. In this talk I will present some of the simple ideas from network analysis that might help extract some of these properties.

S. Perdrix and P. Jorrand: Toward Minimal Resources for Universal Measurement-Based Quantum Turing Machines

The driving force of research in quantum computation is that of looking for the consequences of having information encoding, processing and communication make use of quantum physics, i.e. of the ultimate knowledge that we have, today, of the physical world, as described by quantum mechanics. Quantum mechanics, the mathematical formulation of quantum physics, relies on four postulates: (i) the state space of a quantum system is a Hilbert space; (ii) the evolution of the state of a closed quantum system is deterministic and characterized by a unitary operator; (iii) measurement, i.e. the evolution of a quantum system interacting with its (classical) environment is probabilistic and characterized by an hermitian operator named observable; and (iv) the state space of a quantum system composed of several quantum subsystems is the tensor product of the state spaces of its components. The question is then: how to take advantage of these postulates to the benefits of computation?

The most common approach to quantum computation exploits all four postulates in a rather straightforward manner. The elementary carrier of information is a qubit: the state of a n-qubit register lives in a -dimensional Hilbert space, the tensor product of n 2-dimensional Hilbert spaces (postulates i and iv). Then, by reproducing in the quantum world the most traditional organization of classical computation, quantum computations are considered as comprising three steps in sequence: first, initial state preparation (postulate iii can be used for that, possibly with postulate ii); second, computation by deterministic unitary state transformation (postulate ii); and third, output of a result by probabilistic measurement (postulate iii).

The second step assumes that the n-qubit register is a closed quantum system, i.e. does not interact with its environment while the computation is going on. This creates very severe difficulties for the implementation of physical quantum computing devices. A physical qubit is indeed necessarily interacting with an external physical environment, either because the qubit is constrained to reside in some precise location (e.g. ion traps), or because it ``flies'' across some free space while being operated upon (photons). In both cases, the state becomes entangled with (i.e. dependent upon) the states of particles belonging to the environment: the state is altered and, after a time depending on the chosen technology, it is no longer relevant for the ongoing computation. This unavoidable physical process, known as decoherence, can be kept under control by means of quantum error correcting codes. But this is highly resource consuming. Depending on the scheme chosen, such codes require 3 to 9 physical 4 6 qubits per logical qubit, and the correction process takes time (10 to 10 elementary unitary operations must be achievable within the decoherence time for ensuring successful error correction).

Then, the idea is: instead of trying to climb over the high and steep physical obstacle of decoherence, just avoid it, disregard the second postulate, and rely upon the three other postulates only. In addition to being physically motivated, this has also been proved to be computationally relevant. Nielsen [3] has indeed shown that a generalization of quantum teleportation can be used for designing a universal quantum computation scheme based on measurement on at most 4 qubits. Leung [1,2] has improved this result by showing that measurements on at most 2 qubits are universal. A seemingly very different approach has been proposed by Briegel and Raussendorf [5,6]. In their ``One way quantum computer'', a grid of qubits is initially prepared in a special fully entangled state, the ``cluster state'', where some of the qubits encode the input of the computation and others are designated as output qubits. Computation then operates stepwise, by successively measuring individual qubits: at each step, a yet unmeasured qubit and an observable are chosen and the corresponding measurement is applied. While the initial entanglement is consumed step by step by these measurements, a result is eventually pushed to the output qubits. However these two measurement-based quantum computation schemes, both proved to be universal, are still rather specific. There is a need for a more abstract model, of which both would be instances.

This presentation (based upon [4], with a few afterthoughts) introduces a new family of abstract computation models, Measurement-Based Quantum Turing Machines (MQTM). A hierarchy of models of that sort, ranked according to the amount of resources they use, are proved to be universal for quantum computation. While also pointing out the necessity and the precise role of classical control in measurement-based quantum computation, one of these models exhibits a new upper bound for the minimal resources needed for achieving quantum universality. Another class of such models, with slightly more restricted resources, is proved universal for classical computations, and proved not universal for quantum computations, thus characterizing, by comparing the amounts of resources, where the gap is between the classical and the quantum approaches to computing.

Let be a finite set and be a family of its subsets. is determined when certain configurations are excluded. The excluded configurations are determined by inclusions only. The following one is a typical theorem. Suppose that contains no 4 distinct members such that (4 inclusions). Then is at most the size of the two largest levels, that is the number of all subsets of sizes and . Another example is when the family contains no distinct members satisfying . Then the family can have at most members. This is nearly sharp, since there is a construction containing members. The new results are jointly done with A. De Bonis.

Young diagram is a collection of cells arranged in left-justified rows with a weakly decreasing number of boxes in each row. Listing the number of boxes corresponds to a partition of the integer . Any way of putting a number from the set in each cell is called a filling of the diagram. A (standard) Young tableau is a filling that is (a) strictly increasing across each row and (b) strictly increasing down each column. The Young tableau is called a tableau on the diagram . The basic problem is the counting of Young tableaux on any diagram . The answer is given by the famous Hook formula, that is, , where is the Hook function of . Let us extend the concept of Young tableaux to three dimension. Three dimensional Young diagram is specified by an extremal set of boxes. Box, or point, is represented by three dimensional coordinate. The partial order between points is defined as: iff and . A set of points is called extremal if there are no partial order relations between any two points in the set. A three dimensional Young diagram defined by an extremal set is a collection of points, . Furthermore, we can introduce three dimensional Young tableau as in two dimension, and consider the problem of counting the number of three dimensional Young tableaux for any extremal set. Then, we can get a recursion formula for the counting function. Using this formula, we can show the number of Young tableaux to be over three trillion, that is, 6,405,442,434,150.

E. Konstantinova: Sorting and reconstructing permutations in the reversal metric

The reconstruction of permutations distorted by single reversal errors is considered in the paper. This problem is related to the problem of sorting permutations by reversals [1]. One of the mathematical objects of molecular biology is the set of permutations on n elements with the metric which is equal to the minimum number of errors being inversions of an interval that transforms one a permutation to other one. In the paper the problem of finding the minimum number of permutations in a metric ball of a given radius r sufficient to determine uniquely the center of this ball is considered. It is proved that tree permutations obtained from an unknown permutation , , by at most one reversal error in general are not sufficient to reconstruct this permutation. However, any four permutations allow to determine whether there exists a permutation such that these four permutations are obtained from by at most one reversal error and determine uniquely such a permutation if it exists. To get these results we investigate some structure properties of the graph with the reversal metric. In particular, we prove that does not contain bipartite subgraphs . A simple reconstruction algorithm is given also.

In this talk, we discuss the notion of -linked graphs and find sufficient minimum degree conditions for a graph to be -linked.

For a fixed multigraph with vertices , a graph is -linked if for every choice of vertices in , there exists a subdivision of in such that is the branch vertex representing (for all ). This generalizes the notions of -linked, -connected, and -ordered graphs.

Theorem 1. Let be a simple graph with edges and . Every graph of order with is -linked.

Theorem 2. Let be a loopless graph with edges and . Let denote the maximum number of edges over all bipartite subgraphs of . Then every simple graph of order with is -linked.

Note that is exactly the minimum degree condition that provides the -connectivity of . Thus, an evident degree condition for a graph to be -connected, provides that a graph is -linked for many . If one drops the condition , then this degree restriction is not sufficient in general.

The application of network theory to social interactions between animals is an exciting new area of research, and has the potential to make predictions regarding both the ecological and evolutionary properties of populations. However, very few studies have examined social network structure in wild animal populations, and those that have lack replication. Here we present information on the social network structure for two fish species, three-spined sticklebacks (Gasterosteus aculeatus) and guppies (Poecilia reticulata). Furthermore, we present data on multiple populations in guppies allowing us to comment on the general properties of network structure in the species. Social network structure is quantified using mark, release and recapture data, whereby individual fish are given unique identification tags and their social companions documented over a five to seven day period. We found all populations (in both species) to have highly structured social networks that exhibited characteristics consistent with the 'small world' phenomenon (i.e. short path length between individuals but social cliquishness). Furthermore, in both species we observed a significant co-occurrence of pairs of individuals, a finding that fulfils the basic prerequisite for the evolution of reciprocal altruism. The importance of such pair-wise persistence of association patterns is discussed in the context of social learning and predator inspection behaviour.

T. Helleseth, T. Klöve and V.I. Levenshtein: Error-correction capability of binary linear codes beyond the half the minimum distance

The monotone structure of correctable and uncorrectable errors given by the complete decoding for a binary linear code is investigated. It is proved that the simplex codes do not minimize the probability of a decoding error in symmetric binary channels among linear codes of the same length and dimension. New bounds on the error-correction capability of linear codes beyond the half the minimum distance are presented, both for the best codes and for arbitrary codes under some restrictions to their parameters. It is proved that some known codes of low rate are good as the best codes in an asymptotic sense. A conjecture on a threshold property of the error-correction capability of sequences of linear codes and its connection with strengthening Kruscal-Katona theorem for monotone structures formed by correctable and uncorrectable errors for linear codes are given.

Y. Aumann, M. Lewenstein, N. Lewenstein, and D. Tsur: Peeling Codes with Applications to Finding Witnesses

We consider the general setting in which there is a set , with elements taken from some commutative group , of which we seek to discover elements. The set is not provided to us explicitly. Rather, we are provided procedures such that for any set , we can compute the size of and the sum (in the group) of the elements in this intersection. We are interested in minimizing the total work to discover the elements. We introduce the notion of Peeling Collections (or Peeling Codes) which provide efficient solutions to several versions of this general setting. Applications arise in pattern matching and shortest path problems.

R. Ahlswede, B. Balkenhol, C. Deppe, H. Mashurian and T. Partner: T-shift synchronization codes (see [D7])

N. Alon, Y. Kohayakawa, C. Mauduit, C.G. Moreira, and V. Rodl: Measures of pseudorandomness for finite sequences: minimal values

In a series of papers, A. Sarkozy and myself introduced new measures of pseudorandomness for finite binary sequences. These measures are connected to the regularity of the distribution relative to arithmetic progressions, the correlations and the normality. We will present recent results obtained concerning the minima of these measures.

H. Morita and T. Ota: On-line ECG Lossless Compression Using Antidictionaries

An antidictionary is a set of words that never appear in the source data. In 2000, M. Crochemore et. al. have presented a compression algorithm of binary text using antidictionaries [1]. Their coding algorithm has been tested on the Calgary Corpus, and experiments show that we get compression ratios equivalent to those of most common compressors such as pkzip. In this talk, we will show the size of the antidictionary of a finite binary string is less than or equal to that of the dictionary of the string. It supports Crochemore's experiments theoretically. Moreover, we study on the length of substring needed to construct an antidictionary whose size is almost same as that of the entire string of ECG using the results of coupon collector's problems. Experimental results show the proposed algorithm achieved 10% smaller compression ratio than LZ algorithms.

Let A be the binary alphabet and be the set of all finite strings over including the null string of length zero, denoted by . Let be all the substrings of binary string :

is called as a minimal forbidden word (MF) of . The antidictionary of x , denoted by , is defined as the set of MF's of .

First, we consider the case that . We can represent by where and . Let . By Lemma 2, we have . Hence, for each , there exists at most one such that for . It means that

This is an introduction to subsequent talks on joint results with Ahlswede, Cicalese and Deppe about asymmetric coding in arbitrary weighted channels. We shall discuss how the basic conservation laws for information in symmetric coding have a more sophisticated, but still useful formulation in asymmetric coding.

Most animal communication evolved and takes place in the context of a communication network, i.e. several signalers and receivers within communication range of each other. This is self evidently true for long-range signals, but at high density the same is true for short-range signals. There is a growing body of information on the nature of communication networks from the striking choruses of some insects and amphibians to the more extensive networks of visually signaling fish and the long-lived, sometimes territorial birds and mammals. In communication networks, animals can gather information by attending to others' signals and by attending to the signaling interactions between other signalers. Extracting information from signaling interactions can provide receivers with information of a different quality than extracting information from single signals, as the relation of signals to each other can reveal direct information on relative differences in motivation or quality between the signalers. Here, I will provide a general overview on the current state of research on communication networks in animals and describe some recent findings on communication networks in territorial songbirds.

A. Orlitsky, P. Santhanam, and J. Zhang: From 2 to infinity: Information theory of large alphabets

Most information-theoretic results assume fixed, typically binary, alphabets. Yet most practical sources, such as text, audio, or video, have essentially infinite alphabets. To address such sources, we consider not the sequence of observed symbols, but the pattern they form. We show that the patterns of i.i.d. strings over all, including infinite and even unknown, alphabets, can be compressed essentially as well as when the underlying distribution is known in advance, both in block and sequentially.

To prove these results, we relate the problem to a probability estimator designed by I.J. Good and A. Turing while deciphering the Enigma code during World War II, and apply results by Hardy and Ramanujan on the number of integer partitions.

Motifs or patterns in genomic or protein sequences have a strong potential for revealing hitherto unknown structure or functionality. An appropriate definition of motif is however a challenge when the need is to balance its generality with an efficient, practical algorithm to discover them in an unsupervised manner. Rigid motifs are substrings with fixed gaps and dyad motifs are a pair of rigid motifs with varying gaps between the pair of rigid motifs. We use a generalized definition of extensible motifs where there can be m ordered rigid motifs with variable distance between them: these rigid motifs can be single characters or of a predefined density (ratio of wild to solid characters) and size. In this talk we will discuss extensible patterns, the implementation, and comparison with other kinds of patterns and applications.

V. Prelov: On perfect reconstruction of singular sequences from noisy observation

Let be a two-dimensional, partially observable, discrete time, stationary stochastic process where is the non-observable and the observable component. We shall take an interest in finding rather general conditions under which the perfect (error-free) reconstruction of from the observations is possible.

Assume first that is a completely singular stationary process that is transmitted (without any coding) through a memoryless discrete time channel and is the output of this channel. Then we show that in such a situation the perfect reconstruction of the value from the observation is possible for arbitrary .

Further, let where and are a completely singular and a weakly regular stationary stochastic processes, respectively, and does not depend on . It is shown that the value of can be reconstructed without error from the observations for any .

Also, we find some sufficient conditions under which the perfect reconstruction of is possible in the case of rather general non-stationary distortions. In the proof of these results some non-standard information-theoretic methods are intensively used.

The Common Connected Problem (CCP) consists in identifying common connected components of two or more graphs on or reduced to the same vertex set. More formally, let and be two such graphs and let and be the two subgraphs induced by a set of vertices subset of . If and are both connected, is said a common connected component. CCP is the identification of such maximal components (considering the inclusion order), that form a partition of . Let and . We present a non-trivial algorithm solving CCP, running in worst case time. The algorithm combines a dynamical maintenance of spanning forests together with a Hopcroft-like partitioning approach.

The topic of my talk will be on the construction of some new pseudorandom sequences using number theory, including a discussion of theoretical and practical aspects of the notion of pseudorandomness, mostly on the measures introduced by Mauduit and Sárközy.

A. Sanpera, D. Bruss, O. Guehne, P. Hyllus, M. Lewenstein M. Bourennane, H. Weinfurter, M. Eibl, Ch. Kurtsiefer, and S. Gaertner: Witnessing Entanglement

Witnessing entanglement is one of the most challenging tasks both theoretically and experimentally in the area of quantum information. Genuine multipartite entanglement becomes increasingly complex when the number of parties involved increases. Here I will present some of our recent theoretical and experimental results which unambigously demonstrate the detection of genuine multipartite entanglement for 3 and 4-qubit states using the method of entanglement witnesses.

A. Sárközy: On pseudorandom binary sequences and their applications in cryptography

Finite pseudorandom binary sequences play a very important role in cryptography. Usually a computational complexity approach is used to measure the pseudorandom properties of a sequence or of the family of sequences. This approach has certain weak points (to be discussed in the talk), thus recently Mauduit and Sárközy have introduced new measures of pseudorandomness. Goubin, Mauduit, Rivat and Sárközy have constructed large families of binary sequences with good pseudorandom properties in this sense. Ahlswede, Khachatrian, Mauduit, Sárközy and Stewart have introduced and studied further measures of pseudorandomness which are closely connected with the applications in cryptography.

One of the most interesting open problems in quantum information theory is the additivity conjecture for the Holevo capacity of a quantum channel. The role of this conjecture was stressed by Shor's recent proof of its equivalence to several other (sub)additivity problems, in particular, to the additivity conjecture for the minimal output entropy. We propose an observation concerning these additivity problems and based on a particular structure result for subsets of state space of tensor product channel.

For a given quantum channel we consider two optimal sets of states, related to the Holevo capacity and to the minimal output entropy of this channel correspondingly. Some properties of these sets and its convex duality representation are considered.

The additivity of the Holevo capacity for two channels means an existence of an optimal ensemble for tensor product channel, consisting of product states. The assumption of an existence of an optimal ensemble with product state average does not imply additivity of the Holevo capacity, but can be considered as the first step in its proving. We start from the above assumption for two fixed channels with arbitrary constraints and show that optimal sets for the tensor product channel have special hereditary property in this case. This hereditary property of an arbitrary set with pure extreme points imposes strong constraints on the structure of this set. By applying these constraints to the optimal sets for tensor product channel it is possible to obtain interesting conclusions about states with the minimal output entropy (optimal states) and the optimal ensembles for this channel. In particular, it is shown (under the above assumption) that among states with the minimal output entropy for tensor product channel there exist states of special form, called uniformly entangled , whose partial traces are multiple of projectors.

This result implies the following observation. Suppose additivity of the minimal output entropy does not hold for two particular channels while the above assumption concerning average states of optimal ensembles is true for tensor product of these channels. Then the hereditary property of the optimal set for the minimal output entropy implies an existence of the subchannels of the above channels with the following property: only maximally entangled states can be optimal for the tensor product of these subchannels and the chaotic state can be represented as a mixture of maximally entangled optimal states. If we call channels with this special property strongly nonadditive in the sense of the minimal output entropy then we can observe that the global additivity conjecture is equivalent to the union of two following assertions:

Each of the above assertions seems to be weaker then the global additivity conjecture and can be considered separately. This provides a possible way of treating the global additivity conjecture.

The key notion which explains why a classical information stream can be compressed is that of the typical subset. The lecture gives a survey on recent results for streams of qbits which extend the classical theory to quantum sources.

H. Weingarten, Y. Steinberg, and S. Shamai: On the Capacity Region of the General Vector Gaussian Broadcast Channel

We address the widely studied vector Gaussian broadcast channel (VGBC). The general VGBC is not a degraded channel, and therefore its capacity region cannot be characetrized by the classical informational formula for the capacity of the degraded broadcast channel. The classical technique for proving the upper bound for the capacity region of the Gaussian BC, namely, the entropy-power inequality (EPI), fails here due to Minkowsky inequality. We prove that the achievable region which results from Gaussian input statistics, and ``dirty paper coding,'' is indeed the capacity region. Our technique is based on the vector EPI, combined with a new fundamental notion of an enhanced broadcast channel.

In this talk we plan to discuss some joint work with A.Sárközy concerning pseudorandom binary sequences.We shall construct a large family of such sequences with a remarkable uniformity within the family.

The comparison of genomes based on their gene content and gene order is an important means to track large-scale evolutionary events and to annotate gene function. In this presentation, we will discuss several new models and algorithms for such genome comparison ``at a higher level''.

We will discuss the use of common intervals, i.e. intervals containing the same set of genes in multiple genomes, and give efficient algorithms to find them in permutations and in sequences. We will also mention a special subtype of common intervals, conserved intervals, which not only act as a basis of a new whole-genome phylogenetic distance measure, but also are a key feature of genome rearrangement theories like sorting by reversals or transpositions.

In the first part of the lecture a survey on normal numbers metric theory of uniform distribution is given. In the second part metric theorems for distribution measures of pseudorandom sequences are discussed (joint work with W. Philipp).

Let , where denotes the fractional part of and the indicator function of the set . Throughout this paper denotes an increasing sequence of positive integers and . For we define

Among other things, MAUDUIT and S´ARK´´OZY (2000) prove metric results for sequences . Our first result can handle arbitrary increasing sequences and for it yields a sharper error term.

The third part is devoted to the analysis of pair correlations as studied by Rudnick, Sarnak and Zaharescu. Here some joint results of I. Berkes, W. Philipp and R. Tichy are presented.
We prove a Glivenko-Cantelli type strong law of large numbers for the pair correlation of independent random variables. Except for a few powers of logarithms the results obtained are sharp. Similar estimates hold for the pair correlation of lacunary sequences mod 1.

A fixed-to-variable length source code, FV-code, maps fixed length source sequences onto variable length codewords. The optimal code construction is Huffman's construction, see [1]. Variable-to-fixed length source codes, VF-codes, map variable length source sequences onto fixed length codewords. For memoryless sources the optimal code is found using the Tunstall procedure, see [2].

In this presentation we shall consider the storage complexity of the FV-codes and VF codes in relation to the achieved redundancy. Often storage complexity can be traded with time complexity. We shall limit the time complexity in the following way. The cost of coding n symbols (on the average) can be at most. This means that coding a letter takes at most a constant amount of time, independent of n. We shall not consider the cost of designing the code, but only the amount of memory needed in the encoder and decoder.

Both Huffman and Tunstall codes are naturally represented by (binary) rooted trees. The storage cost of representing a tree is at least linear in the number of leaves of the tree, i.e. it is of .

An efficient implementation of a Huffman encoder/decoder was given in [3]. In [4] the storage cost was analyzed and shown to be not more than . In this paper we shall show that is attainable. For the Tunstall codes, an efficient implementation comes from the enumerative approach of [5]. Again we shall show that the storage cost is . Both the Huffman and the Tunstall code have a redundancy which is of order .

Although Arithmetic Codes, see e.g. [6], have a worse redundancy behavior we shall show that in terms of redundancy versus storage complexity these codes outperform both efficient implementations of the Huffman and the Tunstall code.

F. Topsoe: Games of information with applications in physics, finance and other areas

The simplest conflict situations which can be dealt with from a game theoretical point of view concern two-person zero-sum games. This is the setting we will discuss in cases where the objective function can be viewed as complexity or description length. It appears that this type of games address a fundamental aspect in physics and other sciences, viz. the inmterplay between the observer (the physicist, the investor, the statistician or what the case may be) on the one hand and the system (statistical mechanical system, market, data or ...) on the other.

In the talk I will focus first on simple theoretical facts related to the notion of Nash equilibrium and then outline possible applications, probably with emphasis on non-extensive statistical physics (going beyond Boltzmann-Gibbs-Shannon theory) and on some models related to finance.

E.C. van der Meulen and S. Vangheluwe: New Signature Codes for the -user multiple-accessbinary adder channel with a changing user-population

Abstract:

By combining techniques of Chang [3] and Cantor and Mills [2], we con-struct signature codes for a -user binary adder multiple access channel, when any subset of users can be active at any time, for new values of the parameters (the codeword length) and , different from the ones which can be obtained directly from the Cantor and Mills construction.

We consider a multiple-access communication system, in which users share a common, bit and block synchronized, binary adder channel. In the classical -user multiple-access channel, as defined in multi-user information theory, all users are assumed to be active. In this setup, messages, emanating from statistically independent sources, are encoded independently according to block codes called a -user code ; each individual code is called a constituent code. For the -input noiseless binary adder channel each user's input alphabet is the integer set and the output is the sum of the inputs , i.e. . A -user code for the binary adder MAC is said to be uniquely decodable (UD) iff all sums consisting of one codeword each from each constituent code are distinct. Chang and Weldon [4] presented the capacity region of the memoryless noiseless -user binary adder channel and constructed a class of -user UD codes of length for this channel where

Another multiple-access situation arises when the -users are not always active, as is the case in many real-life examples. In the model adopted by A. and Györfi [1] one assumes that the set of users changes with time, but that the number of active users is at most at any instant, . For this multiple-access situation with a partially-active user population one principal task to be performed by the receiver is to identify the set of active users. This problem can be studied with so-called signature codes, where each user has two codewords one of which is the all-zero one. The inactive users send the all-zero codeword while the active users send their other codeword. Formally, each user is equipped with a binary -dimensional vector . The output of the binary adder MAC with partially active users is the sum of the input vectors assigned to the active users:

where denotes the set of active users. Following A and Györfi [1] we call a set of binary vectors of length a UD signature code of parameter , denoted by iff all sums of at most distinct vectors in the code are different. We consider here only the case , i.e., -codes. Both Lindström [5] and Cantor and Mills [2] presented constructions of UD signature codes for the binary adder MAC for certain pairs with

There is an interesting connection between the Chang-Weldon codes given by (1) and the signature codes given by (2). Chang [3] analyzed the Chang-Weldon code construction further and provided schemes for the explicit construction of -user UD codes of arbitrary length for the -user binary adder MAC considered in the first setup. His constructive schemes are based on a shortening algorithm applied to the difference matrix obtained at step in the iterative Chang-Weldon procedure.

Motivated by Chang's search for additional Chang-Weldon type codes, we applied a similar shortening technique to the matrices occurring in the Cantor and Mills construction of signature codes , and thus obtained signature codes for other parameter values than those given by (2). Since the restrictions on a signature code are more stringent than those on a -user code for a binary adder MAC in the first setup, our shortening technique is also more complicated than the one invented by Chang. It involves the removal of rows and columns of various matrices at different steps of the Cantor and Mills procedure.

In this report we consider the Wyner-Ziv (1976) configuration. In this source coding situation with a fidelity criterion only the decoder gets side-information from the source. The rate-distortion function for this configuration was found by Wyner and Ziv. Here we give a formulation of this function in terms of what we call Shannon strategies. For this formulation we can prove that it is itself continuous for distortion 0. This fact was not proved by Wyner and Ziv. Using our formulation we can also find an algorithm that computes the Wyner-Ziv function. In this algorithm techniques of Blahut (1972) and Csiszar and Korner (1981) are applied.

I will describe recent progress in understanding the identification capacity of quantum channels. Loeber has introduced the ``simultaneous ID capacity'' of a quantum channel, and using his and Steinberg's results one can see that it equals the transmission capacity. However, non- simultaneous ID capacity behaves differently: while it is the transmission capacity for cq-channels (Ahlswede/Winter, 2001) and for qc-channels (Winter, 2004), even for a noiseless qubit it is not 1 but 2. We can compute it for some simple channels but in general, its determination is an open problem. In fact, in generalisation of a construction by Ahlswede and Dueck (that common randomness of rate R and zero-rate communication allow identification rate R), we can show that entanglement (EPR pairs) of rate E and zero-rate communication allow identification rate 2E. This is used to determine various feedback ID capacities of quantum channels. If time permits, I will also comment on initial studies of ``identification of quantum messages'' and the (partial) results obtained so far.

K. Ishii and H. Yamamoto: Variations of Sequential MPM Codes with O(1/log n) Maximum Redundancy

The Multilevel Pattern Matching (MPM) code can attain O(1/lon n) maximum redundancy for any finite-sate information source with length n. Although the original MPM code encodes source sequences blockwise, only one directional matching is used in the encoding. Hence, the MPM coding can be implemented sequentially as a kind of dictionary method like Lempel-Ziv codes. We have already shown that the Sequential MPM (S-MPM) coding can also attain O(1/long n) maximum redundancy. We can easily derive from the result that any variation of the S-MPM code can attain O(1/log n) maximum redundancy if the total number of words registered in the dictionary and the total number of parsing of a source sequence are the same or less order than the S-MPM coding. In this talk, we propose some variations of the S-MPM code. Since the variations attain less number of parsing and the same dictionary size as the S-MPM code, they attain O(1/lon n) maximum redundancy. The performances of variations are also compared for Calgary Compression Corpus to show that for practical files, the variations can attain better performance than the original MPM code and S-MPM code.