Lipton, GLL, A Negative Impossibility Theorem, here.
Ravi Kannan is a long-time friend, a brilliant theorist, and a wonderful speaker. He has won numerous awards, including the Fulkerson Prize and the Knuth Prize, for his ground-breaking research.
Today I wish to talk about a recent presentation that Ravi gave at Tech on clustering, which contained a negative impossibility theorem.
The theorem is from his book with John Hopcroft on algorithms for this century. This is a novel work that focuses on data not algorithms, is a labor of over five years, and may become the algorithm book. I have only had a short chance to look at the book, which is available on-line, but it looks exciting.
John Hopcroft and Ravi Kannan, Computer Science Theory for the Information Age, here.
Computer science as an academic discipline began in the 60’s. Emphasis was on programming languages, compilers, operating systems and the mathematical theory that supported these areas. Courses in theoretical computer science covered finite automata, regular expressions, context free languages, and computability. In the 70’s, algorithms was added as an important component of theory. The emphasis was on making computers useful. Today, a fundamental change is taking place and the focus is more on applications. The reasons for this change are many. Some of the more important are the merging of computing and communications, the availability of data in digital form, and the emer- gence of social and sensor networks.
Although programming languages and compilers are still important and highly skilled individuals are needed in these area, the vast majority of researchers will be involved with applications and what computers can be used for, not how to make computers useful. With this in mind we have written this book to cover the theory likely to be useful in the next 40 years just as automata theory and related topics gave students an advantage in the last 40 years. One of the major changes is the switch from discrete mathematics to more of an emphasis on probability and statistics. Some topics that have become impor- tant are high dimensional data, large random graphs, singular value decomposition along with other topics covered in this book.