Home
Resource
Discrete local central limit theorems and boolean function complexity measures
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(819.43 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Gilmer, Justin. Discrete local central limit theorems and boolean function complexity measures. Retrieved from https://doi.org/doi:10.7282/T3ZG6TZC

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitleDiscrete local central limit theorems and boolean function complexity measures
NameGilmer, Justin (author); Saks, Michael (chair); Kahn, Jeff (internal member); Kopparty, Swastik (internal member); Dvir, Zeev (outside member); Rutgers University; Graduate School - New Brunswick
Date Created2015
Other Date2015-01 (degree)
SubjectMathematics, Central limit theorem, Algebra, Boolean, Combinatorial analysis
Extent1 online resource (vii, 106 p. : ill.)
DescriptionThis 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.
NotePh.D.
NoteIncludes bibliographical references
Noteby Justin Gilmer
Genretheses, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/T3ZG6TZC
Languageeng
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024