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;
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.”


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: