Statistical Science

1993. Vol. 8. No. 1, 7677

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: *ChenStein 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 HallDietHch Ha14 Philadelphia, Penn Random Graphs by BollobAs (1985), which is a bible

sylvania 191046302. 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 ChenStein 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 8812868, DMS9211634, ARO Grants DAAL0389.

shelf of anyone interested in probability, graphs or G0092, DAAL0391G0110 and NSA Grant MDA

discrete algorithms. 904H2034.

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 367377.

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 343366.

BENDER, E. A. and WILLIAMSON, S. G. (1991). Foundations of

of probability always drives the problem formation and Applied Combinatorics. AddisonWesley, 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 randomlike graphs. In

Probabilistic Combinatorics and Its Applications (B. Bollo.

ming, vols. 13 (Knuth, 1973). A more recent and Us, ed.) 2156. 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 2630.

FEIGENBAUM, J. and LAGAILIAS, J. C. (1993). Probabilistic algo

tions. Another recent volume that anyone involved rithms for speedup. Statist. Sci. 8 2025.

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 NPcompleteness 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. 13502524.

KNUTH, D. E. (1973). The Art of Computer Programming 13.

A final volume that deserves mention here is the AddisonWesley, 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 261277.

MAGos, B. M. (1993) Randomly wired multishape networks.

topics. In particular, the essay by F. R. K. Chung (1991) Statist. Sci 8 7075.

provides quite another perspective on derandomization WILF, H. S. (1990). Generatingfunctionology. Academic, New

theory and illustrates many of the subtleties that per York.

i