# Some consequences of the Roychowdhury-Orlitsky-Siu result from 1994

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!

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)$.
• 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 Aug 29 '17 at 13:34
• Right, the inside probability is over the choice of the input $x \in \{0,1\}^n$. – Yuval Filmus Aug 29 '17 at 13:36
• 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 Aug 29 '17 at 13:38
• 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 Aug 29 '17 at 13:40
• 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 Aug 29 '17 at 13:43