# Constructing xor separable boolean upper bound

Problem statement Suppose I have a boolean function $$f: \mathbb{F}_2^n \times \mathbb{F}_2^m \to \mathbb{F}_2$$ where $$\mathbb{F}_2 = \{0,1\}$$.

I define two boolean functions $$h: \mathbb{F}_2^n \to \mathbb{F}_2$$ and $$g: \mathbb{F}_2^m \to \mathbb{F}_2$$ to be xor separable upper bound of $$f$$ if $$f(\vec{x}, \vec{y}) \leq h(\vec{x}) \oplus g(\vec{y})$$ for all $$\vec{x} \in \mathbb{F}_2^n$$ and $$\vec{y} \in \mathbb{F}_2^m$$. (Here $$\oplus$$ is the logical xor operator). Let $$S$$ denote the set of xor separable upper bounds of $$f$$.

I would like to like to optimize the following: $$\min_{(h,g) \in S} |\# h^{-1}(0) - \frac{1}{2} 2^n|$$

In particular, I wish to find the optimal $$h$$ and $$g$$. However, this seems incredibly difficult.

Question: Is there a heuristical method to find $$h$$ and $$g$$ such that $$|\# h^{-1}(0) - \frac{1}{2} 2^n|$$ is "small" (doesn't have to be the optimal value)? Feel free to assume any nice boolean expression format for $$f$$ (such as CNF or DNF, etc...). I cannot come up with an algorithm better than brute force iteration. Here, $$n$$ and $$m$$ can be very big (order of hundreds)

Comments Note that $$S$$ is not empty since the constant function pair of $$(h = 1, g = 0)$$ is in $$S$$. Thus the minimization problem is well posed. Furthermore, I am not certain if this will help, but does the problem become easier if $$\#f^{-1}(1)$$ very small compared to $$2^{n + m}$$?

Edit Instead of optimizing $$\min_{(h,g) \in S} |\# h^{-1}(0) - \frac{1}{2} 2^n|$$, getting the tightest upper bound would be interesting as well.