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 comment