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

Improve this question
$\endgroup$
4
  • 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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.