This paper proposes a theoretical analysis of recommendation systems in an online setting, where items are sequentially recommended to users over time. In each round, a user, randomly picked from a population of $m$ users, arrives. The decision-maker observes the user and selects an item from a catalogue of $n$ items. Importantly, an item cannot be recommended twice to the same user. The probabilities that a user likes each item are unknown, and the performance of the recommendation algorithm is captured through its regret, considering as a reference an Oracle algorithm aware of these probabilities. We investigate various structural assumptions on these probabilities: we derive for each of them regret lower bounds, and devise algorithms achieving these limits. Interestingly, our analysis reveals the relative weights of the different components of regret: the component due to the constraint of not presenting the same item twice to the same user, that due to learning the chances users like items, and finally that arising when learning the underlying structure.

In this paper, we prove a sharp limit on the community detection problem with colored edges. We assume two equal-sized communities and there are m different types of edges. If two vertices are in the same community, the distribution of edges follows pi= αilog n/n for 1 ≤ i ≤ m, otherwise the distribution of edges is qi= βilog n/n for 1 ≤ i ≤ m, where αiand αiare positive constants and n is the total number of vertices. Under these assumptions, a fundamental limit on community detection is characterized using the Hellinger distance between the two distributions. If Σi=1m(√αi- √βi)2> 2, then the community detection via maximum likelihood (ML) estimator is possible with high probability. If Σi=1m(√αi- √βi)2<; 2, the probability that the ML estimator fails to detect the communities does not go to zero.