Math's New Breakneck Speed.

AuthorBurrows, Leah
PositionFRONTIER HORIZONS - Algorithms for optimization problems

WHAT IF a large class of algorithms used today--from those that help us avoid traffic to algorithms that identify new drug molecules--worked exponentially faster? Computer scientists at the Harvard School of Engineering and Applied Sciences (SEAS) have developed a completely new kind of algorithm, one that exponentially speeds up computation by dramatically reducing the number of parallel steps required to reach a solution.

A lot of so-called optimization problems--problems that find the best solution from all possible solutions, such as mapping the fastest route from point A to point B--rely on sequential algorithms that have not changed since they first were described in the 1970s. These solve a problem by following a sequential step-by-step process. The number of steps is proportional to the size of the data, but this has led to a computational bottleneck, resulting in lines of questions and areas of research that are just too computationally expensive to explore.

"These optimization problems have a diminishing returns property," says Yaron Singer, assistant professor of computer science at SEAS and senior author of the research. "As an algorithm progresses, its relative gain from each step becomes smaller and smaller."

Singer wondered what if, instead of taking hundreds or thousands of small steps to reach a solution, an algorithm could take just a few leaps? "This algorithm and general approach allows us to dramatically speed up computation for an enormously large class of problems across many different fields, including computer vision, information retrieval, network analysis, computational biology, auction design, and many others. We can now perform computations in just a few seconds that would have previously taken weeks or months."

Traditionally, algorithms for optimization problems narrow down the search space for the best solution one step at a time. In contrast, this new algorithm samples a variety of directions in parallel. Based on that sample, the algorithm discards low-value directions from its search space and chooses the most valuable directions to progress towards a solution.

Let's say you are in the mood to watch a movie similar to "The Avengers." A traditional recommendation algorithm would sequentially add a single cinematic selection in every step which has similar attributes to those of "The Avengers." In contrast, the new algorithm samples a group of films at random, discarding those that are too dissimilar to "The...

To continue reading

Request your trial

VLEX uses login cookies to provide you with a better browsing experience. If you click on 'Accept' or continue browsing this site we consider that you accept our cookie policy. ACCEPT