Given a set of pairwise comparisons, the classical ranking problem computes a single ranking that best represents the preferences of all users. In this paper, we study the problem of inferring individual preferences, arising in the context of making personalized recommendations. In particular, we assume users form clusters; users of the same cluster provide similar pairwise comparisons for the items according to the Bradley-Terry model. We propose an efficient algorithm to estimate the preference for each user: first, compute the net-win vector for each user using the comparisons; second, cluster the users based on the net-win vectors; third, estimate a single preference for each cluster separately. We show that the net-win vectors are much less noisy than the high dimensional vectors of pairwise comparisons, therefore our algorithm can cluster the users reliably. Moreover, we show that, when a cluster is only approximately correct, the maximum likelihood estimation for the Bradley-Terry model is still close to the true preference.

In standard clustering problems, data points are represented by vectors, and by stacking them together, one forms a data matrix with row or column cluster structure. In this paper, we consider a class of binary matrices, arising in many applications, which exhibit both row and column cluster structure, and our goal is to exactly recover the underlying row and column clusters by observing only a small fraction of noisy entries. We first derive a lower bound on the minimum number of observations needed for exact cluster recovery. Then, we study three algorithms with different running time and compare the number of observations needed by them for successful cluster recovery. Our analytical results show smooth time-data trade offs: one can gradually reduce the computational complexity when increasingly more observations are available.

The performance gain by allowing half-duplex source cooperation is studied for Gaussian interference channels. The source cooperation is in-band, meaning that each source can listen to the other source's transmission, but there is no independent (or orthogonal) channel between the sources. The half-duplex constraint supposes that at each time instant the sources can either transmit or listen, but not do both. Our main result is a characterization of the sum capacity when the cooperation is bidirectional and the channel gains are symmetric. With unidirectional cooperation, we essentially have a cognitive radio channel. By requiring the primary to achieve a rate close to its link capacity, the best possible rate for the secondary is characterized within a constant. Novel inner and outer bounds are derived as part of these characterizations.

We study the two-user interference channel where the source nodes may transmit and receive in half-duplex while the destinations only receive as usual. Depending on the sources, the channel can be in one of three modes: A) both sources transmit, B) source 1 transmits while source 2 receives, and C) source 2 transmits and source 1 receives. This allows a limited form of cooperation between the sources. In this paper, we focus on the corresponding symmetric linear deterministic channel and derive its sum capacity. We consider a scheme which, by operating in modes B and C, transforms mode A into a virtual two-user interference channel with rate-limited bit pipes between the two source nodes and from each source node to the destination node it causes interference to. For the virtual channel so created, we propose a generalization of the superposition coding scheme of Han-Kobayashi to take advantage of the bit pipes. Finally, we derive matching upperbounds to show that the performance of the composite scheme is indeed optimal for the original channel.