Please see PDF version
Statistical Science
1993. Vol. 8. No. 1, 76 77
Mi~ssing Pieces, Derandomization and Concluding Remarks
J. Michael Steele
Abstract. The most salient omissions from the survey provided by the preceding articles are reviewed and ameliorated by reference to recent publications.
Key words and phrases: *Chen Stein method, derandomization, expander graphs, percolation theory, pseudorandom graphs, random graphs.
No survey is ever complete, and completeness is some of the pristine virtue of deterministic construc
especially elusive for a survey of a rapidly evolving tions.
subject like the interface of probability and the theory The classic way to atone for the easy virtue of proba
of algorithms. In just the last few months there has bilistic constructions has been to supply deterministic
been stunning progress on transparent proof tech replacements, and a famous illustration of this tradi
niques, which, in a nutshell, are methods that (in some tion arises in the discussion of expander graphs in the
versions) allow one to test the validity of alleged proofs article by Maggs in this issue. Though it is shockingly
by applying tests that will fail with probability 112 easy to show the existence of all sorts of expander
unless the proof is valid. Some of the foundations that graphs via probability, many researchers seemed to
underlie this development are touched on by Feigen breathe a sigh of relief when deterministic construc
baum and Lagarias and by Feigenbaum in this issue. tions for good expanders were developed, even when
Even so, an honest sketch of the new ideas in transpar the new constructions called on methods as sophisti
ent proof techniques would require a substantial excur cated as those used by Lubotzky, Phillips and Samak
sion into the most modern bits of computational (1988).
complexity theory. Rather than take on that excursion, Although most of the discoveries provoked by the
we have to be content with referring the reader to the urge to replace a randomized construction with a deter
journalistic accounts of Kolata (1992) and Cipra (1992) ministic one have turned out to be rather specialized,
and the more technical discussion of Johnson (1992). there are recent developments that change this situa
The latter contains pointers to the appropriate scien tion and offer enticing suggestions of an important
tific literature. new theory of derandomization. Instead of pursuing
If one studies the engineering of these recent ad clever ad hoc constructions, the new idea is to look
vances in transparent proof techniques, one finds many for algorithmic procedures that replace the very steps
structures that were first supported by probabilistic employed in the randomized construction. This shift
thinking. As it happens, one also finds that consid in perspective turns out to be very fruitful, and a good
erable effort was subsequently invested to replace sense of its power can be found in Chapter 15 of the
most of the original probabilistic scaffolding by con important new book The Probabilistic Method by Alon,
~tructions that could be called pu~ely deterministic. Spencer and Erdds (1992). Further, because of the re
TO probabilists, this passion for excising randomized markable utility of the Lov63z Local Lemma in the
constructions seems curious, but many computer sci more subtle probabilistic constructions, the recent al
entists and combinatorists feel themselves to be on gorithmization of the Local Lemma by Beck (1992)
philosophicaUy shaky ground with randomized con and Alon (1992) offers a compelling validation of the
structions. Thus, in many contexts, such constructions derandomization concept.
are accorded only the status of a pure existence proof, In addition to its useful discussion Of derandOmiza
and, almost always, they are, seen as lacking at least tion, the volume of Alon, Spencer and Erdds (1992)
also provides charming introductory treatments of at
least two other topics that may seem underrepresented
J. Michael Steele is Professor, Department ofStatistics, in this survey, graph algorithms and random graphs.
The Wharton School of the University of Pennsylvania, The latter topic is also well covered in the treatise
3000 Steinberg Hall DietHch Ha14 Philadelphia, Penn Random Graphs by BollobAs (1985), which is a bible
sylvania 19104 6302. for any serious student of random graphs. From the
76
CONCLUDING REMARKS 77
probabilists' point of view, two of the most important plex investigators who examine randomness in a quest
recent links to these areas are to percolation theory and to find acceptable surrogates.
to the Chen Stein method of Poisson approximation.
Much of, the recent progress in percolation theory is ACKNOWLEDGMENTS
beautifully introduced by Grimmett (1989), and the
recent treatise on Poisson approximation of Barbour, Research supported in part by NSF Grants DMS
Holst and Janson (1992) surely belongs on the book 88 12868, DMS 92 11634, ARO Grants DAAL03 89.
shelf of anyone interested in probability, graphs or G 0092, DAAL03 91 G 0110 and NSA Grant MDA
discrete algorithms. 904 H 2034.
Another important sphere of probability in the ser
vice of algorithms that some may see as underrepre REFERENCES
sented here is the analytical probabilistic analysis of
algorithms. This area can be characterized by the use ALON, N. (1992). A parallel algorithmic version of the Local
of explicit combinatorial calculations and generating Lemma. Random Structures Algorithms 2 367 377.
functions to calculate the means and variances of algo ALON, N., SPENCER, J. and ERD6s, P. (1992). The Probabilistic
Method. Wiley, New York.
rithm running times and other features of interest. BARBouR, A. D., HOLST, L. and JANSON, S. (1992). Poisson Ap
Historically, the critical parts of such calculations tend proximation. Clarendon Press, Oxford.
to be more closely connected with real and complex BECK, J. (1992). An algorithmic approach to the LovAaz Local
analysis than with probability theory, but the language Lemma I. Random Structures Algorithms 2 343 366.
BENDER, E. A. and WILLIAMSON, S. G. (1991). Foundations of
of probability always drives the problem formation and Applied Combinatorics. Addison Wesley, Reading, MA.
increasingly contributes to the analysis. Much of this BOLLOBAs, B. (1985). Random Graphs. Academic, New York.
tradition springs from seminal work of Donald Knuth, BOLLOBAS, B., ed. (1991). Probabilistic Combinatorics and Its
with many illustrations of the central themes found in Applications. Amer. Math. Soc., Providence, RI.
his now classic books The Art of Computer Program CHUNG, F. R. K. (1991). Constructing random like graphs. In
Probabilistic Combinatorics and Its Applications (B. Bollo.
ming, vols. 1 3 (Knuth, 1973). A more recent and Us, ed.) 21 56. Amer. Math. Soc., Providence, RI.
introductory treatment that is sympathetic in ap CipaA, B. A. (1992). Theoretical computer scientists develop
proach is the text of Bender and Williamson (1991), transparent proof technique. SIAM News 25 1.
which also can be commended for the insights it offers FEWFNBAUM, J. (1993). Probabilistic algorithms for defeating
into asymptotic analyses assisted by generating func adversaries. Statist. Sc~ 8 26 30.
FEIGENBAUM, J. and LAGAILIAS, J. C. (1993). Probabilistic algo
tions. Another recent volume that anyone involved rithms for speedup. Statist. Sci. 8 20 25.
with the analytical tradition should read is Wilf (1990), GRIMMETT, G. (1989). Percolation. Springer, New York.
which christens "generatin~ctionology" as a field in JOHNSON, D. S. (1992). The NP completeness column: An ongoing
itself and also offers up many of the field's secrets in guide, 23rd ed.: The tale of the second prover. J. Algorithms
a way in which they can be enjoyably mastered. 13502 524.
KNUTH, D. E. (1973). The Art of Computer Programming 1 3.
A final volume that deserves mention here is the Addison Wesley, Reading, MA.
recent collection Probabilistic Combinatorics and Its KOLATA, G. (1992). New short cut found for long proofs. New
Applications, edited by BollobAs (1991). The seven York 7Ymes, April 6, Section C.
essays in this collection are C of great interest to the LUBoTmY, A., PHILLIPS, R. and SARNA1K, P. (1988). Ramanujan
field, and each points toward many lively research graphs. Combinatorica 8 261 277.
MAGos, B. M. (1993) Randomly wired multishape networks.
topics. In particular, the essay by F. R. K. Chung (1991) Statist. Sci 8 70 75.
provides quite another perspective on derandomization WILF, H. S. (1990). Generatingfunctionology. Academic, New
theory and illustrates many of the subtleties that per York.
i