Bayesian networks have become one of the major models used for statistical inference. We study the question whether the decisions computed by a Bayesian network can be represented within a low-dimensional inner product space. We focus on two-label classification tasks over the Boolean domain. As main results we establish upper and lower bounds on the dimension of the inner product space for Bayesian networks with an explicitly given (full or reduced) parameter collection. In particular, these bounds are tight up to a factor of 2. For some nontrivial cases of Bayesian networks we even determine the exact values of this dimension. We further consider logistic autoregressive Bayesian networks and show that every sufficiently expressive inner product space must have dimension at least Ω(n2), where n is the number of network nodes. We also derive the bound 2Ω(n) for an artificial variant of this network, thereby demonstrating the limits of our approach and raising an interesting open question. As a major technical contribution, this work reveals combinatorial and algebraic structures within Bayesian networks such that known methods for the derivation of lower bounds on the dimension of inner product spaces can be brought into play.

Heilbronn conjectured that among arbitrary n points in the two-dimensional unit square [0,1] 2 , there must be three points which form a triangle of area O(1/n 2 ). This conjecture was disproved by a nonconstructive argument of Komlós, Pintz, and Szemerédi [J. London Math. Soc., 25 (1982), pp. 13--24], who showed that for every n there exists a configuration of n points in the unit square [0,1] 2 where all triangles have area $\Omega({\log n}/{n^2})$. Here we will consider a three-dimensional analogue of this problem and show how to find deterministically in polynomial time n points in the unit cube [0,1] 3 such that the volume of every tetrahedron among these n points is $\Omega(\log n/n^3)$.