tag:blogger.com,1999:blog-3722233.post1903515936383568055..comments2020-11-24T09:46:09.481-06:00Comments on Computational Complexity: The New Oracle Result! The new circuit result! which do you care about?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-59272968291211111692015-04-28T08:48:06.262-05:002015-04-28T08:48:06.262-05:00As you may remember, Bill, I was doing recursion t...As you may remember, Bill, I was doing recursion theory as a grad student and shifted over to work with Mike on circuit complexity. The key moment in that evolution was a talk by Cook on his "taxonomy" paper -- "Here are these circuit classes, they classify the difficulty of computing things in parallel, here are some interesting containments, can we get any separations?" I think that I was among the first people to use the name "AC^0" for constant depth, polynomial size, unbounded fan-in, which brings Furst-Saxe-Sipser-Ajtai into the context of the NC hierarchy.<br /><br />So I definitely think the circuit results are more interesting for themselves than for their applications as oracle results. Even though the program of extending these results upward to larger circuit classes (like P) hasn't panned out and may never pan out, a concrete lower bound ("you can't solve this problem with these resources") adds more to what we know about general computation.<br /><br />DaveMBhttps://www.blogger.com/profile/00779581893863396042noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33421295972377713162015-04-23T15:29:52.780-05:002015-04-23T15:29:52.780-05:00I second Fred. Lower bounds for circuits imply oth...I second Fred. Lower bounds for circuits imply other results. But I haven't seen things happening other way around. (Ryan has shown that a reverse traffic could also exist, but this is just a rare and nice exception so far.) Also, to write what an "oracle separation" means will require 2-3 pages (at least). To write what a lower bound for circuits means - just 3-4 sentences. The introduction being: few AND-OR-NOT on 0-1 bits - and what can we get?<br /><br />But it is definitely nice that circuits are related to more "exotic" things like oracles. Anyone can choose what to love: root or tree. Both are important. Without the tree, root (hard root - progress is SO slow, adversary is So powerful) couldn't survive ... But died the root, the tree would definitely die. <br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65136977130100479242015-04-23T12:33:59.491-05:002015-04-23T12:33:59.491-05:00In part because I am of a certain age, I would hav...In part because I am of a certain age, I would have been more likely to say "wow!" upon first seeing the paper had it been titled "The Polynomial-Time Hierarchy is Infinite Relative to a Random Oracle." The problem was open for so long I had forgotten it was open. Of course... I read Lance's post "PH Infinite Under a Random Oracle" first, so the "wow!" opportunity was not missed.<br /><br /> That said, the circuit results are surely more interesting. For one thing, they are stronger (they imply the oracle results as well as other things; and they are not equivalent). Second, they are another (very very small) step in the quest for stronger circuit lower bounds. For the same reason I agree that Parity not in AC_0 (etc.) is more interesting than \exists A (ParityP^A not in PH^A). Come to think of it, it's also easier to write down!Fred Greenhttp://cs.clarku.edu/~fgreen/index.htmlnoreply@blogger.com