Stadstical SL*nce

1993, Vol. 8. No. 1, 12

In This Issue

This issue of Statistical Science is devoted to a report sic, but its life has been transformed by a world of

on probability and algorithms prepared under the super new applications and powerful new tools, like Cheeger's

vision of a panel selected by the Committee on Applied inequality, which has been imported from the field of

and Theoretical Statistics of the National Research Coun differential geometry.

cil. In organizational structure, the Committee on Ap The next article, "Probabilistic Algorithms for Speed.

plied and Theoretical Statistics is part of the Board on up" by Feigenbaum and Lagarias begins with a basic

Mathematical Sciences, which in turn is part of the i~cletion to the probabilistic complexity classes

Commission on Physical Sciences, Mathematics and Ap that have become of great importance in theoretical

plications of the National Research Council. The National computer science. It follows through with practical

Research Council is the principal operating agency of the illustrations of probabilistic: speedups in prime testing

National Academy of Sciences. and integer factorization. In the final section, it devel.

The articles reprinted here view the interface of proba ops the connection between probabilistic speedup and

bility and algorithms from an uncommonly wide range communication complexity, a fascinating new topic

of perspectives. Some of the articles recall the evolving initiated by Andrew Yho that asks how many messages

confluence between the traditional concerns of the theory two people must exchange to compute fix, y) if one of

of algorithms and technology of, ppl ed probab t , but them knows x and the other knows y.

a i iii 3r

others reveal how theoretical computer scientists have Of all the. notions of theoretical computer science

spawned new varieties of computational complexity to that have been developed in the last dozen years, those

deal with the use of randomized methods, how probabil that speak to the preservation of privacy seem to exert

ity can guide the development of methods that preserve a particular fascination. In her article "Probabilistic

privacy or how issues of hardware design are now in Algorithms for Defeating Adversaries," Feigenbaum

formed by probabilistic insights. introduces us to the role of probability in addressing

The article "Simulated Annealine by Bertaimas and the private use of shared resources. Important connec

Tsitsikhs offers a natural start by giving a succinct tions subsequently are made to the notions of zero

reprise of a famous method that calls on the theory of knowledge proof systems and of authentication, a topic

Markov chains to provide a strategy for maximizing a that has numerous applications ~even down to our

function defined on a finite set. One of the great charms everyday experience with automated teller machines.

of simulated annealing is its extraordinary generality. In the last of the suite of articles focusing on proba

Almost any optimization problem can be approached by' bility and computational complexity is "Pseudorandom

simulated annealing, and often the coding is quite easy Numbers" by Lagarias. Statisticians and probabilists

Still, considerable analytical finesse is required for a deep familiar with the classic uses of pseudorandom num

understanding of the behavlor of simulated annealing, bers will find that theoretical computer scientists put

and, even after several years of intense investigation of a very different set of issues in play. One of the most

the method, there remain basic questions, not the least fascinating of these is the connection between compu

of which concern the validity of the statistical mechanics tational complexity and oneway functions.

metaphor that first set the ball rolling. Statisticians and probabilists may feel that they

The next article, "Approximate Counting via Markov have returned to more familiar ground on turning to

Chains," by Aldous recalls another basic means by which the essay "Probabilistic Analysis of Packing and Re

Markov chams have found powerful uses in combmato. lated Partitioning Problems" by Coffinan, Johnson,

rial calculations. The key observation is that there is an Lueker and Shor. Some of the issues the authors en

intimate relationship between having an explicit formula gage can be well understood on the factory floor, since,

for the cardinality of a finite set S and having a fast after all, that is where they originated. Still, the analy

algorithm for choosing an element of S at random ac ses evolving in the area they survey offer layers of

cording to the uniform distribution. This relationship has depth that will call for years of further exploration.

been exploited to provide new algorithms for determining In the article "Probability and Problems in Euclidean

the volume of a convex set iii R', for computing the Combinatorial Optimization," the focus is on problems

number of matchings in a graph and for many other like the traveling salesman problem, minimal spanning

problems. This line of investigation is part of a renais tree and minimal matching that have long been at the

sance that,is underway in the theory of Markov chains. center of algorithmic investigations, and evidence is

The fundamental question often comes down to knowing rapidly accumulating that they also offer vital chal.

how long a Markov chain must run before reaching lenges to probabilists.

approximate stationarity. This question may seem clas When one speaks of algorithms and paradigms that

i

2 IN THIS ISSUE

have had profound practical impact, there are no also offer advantages in the area of fault tolerance.

greater examples than the simplex algorithm and linear The final article, "Missing Pieces, Derandomization

programming. Shamir's article "Probabilistic Analysis and Concluding Remarks," makes up for the survey's

in Linear Programming" offers a rapidfire review of major omissions by providing connections to a number

the contributions that probability is making in this of recent articles and monographs that deal with sub

central area. jects that are closely related to the theme of this panel

The next two articles again invite statisticians and report.

probabilists to look beyond their traditional concerns.

One of the most explosive domains of technical devel

opment in the last five years has been in the field of ACKNOWLEDGMENTS

parallel computation. The paradigm is natural in some

applications, such as computer vision, but every year Support for this Panel of the Committee on Applied

more examples are produced that show the paradigm's and Theoretical Statistics was provided in part by

value in other areas. Ramachandran~s article "Random the Air Force Office of Scientific Research, the Army

ization in Parallel Algorithms" details how probability Research Office and the National Science Foundation.

relates to the emerging theory of parallel computa Additional support came from core funds of the Board

tional complexity. Ramachandran also discusses deran on Mathematical Sciences, National Research Council,

domization, the process by which one tries to replace which were provided by IBM and the following federal

randomized algorithms with purely deterministic ones. agencies: Air Force Office of Scientific Research, De

This is an energetic area of investigation where proba partment of Energy, National Science Foundation, Na

bilists may find opportunity to play the ironic role of tional Security Agency, and Office of Naval Research.

helping to do without randomness. The report Probability and Algorithms, from which

The nexttolast article, "Randomly Wired Multistage these articles are reprinted with the permission of the

Networks," by Maggs is the article that gets closest to National Academy Press, is available from National

the relationship of probability to hardware design. The Academy Press, 2101 Constitution Avenue, N.W.,

irony it offers to design engineers is the observation Washington, D.C., 20418 (tollfree telephone: 1800

that in multistage networks there are ways in which 6246242). The report is published here in its entirety,

randomly wired networks offer performance benefits with minor editorial changes.

over traditional designs. Moreover, random designs J. Michael Steele

1

1

1

i

i