Gabizon Deterministic Extraction from Weak Random Sources

1. Auflage 2010
ISBN: 978-3-642-14903-0
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 148 Seiten

Reihe: Monographs in Theoretical Computer Science. An EATCS Series

A deterministic extractor is a function that extracts almost perfect random bits from a weak random source. In this research monograph the author constructs deterministic extractors for several types of sources. A basic theme in this work is a methodology of recycling randomness which enables increasing the output length of deterministic extractors to near optimal length. The author's main work examines deterministic extractors for bit-fixing sources, deterministic extractors for affine sources and polynomial sources over large fields, and increasing the output length of zero-error dispersers. This work will be of interest to researchers and graduate students in combinatorics and theoretical computer science.

Autoren/Hrsg.

Gabizon, Ariel

Inhaltsverzeichnis

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