## 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 is a hierarchy level.”
*Clear as mud?

.

May 12, 2015 at 4:13 pm

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

LikeLike