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?

.

Advertisements

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


Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: