View all news

Academics present new breakthroughs for fundamental problems in computer science

19 October 2015

Academics from the University of Bristol will present new breakthroughs on two fundamental problems in computer science. These results will be presented at the world's leading international conference in computer science this week

The 56th annual IEEE symposium on Foundations of Computer Science (FOCS 2015) will take place in California from 18-20 October.

One of the most challenging questions in computer science is whether there exist problems that are provably hard to solve.  This is most famously shown in an unsolved computer science question of whether P=NP, for which anyone who solves the problem would be awarded a prize of $1,000,000. 

In the first paper, New unconditional hardness results for dynamic and online problemsDr Raphaël Clifford, Reader in Algorithm Design in the University’sDepartment of Computer Science and colleagues from Aarhus University, have proved hardness results for versions of matrix vector multiplication, a fundamental tool in much of applied mathematics.  The researchers go on to show further hardness results for problems where the data are dynamically changing.

Further information

Edit this page