3
$\begingroup$

Suppose C is a large circuit computing a function $f:2^n \rightarrow 2^m$. For a function $g$ let $B(g)$ denote the size of the minimal Boolean circuit computing $g$. What can be said about the moments of $B(g)$ for $g$ a random restriction of $f$? What about the same question for the concatenation of $k$ random restrictions for some fixed $k$?

Apologies if this question is too basic, but I haven't found a source that directly addresses this question, if you know of one please let me know.

$\endgroup$

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.