The Discrepancy Method

✍ Scribed by Bernard Chazelle

• Year: 2002
• Tongue: English
• Leaves: 491
• Category: Library

✦ Synopsis

The discrepancy method has produced the most fruitful line of attack on a pivotal computer science question: What is the computational power of random bits? It has also played a major role in recent developments in complexity theory. This book tells the story of the discrepancy method in a few succinct independent vignettes. The chapters explore such topics as communication complexity, pseudo-randomness, rapidly mixing Markov chains, points on a sphere, derandomization, convex hulls and Voronoi diagrams, linear programming, geometric sampling and VC-dimension theory, minimum spanning trees, circuit complexity, and multidimensional searching. The mathematical treatment is thorough and self-contained, with minimal prerequisites. More information can be found on the book's home page at http://www.cs.princeton.edu/~chazelle/book.html.

✦ Table of Contents

The Discrepancy Method......Page 1
Table of Contents......Page 3
Preface......Page 9
1 Combinatorial Discrepancy......Page 17
The Method of Conditional Expectations......Page 19
The Hyperbolic Cosine Algorithm......Page 21
The Unbiased Greedy Algorithm......Page 22
1.2 The Entropy Method......Page 23
1.4 Discrepancy and the VC Dimension......Page 26
Primal and Dual Shatter Functions......Page 27
Beating the Standard Deviation Bound......Page 30
The Hadamard Matrix Bound......Page 33
The Eigenvalue Bound......Page 35
Roth's 1/4-Theorem......Page 36
The View from Harmonic Analysis......Page 39
Hereditary Discrepancy and Determinants......Page 42
Application: Points and Halfplanes......Page 45
The Trace Bound......Page 48
Application II: Boxes and Higher Dimension......Page 51
1.6 Bibliographical Notes......Page 54
2 Upper Bound Techniques......Page 57
2.1 Numerical Integration and Koksma's Bound......Page 58
2.2 Halton-Hammersley Points......Page 59
2.3 Arithmetic Progressions in R/Z......Page 62
Weyl's Ergodicity Criterion......Page 63
Continued Fractions......Page 65
Irrational Lattices......Page 68
2.4 Jittered Sampling......Page 70
2.5 An Orbital Construction for Points on a Sphere......Page 73
Quaternions and SO(3)......Page 75
Spherical Harmonics and the Laplacian......Page 77
Spectrum of Self-Adjoint Operators......Page 80
Harmonic Analysis on a Tree......Page 82
Operator Discrepancy......Page 84
Spherical Cap Discrepancy......Page 86
Hecke Operators and the Ramanujan Bound......Page 93
The Modular Group......Page 97
Modular Forms......Page 104
Deligne's Spectral Bounds for Cusp Forms......Page 109
2.6 A Review of Arithmetic Algebraic Geometry......Page 110
L-Functions of Modular Forms......Page 111
Hecke Operators and Euler Products......Page 113
Elliptic Curves......Page 116
The Riemann Surface of the Curve X_0(N)......Page 119
The Addition Law of Elliptic Curves......Page 121
Zeta Functions of Number Fields......Page 123
Zeta Functions of Curves......Page 125
The Hasse-Weil L-Function......Page 129
The Shimura-Taniyama Conjecture......Page 130
2.7 The Laplacian and Optimum Principles......Page 133
2.8 The Spanning Path Theorem......Page 139
A Volume Argument......Page 141
The Iterative Reweighting Method......Page 143
2.9 Bibliographical Notes......Page 146
3 Lower Bound Techniques......Page 149
3.1 The Method of Orthogonal Functions......Page 150
Haar Wavelets......Page 151
Riesz Products......Page 155
Orthogonality and Independence......Page 157
3.2 The Fourier Transform Method......Page 160
Beck's Amplification Method......Page 161
Bessel Functions and the Fejer Kernel......Page 166
3.3 The Finite Differencing Method......Page 171
Buffon's Needle as a Discrepancy Tool......Page 172
A Probabilistic Interpretation......Page 176
The Alexander-Stolarsky Formula......Page 178
The Discrepancy of Halfspaces......Page 179
Approximate Diagonalization......Page 182
3.4 Bibliographical Notes......Page 183
4 Sampling......Page 185
4.1 Epsilon-Nets and Epsilon-Approximations......Page 186
The Greedy Cover Algorithm......Page 187
The Weighted Greedy Sampling Algorithm......Page 188
4.3 Sampling in Bounded VC-Dimension......Page 190
Building an Epsilon-Approximation......Page 191
Three Ways to Build an Epsilon-Net......Page 195
Product Range Spaces......Page 199
4.4 Weak Epsilon-Nets......Page 203
A Primer on Hyperbolic Geometry......Page 205
Hyperbolic Triangle Groups......Page 212
Nets for Uniform Circular Distributions......Page 213
4.5 Bibliographical Notes......Page 216
5 Geometric Searching......Page 219
5.1 Optimal Epsilon-Cuttings......Page 220
Point Location Among Hyperplanes......Page 227
Hopcroft's Problem......Page 229
5.3 Simplex Range Searching......Page 230
The Conjugation Tree......Page 232
The Spanning-Path Tree......Page 234
Simplicial Partitions......Page 235
Logarithmic Query Time......Page 240
Space-Time Tradeoffs......Page 241
5.4 Bibliographical Notes......Page 242
6 Complexity Lower Bounds......Page 244
6.1 Arithmetic Circuits......Page 249
Entropy-Increasing Computation......Page 251
The Spectral Lemma......Page 253
A Wavelet Argument for Box Matrices......Page 259
Triangle Matrices via Buffon's Needle......Page 265
Applications of the Trace Lemma......Page 266
6.2 Data Structures and Eigenvalues......Page 267
6.3 Monotone Circuits......Page 273
Box Matrices and Chinese Remaindering......Page 275
Line Matrices and the Euler Totient Function......Page 278
Simplex Matrices and Heilbronn's Problem......Page 279
6.4 Geometric Databases......Page 285
Simplex Queries: An Isoperimetric Inequality......Page 287
Box Queries: The Hyperbolic Boundary......Page 293
6.5 Bibliographical Notes......Page 297
7 Convex Hulls and Voronoi Diagrams......Page 299
7.1 Geode and Conflict Lists......Page 301
7.2 A Probabilistic Algorithm......Page 304
7.3 Derandomization......Page 310
Sharp Energy Estimation......Page 311
The Oracle......Page 317
Complexity Analysis......Page 321
7.4 Bibliographical Notes......Page 322
8 Linear Programming and Extensions......Page 323
The Four Axioms......Page 324
Linear Programming as an LP-Type Problem......Page 325
A Deterministic Solution......Page 327
8.2 Linear Programming in Linear Time......Page 328
8.3 Computing Loewner-John Ellipsoids......Page 329
8.4 Bibliographical Notes......Page 330
9 Pseudorandomness......Page 332
9.1 Finite Fields and Character Sums......Page 335
9.2 Pairwise Independence......Page 338
9.3 Universal Hash Functions......Page 340
9.4 Random Walk on an Expander......Page 345
Spectral Properties of Expanders......Page 348
Recycling Random Bits......Page 350
9.5 Low Bias from Quadratic Residues......Page 352
Low-Discrepancy Arithmetic Progressions......Page 354
Small Fourier Coefficients......Page 357
Interpolating a Sparse Polynomial......Page 358
9.7 Bibliographical Notes......Page 359
10 Communication Complexity......Page 362
10.1 Inner Product Modulo Two......Page 363
Distributional Communication Complexity......Page 364
The Matrix Rank Bound......Page 365
10.2 Searching in a Finite Universe......Page 367
10.3 The Master Argument......Page 369
A Hierarchy of Tree Contractions......Page 371
A Product Space Construction......Page 372
Candidate Queries......Page 376
Probability Amplification by Projection......Page 379
Point Separation......Page 382
Approximate Nearest Neighbors......Page 387
10.5 Bibliographical Notes......Page 390
11 Minimum Spanning Trees......Page 392
11.1 Linear Selection as Low-Discrepancy Sampling......Page 393
11.2 The Soft Heap: An Approximate Priority Queue......Page 395
11.3 Computing the MST......Page 397
A Preview......Page 401
The Effect of Corruption......Page 406
The Algorithm......Page 407
Correctness......Page 417
The Decay Lemma......Page 421
Complexity Analysis......Page 425
11.4 The Soft Heap, Cont'd......Page 428
Implementing the Four Operations......Page 431
The Error Rate......Page 440
The Running Time......Page 442
11.5 Bibliographical Notes......Page 444
A.1 Common Distributions......Page 446
A.2 Tail Estimates......Page 450
The Chernoff and Hoeffding Bounds......Page 0
A Unifying View of Tail Estimation......Page 454
A.3 Entropy......Page 455
A.4 Bibliographical Notes......Page 457
Functions in L^2(R^d)......Page 458
Abelian Groups......Page 459
B.2 Fourier Series......Page 462
C.1 Polytopes......Page 465
C.2 Voronoi Diagrams......Page 468
Bibliography......Page 470
Index......Page 485