Blog Category: mathematics

What made you (continue to) want to write a book?


Many people have asked me why I decided to write a book. A better questions is: “When you realized that writing the book was going to be orders of magnitude harder and take much longer than you thought it would, what made you decide to continue writing the book?”

My co-author, Wolfgang Polak, and I recently received a book review of the sort that is the dream of every author. A dream review is, of course, positive. But more importantly, it praises the aspects of the book that were most important to the author – the reasons the author kept going after other books on the subject came out and the author had a more reasonable (but still too optimistic) estimate of the vast amount of  effort it would take to finish it. (The review appeared in Computing Reviews, but is behind a paywall. Excerpts appear on the book’s Amazon and MIT press web pages.)

In our case,  one of the things that kept us going Continue Reading

A Gentle Introduction

on Comments (6)

Quantum Computing: A Gentle Introduction by Eleanor Rieffel and Wolfgang PolakOur book, Quantum Computing: A Gentle Introduction, has been out for a little over a month. So far, it has received as much attention from weaving blogs as science blogs, due to the card-woven bands on the cover.

MIT press takes pride in their cover designs, but warns authors that  “schedules rarely allow for individual consultation between designers and authors.” They do, however, ask authors to fill out a detailed questionnaire that includes questions asking for the authors’ thoughts with respect to a cover. It was the third question “What would you like the viewer to think or feel when they see the cover?” that prompted me to think that a fabric with abstract, colorful designs would suggest a “gentle” introduction to an abstract and colorful subject. Continue Reading

Limitations of wisdom


Panos Ipeirotis published a nice analysis of the independence assumption of Surowiecki’s Wisdom of Crowds theory. In short, he finds that in some cases independence is necessary, in some cases it seems that some information leakage doesn’t hurt, and in another class of circumstances, pooling information leads to reliably better outcomes than independent guessing.

What’s going on?

Continue Reading

Benoît Mandelbrot, 1924-2010

on Comments (1)

I am saddened to hear that Benoît Mandelbrot has passed away. His The Fractal Geometry of Nature excited and intrigued me when I was in high school, though I admit that while I, like many others, examined all the pictures, I read only scattered parts of the text. The talk of his I attended as an undergraduate was the first technical talk by a famous mathematician that I understood, essentially, in full.  The popularity of fractals was due to the gorgeous pictures,  and was aided by the simplicity of some of the underlying mathematics, which made it accessible to so many, and to the connection of fractals to so many phenomena. That fractals appeared at all scales in nature, from galaxies, to coastlines, to trees, I knew from looking at his book, but their tie to economics was new to me. He struck me as arrogant, but in an endearing way since his pride in his contributions stemmed from his intense love of the work and his absolute conviction of its importance. He clearly enjoyed his maverick status as someone who worked in a different way than most mathematicians, and on non-standard mathematics. Although he taught us to look for self-similar patterns throughout the universe, we won’t find the like of him any time soon.

Overflow overflow?


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 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.

Computing with Secrets

on Comments (1)

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.

Computing with Secrets, but Keeping them Safe

Computing with Secrets, but Keeping them Safe

Research advice and a search challenge

on Comments (9)

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.

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

768 bites the dust!

on Comments (1)

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 2009 research results excited you the most?

on Comments (3)

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.

Continue Reading

Quantum inspired classical results

on Comments (7)

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.

Continue Reading