{\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf110
{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
{\colortbl;\red255\green255\blue255;}
\margl1440\margr1440\vieww10800\viewh8400\viewkind0
\deftab720
\pard\pardeftab720\partightenfactor0

\f0\fs24 \cf0 \expnd0\expndtw0\kerning0
Computational Barriers to Representing Conditional Independence\
\
Daniel M. Roy\
\'a0\
Abstract\
\
A sub-community of machine learning---working in an area called probabilistic programming---are now using sampling programs as specifications for complex probability distributions over large collections of random variables, and writing very general algorithms for computing conditional distributions.\'a0 The efficiency of these algorithms generally relies upon an abundance of conditional independences. In this work, we look at the problem of representing conditional independencies that hold among these random variables.\'a0 In particular, we look at the setting of exchangeable sequences and arrays of random variables.\'a0 The study of the computability of representation theorems due to de Finetti, Aldous, and Hoover reveals that representing conditional independence can come at a steep computational cost, but also that a change of representation---to one allowing a small probability of error---allows us to represent conditional independences in these random structures.}