The “Theoretical Computer Science” Q&A site, aka TheoryOverflow, is now in public beta. Now you can ask all those theoretical computer science questions that you’ve been putting off working on while you were watching the saga that has been…the Next Food Network Star. What you thought I was going to say the supposed proof of P versus NP?
Undergraduate School on Experimental QIP
The Institute for Quantum Computing at the University of Waterloo, Canada, will once again go ahead with its Undergraduate School on Experimental Quantum Information Processing (USEQIP 2011). We have locked down our dates for May 30th to June 10th, 2011. Please pass this information to any Undergraduate student that may be interested. (http://go.iqc.ca/useqip2011)
USESIP is a two-week program on the theory and experimental study of quantum information processors aimed primarily at students just completing their junior year. The program is designed to introduce students to the field of quantum information processing. The lectures are geared to students of engineering, physics, chemistry and math, though all interested students are invited to apply. The program has space for 12 students and is fully funded through the Institute for Quantum Computing. All travel and housing costs are funded.
The summer school is staffed by the faculty of the Institute for Quantum Computing, a multidisciplinary research center at the University of Waterloo and an internationally recognized leader in the development of quantum information processors. The 2-week program will consist of lectures introducing quantum information theory and experimental approaches to quantum devices, followed by hands-on exploration of QIP using the experimental facilities of the institute.
The program will include:
- Introduction to quantum information processing, including a brief review of quantum mechanics and linear algebra
- Introduction to nuclear magnetic resonance, which is a versatile test-bed for QIP and will be used to experimentally explore QIP concepts
- Introduction to optics, Mach-Zender interferometry and Bell inequalities
- Introduction to quantum cryptography
- Introduction to quantum error correction
- Introduction to quantum algorithms
- Introduction to current questions in foundations of quantum mechanics including quantum measurement
Tunneling Frogs?
More P vs NP
The Gray Lady on P vs NP with, crazily, a mention of this here blog. Totally not deserving of said mention, but the article is fun.
Don't Forget To Look Up Tonight!
Perseids meteor shower peaking Thursday night through Friday morning.
“For my part I know nothing with any certainty, but the sight of the stars makes me dream.” – Vincent van Gogh
Two Yreka Physicists in the Papers: Hella Cool
Carlos Alcala from McClatchy Newspapers has written a nice article about Austin Sendek and his quest to get “hella” as the official prefix for 1027. It even has a quote from another Yrekan physicist about the prospects for “hella”:
The CCU may not be the last word, though, said David Bacon, a University of Washington computer science/physics research professor.
Bacon has blogged in support of hella and claims it isn’t just because he, too, hails from Yreka.
“It’s just a cute idea,” he said.
And, the United States could adopt it irrespective of the international measurement authorities, he said. “We don’t use the metric system, right?”
Sadly it seems that the committee has no sense of humor about the serious work of SI unit-ology:
Sendek’s most recent effort was an e-mail Wednesday to professor Ian Mills, an English physicist who chairs the international Consultative Committee on Units – the group with the last say on measurement lingo. He asked if he could present the hella proposal to the committee in person.
“I believe a personal proposition would be a fitting way to top off this whimsical international discussion, even if the committee has no intentions of actually implementing the prefix,” he wrote.
Mills responded Thursday, but in the negative.
“I am afraid it is not practical,” wrote Mills, who earlier agreed to share the idea with his committee. “I will let you know how your proposal is received.”
Oh, that is sooooo hella weak.
PNP Hype
One of the most interesting things about the recent claim of a proof that P does not equal NP (see this post on the ice tea blog for a list of problems people are having with the proof, as well as this page hosted on the polymath project) is the amount of interest this paper has drawn. Certainly a large part of this has to do wit the fact that current there are (a) more computer science bloggers than ever before and (b) so many tweeters tweeting the night away. Also, of course, Slashdot can cause all hell to break lose.
But I wonder if there isn’t something else going on here. Privately I have spoken to colleagues who are much more qualified to understand this proof and they are generally skeptical of the claim. This seems completely rational to me, considering the long list of claims that either P=NP or P does not equal NP that have been shot down over the years (a fascinating list at the P-versus-NP page.) That their priors are well tilted toward skepticism seems fairly natural. So, my guess is that for the hard-core complexity theorists their really isn’t that much interest in taking time out of what they are working on understanding the paper…unless someone who they really respect tells them they should do so (I think the Optimizer’s post is a good example of this. Plus, please, people, stop emailing Scott, he needs to get some work done 😉 )
Yet still there is a lot of interest. I’d like to suggest that the reason for this is that the paper involves an unusual diversity of topics in attempting to make a proof. Indeed the paper (an updated version is available here) consists mostly of a lot of review of the fields which are claimed to be needed to understand the proof. These include work on random instances of k SAT, finite model theory, Hammersly-Clifford theorem, and more. Now there are people in theoretical computer science who have enough breadth to skip these review chapters, but I would say that they are in the minority. And even more interestingly there are people who probably are experts in just one of these areas who can read and nod their head at section of the proof, but don’t know the other sections. Okay well maybe I am projecting here, but I know when a group of AI people heard about the paper they were very interested that it used some of the concepts they use everyday. So maybe the reason that this particular P not equal to NP paper has grabbed this much attention is that it samples from a wide group of people who see parts they understand and therefore gets these people to try to understand the full proof. Okay that and the fact that the paper isn’t really “cranky.”
Now as to whether or not the proof is actually correct, well I’m not as rich as Scott, but I would bet that some of the points raised in objection are actually problems, so I’d need some pretty stellar odds before I’d bet that the proof is correct.
Oh and one other thought: it seems that the paper was actually “leaked” after Deolalikar sent the paper to a group of respected complexity theorists. I sure hope that whoever leaked the paper consulted the NyTimes ethicist before leaking it. Or maybe it was WikiLeaks who leaked the paper? Have they no shame?!?!
update:. Note that some people did ask the author for permission before posting about it. See this comment
P NP ?
Vinay Deolalikar from HP Labs has announced a possible proof that P does not equal NP: see here. Apparently this a fairly serious attack by a serious researcher (previous attacks have all, apparently, come from jokesters who use the well known method of hiding mistakes in jokes.) Will it survive? Watch the complexity blogs closely, my friends 🙂
Jerrrrry!
Jerry Rice to be inducted into the Hall of Fame tomorrow. It really was a lot like this
[youtube]http://www.youtube.com/watch?v=hwVakjO0Awg&feature=related[/youtube]
Not bad for #16 in the draft:
[youtube]http://www.youtube.com/watch?v=bpc5TcNRTvs[/youtube]
One of the greatest draft moves of all time, I think.
NSF CCF Funding
Dmitry Maslov, who is currently a program director at the NSF, sends me a note about the upcoming funding opportunity at the NSF
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/pgm_summ.jsp?pims_id=503220&org=CCF
This is a great opportunity to get funding to work on your favorite quantum computing project. Yes, people will fund you to work on the stuff you want to work on! I know, it’s amazing! So go out and write a great grant application…just make sure it’s not too much greater than mine 🙂