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.


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.