Communications of the ACM
Academics Present New Breakthroughs For Fundamental Problems in Computer Science
Academics from the University of Bristol presented breakthroughs on two fundamental problems in computer science this week at the 56th annual IEEE symposium on Foundations of Computer Science.
Credit: University of Bristol News
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