2
$\begingroup$

Let $F = \{f:\{0,1\}^n \to \{0,1\}\}$ be the set of all boolean functions on $n$ bits. Any such function can be written as a polynomial

$f(x) = a_0 + \sum_i^n a_i x_i + \sum_{i,j}^n a_{i,j} x_i x_j + \cdots $,

where addition and multiplication is modulo 2. The values of these coefficients constitute a perfect encoding of the function in $2^n$ bits.

Now suppose that we wish to encode any function $f \in F$ into $m < 2^n$ bits. One example, $f \mapsto f_l$, is to keep only first $l$ orders of the polynomial expansion, setting all higher terms to zero.

We want to minimize the worst-case error probability $\epsilon = \max_{f \in F} \frac{1}{ 2^n} \sum_{x\in \{0,1\}^n} |f(x)-f_l(x)|$.

Is truncating the polynomial expansion the optimal way to approximate the functions in order to minimize the error or is there a better way?

$\endgroup$
  • $\begingroup$ Have you tried working through some examples? You should be able to write a program to find the optimal solutions for various small values of $m,n$, and then just see whether your proposal is indeed optimal in all those cases. $\endgroup$ – D.W. May 4 '16 at 19:03
  • $\begingroup$ I think this is really an information theory question. Given a string of $2^n$ bits (namely, the truth table of the function), what is the best way to represent it using only $m<2^n$ bits? There are various ways to formulate it this as a lossy compression question. The way you have formulated it, the parameter $\epsilon$ has to be big (at least a constant) whenever $m< 2^n/2$ (or $2^n/c$ for any constant $c$), since there are just too many strings of length $2^n$ to represent all of them well using just $m$ bits. $\endgroup$ – Adam Smith May 7 '16 at 2:15
  • $\begingroup$ Your question seemed to be after something about representations of functions as polynomials though. Is it possible to formulate the thing you were after more precisely? $\endgroup$ – Adam Smith May 7 '16 at 2:16
  • $\begingroup$ @D.W. Also, I have tried enumerating encoding in simple cases to find the optimal strategy. However, there is not much to be learned from this approach as it quickly becomes intractable numerically. There are about $2*10^9$ partitions of the 16 functions on 2 bits into 8 groups (sending 3 bits), and $2*10^8$ into 4 groups (sending 2 bits), both of which are intractable. Partitioning into only 2 groups (sending only one bit) leads to "only" 32767 possibilities, but we already know the optimal strategy in that case anyways $\endgroup$ – philippe May 9 '16 at 11:33
  • $\begingroup$ @AdamSmith Indeed this has a lot to do about information theory, or more precisely communication complexity. I formulated the questions in terms of polynomials, because it seems like this is a natural way to do lossy compression of functions. This is because by omitting the terms with higher powers in the polynomials allows a high success probability of correctly computing the function on most input strings. Maybe what I want to know is: Are all encodings that send $m$ bits of information about the function equivalent in terms of the error $\epsilon$? $\endgroup$ – philippe May 9 '16 at 11:35

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.