Author: Nathan Ryan

Title: Causal inference for the Millennium Villages Project

Speaker: Dr. Shira Mitchell, Columbia University, Columbia Population Research Center

Abstract:  The Millennium Villages Project (MVP) is a ten-year integrated rural development project implemented in ten sub-Saharan African sites. We describe the design for causal inference about the MVP’s effect on a variety of development indicators. Causal inference for the MVP context presents many challenges: a nonrandomized design, limited baseline data for candidate control areas, and the assignment of treatment to only ten sites, limiting effective sample sizes. We develop and carry out a matching procedure tailored to small samples and designed to facilitate communication with subject-matter experts. Following the design, we propose hierarchical Bayesian causal models for multiple outcomes. This work provides a case study of the careful evaluation design of a non-randomized intervention, with clear pre-specification of the procedure and matches before outcome data are available.

Title: Computing canonical forms of graphs

Abstract: Determining the computational complexity of the problem of finding canonical representatives of graphs is a long-standing unresolved question.  This question is of fundamental interest in the theory of computing because of its close relationship with graph-isomorphism testing.

While the problem may be difficult in general, group-theoretic methods have enabled polynomial-time solutions for important classes of graphs, including graphs of bounded valence.  In practice, however, variants of backtrack search to find lexicographic leaders have long been accepted as quite effective; for example, the system nauty is the leader in this category.

In this talk, I will discuss theoretical limitations of the lexicographic-leader approach to finding canonical forms.  It turns out that this approach leads to NP-complete problems, even for very restricted classes of graphs for which there are simple polynomial-time solutions by group-theoretic methods.

Title: Tying different knots: problems with isomorphism in algebra

Abstract: In 1905 Max Dehn proved if you tie a knot by “over-under” you never end up with the same knot as when you tie it “under-over”.  His proof — still the only proof — hinged on a very delicate and typically difficult problem of computing isomorphisms in algebra.  By the 1950’s Adian and Rabin had proved the approach in general is undecidable — no computer can do it.

Yet, the uses for isomorphism are too profound to give up after undecidability. The decades that followed saw the founders of computational algebra – Cannon, Neubuser, and Sims – make substantial inroads on the problem.  Theoretical Computer Scientists Miller, Lipton-Zalcstein, and Tarjan framed the problem in the emerging complexity zoo with the curious realization that group isomorphism is in one form easier than graph isomorphism and in another form harder.

Today isomorphism in algebra is experiencing a renaissance.  Long-standing “hard cases” are crumbling with the discovery of new linear perspectives.  Old practical algorithms are being combined with new data structures to result in exponential improvements.  And the approaches grow by the month.  The vanguard of this exciting new wave are researchers at  Aachen, Auckland, Bucknell, Chicago, Colorado State, London, Santa Fe, and Sydney.

We will report on what we know, what we want to know, and give the reasons for all the recent attention. The talk will not assume a technical proficiency in mathematics or computation.