Is it possible to approximate the cardinal of boolean functions inside a ball?

19 Views Asked by At

Let $\mathcal{X}$ be an input space equiped with a distribution $\mathcal{D}_{\mathcal{X}}$.

We denote $\mathcal{F}$ the set of boolean functions defined on $\mathcal{X}$.

Fix $\epsilon >0$ and $h$ be a boolean function (a function that takes values in $\{0,1\}$). We define $\mathcal{L}_1$ as $||f - g ||_{\mathcal{L}_1} = \mathbb{P}_{x \sim \mathcal{D}} [f(x) \neq g(x)]$.

Is it possible to upper bound the cardinal of boolean functions inside the ball $\mathcal{B}_{\mathcal{L}_1}(h, \epsilon)$?