Please see PDF version
Stadstical SL*nce
1993, Vol. 8. No. 1, 1 2
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 one way 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 rapid fire 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 next to last 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 (toll free telephone: 1 800
that in multistage networks there are ways in which 624 6242). 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