Position:  PhD Candidate

Current Institution:  Stanford University

Abstract:  Fast Algorithms for Property Testing

My research area is graph theory and combinatorics and their application to theoretical computer science. The goal of property testing is to design an algorithm to efficiently test whether an object such as a function or a graph has a certain property such as containing triangles or linearity, respectively. Typically, the input size of the object such as a graph is enormous and even polynomial time complexity is impractical in real-life applications. We want to design a randomized algorithm which only queries a small number of bits of the input independent of the input size but can still make a correct decision with good precision. Although constant time queries have been found in some cases, a common drawback and open question in the field has been that the constant is typically enormous. We resolved this question for testing permutations, i.e., strings of length n of distinct integers 1 to n, with respect to several commonly used distances in permutations defined from the perspective of geometry, algebra, and analysis. Not only did we show that a property testing algorithm with constant query complexity exists but also that the constant is mild. We managed to overcome the common obstacle in testing general properties. There are many other open questions in property testing related to graphs, sequences, and permutations depending on different metrics we use. I am actively working on these areas. Improving the bounds in these topics is closely connected to other fields of mathematics such as number theory. Besides property testing, I also work in other fields of theoretical computer science related to smooth analysis and social network. I apply methods in combinatorics to explain why certain natural algorithms on graphs and social networks with certain properties have small time complexity.

Bio:
Fan Wei is a PhD candidate at the Department of Mathematics at Stanford University, supervised by Professor Jacob Fox. She received a bachelor’s degree in mathematics from MIT and a master’s (advanced study with distinction) from Cambridge University in the U.K.  Her research interests are graph theory combinatorics and their application to theoretical computer science. She has held internships in the Microsoft Research New England and Microsoft Research Redmond Theory groups, and she received the Cambridge Overseas Trust Scholarship from Cambridge University. She also won the AMS-MAA-SIAM Frank and Brennie Morgan Prize for Outstanding Research in Mathematics and the MIT John A. Bucsela Prize in Mathematics.