## Computer Science

Design an efficient search algorithm on a graph whose nodes are different bracketings of the same expression abcdef… and whose edges are due to the associative property `(ab)c=a(bc)`

. The shortest path problem is known to be NP-complete, so how do we find an epsilon-approximate algorithm?

Implement a testing utility to conveniently and tersely specify integration tests. It should be possible to aggregate different test sets together under a parent test set, possibly leveraging the filesystem to specify split test sets in different files. These tests should then be runnable, such that errors thrown during tests do not halt the test suite, and are reported to the user. A final score based on failures and successes of tests should be indicative of the performance of the system to test.

Extract a data-flow representation from a program based on its (unstructured) control-flow graph optionally using the data-centric RVSDG intermediate representation. The program can be assumed to have no side effects (purity), such that it only contributes to the production of final values. This work will however be used for further introspection of programs, and not for executing optimizing compiler passes.

## Statistics

Under what conditions can we tractably find MAP in non-selective Sum-Product Networks?

What bounds on expressivity of SPNs can we put for various leaf distributions?

How can we decompose inference problems in probabilistic programs?

## Category Theory

Determine if FinStoch has all colimits.

Understand how to construct a free Markov category.

Understand how a probability monad and a maybe monad can be used to define a category of partial stochastic maps.

Determine if Stoch has a closed monoidal structure (or something close to it).