TY - JOUR
TI - Discrete local central limit theorems and boolean function complexity measures
DO - https://doi.org/doi:10.7282/T3ZG6TZC
PY - 2015
AB - This thesis consists of 6 chapters (the first being an introduction). Two chapters relate to local central limit theorems, and three chapters relate to various boolean function complexity measures. Although the problems studied in this work originate from different areas of mathematics, the methods used to attack these problems are unified in their probabilistic and combinatorial nature. In Chapter 2 we prove a local central limit theorem for the number of triangles in the Erdos-Renyi random graph G(n,p) for constant edge probability p. In Chapter 6 we apply an existing local limit theorem for sums of independent random variables to estimate the density of a certain set of integers called happy numbers. In Chapters 3, 4, and 5 we will investigate the general question of how large one complexity measure of boolean functions can be relative to another. In one case we present a probabilistic construction of family of boolean functions which show tight (in the sense that there is a matching upper bound) separation between two measures, namely block sensitivity and certificate complexity. We also give partial results for upper bounding one measure in terms of another. This includes a new approach to the well known sensitivity conjecture which asserts that the degree of any boolean function is bounded above by some fixed power of its sensitivity.
KW - Mathematics
KW - Central limit theorem
KW - Algebra, Boolean
KW - Combinatorial analysis
LA - eng
ER -