Abstract:

In this talk we review and survey some recent work and work in
progress on data mining and web search. We discuss Latent Semantic
Analysis and give conditions under which it is robust. We also
consider the problem of collaborative filtering and show how
spectral techniques can give a rigorous and robust justification
for doing so. We consider the problems of web search and show how
both Google and Klienberg's algorithm are robust under a model of
web generation, and how this model can be reasonably extended. We
then give an algorithm that provably gives the correct result in
this extended model. The results surveyed are joint work with
Azar, Karlin, McSherry and Saia (STOC 2001), and Achlioptas,
Karlin and McSherry (FOCS 2001).