Text

theses

ETD_8019

Ph.D.

Includes bibliographical references

This thesis studies three problems in combinatorics. Our first result is a quantitative local limit theorem for the distribution of the number of triangles in the Erdos-Renyi random graph G(n, p), for a fixed p ∈ (0, 1). This proof is an extension of the previous work of Gilmer and Kopparty, who proved that the local limit theorem held asymptotically for triangles. Our work gives bounds on the l1 and l∞ distance of the triangle distribution from a suitable discrete normal.
In our second result we prove a stability version of a general result that bounds the permanent of a matrix in terms of its operator norm. More specifically, suppose A is an n × n matrix, and let P denote the set of n × n matrices that can be written as a permutation matrix times a unitary diagonal matrix. Then it is known that the permanent of A satisfies |per(A)| ≤ kAk n 2 with equality iff A/kAk2 ∈ P (where kAk2 is the operator 2-norm of A). We show a stability version of this result asserting that unless A is very close (in a particular sense) to one of these extremal matrices, its permanent is exponentially smaller (as a function of n) than kAk n 2 . In particular, for any fixed α, β > 0, we show that |per(A)| is exponentially smaller than kAk n 2 unless all but at most αn rows contain entries of modulus at least kAk2(1 − β).
Finally, we construct large sequences with the property that the contents of any small window determine the location of the window, robustly. Such objects have found ii many applications in practical settings, from positioning of wireless devices to smart pens, and have recently gained some theoretical interest. In this context, we give the first explicit constructions of sequences with high rate and constant relative distance. Accompanying these efficient constructions, we also give efficient decoding algorithms, which can determine the position of the window given its contents, even if a constant fraction of the contents have been corrupted.

by Ross Berkowitz

doi:10.7282/T3KS6VHN

ETD doctoral

The author owns the copyright to this work.