Probability and algorithms / Panel on Probability and Algorithms, Committee on Applied and Theoretical Statistics, Board on Mathematical Sciences, Commission on Physical Sciences, Mathematics, and Applications, National Research Council.

Format:

Book

Contributor:

National Research Council (U.S.). Panel on Probability and Algorithms.

Language:

English

Subjects (All):

Probabilities.

Algorithms.

Physical Description:

1 online resource (188 p.)

Edition:

1st ed.

Place of Publication:

Washington, D.C. : National Academy Press, 1992.

Language Note:

English

Summary:

Some of the hardest computational problems have been successfully attacked through the use of probabilistic algorithms, which have an element of randomness to them. Concepts from the field of probability are also increasingly useful in analyzing the performance of algorithms, broadening our understanding beyond that provided by the worst-case or average-case analyses. This book surveys both of these emerging areas on the interface of the mathematical sciences and computer science. It is designed to attract new researchers to this area and provide them with enough background to begin explorations of their own.

Contents:

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

3. Approximate Counting Via Markov Chains

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

4. Probabilistic Algorithms for Speedup

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

5. Probabilistic Algorithms for Defeating Adversaries

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

6. Pseudorandom Numbers

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

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

8. Probability and Problems in Euclidean Combinatorial Optimization

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

9. Probabilistic Analysis in Linear Programming

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

10. Randomization in Parallel Algorithms

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

11. Randomly Wired Multistage Networks

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

12. Missing Pieces, Derandomization, and Concluding Remarks

Notes:

Bibliographic Level Mode of Issuance: Monograph

Includes bibliographical references.

ISBN:

9786610196296

9781280196294

1280196297

9780309596176

0309596173

9780585155777

0585155771

OCLC:

44964286