4
$\begingroup$

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.

$\endgroup$

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.