SoftcoverISBN:  9781470461560 
Product Code:  SURV/265 
List Price:  $125.00 
MAA Member Price:  $112.50 
AMS Member Price:  $100.00 
eBookISBN:  9781470468736 
Product Code:  SURV/265.E 
List Price:  $125.00 
MAA Member Price:  $112.50 
AMS Member Price:  $100.00 
SoftcoverISBN:  9781470461560 
eBookISBN:  9781470468736 
Product Code:  SURV/265.B 
List Price:  $250.00$187.50 
MAA Member Price:  $225.00$168.75 
AMS Member Price:  $200.00$150.00 
Softcover ISBN:  9781470461560 
Product Code:  SURV/265 
List Price:  $125.00 
MAA Member Price:  $112.50 
AMS Member Price:  $100.00 
eBook ISBN:  9781470468736 
Product Code:  SURV/265.E 
List Price:  $125.00 
MAA Member Price:  $112.50 
AMS Member Price:  $100.00 
Softcover ISBN:  9781470461560 
eBookISBN:  9781470468736 
Product Code:  SURV/265.B 
List Price:  $250.00$187.50 
MAA Member Price:  $225.00$168.75 
AMS Member Price:  $200.00$150.00 

Book DetailsMathematical Surveys and MonographsVolume: 265; 2022; 251 ppMSC: Primary 68; 52; 05; 03; 11;
Understanding the behavior of basic sampling techniques and intrinsic geometric attributes of data is an invaluable skill that is in high demand for both graduate students and researchers in mathematics, machine learning, and theoretical computer science. The last ten years have seen significant progress in this area, with many open problems having been resolved during this time. These include optimal lower bounds for epsilonnets for many geometric set systems, the use of shallowcell complexity to unify proofs, simpler and more efficient algorithms, and the use of epsilonapproximations for construction of coresets, to name a few.
This book presents a thorough treatment of these probabilistic, combinatorial, and geometric methods, as well as their combinatorial and algorithmic applications. It also revisits classical results, but with new and more elegant proofs.
While mathematical maturity will certainly help in appreciating the ideas presented here, only a basic familiarity with discrete mathematics, probability, and combinatorics is required to understand the material.ReadershipGraduate students and researchers interested in combinatorics, computational geometry, statistics, and machine learning.

Table of Contents

Chapters

A probabilistic averaging technique

First constructions of epsilonnets

Refining random samples

Complexity of set systems

Packings of set systems

Epsilonnets: Combinatorial bounds

Epsilonnets: An algorithm

Epsilonnets: Weighted case

Epsilonnets: Convex sets

VCdimension of $k$fold unions: Basic case

VCdimension of $k$fold unions: General case

Epsilonapproximations: First bounds

Epsilonapproximations: Improved bounds

Epsilonapproximations: Relative case

Epsilonapproximations: Functional case

A summary of known bounds


Additional Material

RequestsReview Copy – for reviewers who would like to review an AMS bookPermission – for use of book, eBook, or Journal contentAccessibility – to request an alternate format of an AMS title
 Book Details
 Table of Contents
 Additional Material
 Requests
Understanding the behavior of basic sampling techniques and intrinsic geometric attributes of data is an invaluable skill that is in high demand for both graduate students and researchers in mathematics, machine learning, and theoretical computer science. The last ten years have seen significant progress in this area, with many open problems having been resolved during this time. These include optimal lower bounds for epsilonnets for many geometric set systems, the use of shallowcell complexity to unify proofs, simpler and more efficient algorithms, and the use of epsilonapproximations for construction of coresets, to name a few.
This book presents a thorough treatment of these probabilistic, combinatorial, and geometric methods, as well as their combinatorial and algorithmic applications. It also revisits classical results, but with new and more elegant proofs.
While mathematical maturity will certainly help in appreciating the ideas presented here, only a basic familiarity with discrete mathematics, probability, and combinatorics is required to understand the material.
Graduate students and researchers interested in combinatorics, computational geometry, statistics, and machine learning.

Chapters

A probabilistic averaging technique

First constructions of epsilonnets

Refining random samples

Complexity of set systems

Packings of set systems

Epsilonnets: Combinatorial bounds

Epsilonnets: An algorithm

Epsilonnets: Weighted case

Epsilonnets: Convex sets

VCdimension of $k$fold unions: Basic case

VCdimension of $k$fold unions: General case

Epsilonapproximations: First bounds

Epsilonapproximations: Improved bounds

Epsilonapproximations: Relative case

Epsilonapproximations: Functional case

A summary of known bounds