PROBABILITY AND ALGORITHMS -- Copyright -- Preface -- Contents -- 1. Introduction -- 1.1 PROBABILISTIC ALGORITHMS -- 1.1.1 Everyday Examples -- 1.1.2 Hashing -- 1.1.3 Geometry -- 1.1.4 Competitive Analysis -- 1.1.5 Random Constructions -- 1.1.6 Testing Equality and Faith -- 1.2 PROBABILISTIC ANALYSIS OF ALGORITHMS -- 1.2.1 Sample Analyses: The Assignment Problem -- 1.2.2 Quick Lessons from Quicksort -- 1.3 HOW TO USE THIS SURVEY -- REFERENCES -- 2. Simulated Annealing -- ABSTRACT -- 2.1 THE METHOD -- 2.2 CONVERGENCE ANALYSIS -- 2.2.1 Basic Results -- 2.2.2 Taking the Instance Size into Account -- 2.3 BEHAVIOR IN PRACTICE -- REFERENCES -- 3. Approximate Counting Via Markov Chains -- ABSTRACT -- 3.1 EXACT AND APPROXIMATE COUNTING -- 3.2 RECURSIVE ESTIMATION OF SIZE -- 3.3 THE MARKOV CHAIN METHOD OF SIMULATING A PROBABILITY DISTRIBUTION -- 3.4 ESTIMATING MIXING TIMES -- 3.5 CONCLUSION -- REFERENCES -- 4. Probabilistic Algorithms for Speedup -- ABSTRACT -- 4.1 INTRODUCTION -- 4.2 PROBABILISTIC COMPLEXITY CLASSES -- 4.3 PROBABILISTIC ALGORITHMS IN NUMBER THEORY: FACTORING AND PRIMALITY TESTING -- Miller's Primality Test -- Solovay-Strassen Primality Test -- Dixon's Random Squares Factoring Algorithm -- 4.4 COMMUNICATION COMPLEXITY -- Randomized Prime Protocol -- Repeated Equality Protocol -- REFERENCES -- 5. Probabilistic Algorithms for Defeating Adversaries -- ABSTRACT -- 5.1 INTRODUCTION -- 5.2 EXAMPLES -- 5.2.1 Authentication -- 5.2.2 Computing with Encrypted Data -- 5.3 ZERO-KNOWLEDGE PROOF SYSTEMS AND INSTANCE-HIDING SCHEMES -- REFERENCES -- 6. Pseudorandom Numbers -- ABSTRACT -- 6.1 INTRODUCTION -- 6.2 EXPLICIT CONSTRUCTIONS OF PSEUDORANDOM BIT GENERATORS -- 6.3 COMPUTATIONAL INFORMATION THEORY AND CRYPTOGRAPHY -- 6.4 PERFORMANCE OF CERTAIN PSEUDORANDOM BIT GENERATORS -- REFERENCES.

7. Probabilistic Analysis of Packing and Related Partitioning Problems -- ABSTRACT -- 7.1 INTRODUCTION -- 7.1.1 Problems -- 7.1.2 Analysis -- 7.1.3 Bp Algorithms -- 7.1.4 Ms Algorithms -- 7.2 ANALYTICAL TECHNIQUES -- 7.2.1 Markov Chains -- 7.2.2 Bounds -- 7.2.3 Stochastic Planar Matching -- 7.2.4 Linear Programming -- 7.3 RELATED TOPICS -- 7.3.1 Variants -- 7.3.2 Higher Dimensions -- 7.3.3 General Bounds -- 7.3.4 Distributions -- 7.4 DIRECTIONS FOR FURTHER STUDY -- REFERENCES -- 8. Probability and Problems in Euclidean Combinatorial Optimization -- ABSTRACT -- 8.1 INTRODUCTION -- 8.2 SUBADDITIVE EUCLIDEAN FUNCTIONALS -- 8.3 TAIL PROBABILITIES -- 8.4 THE TSP IN FRACTAL SPACES -- 8.5 MINIMAL SPANNING TREES -- 8.6 MATCHING PROBLEMS -- 8.7 THE VALUES OF THE CONSTANTS -- 8.8 THE CENTRAL LIMIT PROBLEM -- 8.9 WORST-CASE GROWTH RATES -- 8.10 CONCLUDING REMARKS -- REFERENCES -- 9. Probabilistic Analysis in Linear Programming -- ABSTRACT -- 9.1 THE LINEAR PROGRAMMING PROBLEM -- 9.2 PROBABILISTIC ANALYSIS -- 9.2.1 Parametric Simplex Variants -- 9.2.2 Borgwardt's Results -- 9.2.3 Asymptotic Results: Smale and Others -- 9.2.4 Adler, Haimovich: Sign-Invariant Model for Phase II -- 9.2.5 The Quadratic Results -- 9.3 RANDOMIZED ALGORITHMS -- 9.4 THE ROAD AHEAD -- REFERENCES -- 10. Randomization in Parallel Algorithms -- ABSTRACT -- 10.1 INTRODUCTION -- 10.2 QUALITY MEASURES FOR RANDOMIZED PARALLEL ALGORITHMS -- 10.3 THE RANDOMIZED PARALLEL COMPLEXITY CLASS RNC -- 10.4 SOME IMPORTANT PROBLEMS IN RNC -- 10.4.1 Testing if a Multivariate Polynomial is not Identically Zero -- 10.4.2 Finding a Maximum Matching in a Graph -- 10.5 RANDOMIZATION LEADS TO SIMPLE PARALLEL ALGORITHMS -- 10.6 ELIMINATING RANDOMIZATION -- 10.7 CONCLUSION -- REFERENCES -- 11. Randomly Wired Multistage Networks -- ABSTRACT -- 11.1 INTRODUCTION -- 11.1.1 Dilated Butterflies -- 11.1.2 Delta Networks.

11.1.3 Multibutterflies -- 11.1.4 Expansion -- 11.1.5 History -- 11.1.6 Outline -- 11.2 PACKET SWITCHING -- 11.3 CIRCUIT SWITCHING -- 11.3.1 Unique Neighbors -- 11.3.2 The Algorithm -- 11.4 FAULT TOLERANCE -- 11.5 NONBLOCKING NETWORKS -- REFERENCES -- 12. Missing Pieces, Derandomization, and Concluding Remarks -- REFERENCES.