P-complete and the limits of parallelization

We’re entering an era where CPU clock speeds will soon cease to scale upwards and instead CPU manufacturers are planning to put more and more independent cores on a chip.  Intel plans to release an 80-core chip within 5 years. Consequently the research community is setting their eye on the manifold barriers to writing correct…

3

Robin’s theorem

Most computer scientists are familiar with the P = NP problem, which asks essentially whether we can verify more problems in polynomial time than we can solve. So fundamentally does complexity theory hinge on this result that the Clay Mathematics Institute has labelled it one of their seven Millennium Prize Problems, and will award $1,000,000…

2

Cache-oblivious data structures

In most data structure and algorithms classes, the model used for basic analysis is the traditional RAM model: we assume that we have a large, random-access array of memory, and count the number of simple reads/writes needed to perform the algorithm. For example, selection sort takes about n(n-1)/2 reads and 2n writes to sort an…

10

K-nearest neighbor spatial search

I apologize to everyone for the hiatus – I realise a post is more than a little overdue and will try to be more regular in the future. I appreciate the support that I’ve received for the blog and continuing it. Consider the following problem: you’re starting a website for a chain of restaurants, and you…

7