Causality: an algorithmic framework and a computational complexity perspective

点击翻译按钮获取中文摘要

Establishing cause-effect relationships is a fundamental goal of empirical science, and finding the causes of diseases, economic crises, or other complex phenomena is of great importance for policy-making. Such causal inference typically requires combining observed and interventional data with existing knowledge. The structural approach to causal inference, developed over the past decades by Judea Pearl and others, allows researchers to model complex causal relationships, reason about their implications, and estimate causal effects of interest. In this approach, causal knowledge is encoded using directed or partially directed graphs, which is an intuitive representation that is readable by non-specialists.The graphical causal modeling approach currently receives substantial attention in Epidemiology, Sociology and other disciplines, but is not yet widely applied. An important barrier to its application is of algorithmic nature: Several key results of structural causality are either not general, i.e. do not apply for certain types of inputs, or are proved non-constructively, such that efficient algorithms to find solutions are lacking. In collaboration with scientists from application areas, we have identified several problems of real-world importance that require more general and/or more efficient solutions. The goal of this proposal is to study those problems from an algorithmic and computational complexity perspective.Our main focus will be on questions concerning identification and estimation of causal effects, with a secondary focus on learning possible causal structures from data. The graphical language used in structural causal modeling allows us to apply discrete- and graph-algorithmic techniques as well as advanced methods of computational complexity theory. While we expect to obtain some negative outcomes like NP-hardness results, the main goal is to provide effective algorithms, and with our collaborators we aim to feed our positive algorithmic results back into the application areas in the form of working software packages.