9
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ 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?) ? $\endgroup$ – C.P. Jul 17 '18 at 15:54
  • $\begingroup$ 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. $\endgroup$ – J.-E. Pin Jul 17 '18 at 16:23
  • $\begingroup$ 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. $\endgroup$ – Ariel Jul 17 '18 at 18:45
  • $\begingroup$ @Ariel For any $c$ I feel like the recursion still holds when $n$ is large, due to the concentration of weight in each part. $\endgroup$ – Willard Zhan Jul 19 '18 at 19:29

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.