Leonard Schulman

senior fellow
EURIAS cohort 2017/2018
discipline Computer science & informatics
Professor of Computer Science, California Institute of Technology

Research project

Causality, Graphical Models and Explicit Constructions in Combinatorics and Coding Theory

Topic 1: Algorithms and Information Theory for Causal Inference

 

Can we draw rational conclusions from data in absence of well-controlled scientific experiments that differentiate causal from correlative relationships? This question is of profound significance for society. There are many reasons that we must often make do with passive observation, including: ethical considerations, especially with regard to human subjects; governance constraints; and uniqueness of the system and the inability to re-run history, as e.g., regarding climate. Conceptually, the question raises the exciting prospect of extending the scientific method, rigorously, beyond the traditional framework of controlled or natural experiments.

 

Our working framework is "structured causal models", developed in the 1990s. In this approach, interactions among system variables can be represented by a directed graph; remarkably, certain graphs allow for statistically sound causal inference from passive data. Despite abundant work, this approach has so far had limited effect on practice. I argue that this is largely due to fragility of the existing theory. First, few graphs, generally only very sparse ones, allow causal identifiability. Second, the requirement regarding absence of an edge is absolute: even a slight interaction effect requires it be retained in full.

 

Representative goals include: (I) Developing identifiability theorems which relax the model verification requirements in exchange for "error bars" on the identified causal effect. (II) Developing algorithms which, for suitable graphs, require as input only the probabilities of relatively likely events.

 

Topic 2: Coding Theory and High-Dimensional Combinatorics

 

One of the key tools for the interactive coding theorem are tree codes, which we know to exist, but do not know how to construct, despite many efforts. I have made a speculative construction but it depends upon a conjecture in analytic number theory that is currently out of reach. I plan to study variations which may circumvent this obstacle.

 

Relatedly, I am interested in "analog error-correcting codes": linear subspaces based on the Dvoretzky theorem on Euclidean Sections, a result in its essence similar to the Shannon coding theorem. I wish to develop explicit constructions of these objects (only randomized constructions are known), which would enable a power-limited analogue of the interactive coding theorem. This is closely related to problems in signal processing and control theory.

Biography

 

Leonard J. Schulman is Professor of Computer Science at the California Institute of Technology (Caltech) and Director of the Caltech Center for the Mathematics of Information. He holds a Ph.D. in Applied Mathematics from the Massachusetts Institute of Technology (MIT). His main research interests are in algorithms and communication protocols; combinatorics and probability; coding and information theory; and quantum computation.

Selected publications

'Analysis of a classical matrix preconditioning algorithm', with A. Sinclair. Journal of the ACM (JACM), vol. 64, no. 2, 2017.

 

'Extractors for Near Logarithmic Min-Entropy', with G. Cohen. Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS), 2016, pp. 178-187.

 

'Stability of Causal Inference', with P. Srivastava, UAI'16 Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence (UAI), 2016, pp. 666-675.

 

'Tree codes and a conjecture on exponential sums', with C. Moore, Proceedings of the fifth conference on Innovations in Theoretical Computer Science (ITCS), 2014.

 

'The effectiveness of Lloyd-type methods for the k-means problem', with R. Ostrovsky, Y. Rabani & C. Swamy. Journal of the ACM (JACM), vol. 59, no. 6, 2012.

institut

senior fellow
EURIAS promotion 2013/2014
Israel Institute for Advanced Studies (IIAS)
discipline Archaeology
2013
senior fellow
EURIAS promotion 2015/2016
Israel Institute for Advanced Studies (IIAS)
discipline History
2015
senior fellow
EURIAS promotion 2014/2015
Israel Institute for Advanced Studies (IIAS)
discipline Art History
2014
senior fellow
EURIAS promotion 2012/2013
Israel Institute for Advanced Studies (IIAS)
discipline Linguistics
2012