Theses Doctoral

Testing Convexity and Acyclicity, and New Constructions for Dense Graph Embeddings

Sun, Timothy

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.


  • thumnail for Sun_columbia_0054D_15301.pdf Sun_columbia_0054D_15301.pdf application/pdf 821 KB Download File

More About This Work

Academic Units
Computer Science
Thesis Advisors
Chen, Xi
Servedio, Rocco Anthony
Ph.D., Columbia University
Published Here
June 5, 2019