<p>I am not an expert on circuits and I wonder whether the following problem was already studied (and possibly solved). Any reference or suitable method to solve this question would be welcome. </p>

<p>Let $C_{n}$ be the Boolean circuit satisfying the following conditions:</p>

<ol>
<li>the depth of $C$ is $2n$,</li>
<li>the gates of odd level are binary $\operatorname{AND}$ gates,</li>
<li>the gates of even level are binary $\operatorname{OR}$ gates.</li>
</ol>

<p>The circuit $C_{n}$ computes a function $f_n$ which associates to each binary word of 
length $2^{2n}$ a Boolean value.
For instance, for $n = 1$, $f_1(1010) = 0$ and $f_1(0011) = 1$, as shown in the<br>
figure below:</p>

<p><a href="https://i.sstatic.net/Qs3gp.gif" rel="noreferrer"><img src="https://i.sstatic.net/Qs3gp.gif" alt="enter image description here"></a>
For $0 \leqslant k \leqslant 2^{2n}$, let $L_k = \{ u \in \{0, 1\}^{2^{2n}} \mid |u|_1 = k \}$,
a language of size 
$$
  \binom{2^{2n}}{k} = \frac{2^{2n}!}{k! (2^{2n} - k)!}
$$
Here is an instance of the problem I have in mind: if 40\% of the bits of the input
$x$ are equal to $1$, what is the expected value of $f_n(x)$? Here are a few more precise instances of this problem.</p>

<ol>
<li><p>Compute the average value of $f_n(x)$ on $L_k$, that is,
$$
  \frac{k! (2^{2n} - k)!}{2^{2n}!} \sum_{x \in L_k} f_n(x),
$$</p></li>
<li><p>In particular, let $c \in [0,1]$ be a real number and let $c_n = \lfloor
 c2^{2n}\rfloor$. Can one estimate the average value of $f_n(x)$ on $L_{c_n}$, that is,
$$
 \frac{c_n! (2^{2n} - c_n)!}{2^{2n}!} \sum_{x \in L_{c_n}} f_n(x)\ ?
$$</p></li>
<li><p>Does the limit of the previous expression exists when $n$ tends to $\infty$?
$$
 \lim_{n \to \infty} \frac{1}{\binom{2^{2n}}{c_n}} \sum_{x \in L_{c_n}} f_n(x) = 
 \lim_{n \to \infty} \frac{c_n! (2^{2n} - c_n)!}{2^{2n}!} \sum_{x \in L_{c_n}} f_n(x)
$$</p></li>
</ol>

CC BY-SA 4.0
2018-07-17T15:54:45.603Z
Can you be more explicit on the definition of $C_n$ ? 
Do you mean that the circuits is actually the full binary alternating formula of depth $2n$ ? (each gates is fan-out $1$ and fan-in $2$) or is it any circuits satisfying your specifications (with arity $2$ gates?) ?
C.P.
CC BY-SA 4.0
2018-07-17T16:23:43.343Z
Thanks for the comment.Each gate has fan-in $2$, so  $C_n$ is indeed the full binary alternating formula of depth $2n$. I edited the question accordingly.
J.-E. Pin
CC BY-SA 4.0
2018-07-17T18:45:29.360Z
If I haven't made any obvious mistakes, then for uniformly distributed inputs over $\{0,1\}^{2^{2n}}$, the probability of evaluating to zero satisfies $p(n)=p^2(n-1)*(2-p(n-1))^2$, which seems to converge to $1$ very quickly. This would answer your third question in the $c_n\le \frac{1}{2}2^{2n}$ case.
Ariel
CC BY-SA 4.0
2018-07-19T19:29:34.910Z
@Ariel For any $c$ I feel like the recursion still holds when $n$ is large, due to the concentration of weight in each part.
Wei Zhan
<reference-request><circuit-complexity><circuits>
Expected value of the evaluation of Boolean circuits of depth $2n$
J.-E. Pin
# Expected value of the evaluation of Boolean circuits of depth $2n$

(Asked by: username_0 on 2018-07-17)

I am not an expert on circuits and I wonder whether the following problem was already studied (and possibly solved). Any reference or suitable method to solve this question would be welcome.

Let $C\_{n}$ be the Boolean circuit satisfying the following conditions:

1. the depth of $C$ is $2n$,
2. the gates of odd level are binary $\operatorname{AND}$ gates,
3. the gates of even level are binary $\operatorname{OR}$ gates.

The circuit $C\_{n}$ computes a function $f\_n$ which associates to each binary word of
length $2^{2n}$ a Boolean value.
For instance, for $n = 1$, $f\_1(1010) = 0$ and $f\_1(0011) = 1$, as shown in the  
figure below:

[![enter image description here](https://i.sstatic.net/Qs3gp.gif)](https://i.sstatic.net/Qs3gp.gif)
For $0 \leqslant k \leqslant 2^{2n}$, let $L\_k = \{ u \in \{0, 1\}^{2^{2n}} \mid |u|\_1 = k \}$,
a language of size
$$
\binom{2^{2n}}{k} = \frac{2^{2n}!}{k! (2^{2n} - k)!}
$$
Here is an instance of the problem I have in mind: if 40\% of the bits of the input
$x$ are equal to $1$, what is the expected value of $f\_n(x)$? Here are a few more precise instances of this problem.

1. Compute the average value of $f\_n(x)$ on $L\_k$, that is,
   $$
   \frac{k! (2^{2n} - k)!}{2^{2n}!} \sum\_{x \in L\_k} f\_n(x),
   $$
2. In particular, let $c \in [0,1]$ be a real number and let $c\_n = \lfloor
   c2^{2n}\rfloor$. Can one estimate the average value of $f\_n(x)$ on $L\_{c\_n}$, that is,
   $$
   \frac{c\_n! (2^{2n} - c\_n)!}{2^{2n}!} \sum\_{x \in L\_{c\_n}} f\_n(x)\ ?
   $$
3. Does the limit of the previous expression exists when $n$ tends to $\infty$?
   $$
   \lim\_{n \to \infty} \frac{1}{\binom{2^{2n}}{c\_n}} \sum\_{x \in L\_{c\_n}} f\_n(x) =
   \lim\_{n \to \infty} \frac{c\_n! (2^{2n} - c\_n)!}{2^{2n}!} \sum\_{x \in L\_{c\_n}} f\_n(x)
   $$

**Tags:** reference-request, circuit-complexity, circuits

> **Comments:**
> **username_1**: Can you be more explicit on the definition of $C_n$ ?  Do you mean that the circuits is actually the full binary alternating formula of depth $2n$ ? (each gates is fan-out $1$ and fan-in $2$) or is it any circuits satisfying your specifications (with arity $2$ gates?) ?  
> **username_0**: Thanks for the comment.Each gate has fan-in $2$, so  $C_n$ is indeed the full binary alternating formula of depth $2n$. I edited the question accordingly.  
> **username_2**: If I haven't made any obvious mistakes, then for uniformly distributed inputs over $\{0,1\}^{2^{2n}}$, the probability of evaluating to zero satisfies $p(n)=p^2(n-1)*(2-p(n-1))^2$, which seems to converge to $1$ very quickly. This would answer your third question in the $c_n\le \frac{1}{2}2^{2n}$ case.  
> **username_3**: @username_2 For any $c$ I feel like the recursion still holds when $n$ is large, due to the concentration of weight in each part.  

---

## 0 answers

