The Discrepancy Method: Randomness and Complexity

by Bernard Chazelle

• ISBN13: 9780521770934
• ISBN10: 0521770939
• Format: Hardcover
• Copyright: 2000-07-24
• Publisher: Cambridge University Press

Summary

The discrepancy method is the glue that binds randomness and complexity. It is the bridge between randomized computation and discrepancy theory, the area of mathematics concerned with irregularities in distributions. The discrepancy method has played a major role in complexity theory; in particular, it has caused a mini-revolution of sorts in computational geometry. This book tells the story of the discrepancy method in a few short independent vignettes. It is a varied tale which includes such topics as communication complexity, pseudo-randomness, rapidly mixing Markov chains, points on the sphere and modular forms, derandomization, convex hulls, Voronoi diagrams, linear programming and extensions, geometric sampling, VC-dimension theory, minimum spanning trees, linear circuit complexity, and multidimensional searching. The mathematical treatment is thorough and self-contained. In particular, background material in discrepancy theory is supplied as needed. Thus the book should appeal to students and researchers in computer science, operations research, pure and applied mathematics, and engineering.

Table of Contents

Preface	xi
Combinatorial Discrepancy	1	(32)
Greedy Methods	3	(4)
The Method of Conditional Expectations	3	(2)
The Hyperbolic Cosine Algorithm	5	(1)
The Unbiased Greedy Algorithm	6	(1)
The Entropy Method	7	(2)
The Beck-Fiala Theorem	9	(1)
Discrepancy and the Vapnik-Chervonenkis Dimension	10	(6)
Primal and Dual Shatter Functions	11	(3)
Beating the Standard Deviation Bound	14	(2)
Lower Bounds	16	(15)
The Hadamard Matrix Bound	17	(1)
The Eigenvalue Bound	18	(1)
Roth's 1/4-Theorem	19	(3)
The View from Harmonic Analysis	22	(3)
Hereditary Discrepancy and Determinants	25	(3)
Square Matrices Revisited	28	(3)
Bibliographical Notes	31	(2)
Upper Bound Techniques	33	(92)
Numerical Integration and Koksma's Bound	34	(1)
Halton-Hammersley Points	35	(3)
Arithmetic Progressions in R/Z	38	(8)
Weyl's Ergodicity Criterion	39	(2)
Continued Fractions	41	(3)
Irrational Lattices	44	(2)
Jittered Sampling	46	(3)
An Orbital Construction for Points on a Sphere	49	(37)
Quaternions and SO(3)	51	(2)
Spherical Harmonics and the Laplacian	53	(3)
Spectrum of Self-Adjoint Operators	56	(2)
Harmonic Analysis on a Tree	58	(2)
Operator Discrepancy	60	(2)
Spherical Cap Discrepancy	62	(7)
Hecke Operators and the Ramanujan Bound	69	(4)
The Modular Group	73	(7)
Modular Forms	80	(5)
Deligne's Spectral Bounds for Cusp Forms	85	(1)
A Review of Arithmetic Algebraic Geometry*	86	(23)
L-Functions of Modular Forms	88	(2)
Hecke Operators and Euler Products	90	(2)
Elliptic Curves	92	(4)
The Riemann Surface of the Curve X0(N)	96	(2)
The Addition Law of Elliptic Curves	98	(2)
Zeta Functions of Number Fields	100	(2)
Zeta Functions of Curves	102	(3)
The Hasse-Weil L-Function	105	(1)
The Shimura-Taniyama Conjecture	106	(3)
The Laplacian and Optimum Principles*	109	(6)
The Spanning Path Theorem	115	(7)
A Volume Argument	117	(3)
The Iterative Reweighting Method	120	(2)
Bibliographical Notes	122	(3)
Lower Bound Techniques	125	(36)
The Method of Orthogonal Functions	126	(10)
Haar Wavelets	127	(4)
Riesz Products	131	(2)
Orthogonality and Independence*	133	(3)
The Fourier Transform Method	136	(11)
Beck's Amplification Method	137	(5)
Bessel Functions and the Fejer Kernel	142	(5)
The Finite Differencing Method	147	(12)
Buffon's Needle as a Discrepancy Tool	148	(4)
A Probabilistic Interpretation*	152	(2)
The Alexander-Stolarsky Formula	154	(1)
The Discrepancy of Halfspaces	155	(3)
Approximate Diagonalization*	158	(1)
Bibliographical Notes	159	(2)
Sampling	161	(34)
&epsis;-Nets and &epsis;-Approximations	162	(1)
General Set Systems	163	(3)
The Greedy Cover Algorithm	163	(1)
The Weighted Greedy Sampling Algorithm	164	(2)
Sampling in Bounded VC-Dimension	166	(13)
Building an &epsis;-Approximation	167	(4)
Three Ways to Build an &epsis;-Net	171	(4)
Product Range Spaces	175	(4)
Weak &epsis;-Nets	179	(13)
A Primer on Hyperbolic Geometry*	181	(7)
Hyperbolic Triangle Groups	188	(1)
Nets for Uniform Circular Distributions	189	(3)
Bibliographical Notes	192	(3)
Geometric Searching	195	(25)
Optimal &epsis;-Cuttings	196	(7)
Cuttings in Action	203	(3)
Point Location Among Hyperplanes	203	(2)
Hopcroft's Problem	205	(1)
Simplex Range Searching	206	(12)
The Conjugation Tree	208	(2)
The Spanning-Path Tree	210	(1)
Simplicial Partitions	211	(5)
Logarithmic Query Time	216	(1)
Space-Time Tradeoffs	217	(1)
Bibliographical Notes	218	(2)
Complexity Lower Bounds	220	(53)
Arithmetic Circuits	224	(17)
Entropy-Increasing Computation	226	(3)
The Spectral Lemma	229	(5)
A Wavelet Argument for Box Matrices	234	(6)
Triangle Matrices via Buffon's Needle	240	(1)
Data Structures and Eigenvalues	241	(6)
Monotone Circuits	247	(12)
Box Matrices and Chinese Remaindering	249	(3)
Line Matrices and the Euler Totient Function	252	(1)
Simplex Matrices and Heilbronn's Problem	253	(6)
Geometric Databases	259	(12)
Simplex Queries: An Isoperimetric Inequality	261	(6)
Box Queries: The Hyperbolic Boundary	267	(4)
Bibliographical Notes	271	(2)
Convex Hulls and Voronoi Diagrams	273	(24)
Geode and Conflict Lists	275	(3)
A Probabilistic Algorithm	278	(6)
Derandomization	284	(12)
Sharp Energy Estimation	285	(6)
The Oracle	291	(4)
Complexity Analysis	295	(1)
Bibliographical Notes	296	(1)
Linear Programming and Extensions	297	(9)
LP-Type Problems	298	(4)
The Four Axioms	298	(1)
Linear Programming as an LP-Type Problem	299	(2)
A Deterministic Solution	301	(1)
Linear Programming in Linear Time	302	(1)
Computing Lowner-John Ellipsoids	303	(1)
Bibliographical Notes	304	(2)
Pseudorandomness	306	(30)
Finite Fields and Character Sums*	309	(3)
Pairwise Independence	312	(2)
Universal Hash Functions	314	(5)
Random Walk on an Expander	319	(7)
Spectral Properties of Expanders	322	(2)
Recycling Random Bits	324	(2)
Low Bias from Quadratic Residues	326	(2)
Polynomial Interpolation	328	(5)
Low-Discrepancy Arithmetic Progressions	328	(3)
Small Fourier Coefficients	331	(1)
Interpolating a Sparse Polynomial	332	(1)
Bibliographical Notes	333	(3)
Communication Complexity	336	(30)
Inner Product Modulo Two	337	(4)
Distributional Communication Complexity	338	(1)
The Matrix Rank Bound	339	(2)
Searching in a Finite Universe	341	(2)
The Master Argument	343	(13)
A Hierarchy of Tree Contractions	345	(1)
A Product Space Construction	346	(4)
Candidate Queries	350	(3)
Probability Amplification by Projection	353	(3)
Applications	356	(8)
Predecessor Searching	356	(1)
Point Separation	356	(5)
Approximate Nearest Neighbors	361	(3)
Bibliographical Notes	364	(2)
Minimum Spanning Trees	366	(53)
Linear Selection as Low-Discrepancy Sampling	367	(2)
The Soft Heap: An Approximate Priority Queue	369	(2)
Computing the MST	371	(30)
A Preview	375	(4)
The Effect of Corruption	379	(2)
The Algorithm	381	(9)
Correctness	390	(5)
The Decay Lemma	395	(3)
Complexity Analysis	398	(3)
The Soft Heap, Cont'd	401	(16)
Implementing the Four Operations	404	(9)
The Error Rate	413	(2)
The Running Time	415	(2)
Bibliographical Notes	417	(2)
A Probability Theory	419	(12)
A.1 Common Distributions	419	(4)
A.2 Tail Estimates	423	(5)
The Chernoff and Hoeffding Bounds	425	(2)
A Unifying View of Tail Estimation	427	(1)
A.3 Entropy	428	(2)
A.4 Bibliographical Notes	430	(1)
B Harmonic Analysis	431	(12)
B.1 Fourier Transforms	431	(4)
Functions in L2(Rd)	431	(1)
Abelian Groups	432	(3)
B.2 Fourier Series	435	(3)
C Convex Geometry	438	(1)
C.1 Polytopes	438	(3)
C.2 Voronoi Diagrams	441	(2)
Bibliography	443	(15)
Index	458