Testing Convexity and Acyclicity
At present, colossal amounts of data are being generated across many industries, including in large-scale scientific experiments and by devices such as smartphones and wireless sensor networks. These datasets are so massive that running traditional algorithms is too prohibitively time-consuming. Property testing, a branch of algorithms research, addresses this issue by examining which questions about datasets can be answered by examining only a small fraction of the input.
In this talk, we present recent results in testing fundamental, well-known properties in two different domains. In high-dimensional convexity testing, we give essentially optimal algorithms in the model where algorithms only have access to random samples. In the realm of graph property testing, we prove a new lower bound for testing acyclicity in sparse directed graphs.
Timothy Sun is currently a visiting Assistant Professor at Emory University. He received his PhD at Columbia University in 2019 under the supervision of Xi Chen and Rocco Servedio. His current research interests include property testing and topological graph theory and algorithms.