Recommender systems are a nice tool to help find items of interest from an overwhelming number of available items. Collaborative Filtering (CF), the best known technology for recommender systems, is based on the idea that a set of like-minded users can help each other nd useful information. A new user poses a challenge to CF recommenders, since the system has no knowledge about the preferences of the new user, and therefore cannot provide personalized recommendations. A new user preference elicitation strategy needs to ensure that the user does not a) abandon a lengthy signup process, and b) lose interest in returning to the site due to the low quality of initial recommendations. We extend the work of 23 in this paper by incrementally developing a set of information theoretic strategies for the new user problem. We propose an o ine simulation framework, and evaluate the strategies through extensive o ine simulations and an online experiment with real users of a live recommender system.