BRICS · Contents · Programme

**A BRICS Mini-Course**

**May 9, 10, 14 and 15, 2001**

**Lectures by
Devdatt Dubhashi, dubhashi@cs.chalmers.se
**

**
**

All That Jazz

Is this really a course about IT and all that jazz, and if so, what's it doing here amidst the serious Ph.D. stuff, you ask incredulously. Well, the answer is yes and no. The main aim of the course is to get you interested in algorithms and specifically, some elegant, powerful and versatile mathematical techniques that are useful in algorithm design and analysis. The two techniques we will focus on are

- Randomization, in particular Markov chains and sampling.
- Linear algebra, in particular, the singular value decomposition.

Web surfing, which is everyone's favourite pastime, will be used as a test bed for these techniques. The aim will be to convince you that in such real life scenarios, dramatic and substantial progress is made not by hacking but by bringing to bear "serious" theoretical computer science and mathematical techniques on the issues at hand.

Roughly, the first half of each lecture will be quite non-technical, and the second half fairly technical.

### Wednesday May 9, 2001, 14:15-16:00 in Auditorium D3

### The Importance of Being Ranked

Why do you prefer Google to other search engines? Because it ranks the results better! (So if you don't use it, you should! Disclaimer; I'm not employed by Google!) How does Google do it? By taking a random walk!

### Literature

- O. Haagstrom, Finite Markov Chains and Algorithmic Applications.
- Kleinberg, Jon M. Authoritative sources in a hyperlinked environment. J. ACM 46 (1999), no. 5, 604-632.
- Larry Page, Sergey Brin, R. Motwani, and T. Winograd, The PageRank Citation Ranking: Bringing Order to the Web. 1998.
- L. Introna and H. Nissenbaum, Defining the Web: The Politics of Search Engines. IEEE Computer. Jan. 2000, pp. 54-62.
- S. Lawrence and C. Lee Giles, Searching the World Wide Web. Science, Vol 280, pp. 98-100, 1998.
- L. Lovasz, Random Walks on Graphs: A Survey. Bolyai Mathematical Studies, Combinatorics, Paul Erdos is 80 (vol 2), pp. 1-46 Hungary 1993.

### Thursday May 10, 2001, 14:15-16:00 in Auditorium D4

### Latent Semantic Indexing

A British web page might talk of a "lift" while an American one is likely to talk of an "elevator", when referring to the same thing. How can we extract the hidden "latent semantic" information out of the text on a page?

### Literature

- Michael W. Berry and Susan T. Dumais, and Gavin W. O'Brien, Using Linear Algebra for Intelligent Information Retrieval. SIAM Review 37:4 (1995), pp. 573-595.
- C. Papadimitriou, P. Raghavan, H. Tamaki and S. Vempala, Latent Semantic Indexing: A probabilistic Analysis. J. Comput. Systems Sciences, 61. pp. 217-235, 2000.

### Monday May 14, 2001, 14:15-16:00 in Auditorium D4

### Clustering

The query "Java" is likely to return pages for programming language, the Indonesian island and the coffee of the same name. How can one automatically form clusters corresponding to these?

### Literature

- R. Kanna, S. Vempala and A. Vetta, On Clusterings: Good, Bad and Spectral. Proc. of the 41st Foundations of Computer Science (FOCS '00), Redondo Beach, 2000.
- Drineas, P.; Frieze, Alan; Kannan, Ravi; Vempala, Santosh; Vinay, V. Clustering in large graphs and matrices. Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 1999)

### Tuesday May 15, 2001, 14:15-16:00 in Auditorium D4

### Collaborative Filtering

When you go to Amazon.com to buy a book, they provide you a list of recommendations. Sometimes they really snare you! How do they do it?

### Literature

- Yossi Azar, Amos Fiat, Anna R. Karlin, Frank McSherry, and Jared Saia, Spectral Analysis of Data. 2000.
- L.H. Ungar and D.P. Foster, A Formal Statistical Approach to Collaborative Filtering. Conference on Automated Learning and Discovery (CONALD), 1998.