Perturbative Approximations to Stochastic Satisfiability Problems
Speaker: Stephen Eubank, Department of Public Health Sciences, University of Virginia
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.
Bio: Stephen Eubank is deputy director in the Network Systems Science and Advanced Computing division and a tenured professor of the Department of Public Health Sciences. Eubank has previously researched fluid turbulence, nonlinear dynamics and chaos, time series analysis of markets (as a founder of Prediction Company), natural language processing (as a Visiting Scientist at ATR in Kyoto, Japan), and simulations of large interaction-based systems. As a staff member at Los Alamos National Laboratory, Eubank played a leading role in the development of the traffic microsimulation component of the Transportation Analysis and Simulation System (TRANSIMS), developed the Epidemiological Simulation System(EpiSims) project, and served as team leader for the Urban Infrastructure Suite (UIS), of which both TRANSIMS and EpiSims are parts. UIS is a collection of interoperable simulations of interacting infrastructures, each of which simulates the behavior of every individual in a large urban region. The goal of UIS is to model the dynamics of systems including both physical and social components. Eubank joined the Biocomplexity Institute of Virginia Tech in January 2005 and pursued interests both in developing advanced technology for the study of realistic socio-technical systems and also in understanding how the dynamics of diffusive processes on networks, such as disease transmission, are related to the structure of the underlying networks. Eubank also serves as the Principal Investigator for one of the research groups that form the National Institute of Health's MIDAS (Modeling Infectious Disease Agent Study) network.