Thursday, April 22 2021
11:30am-12:30pm Eastern Time (ET)
Bio: Stephen Eubank is deputy director in the Network Systems Science and Advanced Computing division and a tenured professor, Department of Public Health Sciences.
Title: Perturbative Approximations to Stochastic Satisfiability Problems
Abstract: Determining optimal interventions in a network-based epidemiology model can be cast as a stochastic satisfiability (SSAT) problem: What is the total probability that any of a large number of sets of random events occurs? The SSAT construct appears in many guises in many domains, e.g., as Moore-Shannon network reliability in network science or as partition functions in statistical mechanics and field theory. Solving this problem even approximately is notoriously hard, and the solutions themselves are specific to the problem instance, sensitive to small changes in its global structure, and unlikely to lead to feasible interventions in epidemiology. Nevertheless, it is interesting and important to be able to compare the optima found using various heuristics to the true optimum. Here I will describe work in progress applying perturbative methods from statistical physics in combination with tools from computer-aided design to yield approximations of controllable computational complexity with tight error bounds (but in an unusual sense) that respect important symmetries of the true solution.