Deterministic Extraction from Weak Random Sources (eBook)

Preface 4
Contents 8
1 Introduction 11
1.1 Organization of This Book 11
1.2 The Classical Story 11
1.2.1 Seeded Extractors 13
1.2.2 Deterministic Extraction for Restricted Classes 13
1.3 Other Motivations 13
1.4 Techniques --- the Recycling Paradigm 15
1.4.1 A Simple Example 15
1.4.2 The General Principle and the Applicationfor Affine Sources 16
1.4.3 The Recycling Paradigm in Bit-Fixing Sources 18
1.4.4 The Recycling Paradigm for Zero-Error Dispersers 19
1.4.5 What Else Is There in This Book? 20
2 Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed 21
2.1 Introduction 22
2.1.1 Bit-Fixing Sources 22
2.1.2 Our Results 23
2.1.3 Overview of Techniques 23
2.1.4 Outline 28
2.2 Preliminaries 28
2.2.1 Averaging Samplers 28
2.2.2 Probability Distributions 29
2.3 Obtaining an Independent Seed 31
2.3.1 Seed Obtainers and Their Application 31
2.3.2 Constructing Seed Obtainers 32
2.4 Extracting a Few Bits for Any k 35
2.5 Sampling and Partitioning with a Short Seed 35
2.6 A Seeded Bit-Fixing Source Extractor with a Short Seed 37
2.7 Deterministic Extractors for Bit-Fixing Sources 38
2.7.1 An Extractor for Large k (Proof of Theorem 2.1) 38
2.7.2 An Extractor for Small k (Proof of Theorem 2.2) 40
2.8 Discussion and Open Problems 41
3 Deterministic Extractors for Affine Sources over Large Fields 43
3.1 Introduction 43
3.1.1 Affine Source Extractors 44
3.1.2 Our Results 44
3.1.3 Previous Work 45
3.2 Overview of Techniques 45
3.2.1 Extracting Many Bits from Lines 46
3.2.2 Linear Seeded Affine Source Extractors 47
3.2.3 Using the Correlated Randomness as a Seed 48
3.3 Preliminaries 49
3.3.1 Probability Distributions 49
3.3.2 Characters of Finite Fields 51
3.4 Extracting One Bit from Lines 54
3.5 Extracting Many Bits from Lines 55
3.6 A Linear Seeded Extractor for Affine Sources 59
3.7 Composing Extractors 61
3.8 Putting It All Together 63
4 Extractors and Rank Extractors for Polynomial Sources 64
4.1 Introduction 65
4.1.1 Rank Extractors 66
4.1.2 Extractors and Condensers for Polynomial Sources 67
4.1.3 Rank Versus Entropy --- Weak Polynomial Sources 70
4.1.4 Organization 71
4.2 General Preliminaries 71
4.2.1 Probability Distributions 71
4.2.2 Polynomials over Finite Fields 72
4.2.3 The Number of Solutions to a System of Polynomial Equations 74
4.3 Algebraic Independence and Rank 75
4.4 An Explicit Rank Extractor 77
4.4.1 Preliminaries for the Proof of Theorem 4.4 78
4.4.2 Proof of Theorem 4.4 79
4.5 Extractors for Polynomial Sources 82
4.5.1 Preliminaries for the Proof of Theorem 4.5 83
4.5.2 Proof of Theorem 4.5 86
4.6 Improving the Output Length 89
4.7 Extractors for Weak Polynomial Sources 91
4.7.1 Proof of Theorem 4.9 92
4.7.2 The Entropy of a Polynomial Mapping 95
4.8 Rank Extractors over the Complex Numbers 96
4.9 Discussion and Open Problems 97
5 Increasing the Output Length of Zero-Error Dispersers 99
5.1 Introduction 100
5.1.1 Randomness Extractors and Dispersers 100
5.1.2 Zero-Error Dispersers 101
5.1.3 Increasing the Output Length of Zero-Error Dispersers 102
5.1.4 Applications 104
5.1.5 Outline 110
5.2 Preliminaries 110
5.3 A Composition Theorem 113
5.3.1 Zero-Error Dispersers 113
5.3.2 Strongly Hitting Dispersers 114
5.4 Zero-Error Dispersers for Multiple Independent Sources 116
5.4.1 Formal Definition of Multiple Independent Sources 116
5.4.2 A Subsource Hitter for 2-Sources 116
5.4.3 Zero-Error Dispersers for 2-Sources 119
5.4.4 Zero-Error Dispersers for O(1)-Sources 121
5.4.5 Rainbows and Implicit O(1) Probe Search 122
5.5 Zero-Error Dispersers for Bit-Fixing Sources 124
5.6 Zero-Error Dispersers for Affine Sources 127
5.7 Open Problems 129
A Sampling and Partitioning 131
A.1 Sampling Using l-wise Independence 131
A.2 Sampling and Partitioning Using Fewer Bits 133
B Basic Notions from Algebraic Geometry 137
B.1 Affine and Projective Varieties 137
B.2 Varieties and Ideals 139
B.3 The Dimension and Degree of a Variety 140
B.4 The Projective Closure of an Affine Variety 143
B.5 The Dimension of Intersections of Hypersurfaces 144
B.6 The Degree of Intersections of Hypersurfaces 146
B.7 Bombieri's Theorem 148
Bibliography 150