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

<p>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}$.</p>

<p>My question is the following. </p>

<p>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$  ) </p>

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

CC BY-SA 3.0
2012-10-11T14:48:13.487Z
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$?
Sasho Nikolov
CC BY-SA 3.0
2012-10-11T14:53:22.220Z
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}$.)
Colin McQuillan
CC BY-SA 3.0
2012-10-11T14:57:01.500Z
To approximate any balanced function (not only $MAJ_n$) you need $m$ to be at least approx. $2^{(1-\delta)n}$.
Yury
CC BY-SA 3.0
2012-10-14T02:36:05.580Z
@Colin You mean if the $s_i$ are not constrained; in your example, you can take $f$ to be the OR function.
Yuval Filmus
<cc.complexity-theory><boolean-functions>
Sparse Boolean Function and Other Boolean Functions
Elely
# Sparse Boolean Function and Other Boolean Functions

(Asked by: username_0 on 2012-10-11)

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 )?

**Tags:** cc.complexity-theory, boolean-functions

> **Comments:**
> **username_1**: 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$?  
> **username_2**: 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}$.)  
> **username_3**: To approximate any balanced function (not only $MAJ_n$) you need $m$ to be at least approx. $2^{(1-\delta)n}$.  
> **username_4**: @Colin You mean if the $s_i$ are not constrained; in your example, you can take $f$ to be the OR function.  

---

## 0 answers

