And now a word from our sponsors
Today I interrupt your regularly-scheduled P vs. NP programming to bring you a special message from Dmitry Maslov, the program director at NSF Computing and Communication Foundations (CCF) who handles quantum information science. Besides paying for my CAREER grant (and thus, arguably, in an indirect sense, for this blog), Dmitry also happens to be one of my favoritest people anywhere: a stand-up guy who’s doing an incredible amount to help quantum computing research in the United States. So, given that what he wants is for us to send in more proposals, so that he can help us even more, I found it impossible to say no to his request for some advertising space on Shtetl-Optimized. Announcement follows.
The Division of Computing and Communication Foundations at the National Science Foundation invites proposal submissions in the area of Quantum Information Science (QIS). NSF’s interest in Science and Engineering Beyond Moore’s Law emphasizes all areas of QIS. The range of topics of interest is broad and includes, but is not limited to, all topics relevant to Computer Science in the areas of quantum computing, quantum information, quantum communication, and quantum information processing. Please note the deadlines:MEDIUM Projects
Full Proposal Submission Window: September 1, 2010 – September 15, 2010
LARGE Projects
Full Proposal Submission Window: November 1, 2010 – November 28, 2010
SMALL Projects
Full Proposal Submission Window: December 1, 2010 – December 17, 2010
Additional information may be found here: http://www.nsf.gov/funding/
Follow
Comment #1 August 15th, 2010 at 6:14 pm
You did the following:
1) Chickened out of really taking a stance on the problem.
Made excuses about your vacations.
2) Made an ambivalent 200 grand bet, which would have shown you to be right either way.
3) When people have come out with serious objections, ride on their shoulders and again make some clever statements.
Comment #2 August 15th, 2010 at 6:57 pm
This is a great post and I totally agree with it.
I’m going to change the subject (but not completely!) with this math question, inspired by a comment a couple of posts back: One of the shortcomings of my previous complexity zoology project is that the list of complexity classes was too big. I now realize that two complexity classes A and B can both be interesting, and yet the relations between them can be boring. In my project, I took all of the classes from the Complexity Zoo that are decision classes, and only threw out a few that seemed too arcane. Too many were left for all pairs to be interesting.
I would like to find a large (and ideally maximal) clique of complexity classes such that the relations between every pair are interesting. For instance, {P, NP, BQP, QMA, PH, PP, PSPACE, P/poly, NEXP} is such a clique, but it is neither large nor maximal. The clique that I want would contain this one. Also, there is no need to worry about complementation in this list, because I will take coA and A cap coA to be interesting if A is interesting (relative to any B).
Note that if the relation between two classes is an open problem, with or without an oracle or a random or algebrized oracle, that can count as interesting.
So, Scott or any fan of Scott, can you suggest such a list?
Comment #3 August 15th, 2010 at 6:57 pm
marku, you did the following:
1) Left an anonymous comment that made no sense whatsoever.
2) Used the phrase “ambivalent 200 grand bet” without apparent irony.
3) Inadvertently illustrated why I decided to make the bet in the first place, rather than responding to Deolalikar’s paper in a more conventional way. If there are people like you out there, who can’t even make the inference
Scott has bet $200,000 a proof won’t work => Scott has taken a stance that it won’t work,
then how many more would fail to infer my stance from detailed arguments about possible gaps in Deolalikar’s paper?
Comment #4 August 15th, 2010 at 7:01 pm
Greg, did you mean to put your comment in the last post? If so, I’ll be happy to move it.
Comment #5 August 15th, 2010 at 7:16 pm
The first sentence was intended for this post. As for the rest, you can move it to any recent post; I had trouble deciding and I also don’t really care. In fact one reason that I thought of it was that I mentioned Complexity Zoology in my grant proposal.
Comment #6 August 15th, 2010 at 8:52 pm
And as long as we’re posting things only marginally connected here, apparently Conservapedia has decided that Scott is a nasty liberal and that all those mean liberal academics have been mean to Deolalikar, or something like that:
Scott is mentioned by name on the front page:
http://conservapedia.com/Main_Page
Apparently, they really, really didn’t like when he quoted Richard Dawkins.
Comment #7 August 15th, 2010 at 10:26 pm
I was going to say that it is a perverse badge of honor to be denigrated by Conservapedia. Which it is. But actually, Conservapedia is also a un-funny ego trip on the part of Andrew Schlafly, who personally added this otherwise hilarious criticism of Scott. In some ways A. Schlafly is an intelligent guy, like the rest of his family, although I don’t know that he is the sharpest tool in that shed. But it also goes to show: The biggest liar of all is a fanatic who believes his own propaganda.
Comment #8 August 15th, 2010 at 10:35 pm
Also, another example of how Conservapedia (or Andrew Schlafly himself in this case also) is hilarious when it isn’t reprehensible: The page on “counterexamples” to relativity.
Counterexample #8: The action-at-a-distance of quantum entanglement.
Counterexample #9: The action-at-a-distance by Jesus, described in John 4:46-54.
Maybe relativity could take on one of quantum entanglement and Jesus. But if you hit it with both quantum entanglement and Jesus back to back, relativity doesn’t stand a chance.
Comment #9 August 16th, 2010 at 1:24 am
Scott has bet $200,000 a proof won’t work.
really?
lets change the amount.
Scott has bet $1 proof wont work.
Your choice of amount was very intelligent indeed.
Either way, you would have won
Comment #10 August 16th, 2010 at 2:27 am
Glad to hear about Conservapedia and Andrew Schlafly. An excellent P.J. O’Rourke quote (as I recall it): “It is easy being one the funniest conservatives in the world. The only contenders are me, William Buckley, and Pat Robertson. And sometimes I wonder if Pat is really trying to be funny.”
William is no longer with us. I have to admit I thought he was a pretty sharp guy when I was in sixth grade. In later years I realized he was a nut, but a likable nut. P.J. O’Rourke is great to read anytime.
Anyway, maybe Andrew can get the total back to three.
Comment #11 August 16th, 2010 at 5:40 am
I’m indeed honored to have finally made Conservapedia!
However, I notice that Schlafly didn’t dare to mention my $200,000 bet. Is that because money on the line is a language that even gun-toting, freedom-loving, professor-hating cowboys understand, and the bet might have given them pause?
Comment #12 August 16th, 2010 at 1:19 pm
@Scott
http://conservapedia.com/P%3DNP
Comment #13 August 16th, 2010 at 1:29 pm
What a horrible site conservapedia is.
Supporting the most stupid theories
in the world and then slamming my
beloved flat earth theory as liberal
bogus invented by evolutionists 🙂
At least it’s more reallistic than
creation.
Comment #14 August 17th, 2010 at 9:54 am
Greg, perhaps add BPP and #P? I’d be very interested in a more detailed Complexity Zoology, maybe it would start the road to a Makowsky-style cage cleanup?
Comment #15 August 17th, 2010 at 10:32 am
Scott, is this the right link? it seems that the link in the post is to another NSF call for proposals.
Comment #16 August 17th, 2010 at 11:07 am
Andras: Certainly you should include BPP and P^#P. (You can’t add #P itself because it is not Boolean.) In all I would want at least 50 classes (expanded to more with complementation and intersection with complement, maybe also with the class operator A -> P^A).
Comment #17 August 17th, 2010 at 11:26 am
Greg, it seems like you primarily have classes which are comparatively large. Maybe looking at small classes might help? L might be an example (if I’m not mistaken whether L=P is open as is whether L = RL but I’m not aware of any interesting connections between L and comparatively large classes like PP and NP. )
Comment #18 August 17th, 2010 at 12:07 pm
Joshua, certainly L is an interesting smaller class and probably should be included. There is a technical reason that smaller classes work less well in Complexity Zoology: On the one hand, I have to use oracle separations to make sense of the map of complexity classes. On the other hand, the oracle model begins to break down for classes that are too small (or too large), because it is tricky to define a natural level of oracle access. Nonetheless, for L it’s still okay.
The sense of my question, though, is that I don’t need help with individual classes; I have plenty of them. The problem is an excessive proliferation of *pairs* of classes. To see what I’m talking about, take a look at the Complexity Zoology project where I last left it off.
My request is for a large clique of interesting pairs of classes. I think this much at least is safe:
L, P, NP, RP, BPP, BQP, MA, AM, SZK, CZK, IP, QIP, Σ_2P, Σ_3P, PP, PH, BQP, QMA, S_2P, BPP_path, MP, RG, QRG, +P, PSPACE, EXP, NEXP
plus the polynomial Turing closure (A -> P^A) and the polynomial advice closure (A -> A/poly) of some of these classes. (But I am not sure which ones should be so extended.) In fact, this list seems too conservative. The disease that eventually infected the project was comparisons like DQP vs ModP, where understandably no one cares to even call the relation an open problem.
Comment #19 August 17th, 2010 at 4:21 pm
Greg, sorry yes, that makes more clear what you are trying to do.
Comment #20 August 18th, 2010 at 12:47 am
Thanks, Scott, for drawing attention to this, which I will have a go at. I was concerned I might only have a short time to prepare, but I see that, for grant budgets, computer scientists use the word `small’ to mean `gigantic or smaller’. Since there may be other culture differences, I ask
1) In the proposal, should I freely confess my plan to engage in the arcane definition-lemma-theorem-proof tradition of exposition?
2) Is it okay that when I wander through the Complexity Zoo, I only recognize a few ancient species?
3) Can I treat a Quantum Computer as if it were some kind of mathematical abstraction?
Comment #21 August 18th, 2010 at 2:19 am
pure mathematician: your questions would be much better directed to Dmitry or someone else at NSF! However, my guesses as to the answers are
1) yes
2) yes
3) yes
Comment #22 August 18th, 2010 at 2:40 am
My answers:
1) It worked for me.
2) I think so. You should understand BQP.
3) It has always worked for me, with one caveat. You have to accept certain definitions without creative changes for the math to be relevant to QCQI. For instance, p-adic Hilbert spaces are out, unless you can explain why they are relevant to quantum computing.
Comment #23 August 19th, 2010 at 2:36 am
Scott, I see you have a new paper on eccc.uni-trier.de. Nice, but why don’t you upload to arxiv any more? Is it no longer where the action is?
Comment #24 August 19th, 2010 at 4:04 am
asdf: I upload mostly-quantum papers to both quant-ph and ECCC, but mostly-classical papers to ECCC only. The one you saw has very little to do with quantum aside from the motivation.
Comment #25 August 19th, 2010 at 10:09 am
After so many years of occasionally controversial blogging (in your own words in a previous blog entry) how come you have not made a “Controversy” link on wikipedia …
http://en.wikipedia.org/wiki/Scott_Aaronson
The worst you have achieved is a polite Conservapedia listing recently.
Comment #26 August 19th, 2010 at 10:57 am
In my opinion: It has been a tangible setback for the complexity theory community to maintain a separate ECCC from the arXiv. It would be much better if ECCC were an arXiv overlay, which is an idea that has been floating around for roughly a decade. Short of that, I recommend that anyone who is choosing between ECCC and the arXiv post to both of them.
Comment #27 August 20th, 2010 at 12:22 am
Thanks for answer re ECCC. I agree with Greg, it would be great if you could upload to arxiv as well.
I have another question (physics related) if it’s ok, because of the use of Kolmogorov complexity in the paper. Is there a theorem (i.e. formally provable with no handwaving in some version of axiomatic quantum mechanics) that it’s even possible to generate uncomputably random bits in a physical system? That would mean a physical system can’t be simulated by a Turing machine (weakens Church-Turing thesis) and allow discovery of vast amounts of undecidable arithmetic facts, which has always struck me as a bit odd and maybe unphysical. I’ve asked this before but there wasn’t a really clear answer that I could discern.
Comment #28 August 20th, 2010 at 11:33 pm
A question about the original posting: When I follow the link to nsf.gov, there is no announcement about a QIS program in the CCF division. Will it be announced there later?
Comment #29 August 23rd, 2010 at 9:01 pm
I second Greg’s question. It seems that the quote from Dmitry Maslov is an (informal?) email to at least two bloggers. I couldn’t find the quote anywhere else. Anyway, it looks like `Algorithmic Foundations’ covers these topics.