Skip to main content

Probability and Algorithms (1992) / Chapter Skim
Currently Skimming:

12 Missing Pieces, Derandomization, and Concluding Remarks
Pages 175-178

The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.


From page 175...
... As it happens, one also finds that considerable effort was subsequently invested to replace most of the original probabilistic scaffolding by constructions that could be called purely deterministic. To probabilists, this passion for excising randomized constructions seems curious, but many computer scientists and combinatorists feel themselves to be ~ Research supported in part by NSF grant DMS88-19868, AFOSR grant 89-0301, ARO grant DAAL03-89-G-0092, and NSA grant MDA-904-H-2034.
Read the entire page →
From page 176...
... The classical way to atone for the easy virtue of probabilistic constructions has been to supply deterministic replacements, and a famous iDustration of this tradition arises in the discussion of expander graphs in Chapter il. Though it is shockingly easy to show the existence of all sorts of expander graphs via probability, many researchers seemed to breathe a sigh of relief when deterministic constructions for good expanders were developed, even when the new constructions called on methods as sophisticated as those used by [ubotzky et al.
Read the entire page →
From page 177...
... Historically, the critical parts of such calculations tend to be more closely connected with real and complex analysis than with probability theory, but the language of probability always drives the problem formation and increasingly contributes to the analysis. Much of this tradition springs from seminal work of Donald Knuth, with many illustrations of the central themes found in his now classical books The Art of Computer Programming, vols.
Read the entire page →
From page 178...
... (1992) , Theoretical computer scientists develop transparent proof technique, SIAM News 25 (May)
Read the entire page →

Key Terms

  • transparent proof
  • proof techniques
  • mathematical society
  • randomized constructions
  • probabilistic constructions

  • poisson approximation
  • generating functions
  • deterministic constructions
  • computer scientists
  • percolation theory

  • randomized construction
  • expander graphs
  • american mathematical
  • honest sketch
  • subsequently invested

  • excising randomized
  • deterministic replacements
  • complex analysis
  • purely deterministic
  • charming introductory

  • recent progress
  • compelling validation
  • theoretical computer
  • algorithmic version
  • seminal work

  • offer enticing
  • constructions called
  • supply deterministic
  • nsa grant
  • recent advances


    • This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
    More information on Chapter Skim is available.