## Boolean Circuit Complexity, Recent Advance.

### May 9, 2015

It’s been a month for breakthroughs in circuit complexity. Following on from vzn’s survey of arithmetic circuit complexity at his Turing Machine blog, R.J Lipton’s P=NP has a similar post covering a recent breakthrough paper on Boolean circuit complexity;
https://rjlipton.wordpress.com/2015/05/08/a-tighter-grip-on-circuit-depth/
The Benjamin Rossman, Rocco Servedio, and Li-Yang Tan paper in question is titled, An average-case depth hierarchy theorem for Boolean circuits. Showing amongst other things, that polynomial hierarchy is infinite for a random oracle. Lipton explains, “The point in BP.NP = Almost NP is that random oracles furnish random bits for the computations. The random oracles could be richer in that exponentially many poly-length computations could use exponentially many random oracle bits in-toto. But the aforementioned closure properties together with probability amplification bridge the difference to machines using polynomially many independent bits when ${{\cal C}}$ is a hierarchy level.”
Clear as mud?

.