Combinatorial Statistics and Brain Science

My research focuses on developing a new field named Combinatorial Statistics, along with its application in Brain Science. Combinatorial Statistics studies both sampling complexity (amount of data) and computational complexity (running time) for inferring from high dimensional distributions parameterized by discrete structures such as graphs, partitions, permutations or multicomplexes. Such distributions play an important role in a number of important scientific domains including computational neuroscience, genomics, social networks, coding theory and molecular and evolutionary biology. Success on this research will lead to a new mathematical theory of finding complex structures from data, which integrates ideas from computation, combinatorics, statistics and high dimensional probability in a unified paradigm. To achieve this goal, I devoted my early career in establishing a new combinatorial inference theory for graphical models. Graphical models parameterize high dimensional distributions by graphs, which encode complex conditional independence relationships among many random variables. Combinatorial inference aims to test or assess uncertainty of some global structural properties of the underlying graph based on data (e.g., Whether the graph is disconnected? What is the maximum degree of the graph? Whether the graph is triangle-free?). It holds a lot of promise for modern scientific data analysis since such global structural properties carry important scientific meanings (e.g., in studying brain networks, the maximum degree of a node reflects the activity level of the corresponding brain region). However, until recently, no systematic combinatorial inference theory exists in the literature. To bridge this gap, my research addresses two basic questions: (i) What are the fundamental limits of a combinatorial inference algorithm under a computational budge? (ii). Does an understanding of these limits direct us towards the construction of better combi