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.


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.