The Discrepancy Method: Randomness and Complexity

Contents Preface page xi 1 Combinatorial Discrepancy 1 1.1 Greedy Methods 3 The Method of Conditional Expectations 3 The Hyperbolic Cosine Algorithm 5 The Unbiased Greedy Algorithm 6 1.2 The Entropy Method 7 1.3 The Beck-Fiala Theorem 10 1.4 Discrepancy and the VC-Dimension 10 Primal and Dual Shatter Functions 11 Beating the Standard Deviation Bound 14 1.5 Lower Bounds 17 The Hadamard Matrix Bound 17 The Eigenvalue Bound 19 Roth’s 3⁄8-Theorem 20 4 The View from Harmonic Analysis 23 Hereditary Discrepancy and Determinants 26 Application: Points and Halfplanes 29 The Trace Bound 32 Application I: Points and Lines 35 Application II: Boxes in Higher Dimension 35 1.6 Bibliographical Notes 38 2 Upper Bound Techniques 41 2.1 Numerical Integration and Koksma’s Bound 42 2.2 Halton-Hammersley Points 43 2.3 Arithmetic Progressions in R/Z 46 Weyl’s Ergodicity Criterion 47 v Continued Fractions 49 Irrational Lattices 52 2.4 Jittered Sampling 54 2.5 An Orbital Construction for Points on a Sphere 57 Quaternions and SO (3) 59 Spherical Harmonics and the Laplacian 61 Spectrum of Self-Adjoint Operators 64 Harmonic Analysis on a Tree 66 Operator Discrepancy 68 Spherical Cap Discrepancy 70 Hecke Operators and the Ramanujan Bound 77 The Modular Group 81 Modular Forms 88 Deligne’s Spectral Bounds for Cusp Forms 93 2.6 A Review of Arithmetic Algebraic Geometry * 94 L-Functions of Modular Forms 95 Hecke Operators and Euler Products 97 Elliptic Curves 100 The Riemann Surface of the Curve Xg(N) 103 The Addition Law of Elliptic Curves 105 Zeta Functions of Number Fields 107 Zeta Functions of Curves 109 The Hasse-Weil L-Function 113 The Shimura-Taniyama Conjecture 114 2.7 The Laplacian and Optimum Principles * 117 2.8 The Spanning Path Theorem 123 A Volume Argument 125 The Iterative Reweighting Method 127 2.9 Bibliographical Notes 130 3 Lower Bound Techniques 133 3.1 The Method of Orthogonal Functions 134 Haar Wavelets 135 Riesz Products 139 Orthogonality and Independence * 141 3.2 The Fourier Transform Method 144 Beck’s Amplification Method 145 Bessel Functions and the Fejer Kernel 150 3.3 The Finite Differencing Method 155 Buffon’s Needle as a Discrepancy Tool 156 A Probabilistic Interpretation * 160 The Alexander-Stolarsky Formula 162 The Discrepancy of Halfspaces 163 Approximate Diagonalization * 166 3.4 Bibliographical Notes 167 4 Sampling 169 4.1 ε-Nets and ε-Approximations 170 4.2 General Set Systems 171 The Greedy Cover Algorithm 171 The Weighted Greedy Sampling Algorithm 172 4.3 Sampling in Bounded VC-Dimension 174 Building an ε-Approximation 175 Three Ways to Build an ε-Net 179 Product Range Spaces 183 4.4 Weak ε-Nets 187 A Primer on Hyperbolic Geometry * 189 Hyperbolic Triangle Groups 196 Nets for Uniform Circular Distributions 197 4.5 Bibliographical Notes 200 5 Geometric Searching 203 5.1 Optimal ε-Cuttings 204 5.2 Cuttings in Action 211 Point Location Among Hyperplanes 211 Hopcroft’s Problem 213 5.3 Simplex Range Searching 214 The Conjugation Tree 216 The Spanning-Path Tree 218 Simplicial Partitions 219 Logarithmic Query Time 224 Space-Time Tradeoffs 225 5.4 Bibliographical Notes 226 6 Complexity Lower Bounds 228 6.1 Arithmetic Circuits 233 Entropy-Increasing Computation 235 The Spectral Lemma 237 A Wavelet Argument for Box Matrices 243 Triangle Matrices via Buffon’s Needle 249 Applications of the Trace Lemma 250 6.2 Data Structures and Eigenvalues 251 6.3 Monotone Circuits 257 Box Matrices and Chinese Remaindering 259 Line Matrices and the Euler Totient Function 262 Simplex Matrices and Heilbronn’s Problem 263 6.4 Geometric Databases 269 Simplex Queries: An Isoperimetric Inequality 271 Box Queries: The Hyperbolic Boundary 277 6.5 Bibliographical Notes 281 7 Convex Hulls and Voronoi Diagrams 283 7.1 Geode and Conflict Lists 285 7.2 A Probabilistic Algorithm 288 7.3 Derandomization 294 Sharp Energy Estimation 295 The Oracle 301 Complexity Analysis 305 7.4 Bibliographical Notes 306 8 Linear Programming and Extensions 307 8.1 LP-Type Problems 308 The Four Axioms 308 Linear Programming as an LP-Type Problem 309 A Deterministic Solution 311 8.2 Linear Programming in Linear Time 312 8.3 Computing Lδwner-John Ellipsoids 313 8.4 Bibliographical Notes 314 9 Pseudorandomness 316 9.1 Finite Fields and Character Sums * 319 9.2 Pairwise Independence 322 9.3 Universal Hash Functions 324 9.4 Random Walk on an Expander 329 Spectral Properties of Expanders 332 Recycling Random Bits 334 9.5 Low Bias from Quadratic Residues 336 9.6 Polynomial Interpolation 338 Low-Discrepancy Arithmetic Progressions 338 Small Fourier Coefficients 341 Interpolating a Sparse Polynomial 342 9.7 Bibliographical Notes 343 10 Communication Complexity 346 10.1 Inner Product Modulo Two 347 Distributional Communication Complexity 348 The Matrix Rank Bound 349 10.2 Searching in a Finite Universe 351 10.3 The Master Argument 353 A Hierarchy of Tree Contractions 355 A Product Space Construction 356 Candidate Queries 360 Probability Amplification by Projection 363 10.4 Applications 366 Predecessor Searching 366 Point Separation 366 Approximate Nearest Neighbors 371 10.5 Bibliographical Notes 374 11 Minimum Spanning Trees 376 11.1 Linear Selection as Low-Discrepancy Sampling 377 11.2 The Soft Heap: An Approximate Priority Queue 379 11.3 Computing the MST 381 A Preview 385 The Effect of Corruption 390 The Algorithm 391 Correctness 401 The Decay Lemma 405 Complexity Analysis 409 11.4 The Soft Heap, Cont’d 412 Implementing the Four Operations 415 The Error Rate 424 The Running Time 426 11.5 Bibliographical Notes 428 A Probability Theory 430 A.l Common Distributions 430 A.2 Tail Estimates 434 The Chernoff and Hoeffding Bounds 436 A Unifying View of Tail Estimation 438 A.3 Entropy 439 A.4 Bibliographical Notes 441 B Harmonic Analysis 442 B.l Fourier Transforms 442 Functions in L2(Rd) 442 Abelian Groups 443 B. 2 Fourier Series 446 C Convex Geometry 449 C. l Polytopes 449 C.2 Voronoi Diagrams 452 Bibliography 454 Index 469