…fool me ε times, shame on my constant-depth circuit
February 20th, 2009
Virtually everyone with a CS blog (see Scott Aaronson, Luca Trevisan, and the Complexity Blog) has for the past several weeks been going on about Mark Braverman’s recent proof of the Linial-Nisan conjecture. I don’t have too much to add to the discussion, being a neophyte to much of this stuff, but I did attend a talk Braverman gave at the University of Calgary today, in which he outlined his proof (which is remarkably short, for a proof of a conjecture that took nearly 20 years to solve.) Braverman illustrated his arguments with pictures, which really helped me get a handle on his techniques. Read more…