**Problem Statement:** Let $ f:[0,1]^d \rightarrow [0,1]$ be a $ d$ -dimensional probability density function. Further, for $ c\in [0, 1]$ and $ \mathbf{w}\in \mathbb{R}^d$ , let $ H = \{\mathbf{x} \in [0,1]^d : \mathbf{w}\bullet\mathbf{x} = c\}$ be a hyperplane. This separating hyperplane partitions partitions the unit hypercube $ [0, 1]^d$ , into two regions,

$ $ U = \{\mathbf{x} \in [0,1]^d :\mathbf{w} \bullet \mathbf{x} > c\} \quad \text{ and }\quad L = \{ \mathbf{x} \in [0, 1]^d: \mathbf{w} \bullet \mathbf{x} \leq c\}$ $

Under what conditions on $ f$ can one efficiently compute (approximately or exactly) the cumulative probability of $ f$ over $ L$ (or equivalently over $ U$ ), i.e. $ \int_{L} f(\mathbf{x})d\mathbf{x}$ ?

**Preliminary Ideas**: If $ f$ is something like the uniform distribution then the integral can be computed exactly. For sake of example, suppose that $ \mathbf{0}\in L$ and $ H$ represents the upper limits of integration. Then we are integrating

$ $ \int_{0}^c\int_{0}^{\frac{c – w_dx_d}{w_{d-1}}}\dots\int_{0}^{\frac{c – w_2x_2 – \dots w_dx_d}{w_1}} 1 dx_1 \dots dx_{d-1} dx_d$ $

Which each integral has a closed form solution derivable in polynomial time, and there are only $ d$ number of integrals. Assuming this is correct, then if $ f$ is any polynomial it can also be solved exactly.

**Question** Are there any characteristics, or common families of PDFs in which this problem is polynomial time solvable? In practice, PDFs such as a Gaussian are computed numerically, is there any literature on how well of a numerical approximation can be achieved in this setting, for $ d$ -dimensional PDFs which are computed numerically?