Replacing madness by mere disappointment

Tim Gowers is going to write about his idea for circuit lower bounds in the form of a seven-part dialog between three characters.

The first installment is out, and it already features a gentle and beautiful introduction to the models of boolean circuits and boolean formulas, and to the natural proof impossibility result. He also brings up the very interesting meta-question (which sounds rather new to me) of whether a “random easy function is pseudorandom.”

(The title of the post is how a character in the dialog refers to impossibility results such as natural proofs.)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s