<p>You seem to be looking at the regime of large error. Just wanted to point out that instead if $\epsilon$ is small enough, then for each $i \in \{0,1\}$, the two quantities are linearly related to each other (which you probably already have taken note of). Let us do it for $i=-1, \epsilon=1/6$. I hope the general case can be suitably worked out.</p>

<p>Let $p:\{\pm 1\}^n \Rightarrow \{\pm 1\}$ be a polynomial of degree $d=P_{1,\epsilon}$, such that $p(x) \in [5/6,7/6]$ for each $x \in f^{-1}(1)$ and $p(x)=-1$ for each $x \in f^{-1}(-1)$. Consider the polynomial $q(x)=\frac{6}{7}p(x)-\frac{1}{7}$. For $x \in f^{-1}(-1)$, $q(x)=-1$, and for $x \in f^{-1}(1)$, $q(x) \in [4/7,6/7] \subset [4/7,1]$. Thus $q(x)$ is also a one-sided approximate polynomial for $f(x)$ of same degree $d$ but with error 1-4/7=3/7. Furthermore, it has the additional property that whenever $f(x)=1$, $4/7 \leq q(x) \leq 1$. Now, we reduce its error from $3/7$ to $\epsilon/2=1/12$ by standard method of confidence amplification of approximate polynomials (See, for example, Appendix B of <a href="http://eccc.hpi-web.de/report/2014/048/" rel="nofollow">http://eccc.hpi-web.de/report/2014/048/</a>). Our final polynomial is the majority polynomial MAJ evaluated on constantly many copies of $q$: MAJ$(q(x), \ldots, q(x))$. The one-sided error property is satisfied by the final polynomial as MAJ$(-1, \ldots,-1)=-1$. The degree is $O(d)$. Thus $P_{i,1/12} = O(P_{i,1/6})$.</p>

CC BY-SA 3.0
2016-06-09T08:56:19.553Z
so what prevents this working for large error?
Turbo
CC BY-SA 3.0
2016-06-09T09:52:17.350Z
@Turbo It appears to me that for the amplification to work, the polynomial $q$ is needed to evaluate to $[+\delta,1]$ on $f^{-1}(1)$ and to $-1$ on $f^{-1}(-1)$. This is ensured when $\epsilon \leq 1/2-\delta$. (Note that I work in the $\pm 1$ setting, so I think it corresponds to $\epsilon \approx 1/4$ in the $\{0,1\}$ setting). It would be interesting if one can find a separation between these two quantities for a large constant $\epsilon$ (eg. $\epsilon = 1$).
Swagato
CC BY-SA 3.0
2016-06-09T04:49:58.437Z
2016-06-09T09:47:45.673Z
2016-06-09T09:47:45.673Z
Swagato
<p>I don't think they are polynomially related. Consider the OR function on n bits. There is a polynomial $p(x) = \frac{1}{n} (x_1 + x_2 + \ldots + x_n)$, which approximates it with one sided error $\epsilon = 1- \frac{1}{n}$ because on the all zero input the polynomial is zero, and on any other input its value is between $\frac{1}{n}$ and 1.</p>

<p>However any polynomial approximating the OR function to one sided error $\epsilon/2$ (which is approximately $1/2$) is a bounded-error approximation of OR which is known to require degree $\Omega(\sqrt{n})$.</p>

CC BY-SA 3.0
2015-05-18T02:50:04.553Z
Sorry I was looking at both $i=0,1$.
Turbo
CC BY-SA 3.0
2015-06-04T11:15:57.287Z
Supposing error does not depend on $n$ and error is $>1/2$ could we still show such a separation using 1-sided error polynomials?
Turbo
CC BY-SA 3.0
2015-05-17T23:51:43.470Z
2015-05-17T23:51:43.470Z
Robin Kothari
<p>Given a boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, let $P_{i,\epsilon}$ be minimum multivariate polynomial such that $P_{i,\epsilon}=i\iff f=i$,  $P_{i,\epsilon}\in(i-\epsilon,i+\epsilon)\iff f=1-i$ where $\epsilon\in(0,1)$ at each $i\in\{0,1\}$.</p>

<p>Is atleast for one of $i\in\{0,1\}$,  degrees of $P_{i,\epsilon},P_{i,\epsilon/2}$ polynomially always related? They should be, however I cannot find a reference.</p>

<p>Straight forward interpolation arguments seems to fail as $\epsilon$ gets closer to 1 (but not exactly $1$). </p>

<boolean-functions>
One sided approximation degree
Turbo
# One sided approximation degree

(Asked by: username_0 on 2015-05-17)

Given a boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, let $P\_{i,\epsilon}$ be minimum multivariate polynomial such that $P\_{i,\epsilon}=i\iff f=i$, $P\_{i,\epsilon}\in(i-\epsilon,i+\epsilon)\iff f=1-i$ where $\epsilon\in(0,1)$ at each $i\in\{0,1\}$.

Is atleast for one of $i\in\{0,1\}$, degrees of $P\_{i,\epsilon},P\_{i,\epsilon/2}$ polynomially always related? They should be, however I cannot find a reference.

Straight forward interpolation arguments seems to fail as $\epsilon$ gets closer to 1 (but not exactly $1$).

**Tags:** boolean-functions

---

## 2 answers

### Answer by username_1 on 2016-06-09. Score: 1

You seem to be looking at the regime of large error. Just wanted to point out that instead if $\epsilon$ is small enough, then for each $i \in \{0,1\}$, the two quantities are linearly related to each other (which you probably already have taken note of). Let us do it for $i=-1, \epsilon=1/6$. I hope the general case can be suitably worked out.

Let $p:\{\pm 1\}^n \Rightarrow \{\pm 1\}$ be a polynomial of degree $d=P\_{1,\epsilon}$, such that $p(x) \in [5/6,7/6]$ for each $x \in f^{-1}(1)$ and $p(x)=-1$ for each $x \in f^{-1}(-1)$. Consider the polynomial $q(x)=\frac{6}{7}p(x)-\frac{1}{7}$. For $x \in f^{-1}(-1)$, $q(x)=-1$, and for $x \in f^{-1}(1)$, $q(x) \in [4/7,6/7] \subset [4/7,1]$. Thus $q(x)$ is also a one-sided approximate polynomial for $f(x)$ of same degree $d$ but with error 1-4/7=3/7. Furthermore, it has the additional property that whenever $f(x)=1$, $4/7 \leq q(x) \leq 1$. Now, we reduce its error from $3/7$ to $\epsilon/2=1/12$ by standard method of confidence amplification of approximate polynomials (See, for example, Appendix B of <http://eccc.hpi-web.de/report/2014/048/>). Our final polynomial is the majority polynomial MAJ evaluated on constantly many copies of $q$: MAJ$(q(x), \ldots, q(x))$. The one-sided error property is satisfied by the final polynomial as MAJ$(-1, \ldots,-1)=-1$. The degree is $O(d)$. Thus $P\_{i,1/12} = O(P\_{i,1/6})$.

> **Comments:**
> **username_0**: so what prevents this working for large error?  
> **username_1**: @Turbo It appears to me that for the amplification to work, the polynomial $q$ is needed to evaluate to $[+\delta,1]$ on $f^{-1}(1)$ and to $-1$ on $f^{-1}(-1)$. This is ensured when $\epsilon \leq 1/2-\delta$. (Note that I work in the $\pm 1$ setting, so I think it corresponds to $\epsilon \approx 1/4$ in the $\{0,1\}$ setting). It would be interesting if one can find a separation between these two quantities for a large constant $\epsilon$ (eg. $\epsilon = 1$).  

---

### Answer by username_2 on 2015-05-17. Score: 1

I don't think they are polynomially related. Consider the OR function on n bits. There is a polynomial $p(x) = \frac{1}{n} (x\_1 + x\_2 + \ldots + x\_n)$, which approximates it with one sided error $\epsilon = 1- \frac{1}{n}$ because on the all zero input the polynomial is zero, and on any other input its value is between $\frac{1}{n}$ and 1.

However any polynomial approximating the OR function to one sided error $\epsilon/2$ (which is approximately $1/2$) is a bounded-error approximation of OR which is known to require degree $\Omega(\sqrt{n})$.

> **Comments:**
> **username_0**: Sorry I was looking at both $i=0,1$.  
> **username_0**: Supposing error does not depend on $n$ and error is $>1/2$ could we still show such a separation using 1-sided error polynomials?  

---

