What is Popular Amongst Your Friends?

Recommendation systems are commonly used in e-commerce to suggest relevant content to users. Popular examples include Amazon, iTunes Genius, Google News and typically they operate on a corpus of millions of users/items. Such recommendation systems often rely on "collaborative filters" - algorithms that use implicit or explicit user-item ratings to make recommendations. In this talk I will 

a) discuss the current state-of-the-art in collaborative filtering; 

b) show connections with the problem of channel coding arising in communications and exploit this viewpoint to derive performance limits for collaborative filters; 

c) introduce a simple scalable algorithm based on the principle of "popularity amongst friends (PAF)"; 

d) show that PAF yields competitive performance on real life datasets such Movielens and Netflix movie ratings; 

e) show that PAF is near-optimal in a certain regime.