Home → News → Academics Present New Breakthroughs For Fundamental... → Full Text

Academics Present New Breakthroughs For Fundamental Problems in Computer Science

By ­niversity of Bristol News

October 21, 2015

[article image]

University of Bristol researchers this week presented papers on two fundamental problems in computer science at the IEEE symposium on Foundations of Computer Science in California.

The first paper, from a team led by Raphael Clifford, relates to the question of whether there exist problems that are provably hard to solve. Clifford's team proved hardness results for versions of matrix vector multiplication problems and showed further hardness results for problems in which the data change dynamically.

In the second paper, a team led by He Sun presented the first algorithm for constructing linear-sized spectral sparsifiers that run in almost-linear time. Spectral sparsifiers are used to help speed up big data applications that deal with graphs featuring millions of vertices. The researchers accomplished this by approximating the input of a given graph, but with far fewer vertices, enabling algorithms to run faster. The researchers were able to prove they could construct a spectral sparsifier for any graph in almost linear time, and the output of every sparsifier would yield a constant number of vertices. The researchers say the result is almost optimal in respect to the time complexity of the algorithm and the number of edges in the spectral sparsifier.

From University of Bristol News
View Full Article


Abstracts Copyright © 2015 Information Inc., Bethesda, Maryland, USA


No entries found