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!


1 Answer 1


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)$.

  • $\begingroup$ 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)]$ ? $\endgroup$ Aug 29, 2017 at 13:34
  • $\begingroup$ Right, the inside probability is over the choice of the input $x \in \{0,1\}^n$. $\endgroup$ Aug 29, 2017 at 13:36
  • $\begingroup$ 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? $\endgroup$ Aug 29, 2017 at 13:38
  • $\begingroup$ 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$. $\endgroup$ Aug 29, 2017 at 13:40
  • $\begingroup$ 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! $\endgroup$ Aug 29, 2017 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.