Supermodularity and subadditivity properties of the entropy on themajorization lattice

We prove that the entropy is a supermodular and subadditive function on the lattice of all n-dimensional probability distributions, ordered according to the partial order relation defined by majorization among vectors     

Faster Deterministic Communication in Radio Networks

We study the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication) in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed based on full knowledge about the size and the topology of the network. We show that gossiping can be completed in time units in any radio network of size n, diameter D, and maximum degree Δ=Ω(log n). This is an almost optimal schedule in the sense that there exists a radio network topology, specifically a Δ-regular tree, in which the radio gossiping cannot be completed in less than units of time. Moreover, we show a schedule for the broadcast task. Both our transmission schemes significantly improve upon the currently best known schedules by Gąsieniec, Peleg, and Xin (Proceedings of the 24th Annual ACM SIGACT-SIGOPS PODC, pp. 129–137, 2005), i.e., a O(D+Δlog n) time schedule for gossiping and a D+O(log ³ n) time schedule for broadcast. Our broadcasting schedule also improves, for large D, a very recent O(D+log ² n) time broadcasting schedule by Kowalski and Pelc. A preliminary version of this paper appeared in the proceedings of ISAAC’06. F. Cicalese supported by the Sofja Kovalevskaja Award 2004 of the Alexander von Humboldt Stiftung. F. Manne and Q. Xin supported by the Research Council of Norway through the SPECTRUM project.     

Multi-Criteria Decision Making support system for pancreatic islet transplantation

Pancreatic islet transplantation consists of replacing insulin-producing cells to restore normal glycemia in diabetic patients. This is a minimal invasive procedure that has been proved successful. Unfortunately unpredictability of islet transplant outcome remains a frustrating and costly issue limiting the clinical implementation of this procedure. Multiple variables are involved in the procedure and assessment is subjective to individual operators. The aim of this study was to generate a system expressing the probability of transplant success in relation to four classes of identified variables (donor, organ, isolation and recipient). We have proposed the utilization of Multi-Criteria Decision Making methods (MCDM) as a powerful tool for evaluating pancreatic islet transplant-related information with the goal to achieve optimal decision. Technique Ordered Preference by Similarity to the Ideal Solution (TOPSIS), one of the most widely used MCDM methods in decision support systems, was here utilized with modification to fit better in a medical system. In our modified method, we have utilized fuzzy logic in order to consider uncertain and vague data.     

Bounding the average length of optimal source codes via majorization theory

We consider the problem of bounding the average length of an optimal (Huffman) source code when only limited knowledge of the source symbol probability distribution is available. For instance, we provide tight upper and lower bounds on the average length of optimal source codes when only the largest or the smallest source symbol probability is known. Our results rely on basic results of majorization theory and on the Schur concavity of the minimum average length of variable-length source codes for discrete memoryless sources. In the way to prove our main result we also give closed formula expressions for the average length of Huffman codes for several classes of probability distributions.     

Perfect Strategies for the Ulam-Rényi Game with Multi-interval Questions

We study a new variant of the classical 20 question game with lies (a.k.a. Ulam-Rényi game). The Ulam-Rényi game models the problem of identifying an initially unknown m-bit number by asking subset questions, where up to e of the answers might be mendacious. In the variant considered in this paper, we set an additional constraint on the type of questions, namely, that the subsets they ask for should be the union of at most k intervals for some k>0 fixed beforehand. We show that for any e and m, there exists k only depending on e such that strategies using k-interval question are as powerful (in terms of the minimum number of queries needed) as the best strategies using arbitrary membership questions.     

Optimal strategies against a liar

We consider the following scenario: There are two individuals, say Q (Questioner) and R (Responder), involved in a search game. Player R chooses a number, say x, from the set S={1,…,M}. Player Q has to find out x by asking questions of type: “which one of the sets A₁,A₂,…,A_q, does x belong to?”, where the sets A₁,…,A_q constitute a partition of S. Player R answers “i” to indicate that the number x belongs to A_i. We are interested in the least number of questions player Q has to ask in order to be always able to correctly guess the number x, provided that R can lie at most e times. The case e=0 obviously reduces to the classical q-ary search, and the necessary number of questions is [log_qM]. The case q=2 and e1 has been widely studied, and it is generally referred to as Ulam's game. In this paper we consider the general case of arbitrary q2. Under the assumption that player R is allowed to lie at most twice throughout the game, we determine the minimum number of questions Q needs to ask in order to successfully search for x in a set of cardinality M=qⁱ, for any i1. As a corollary, we obtain a counterexample to a recently proposed conjecture of Aigner, for the case of an arbitrary number of lies. We also exactly solve the problem when player R is allowed to lie a fixed but otherwise arbitrary number of times e, and M=qⁱ, with i not too large with respect to q. For the general case of arbitrary M, we give fairly tight upper and lower bounds on the number of the necessary questions.     

Least adaptive optimal search with unreliable tests

We consider the basic problem of searching for an unknown m-bit number by asking the minimum possible number of yes–no questions, when up to a finite number e of the answers may be erroneous. In case the (i+1)th question is adaptively asked after receiving the answer to the ith question, the problem was posed by Ulam and Rényi and is strictly related to Berlekamp's theory of error correcting communication with noiseless feedback. Conversely, in the fully non-adaptive model when all questions are asked before knowing any answer, the problem amounts to finding a shortest e-error correcting code. Let q_e(m) be the smallest integer q satisfying Berlekamp’s bound . Then at least q_e(m) questions are necessary, in the adaptive, as well as in the non-adaptive model. In the fully adaptive case, optimal searching strategies using exactly q_e(m) questions always exist up to finitely many exceptional m's. At the opposite non-adaptive case, searching strategies with exactly q_e(m) questions—or equivalently, e-error correcting codes with 2^m codewords of length q_e(m)—are rather the exception, already for e=2, and are generally not known to exist for e>2. In this paper, for each e>1 and all sufficiently large m, we exhibit searching strategies that use a first batch of m non-adaptive questions and then, only depending on the answers to these m questions, a second batch of q_e(m)−m non-adaptive questions. These strategies are automatically optimal. Since even in the fully adaptive case, q_e(m)−1 questions do not suffice to find the unknown number, and q_e(m) questions generally do not suffice in the non-adaptive case, the results of our paper provide e fault tolerant searching strategies with minimum adaptiveness and minimum number of tests.