Consider a group of stations connected through a multiple-access channel, with the constraint that if at a time instant exactly one station transmits a message, then the message is successfully received by any other station, whereas if two or more stations simultaneously transmit their messages then a conflict occurs and all messages are lost. Let us assume that n is the number of stations and that an (arbitrary) subset A of them, |A| ≤ k ≤ n, is active, that is, there are at most k stations that have a message to send over the channel. In the classical conflict resolution problem, the issue is to schedule the transmissions of each station to let every active station use the channel alone (i.e., without conflict) at least once, and this requirement must be satisfied whatever might be the set of active stations A. The parameter to optimize is, usually, the worst case number of transmissions that any station has to attempt before all message transmissions are successful. In this paper, we study the following question: is it possible to obtain a significant improvement on the protocols that solve the classical conflict resolution problem if we allow the protocols to fail over a “small” fraction of all possible subsets of active stations? In other words, is it possible to significantly reduce the number of transmissions that must be attempted if the set of active stations is chosen uniformly at random and the conflict resolution algorithm is only required to work correctly with “high” probability? In this paper, we will show that this is indeed the case. Our main technical tool is a generalization of selectors, a recently introduced combinatorial structure that has found applications in several areas. As it turned out for selectors, we believe that our new combinatorial structures are likely to be useful also outside the present context.

We consider the Conflict Resolution Problem in the context of a multiple-access system in which several stations can transmit their messages simultaneously to the channel. We assume that there are n stations and that at most k, k <= n, stations are active at the same time, i.e, are willing to transmit a message over the channel. If in a certain instant at most d, d <= k, active stations transmit to the channel then their messages are successfully transmitted, whereas if more than d active stations transmit simultaneously then their messages are lost. In this latter case we say that a conflict occurs. The present paper investigates non-adaptive conflict resolution algorithms working under the assumption that active stations receive a feedback from the channel that informs them on whether their messages have been successfully transmitted. If a station becomes aware that its message has been correctly sent over the channel then it becomes immediately inactive, that is, stops transmitting. The measure to optimize is the number of time slots needed to solve conflicts among all active stations. The fundamental question is how much this measure decreases with the number d of messages that can be simultaneously transmitted with success. In this paper we prove that it is possible to achieve a speedup linear in d by providing a conflict resolution algorithm that uses a 1/d ratio of the number of time slots used by the optimal conflict resolution algorithm for the particular case d = 1. Moreover, we derive a lower bound on the number of time slots needed to solve conflicts non-adaptively which is within a log(k/d) factor from the upper bound. To the aim of proving these results, we introduce a new combinatorial structure that consists in a generalization of Komlós and Greenberg codes. Constructions of these new codes are obtained via a new kind of selectors, whereas the non-existential result is implied by a non-existential result for a new generalization of the locally thin families. We believe that the combinatorial structures introduced in this paper and the related results may be of independent interest.

It has been introduced a new generalization of superimposed codes that finds application to the design of efficient algorithms for a variant of group testing known as group testing with inhibitors (GTI). Families associated to these codes have the property that for every q + Sigmai=1spipairwise different members F11,hellip,Fp11,hellip, F1s,hellip,Fpss,G1, hellip,Gqof the family it holds capi=1scupj=1piFjinsube cupi=1qGj. In this paper we present a lower bound on the minimum length of the generalized superimposed codes of A. De Bonis.

Two variants of the well-known group testing problem are considered. In the first variant a finite set of items O and an unknown subset PsubeO are given, and one wants to identify the set P by asking the least number of questions of the form "Is |QcapP|=1?", where QsubeO. This problem naturally arises in the design of efficient contention resolution algorithms for certain random multiple-access communication systems [Berger et al. "Random multiple-access communication and group testing," IEEE Trans. Commun., vol. 32, no. 7, pp. 769-779, 1984]. In the second variant of the problem, the answer to the question "Is |QcapP|=1?" is correctly YES if |QcapP|=1 and NO if |QcapP|=0", and it is left to a (possibly malicious) adversary otherwise. This model was introduced in [Damaschke, "Randomized group testing for mutually obscuring defectives", Inf. Process. Lett., vol. 67, pp. 131-135, 1998], in the context of chemical compound testing. In this correspondence several algorithms for these group testing problems are presented, trying to optimize different measures of performance: The overall number of tests performed by the algorithm, the number of stages in which tests can be arranged, and the decoding complexity of identifying the elements of P from tests outcomes. Some of the given algorithms are optimal with respect to more than one of the above criteria. Instrumental to the results presented in the correspondence are new and improved bounds on certain generalization of superimposed codes introduced in [Dyachkov and Rykov, "A generalization of superimposed codes and its application to the multiple-access channel", in Proc. 1984 IEEE Int. Symp. Inf. Theory, pp. 62-64], [De Bonis and Vaccaro, "Constructions of generalized superimposed codes with applications to group testing and conflict resolution in multiple access channels", Theoretic. Comput. Sci., vol. 306, no. 1-3, pp. 223-243, 2003] a result that it is believed to be of independent interest

Group testing refers to the situation in which one is given a set of objects ${\cal O}$, an unknown subset ${\cal P}\subseteq {\cal O}$, and the task of determining ${\cal P}$ by asking queries of the type "does ${\cal P}$ intersect $\cal Q$?," where $\cal Q$ is a subset of ${\cal O}$. Group testing is a basic search paradigm that occurs in a variety of situations such as quality control testing, searching in storage systems, multiple access communications, and data compression, among others. Group testing procedures have been recently applied in computational molecular biology, where they are used for screening libraries of clones with hybridization probes and sequencing by hybridization. Motivated by particular features of group testing algorithms used in biological screening, we study the efficiency of two-stage group testing procedures. Our main result is the first optimal two-stage algorithm that uses a number of tests of the same order as the information-theoretic lower bound on the problem. We also provide efficient algorithms for the case in which there is a Bernoulli probability distribution on the possible sets ${\cal P}$, and an optimal algorithm for the case in which the outcome of tests may be unreliable because of the presence of "inhibitory" items in ${\cal O}$. Our results depend on a combinatorial structure introduced in this paper. We believe that it will prove useful in other contexts, too.

Let s be the number of unknown positive elements in a population of n members, 2/spl les/s

A form of advertisement which is becoming very popular on the web is based on electronic coupon (e-coupon) distribution. E-coupons are the digital analogue of paper coupons which are used to provide customers with discounts or gift in order to incentive the purchase of some products. Nowadays, the potential of digital coupons has not been fully exploited on the web. This is mostly due to the lack of "efficient" techniques to handle the generation and distribution of e-coupons. In this paper we discuss models and protocols for e-coupons satisfying a number of security requirements. Our protocol is lightweight and preserves the privacy of the users, since it does not require any registration phase.