Final doctoral examination and defense of dissertation of Samantha Petti

Monday, March 9, 2020 - 2:30pm
Klaus 2100

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.