Testing Convexity and Acyclicity, and New Constructions for Dense Graph Embeddings
By: Timothy Sun
Publisher: [publisher not identified]
Published: 2019
Place of publication: [New York, N.Y.?]
Language: eng
Description: Property testing, especially that of geometric and graph properties, is an ongoing area of research. In this thesis, we present a result from each of the two areas. For the problem of convexity testing in high dimensions, we give nearly matching upper and lower bounds for the sample complexity of algorithms have one-sided and two-sided error, where algorithms only have access to labeled samples independently drawn from the standard multivariate Gaussian. In the realm of graph property testing, we give an improved lower bound for testing acyclicity in directed graphs of bounded degree. Central to the area of topological graph theory is the genus parameter, but the complexity of determining the genus of a graph is poorly understood when graphs become nearly complete. We summarize recent progress in understanding the space of minimum genus embeddings of such dense graphs. In particular, we classify all possible face distributions realizable by minimum genus embeddings of complete graphs, present new constructions for genus embeddings of the complete graphs, and find unified constructions for minimum triangulations of surfaces.
Notes: Department: Computer Science.

Thesis advisor: Xi Chen.

Thesis advisor: Rocco Anthony Servedio.

Thesis (Ph.D.)--Columbia University, 2019.