Title: Randomness as a tool for modeling and uncovering structure
Advisor: Santosh Vempala, School of Computer Science, Georgia Institute of Technology
Committee:
Dr. Will Perkins, Department of Mathematics, University of Illinois at Chicago, Chicago
Dr. Prasad Tetali, School of Mathematics, Georgia Institute of Technology
Dr. Eric Vigoda, School of Computer Science, Georgia Institute of Technology
Dr. Lutz Warnke, School of Mathematics, Georgia Institute of Technology
Reader: Dr. Will Perkins, UIC.
Abstract: This thesis is united by two related themes: (i) using randomness to construct an object with a desired structure, and (ii) using randomness to uncover structure. We explore these themes in the following four contexts: (1) building a threshold function by randomly connecting small primitive Boolean circuits, (2) defining the Random Overlapping Communities model (ROC) to approximate the normalized closed walk counts of sparse graphs, including hypercubes, (3) studying a vertex subsampling process of a graph to deduce whether the graph exhibits community structure, and (4) exhibiting a Markov chain for sampling from the hard sphere model that achieves rapid mixing for an improved range of the fugacity parameter.
