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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.