<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=us-ascii"><meta name=Generator content="Microsoft Word 14 (filtered medium)"><!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
        {font-family:Calibri;
        panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
        {margin:0in;
        margin-bottom:.0001pt;
        font-size:12.0pt;
        font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
        {mso-style-priority:99;
        color:blue;
        text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
        {mso-style-priority:99;
        color:purple;
        text-decoration:underline;}
p
        {mso-style-priority:99;
        mso-margin-top-alt:auto;
        margin-right:0in;
        mso-margin-bottom-alt:auto;
        margin-left:0in;
        font-size:12.0pt;
        font-family:"Times New Roman","serif";}
span.EmailStyle18
        {mso-style-type:personal-compose;
        font-family:"Times New Roman","serif";}
.MsoChpDefault
        {mso-style-type:export-only;
        font-size:10.0pt;}
@page WordSection1
        {size:8.5in 11.0in;
        margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
        {page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link=blue vlink=purple><div class=WordSection1><table class=MsoNormalTable border=0 cellpadding=0 width=600 style='width:6.25in'><tr><td style='padding:.75pt .75pt .75pt .75pt'><div class=MsoNormal align=center style='text-align:center'><hr size=2 width="100%" align=center></div><p align=center style='text-align:center'>Boston University -- Computer Science Department<br><br><strong>C O L L O Q U I U M</strong><br><br>Wednesday&nbsp;March 9, 2011<br>11:00am - 12:15pm<br>MCS-135<o:p></o:p></p><div class=MsoNormal align=center style='text-align:center'><span style='font-size:10.0pt;font-family:"Arial","sans-serif";color:blue'><hr size=2 width="100%" align=center></span></div></td></tr><tr><td style='padding:.75pt .75pt .75pt .75pt'><p align=center style='text-align:center'><strong>Algorithmic Recommender Systems</strong><o:p></o:p></p><p align=center style='text-align:center'><strong>Boaz Patt-Shamir</strong><o:p></o:p></p><p align=center style='text-align:center'><strong><span style='color:black;font-weight:normal'><a href="http://www.eng.tau.ac.il/~boaz/"><b>http://www.eng.tau.ac.il/~boaz/</b></a> <o:p></o:p></span></strong></p><p align=center style='text-align:center'><b><o:p>&nbsp;</o:p></b></p><blockquote style='margin-top:5.0pt;margin-bottom:5.0pt'><p><strong>Abstract:</strong> 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.<o:p></o:p></p><p><strong>Short Bio: </strong><span lang=EN>Boaz Patt-Shamir has been a Professor of Computer Science in Tel Aviv University since 1997, where he directs the laboratory for distributed algorithms. He received his BSc in Mathematics and Computer Science from Tel Aviv University, his MSc from Weizmann Institute, and his PhD from MIT. His interests include distributed network algorithms and algorithms for communication networks. In 2002-2004 he has spent a sabbatical in HP Labs in Cambridge, Massachusetts, where he became interested in recommendation systems. </span><o:p></o:p></p><p><strong>Host:</strong> Azer Bestavros<o:p></o:p></p></blockquote></td></tr><tr><td style='padding:.75pt .75pt .75pt .75pt'><div class=MsoNormal align=center style='text-align:center'><span style='font-size:10.0pt;font-family:"Arial","sans-serif";color:blue'><hr size=2 width="100%" align=center></span></div></td></tr></table><p>&nbsp;<o:p></o:p></p></div></body></html>