## 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?

.

### One Response to “Boolean Circuit Complexity, Recent Advance.”

1. C/o Lance Fortnow @ ‘Computational Complexity’.

“Whether the polynomial-time hierarchy is infinite is one of the major assumptions in computational complexity and would imply a large number of statements we believe to be true including that NP-complete problems do not have small circuits and that Graph Isomorphism is not co-NP-complete.”

http://blog.computationalcomplexity.org/2015/04/ph-infinite-under-random-oracle.html

Like