My student Abhinav Aggarwal has just written the inaugural post on his new blog (the name of which, I hope, is not a comment on the soporific qualities of my advisement 🙂 His first post is on the Clever algorithm by Jon Kleinberg. This is inarguably, the paper that started the modern, spectral-based approach to web search that Google has built on so successfully.
Some questions worth pondering while reading through Abhinav’s summary (and hopefully also the seminal paper itself): 1) Why did PageRank “beat out” the Clever algorithm in real-world web search? 2) Are there domains besides web search where one might use a “top left and right eigenvector” approach like the Clever algorithm? 3) What about the “soft” results in the paper like the use of the second eigenvector for clustering? Can these be formalized in an interesting way?
Filed under: Uncategorized | Tags: Byzantine agreement, spectral, theory
Accepted papers for SODA 2014 are now published. Valerie King and I have a paper there on Faster Agreement via a Spectral Method for Detecting Malicious Behavior. This is one of the first papers that I know of that uses a spectral approach to solve a problem in reliable distributed computing. Slides from an early talk on the research in this paper are available on my web page.