<p>Let $f\colon \{0,1\}^n \to \{0,1\}$, and let $g\colon \{0,1\}^n \to \{0,1\}$ be chosen uniformly. Then $\Pr[f=g] \sim 2^{-n}\mathrm{Bin}(2^n,1/2)$, and so a Chernoff bound shows that
$$
\Pr_g[\Pr[f=g] \geq \tfrac{1}{2}+\epsilon] \leq e^{-2\epsilon^2 2^n}.
$$
Now suppose that $f$ goes over all $2^{O(n^2s)}$ circuits of size $s$. The probability that one of them has correlation at least $\frac{1}{2}+\epsilon$ with $g$ is at most $e^{O(n^2s) - \Omega(\epsilon^2 2^n)}$. If $s = o(\frac{\epsilon^22^n}{n^2})$ then this probability is $e^{-\Omega(\epsilon^2 2^n)}$, which is smaller than $\epsilon$ for $\epsilon = \omega (\sqrt{n/2^n})$. We obtain $\sqrt{n/2^n}$ by approximately solving $e^{-\epsilon^2 2^n} = \epsilon$: rearranging, we get $\frac{\epsilon^2}{\log(1/\epsilon)} = 2^{-n}$, which shows that $\epsilon \approx 2^{-n/2}$ and so $\log(1/\epsilon) \approx n$. Plugging in the approximation for $\log(1/\epsilon)$, we see that $\epsilon \approx \sqrt{\log(1/\epsilon) 2^{-n}} \approx \sqrt{n/2^n}$.</p>

<p>This proves the first corollary. For the second corollary, substitute $n := \log (n/2)$.</p>

CC BY-SA 3.0
2017-08-29T13:34:48.667Z
Thanks! What do you mean by that ``$Pr[f=g] \geq \frac{1}{2} + \epsilon$" inside the Chernoff? Isnt it a fixed $f$ argument? So when a $g$ is sampled what is the probability over? Or is the inside one really, $Pr_{x \sim \{0,1\}^n} [f(x)=g(x)]$ ?
gradstudent
CC BY-SA 3.0
2017-08-29T13:36:16.617Z
Right, the inside probability is over the choice of the input $x \in \{0,1\}^n$.
Yuval Filmus
CC BY-SA 3.0
2017-08-29T13:38:54.373Z
Okay! And what is this, $Pr[f=g]  \sim 2^{-n}Bin(2^n,\frac{1}{2})$. Didn't understand this. What is this a probability over?
gradstudent
CC BY-SA 3.0
2017-08-29T13:40:09.810Z
The sample space of the random variable on the left corresponds to the choice of $g$. The probability in $\Pr[f=g]$ is over the choice of $x$.
Yuval Filmus
CC BY-SA 3.0
2017-08-29T13:43:14.070Z
But this is fixed $f$ and $g$ argument, is it? You claim that given any two Boolean functions $f$ and $g$, $Pr_{x \sim \{0,1\}^n}[f(x)=g(x)] \sim \frac{1}{2^n}\frac{(2^n)!}{(2^n-1/2)!(1/2)!}$. Looks so weird!
gradstudent
CC BY-SA 3.0
2017-08-29T13:46:13.890Z
I'm not claiming that. I'm using $\mathrm{Bin}(N,p)$ for the binomial distribution with $N$ trials and success probability $p$.
Yuval Filmus
CC BY-SA 3.0
2017-08-29T15:19:58.317Z
I realized that I had a mistake in the second bullet point. I corrected it. Do you still think it is the same argument as above? In the second column of page 639 where Theorem 1.1 has been proven it seems from the language that $C$ is a depth 2 LTF circuit which takes $n$ bits as input and of which the first $n/2$ bits are being fixed to a certain $x$ (whose truth table is the same as the $f$ in the second bullet point). The random restriction is happening on the rest of the $n/2$ bits of C.
gradstudent
CC BY-SA 3.0
2017-08-29T15:21:58.530Z
But then in the second bullet point  this $f$ is what is being compared to this C. How is this possible when both have different input sizes?
gradstudent
CC BY-SA 3.0
2017-08-29T15:25:04.520Z
As a graduate student you will need to be able to work such things out on your own. I think I've given you enough hints already.
Yuval Filmus
CC BY-SA 3.0
2017-08-29T15:38:24.177Z
I think what is going on is that the notation in this proof of Theorem 1.1 is very confusing. The depth 2 LTF circuit that is being used in the first paragraph to compete against $f$ is not the circuit that has been called $C$ which is over $n$ bits.
gradstudent
CC BY-SA 3.0
2017-08-29T11:44:44.873Z
2017-08-29T15:24:19.153Z
2017-08-29T15:24:19.153Z
Yuval Filmus
<p>This pertains to the proof of theorem 1.1 in this paper, <a href="http://dl.acm.org/citation.cfm?id=2897636" rel="nofollow noreferrer">http://dl.acm.org/citation.cfm?id=2897636</a> </p>

<hr>

<p>So Roychowdhury-Orlitsky-Siu had shown that the number of depth $2$ linear threshold gate circuits mapping $\{0,1\}^n \rightarrow \{0,1\}$ and of size $s \geq n$ is $2^{O(n^2s)}$. I think I do understand the proof of this theorem but its not clear to me as to how the following two corollaries seem to be immediately following from this, </p>

<ul>
<li><p>That for all $\epsilon &gt;&gt; \sqrt{\frac{n}{2^n}}$ with probability at least $1-\epsilon$ a uniformly at random chosen $n-$bit Boolean function is such that it cannot be matched on more than $(\frac{1}{2} + \epsilon)$ fraction of the inputs by a depth $2$ linear threshold circuit of size $s \leq o(\frac{\epsilon^2 2^n}{n^2})$</p></li>
<li><p>That for all $\epsilon &gt;&gt; \sqrt{\frac{\log n}{n}}$ there exists a constant $c$ small enough such that with probability at least $1-\frac{\epsilon}{3}$ a uniformly at random chosen $\lfloor \log (\frac {n}{2} )\rfloor-$bit Boolean function is such that on $(\frac{1}{2}+\frac {\epsilon}{3})-$fraction of the inputs it is not matched by any depth $2$ linear threshold circuit of size $s \leq \frac{c \epsilon^2 n }{\log ^2 n}$</p></li>
</ul>

<p>Can someone kindly put in an explanatory proof for the above two statements?</p>

<hr>

<p>Apparently the second of the above statements is either equivalent to or implies that if the $\lfloor \log (\frac {n}{2} )\rfloor-$bit Boolean function picked is such that it indeed cannot be matched on $(\frac{1}{2}+\frac {\epsilon}{3})-$fraction of the inputs by any depth $2$ linear threshold circuit of size $s \leq \frac{c \epsilon^3 n^{\frac {3}{2}} }{\log ^3 n}$ then with probability at least $1-\frac {\epsilon}{3}$ this function's truth table is the same as an $\frac{n}{2}$-bit string picked uniformly at random. I don't understand why! </p>

<circuit-complexity><linear-algebra><boolean-functions><circuit-depth><circuits>
Some consequences of the Roychowdhury-Orlitsky-Siu result from 1994
gradstudent
# Some consequences of the Roychowdhury-Orlitsky-Siu result from 1994

(Asked by: username_0 on 2017-08-29)

This pertains to the proof of theorem 1.1 in this paper, <http://dl.acm.org/citation.cfm?id=2897636>

---

So Roychowdhury-Orlitsky-Siu had shown that the number of depth $2$ linear threshold gate circuits mapping $\{0,1\}^n \rightarrow \{0,1\}$ and of size $s \geq n$ is $2^{O(n^2s)}$. I think I do understand the proof of this theorem but its not clear to me as to how the following two corollaries seem to be immediately following from this,

* That for all $\epsilon >> \sqrt{\frac{n}{2^n}}$ with probability at least $1-\epsilon$ a uniformly at random chosen $n-$bit Boolean function is such that it cannot be matched on more than $(\frac{1}{2} + \epsilon)$ fraction of the inputs by a depth $2$ linear threshold circuit of size $s \leq o(\frac{\epsilon^2 2^n}{n^2})$
* That for all $\epsilon >> \sqrt{\frac{\log n}{n}}$ there exists a constant $c$ small enough such that with probability at least $1-\frac{\epsilon}{3}$ a uniformly at random chosen $\lfloor \log (\frac {n}{2} )\rfloor-$bit Boolean function is such that on $(\frac{1}{2}+\frac {\epsilon}{3})-$fraction of the inputs it is not matched by any depth $2$ linear threshold circuit of size $s \leq \frac{c \epsilon^2 n }{\log ^2 n}$

Can someone kindly put in an explanatory proof for the above two statements?

---

Apparently the second of the above statements is either equivalent to or implies that if the $\lfloor \log (\frac {n}{2} )\rfloor-$bit Boolean function picked is such that it indeed cannot be matched on $(\frac{1}{2}+\frac {\epsilon}{3})-$fraction of the inputs by any depth $2$ linear threshold circuit of size $s \leq \frac{c \epsilon^3 n^{\frac {3}{2}} }{\log ^3 n}$ then with probability at least $1-\frac {\epsilon}{3}$ this function's truth table is the same as an $\frac{n}{2}$-bit string picked uniformly at random. I don't understand why!

**Tags:** circuit-complexity, linear-algebra, boolean-functions, circuit-depth, circuits


---

## 1 answers

### Answer by username_1 on 2017-08-29. Score: 4

Let $f\colon \{0,1\}^n \to \{0,1\}$, and let $g\colon \{0,1\}^n \to \{0,1\}$ be chosen uniformly. Then $\Pr[f=g] \sim 2^{-n}\mathrm{Bin}(2^n,1/2)$, and so a Chernoff bound shows that
$$
\Pr\_g[\Pr[f=g] \geq \tfrac{1}{2}+\epsilon] \leq e^{-2\epsilon^2 2^n}.
$$
Now suppose that $f$ goes over all $2^{O(n^2s)}$ circuits of size $s$. The probability that one of them has correlation at least $\frac{1}{2}+\epsilon$ with $g$ is at most $e^{O(n^2s) - \Omega(\epsilon^2 2^n)}$. If $s = o(\frac{\epsilon^22^n}{n^2})$ then this probability is $e^{-\Omega(\epsilon^2 2^n)}$, which is smaller than $\epsilon$ for $\epsilon = \omega (\sqrt{n/2^n})$. We obtain $\sqrt{n/2^n}$ by approximately solving $e^{-\epsilon^2 2^n} = \epsilon$: rearranging, we get $\frac{\epsilon^2}{\log(1/\epsilon)} = 2^{-n}$, which shows that $\epsilon \approx 2^{-n/2}$ and so $\log(1/\epsilon) \approx n$. Plugging in the approximation for $\log(1/\epsilon)$, we see that $\epsilon \approx \sqrt{\log(1/\epsilon) 2^{-n}} \approx \sqrt{n/2^n}$.

This proves the first corollary. For the second corollary, substitute $n := \log (n/2)$.

> **Comments:**
> **username_0**: Thanks! What do you mean by that ``$Pr[f=g] \geq \frac{1}{2} + \epsilon$" inside the Chernoff? Isnt it a fixed $f$ argument? So when a $g$ is sampled what is the probability over? Or is the inside one really, $Pr_{x \sim \{0,1\}^n} [f(x)=g(x)]$ ?  
> **username_1**: Right, the inside probability is over the choice of the input $x \in \{0,1\}^n$.  
> **username_0**: Okay! And what is this, $Pr[f=g]  \sim 2^{-n}Bin(2^n,\frac{1}{2})$. Didn't understand this. What is this a probability over?  
> **username_1**: The sample space of the random variable on the left corresponds to the choice of $g$. The probability in $\Pr[f=g]$ is over the choice of $x$.  
> **username_0**: But this is fixed $f$ and $g$ argument, is it? You claim that given any two Boolean functions $f$ and $g$, $Pr_{x \sim \{0,1\}^n}[f(x)=g(x)] \sim \frac{1}{2^n}\frac{(2^n)!}{(2^n-1/2)!(1/2)!}$. Looks so weird!  
> **username_1**: I'm not claiming that. I'm using $\mathrm{Bin}(N,p)$ for the binomial distribution with $N$ trials and success probability $p$.  
> **username_0**: I realized that I had a mistake in the second bullet point. I corrected it. Do you still think it is the same argument as above? In the second column of page 639 where Theorem 1.1 has been proven it seems from the language that $C$ is a depth 2 LTF circuit which takes $n$ bits as input and of which the first $n/2$ bits are being fixed to a certain $x$ (whose truth table is the same as the $f$ in the second bullet point). The random restriction is happening on the rest of the $n/2$ bits of C.  
> **username_0**: But then in the second bullet point  this $f$ is what is being compared to this C. How is this possible when both have different input sizes?  
> **username_1**: As a graduate student you will need to be able to work such things out on your own. I think I've given you enough hints already.  
> **username_0**: I think what is going on is that the notation in this proof of Theorem 1.1 is very confusing. The depth 2 LTF circuit that is being used in the first paragraph to compete against $f$ is not the circuit that has been called $C$ which is over $n$ bits.  

---

