2
$\begingroup$

I just saw a YouTube video where Ryan Williams gives a talk about circuit complexity. He stated that random Boolean functions require exponential size circuits to compute, but I don't understand why this would be so. Can someone explain this aspect of circuit complexity for me? Thank you.

$\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.