Text

theses

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.

ETD_6141

Ph.D.

Includes bibliographical references

by Justin Gilmer

doi:10.7282/T3ZG6TZC

ETD doctoral

The author owns the copyright to this work.