Lars Otten Lars Otten

Graduate Student Alumnus (Ph.D.)

I was a graduate student in Prof. Rina Dechter's group, working towards a Ph.D. in Artificial Intelligence and Machine Learning in the School of Information and Computer Sciences at UC Irvine. I began my studies in the Fall of 2006 and have successfully defended my dissertation in March 2013.


Research  –  Personal  –  Publications  –  Software


My area of concentration is probabilistic inference and constraint reasoning, or more generally inference in graphical models. The unifying theme of my research lies in exploiting problem structure to solve various kinds of inference tasks. The input is often formulated as constraint satisfaction and optimization problems (CSPs / WCSPs) as well as queries over Bayesian and Markov networks (e.g., P(e), MPE, belief updating). These problems are typically NP-hard.

I have investigated methods like variable elimination and belief propagation for exact and approximate reasoning, but the focus of my thesis work is on search methods for optimization. The underlying general framework of AND/OR search spaces allows capturing independencies as well as redundancies among subproblems. Over time my work on these inference methods has also increasingly intersected with distributed computing and statistical learning.

In particular, the main contributions of my graduate work are as follows:

Applications are manifold, but one driving factor in our experimental evaluation are haplotyping and linkage problems over general pedigrees in human genetic analysis (under a joint NIH grant with computational biologists and statisticians). These queries can be modeled as Bayesian networks and are thus susceptible to our advanced inference methods. Other relevant problem domains include medical diagnosis, scheduling and planning, information theory, and image segmentation.

An entry based on my AND/OR Branch and Bound implementation recently placed first in all three MPE tracks of the PASCAL 2011 Probabilistic Inference Challenge. A previous version of my solver placed third in the UAI'10 Approximate Inference Challenge. Before that, I was involved in organizing the UAI'08 Probabilistic Inference Evaluation.

My implementation of sequential and distributed AND/OR Branch and Bound can be downloaded below (full source code under GPL); our research group also maintains a (slightly outdated) website where we make available some of the algorithms that were developed in the past:



Before coming to UCI I was a student at RWTH Aachen University in Aachen, Germany and Chalmers University of Technology in Gothenburg, Sweden, from which I obtained a M.Sc. degree in Dependable Computer Systems in 2006.

I maintain a (sparse) personal webpage at



Journal Articles

Peer-Reviewed Publications




Available for download below is my sequential AND/OR Branch and Bound (AOBB) implementation called daoopt that solves MPE or similar max-product queries over Bayesian or Markov networks. It implements both standard depth-first AOBB and Breadth-Rotating AOBB as introduced in our SoCS'11 paper (PDF) for improved anytime performance. Both variants use the Mini Bucket heuristic for pruning and to guide the search. The full source code also includes distributed AOBB as described in my dissertation.

The problem specification should be in UAI file format, gzipped input is supported. Run the program with the --help argument to see a list of options, and feel free to contact me with questions. In general I'd be happy to hear from you if you're using the solver.