Title: Algorithmic Recommender Systems
Abstract: Recommender systems help users identify objects they may find interesting, where objects may be books to read, films to watch, web pages to browse, and even other users to contact. Formally, the input to the system is the known preferences of the users, as deduced somehow from their past choices. While many interesting ideas have been developed to analyze characteristics of users (or objects) based on past choices, this approach suffers from a foundational theoretical flaw: feedback is ignored.

Put simply, the setting is such that choices determine recommendations, but recommendations are supposed to influence choices. In a recent line of work this gap was bridged by a simple algorithmic model that assumes that the system may ask the user's opinion on any object, and not only make recommendations about supposedly `nice' objects. Typically, algorithms in this model ask users for their opinions on controversial objects, and in return, the output consists of almost complete reconstruction of user preferences. In this talk we discuss this model and survey some basic and recent results.

Surprisingly, it turns out that there are algorithms that can reconstruct user preferences (with high probability), using only a little (polylog factor) more questions than the minimum possible.

Joint work with Aviv Nisgav.