Ten days ago,  a theoretical computer science community Q&A site went beta and seems to be generating a fair amount of activity. I’m a big fan of MathOverflow, and am delighted to see a similar site springing up for a different field.

Thirty-nine days ago,  a new mathematics site went beta, which initially puzzled me since the mathematics community already has the highly successful MathOverflow site. The difference appears to be that MathOverflow is specifically for research mathematics whereas the new site aims to be broader, allowing more elementary questions.

Overall, I think a proliferation of such sites is great, but it is also confusing. It isn’t always clear when a question is research level or not. There are questions tagged algebra or topology on the CS theory site that are pure mathematics questions. There’s a question tagged  graph theory that had been posted previously to MathOverflow. I am delighted to see that both cs.cr.crypto-security and quantum computing already are populated with a few questions, but similar questions in these areas received good answers on MathOverflow. It would be a shame if the proliferation of sites lead to less interaction between fields rather than more. I’ll be curious to see how the usage patterns play out over time.

Tom Simonite of Technology Review interviewed me about the breakthrough in fully homomorphic encryption that I blogged about here. I very much enjoyed talking with him, and was pleased to see that he wrote a good article on the subject: Computing with Secrets, but Keeping them Safe: A cryptographic method could see cloud services work with sensitive data without ever decrypting it. He quotes me a couple of times on the second page of the article and generously gives me the last word.

I’ve been surprised at how little has been written about this breakthrough, little enough that my blog post continues to be among the top 20 hits for a number of related queries. The field is definitely hot, with DARPA recently announcing two related solicitations, DARPA-RA-10-80 and DARPA-BAA-10-81, on PROgramming Computation on EncryptEd Data (PROCEED). The first solicits research proposals for development of new mathematical foundations for efficient computation on encrypted data via fully homomorphic encryption. The second solicitation is broader, with the goal of developing practical methods for computation on encrypted data without decrypting the data and modern programming languages to describe these computations.

I was intending to write a post on the varied reasons mathematicians give for taking long walks as an aid to research. I couldn’t find my favorite quote, so instead I’m posting a search challenge.

I thought I remembered reading, in the book Littlewood’s Miscellany, something along the lines of the following advice:

Researchers spend the vast majority of their time feeling frustrated. To improve the ratio of time feeling fulfilled to time feeling frustrated, whenever you find a new result or succeed in completing a proof, take the time to enjoy it, preferably by taking a long walk.  Definitely don’t dive into the next problem, or go back and check the proof. There is plenty of time for that later.

However, it doesn’t seem to be in that book. Littlewood certainly approved of walking, and the tone of much of his advice is consistent with this quote, but this particular piece of advice doesn’t appear to be there.  I couldn’t find it in a web search either.

I would love to know the true source for this piece of wisdom.

A  Tcho chocolate bar to anyone who can track down the source!

A multinational team announced on January 7th that they, together with hundreds of computers, running for two years, carrying out about 2^67 instructions, factored RSA-768.  For more details, see their paper. They suggest that this result should encourage everyone to follow NIST’s recommendation to phase out 1024-bit RSA keys.

Which research result excited you the most in the past year? We’re not asking for the one you thought most important, or the one that would be most exciting to everyone, but which one got you, personally, most excited.

I’ll start things off with a result that delighted me so much I went around smiling all day, only feeling sad that more people couldn’t appreciate it! The result, that appeared in two papers almost simultaneously, is that some quantum states are too entangled to be able to compute one way. The result enchants me because it is surprising, fundamental, and related to topics close to my heart. Prior to these papers, the conventional wisdom held that more entanglement could only help quantum computation. It came as a complete surprise that it could hurt!  Dave Bacon writes beautifully and succinctly about these startling results in his viewpoint, published in Physics, about the two papers published together in Physics Review Letters 102 last May. Here I give an briefer account in order to explain why these result delighted me so much.

(more…)

In yesterday’s post, I mentioned that one of my favorite topics is classical results informed by the quantum information processing viewpoint. There are now sufficiently many such results that Drucker and deWolf have written a survey, “Quantum Proofs for Classical Theorems.” I was surprised last month, when another such  example popped up in one of the biggest cryptographic results of 2009, Craig Gentry’s discovery of a fully homomorphic encryption scheme.

(more…)

Wiley’s Handbook of Technology Management, which includes my entry on Quantum Computing, just appeared. I received my tome in the mail today. It is definitely the biggest, weightiest, and most expensive publication I’ve contributed to yet! I was only willing to write the entry if I could also post it on the ArXiv. Wiley agreed, so you can find my entry on the ArXiv as “An Overview of Quantum Computing for Technology Managers.”

I hope the entry conveys the excitement of the field while eliminating some of the hype.  It is focused on what is known about what quantum computers can and cannot do. It does not try to explain how they do what they do. (For that, my tutorial with Wolfgang Polak remains a good starting place.) While the entry discusses well known aspects of quantum computation, such as Shor’s algorithm, quantum key distribution, and quantum teleportation,  it also discusses many lesser known results including more recent algorithmic results and established limitations on quantum computation. I had the pleasure of writing about some of my favorite topics in quantum computing, including purely classical results inspired by the quantum information processing point of view, the elegant cluster state model of quantum computation, and Aaronson’s suggestion that limits on computational power be considered a fundamental guiding principle for physical theories, much like the laws of thermodynamics.

Comments and questions welcome!

The next talk in the Bay Area Mathematical Adventures series is this Friday. Robert Bryant, the current director of MSRI, will speak on “Rolling and Tumbling—The idea of Holonomy.” It sounds like a fun talk; he’ll illustrate his talk with “everyday and some not-so-everyday toys.”

I’ve posted the slides from my Bay Area Mathematical Adventures talk last month on From Photographs to Models: The Mathematics of Image-Based Modeling. I blogged about that experience here. I had hoped to post a link to the video at the same time, but it isn’t ready yet. I never feel that a talk is fully captured from just the slides, especially one that was designed to be interactive. I will post a link to the video once it is up.

I’d be tempted to go to Bryant’s talk except that I’m singing that night. Two FXPAL folks, Bill van Melle and I, sing in the 40 voice Bay Choral Guild. We have concerts Fri, Sat, and Sun at various Bay Area locations. Come if you are in the area and would enjoy a concert of festive Baroque choral works performed by our excellent group together with an outstanding group of soloists and musicians!

A couple of weeks ago I attended the SIAM/ACM Joint Conference on Geometric and Physical Modeling and heard a lovely talk by Richard Riesenfeld. Riesenfeld and his wife Elaine Cohen were this year’s Bézier award winners for their work in computer aided geometric design (CAGD). He spoke about his correspondence with Bézier and showed us many of the letters they sent back and forth in the early days of CAD/CAM, with their many hand drawn diagrams and the typed text with the math symbols added in by hand. I spent the time marveling at how they managed to have an effective collaboration over such an impoverished communication channel. But even with all of the wonderful 3D rendering capabilities we have today, it is still hard to communicate about 3D objects and spaces over a distance. Having a visual rendering is not sufficient. Spatial reasoning requires more. Riesenfeld mentioned Bézier’s view that “touch is more discriminative than eyes.”

This theme reminded me that I’ve been meaning to describe and send to the math factory folks  a suggestion for an exhibit in the math museum. Instead, I’ll first write about it here.

(more…)

In early August I thumbed through a copy of The New Yorker idly wondering which article I’d like to read when the name “Glen Whitney” popped out. A close friend of mine from graduate school is named Glen Whitney. Could it be the same person? Sure enough, with the article called Math-hattan, it had to be! The article talks about his efforts to create a math museum and describes the math tours he is currently giving of Manhattan.

The museum itself is still in the planning stages, but the exhibit Math Midway gathered a lot of press during its tour this summer. I love the picture of Glen riding the square wheeled tricycle that’s part of the exhibit. (Before looking at the pictures, how did they succeed in making the ride smooth?) Like the  Bay Area Mathematical Adventures series, this exhibit is great outreach. I hope eventually it will come west.

In graduate school, I found Glen’s enthusiasm for many things, particularly for mathematics, inspiring and infectious. It is great to see him so successfully pursuing this dream.