The Future of Theoretical Computer Science

Last week I attended a fascinating lecture by John Hopcroft, renowned theoretical computer scientist and all round genius. The title of the lecture was The Future of Theoretical Computer Science.

I'm not going to bore you all with the nine (9) pages of notes that I took, but he had a lot of incredibly interesting things to say.

His basic premise was that there is a fundamental revolution going on in the world of information, driven largely by advances in computer systems, and that those who recognise the changes early will benefit. But what do you do if you recognise the changes - how do you adapt (and therefore what should Universities be teaching their students in order to prepare them for the changes that will come).

He briefly discussed the problems that computer science has been dealing with for the past 30 years : programming languages, compilers, OSs, network protocols, algorithms, etc.

And also what he thinks will categorise the next 30 years : large network structures, large data sets, huge dimensional data sets, etc.; and then how to search and access these data sets.

Hopcroft then discussed how we need new theories to deal with these large, noisy, highly dimensional data sets with extreme outlying values.

He spoke briefly about the expressive way that a search engine of the future would need to operate, eg. Instead of searching for graph theory, we want to enter a query like construct an annotated bibliography on graph theory.

To collapse a few points that he made, he talked about both dimension reduction and dimension enlargement. In the context of searching, dimension enlargement could mean analysing your previous queries in order to qualify future queries. He gave an example of searching for shingles which for him would mean the new scientific theory, not roofing material (or worse!).

In the case of huge dimensions, that is an issue because we are now talking about data sets with billions of nodes and tens of thousands of dimensions - current (1950s) graph theory just doesn't work in that space. Instead we need techniques like spectral analysis, dimension reduction and collaborative analysis.

Then there is the issues surrounding human task augmentation - if we are going to deal with even the search results from such huge datasets, we are going to need intelligent methods to cluster documents such as by content (where we can use a simple vector summary of the document word count) or by genre (where we can't). Other solutions to this general problem include collaborative filtering eg. what Amazon use in order to detect changes in buying habits.

---

Phew! And Hopcroft discussed all these issues with examples, mathematical equations, etc. So, the computer science theories of the next 30 years need to be extended to cover the next 30 years.

In response to an audience question, he did concede that few people actually directly use many of the theories that they learn in University, but a theme throughout his lecture was that of adjusting our intuition. For instance, our intuition is naturally tuned to 2 and 3 dimensional problems - the next generation of computer scientists (and us, if we want to keep up) need to be able to intuitively see problems and solutions in massive dimensions and other non-intuitive spaces (although he doesn't believe that quantum computing will happen in his lifetime).

I might try and post some of his equations and examples later, but then again I may not be bothered!