Handbook of Randomized Computing, Volume 2

Front Cover
Sanguthevar Rajasekaran
Springer Science & Business Media, 2001 - Computers - 941 pages
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

1
xi
Contributing Authors
xvii
12
457
References
505
References
529
Definitions and Basic Concepts
537
Lower Bound Techniques
549
Las Vegas Protocols
561
Derandomization in Combinatorial Optimization
731
Preliminaries
733
Sequential Derandomization
735
Parallel Derandomization and Kwise Independence
741
Hypergraph2Coloring and Discrepancies
749
References 128
751
Hypergraph2Coloring and LovazLocalLemma
757
Packing and Covering Integer Programs
763

Monte Carlo Protocols
573
A Bound on the Number of Random Bits
576
Some Applications
579
References
590
Property Testing
597
Testing Graph Properties in the Adjacency Matrix Model
604
Testing Graph Properties in the IncidenceLists Models
620
Testing other Properties
635
References
644
16
645
The Random Projection Method
651
Why?
652
When?
653
Conclusion
669
Randomized vs Deterministic
673
Error Estimation for Indirect MeasurementsFormulation of the Problem
674
References 15
677
Statistical Setting
684
Interval Setting
690
2
693
Necessity and Possibility of Parallelization
697
More Complicated Settings
698
4
707
Error Estimation Algorithms can be Applied to other Practical Problems
708
Proofs
713
References
724
18
725
Scheduling
774
The Delay Sequence Argument 133
782
Multicommodity Flows and Routing in VLSILayout
783
Independent Sets in Hypergraphs
791
6
796
Semidefinite Programming
801
5
805
eApproximations and Linear Programming
812
References
820
A Survey 101
831
Derandomizing Complexity Classes
843
Preliminaries
851
Dispersers and Extractors
866
Constructions of Dispersers and Extractors
873
A Survey of Techniques and Results 255
880
Hitting Set and Pseudorandom Generators
888
A Low End Generator
898
A High End Generator
910
The Compression Approach to Generator Construction
915
Other Hardness Based Deterministic Simulation Results
922
Unconditional Derandomization of SpaceBounded Computation
927
References
935
INDEX
xxv
Randomized Techniques for Modelling Faults and Achieving Robust Computing 313
xxvi
References 218
xli
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information