# More-efficient computation: Finding local solutions to overwhelmingly complex problems

##### Mar 31, 2011 by Larry Hardesty

At a time when the Internet puts an untold amount of information at anyone’s fingertips, and automated scientific experiments churn out data faster than researchers can keep up with it, and communications networks can include billions of people, even the simplest computational tasks can become so enormous that they would overwhelm even a powerful supercomputer. But sometimes it’s enough to know just a little bit about the solution to a monstrous calculation: biologists mining genomic data, for instance, might be interested in just a handful of genes.

At the Innovations in Computer Science conference at Tsinghua University earlier this year, MIT researchers, together with colleagues at Tel Aviv University, presented a new mathematical framework for finding such localized solutions to complex calculations. They applied their approach to some classic problems in computer science, which involve mathematical abstractions known as graphs.

The most familiar example of a graph is probably a diagram of a , where the nodes of the network — the communications devices — are depicted as circles, and the connections between them are depicted as lines. A graph is any such combination of circles and lines, or, as mathematicians say, of vertices and edges. A flow chart is another example of a graph; or a graph could depict citations of scientific papers, where every vertex is a paper, connected by edges to the papers that cite it.

Graphs can represent an endless diversity of data, but for any given graph, it’s often useful to compute what’s called a maximal independent set. An independent set is one where enough vertices have been deleted from the graph that there are no longer any edges: the remaining vertices are desert islands, none connected to any other. An independent set is maximal if trying to restore any of the deleted vertices will also restore an edge. That is, every vertex left out of the set is connected to one of the vertices in the set.

Community representatives

Each vertex in a maximal independent set thus stands in for a cluster of connected vertices. If the graph represents a mesh of citations, for instance, a cluster could be a set of papers on related topics.

A graph could have many different maximal independent sets, and for a large enough graph, computing even one of them could be a prohibitively time-consuming chore. Ning Xie, a graduate student in the Department of Electrical Engineering and Computer Science; his advisor, computer science professor Ronitt Rubinfeld; and Shai Vardi and Gil Tamir of Tel Aviv University devised a method to efficiently determine, for a particular region of a graph, which vertices are and are not included in at least one of the graph’s maximal independent sets. The key to the researchers’ system is that, without having to specify the entire set, they can guarantee that applying their algorithm to a second region of the — or a dozen or a hundred other regions — will yield results consistent with the first.

The researchers’ paper is theoretical: the researchers don’t apply their algorithm to any particular problems. But problems in research areas as diverse as bioinformatics, chemistry, artificial intelligence, scheduling and networking have been characterized as problems of calculating independent sets.

Seshadhri Comandur, a researcher at Sandia National Labs in Livermore, Calif., points out that — as the researchers acknowledge in their paper — others have previously proposed particular algorithms for calculating local solutions of complex problems. “There have been lots of related concepts that have been sort of floating around,” he says, but the MIT and Tel Aviv researchers “have formalized it in an interesting way and, I think, the correct way.” He adds that he’s intrigued to see whether other local-computation algorithms can also be subsumed under the researchers’ new framework. “There are a lot of other results that have a similar flavor,” he says.

This story is republished courtesy of MIT News (web.mit.edu/newsoffice/), a popular site that covers news about MIT research, innovation and teaching.

## Related Stories

#### Fundamental algorithm gets first improvement in 10 years

Sep 27, 2010

The maximum-flow problem, or max flow, is one of the most basic problems in computer science: First solved during preparations for the Berlin airlift, it’s a component of many logistical problems and a staple ...

#### Minimizing communication between cores

Feb 28, 2011

In the mid-1990s, Matteo Frigo, a graduate student in the research group of computer-science professor Charles Leiserson (whose work was profiled in the previous installment in this series), developed a parallel version of a fast Fou ...

#### New standard proposed for supercomputing

Nov 15, 2010

A new supercomputer rating system will be released by an international team led by Sandia National Laboratories at the Supercomputing Conference 2010 in New Orleans on Nov. 17.

#### New algorithm enables much faster dissemination of information through self-organizing networks

Jan 11, 2011

As sensors that do things like detect touch and motion in cell phones get smaller, cheaper and more reliable, computer manufacturers are beginning to take seriously the decade-old idea of "smart dust" -- networks ...

Mar 10, 2011

In recent years, many network scientists have turned their attention away from centralized networks — such as the Internet and the cell-phone network -- and toward ad hoc networks, wireless networks formed ...

#### Chart junk? How pictures may help make graphs better

Nov 04, 2009

Those oft-maligned, and highly embellished, graphs and charts in USA Today and other media outlets may actually help people understand data more effectively than traditional graphs, according to new research from North Carolina ...

## Recommended for you

#### UT Dallas professor to develop framework to protect computers' cores

4 hours ago

UT Dallas cybersecurity expert Dr. Zhiqiang Lin has received funding from the U.S. Air Force to develop a defense framework that burrows deep into a computer system to protect its core.

#### Researcher finds hidden efficiencies in computer architecture

8 hours ago

The computer is one of the most complex machines ever devised and most of us only ever interact with its simplest features. For each keystroke and web-click, thousands of instructions must be communicated ...

#### Scientists apply new graph programming method for evolving exascale applications

10 hours ago

(Phys.org) —Hiding the complexities that underpin exascale system operations from application developers is a critical challenge facing teams designing next-generation supercomputers. One way that computer ...

Apr 17, 2014

(Phys.org) —Google engineers working on software to automatically read home and business addresses off photographs taken by Street View vehicles, have created a product so good that not only can it be used ...

#### Preventing AI from developing anti-social and potentially harmful behaviour

Apr 17, 2014

Next time you play a computer at chess, think about the implications if you beat it. It could be a very sore loser!

#### Researcher seeks to lessen failures in computerized visual recognition programs

Apr 17, 2014

Computer programs that use facial or image recognition systems—be it security cameras or applications that search databases for everything from photographs of wanted criminals to images of bears – are like any other technological ...

##### Jotaf
5 / 5 (1) Mar 31, 2011
Graph theory FTW! It's always great to know about new developments. These guys are in the trenches battling the NP-Hard monster every day!

## More news stories

#### Five features an Amazon phone might offer

Rumors of an Amazon smartphone reached a fever pitch this week, with The Wall Street Journal reporting that the device could be due out this year.

#### All-in-One Media Keyboard offers navigation from the couch

(Phys.org) —Microsoft this week announced its All-in-One Media Keyboard. This is a peripheral that is targeted for users who want a comfortable, useful keyboard to use whether sitting on the living room ...

#### Android gains in US, basic phones almost extinct

The Google Android platform grabbed the majority of mobile phones in the US market in early 2014, as consumers all but abandoned non-smartphone handsets, a survey showed Friday.

#### LinkedIn membership hits 300 million

The career-focused social network LinkedIn announced Friday it has 300 million members, with more than half the total outside the United States.

#### Researchers uncover likely creator of Bitcoin

The primary author of the celebrated Bitcoin paper, and therefore probable creator of Bitcoin, is most likely Nick Szabo, a blogger and former George Washington University law professor, according to students ...

#### More than a quarter of emergency contraceptives in Peru falsified or substandard

A survey of emergency contraceptive pills in Peru found that 28 percent of the batches studied were either of substandard quality or falsified. Many pills released the active ingredient too slowly. Others ...

#### SpaceX launches supplies to space station

A fresh load of supplies is finally on its way to the International Space Station.

#### Researchers successfully clone adult human stem cells

(Phys.org) —An international team of researchers, led by Robert Lanza, of Advanced Cell Technology, has announced that they have performed the first successful cloning of adult human skin cells into stem ...

#### Astronomers discover first self-lensing binary star system

(Phys.org) —A pair of astronomers at the University of Washington has discovered the first known instance of a self-lensing binary-star system. In their paper published in the journal Science, Ethan Kruse ...

#### Researchers create methylation maps of Neanderthals and Denisovans, compare them to modern humans

(Phys.org) —A team of Israeli, Spanish and German researchers has for the first time created a map of gene expression in Neanderthals and Denisovans and has compared them with modern humans. In their paper ...