Let $s$ be a Sparse boolean function $s:\{0,1\}^{n}\rightarrow \{0,1\}$ such that $|s^{-1}(1)| \leq 2^{n\delta}, 0 < \delta <1$

The majority function $MAJ_{n}$ takes value 1 if and only if the number of 1 bits in the input is greater than or equal $\frac{n}{2}$.

My question is the following.

Can we $\epsilon$-approximate $MAJ_{n}(x_{1},..,x_{n})$ as a function of a few sparse functions: $f( s_{1}(x_{1},...,x_{n}),...,s_{m}(x_{1},...,x_{n}) )$ ? ($f$ is some boolean function, and $\epsilon$ approximate means that except for an $\epsilon$ fraction of the inputs, the funciton value of $MAJ_{n}$ is equals to that of $f$ )

What is a good upper bound of m( if the answer of previous question is YES )?

  • $\begingroup$ note: any function can be $\epsilon$-approximated with $m = 2^{(1-\epsilon) n}$ functions that take 1 on a single input. take the sparse functions to be indicators of some arbitrary $2^{(1-\epsilon) n}$ inputs. also any functions can be $\epsilon$ approximated by a single functions that takes 1 on $2^{(1-\epsilon) n}$ inputs - just zero out the function on $2^{\epsilon n}$ inputs. so i guess you want $\delta < 1-\epsilon$..or you want to understand $m$ as a function of $\delta$ and $\epsilon$? $\endgroup$ – Sasho Nikolov Oct 11 '12 at 14:48
  • 2
    $\begingroup$ If $f$ isn't constrained, this question seems to be pretty easy: there is such an $f$ if and only if $m2^{\delta n}\geq 2^n(\frac 1 2-\epsilon)$. (At least for $n$ odd, where $|MAJ_n^{-1}(\{1\})|=2^{n-1}$.) $\endgroup$ – Colin McQuillan Oct 11 '12 at 14:53
  • 1
    $\begingroup$ To approximate any balanced function (not only $MAJ_n$) you need $m$ to be at least approx. $2^{(1-\delta)n}$. $\endgroup$ – Yury Oct 11 '12 at 14:57
  • $\begingroup$ @Colin You mean if the $s_i$ are not constrained; in your example, you can take $f$ to be the OR function. $\endgroup$ – Yuval Filmus Oct 14 '12 at 2:36

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.