This program will focus on inference for distributions parameterized by discrete structures, such as trees, graphs, permutations or partitions. The main research objectives are to characterize the statistical complexity (the number of observations needed) and the algorithmic complexity (running time and memory requirements) for inference on these types of discrete objects, emphasizing theoretical research and analysis over applications and methodological development. For example, interactions on networks can be addressed by a combinatorial parameterization, using distributions on the graphs and hypergraphs of simplicial structure, yielding a standard example of a probability model with combinatorial parameterization. Placing a probability distribution over rankings and decomposition of rankings is also a probability model with combinatorial parameters, and can be used to extend classically deterministic optimization-based methods to stochastic models. Partition parameters arise in modeling gerrymandering in voting districts, where one is interested in distributions of demographic, political affiliation, and social affiliation variables conditional on the partition. Topological data analysis will be part of this program.
Program Working Groups