The Art of Compromise

 

Scientists have confirmed what many suspected all along: We live in an imperfect world, filled with less-than-ideal choices. For example, in computing the solution to a problem with a large number of parts, we're forced to choose between efficient computation and an exact solution. If complete accuracy is essential, the computing process is likely to be slow and costly, whereas if we want a "fast and cheap" answer, there is no guarantee it will be exact. According to a recent study by Prof. Oded Goldreich of the Weizmann Institute's Computer Science and Applied Mathematics Department and his spouse, Prof. Dana Ron of the Electrical Engineering-Systems Department at Tel Aviv University, opting for efficiency over accuracy may very often yield results that are close enough to perfect to be useful in many applications.

Efficiency, in the case of computing, means a processing time that is relatively fast in comparison to the amount of data. If the time needed to carry out the computation grows at a steady rate relative to increasing input, it's considered to be fairly efficient. In comparison, processing that expands exponentially in relation to the data is inefficient and typically impractical.

For extremely large data sets, however, even computing at linear rates can be too slow to be feasible. For certain types of problems, Goldreich and Ron found a way to work with super efficiency - by developing a technique that reads just part of the data. What they had to sacrifice was absolute accuracy.

Their method was designed with networks in mind. Networks, such as the Internet, are large entities made up of sites, or nodes, and the links between them. Questions concerning networks may involve enormous amounts of data. They may ask, for instance, how connected is the network (i.e., can one get from any one point to any other point, and through how many different routes)? Or what is the average distance between two nodes? These issues affect research and planning in areas as diverse as computer networks, transportation and biological studies of gene and protein networks.

The standard algorithms (a computer's plans of action) one might use to answer these questions must analyze all of the data found in a network. So efficient are Goldreich and Ron's algorithms, they're dubbed sublinear (the processing needed is smaller than the input size); they randomly choose samples of network nodes and then scan only a portion of the immediate surroundings. Like election-time pollsters, who come close to predicting the actual election results on the basis of a representative sampling of voters, the scientists' method can produce approximate, but very close, answers on the basis of only a fraction of the data.

One of their algorithms, for example, can determine with near accuracy whether a given network is bipartite (separable into two parts). The nodes of a bipartite network can be partitioned such that all of its links are only to nodes in the opposite part. To process the data in a large network with a standard algorithm could range from time-consuming and expensive to futile. In contrast, the scientists' algorithm works by taking a random sample (sample size is determined by the size of the data list and can be as small as its square root) and then taking a small number of steps in random directions.

Thus in cases in which close is good enough, or better than nothing at all, Goldreich and Ron's algorithms may make a lot of sense. For a small loss in accuracy, the scientists gain a great deal of efficiency. And that, in an imperfect world, is close to ideal - a solution based on compromise.

 

Prof. Oded Goldreich is the incumbent of the Meyer W. Weisgal Professorial Chair of Experimental Physics.

How can we convince someone of something without giving away any information? Prof. Goldreich, whose work often deals with randomness and interaction, came up with the following story to illustrate the key to so-called zero-knowledge proofs:

On Olympus, the practical-minded Hera declared that all new nectar jugs, formerly of gold, be henceforth fashioned from silver. But perceptive Athena complained, claiming the nectar from the silver jugs did not taste as good as that from the gold ones. Zeus, already irritated with Hera's economizing, let loose his ire: "Let her be served 100 gourds of nectar, each poured at random from an old or a new jug, and let her tell them apart!" To Zeus' surprise, Athena correctly identified the source of each sip of nectar, convincing him there really was a difference.

Athena must have had a way of discerning one taste from the other. (Otherwise, even a goddess would have gotten the answer right only about half the time.) But her proof was based only on the randomness of the repeated servings, not on her means of identifying them, so Zeus learned nothing beyond the fact that she was right. Such zero-knowledge proofs are useful in designing secure computer systems.