Blog Author: Eleanor Rieffel

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

Quantum Computing for Technology Managers

on Comments (3)

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!

Mathematical and Musical Adventures

on Comments (2)

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!

My dream virtual (almost) reality exhibit

on Comments (2)

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.

Continue Reading

Marking Up a World: Physical Markup for Virtual Content Creation


FXPAL’s Pantheia system enables users to create virtual models by ‘marking up’ a physical scene with pre-printed visual markers and then taking pictures. The meanings associated with the markers come from a markup language that enables users to specify geometric, appearance, or interactive aspects of the model that are then used by the system to construct the model.  Our “Marking up the World” video appeared at ACM Multimedia this week. In the video you can see how our system works, our viewer features, and a selection of the spaces and objects we have used the system to reconstruct.

Thanks much to Qiong Liu for presenting it, and to John Doherty for putting it together from our clips and for narrating it. The geometric reconstruction work I spoke about last week as part of the Bay Area Mathematical Adventures series was inspired by the issues we discovered while building the system. For more details on our work, see the paper we presented at CGVR ’09 Interactive Models from Images of a Static Scene.

Securing the identity of a past FXPAL researcher

on Comments (1)

Volker Roth left FXPAL last year to become a professor at Freie Universität Berlin. There he leads the Secure Identity Research Group, which takes a user centered approach to addressing security and privacy issues related to mobile devices, cloud computing, and the internet.

He and his group have gotten press recently due to a well-publicized celebration of the opening of their new building. There are some great photos of Volker at this opening on the  Bundesdruckerei web site (Bundesdruckerei endowed the position Volker filled and provides other support for the group).  On the same site is a picture of Volker hobnobbing with Horst Köhler, the president of Germany, and his wife! It is great to see Volker thriving.

More mathematical adventures

on Comments (4)

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.

The End of Summer, and Building Rome in a Day

on Comments (1)

Over the last few weeks we have been sad to see our great crop of summer interns leave. Yesterday, my intern, Kathleen Tuite, left, and also, coincidentally, Slashdot picked up a project related closely related to her graduate work. Check out the Building Rome in a Day website to see videos of point cloud models for landmark buildings. The system her colleagues at the University of Washington built makes these models from millions of photographs found on Flickr.

Also check out a very early version of Kathleen’s cool Photocity game that complements the Building Rome in a Day work. The game encourages people to take photos that will help fill in point cloud models, so the photos collected as people play her game will improve the Building Rome in a Day  results. Conversely, her project involves managing many more photos than an average Photosynth so she will be borrowing and building on the technologies developed by Sameer Agarwal, Yasutaka Furukawa, and the rest of the Building Rome in a Day team.

Search and/or geometry challenge!

on Comments (15)

Some friends of mine believe that “search” has been solved. They explain that they can almost always find what they are looking for, and quickly, using keyword search. My life is much more frustrating! There are all sorts of things I look for and can’t find. An additional source of frustration is that I don’t know when to give up, when to conclude that what I’m looking for isn’t there.

Recently I had this experience with a question I thought would make a good blog challenge:

Does there exist a polyhedron such that all of its faces are nonconvex?

If you can think up a proof or example, please post your answer in the comments section, but with “Spoiler alert:” at its start. If you find an answer through a web search, give us the URL and tell us your search strategy. A URL pointing to discussion of this exact question would also be acceptable, even if the discussion doesn’t provide an answer.

I’d like to give a prize, and thought about various prizes (a Tcho chocolate bar? treating the winner to coffee? …) but decided in true blog spirit to ask for suggestions for an appropriate prize.

P.S. I thought about defining  terms such as “polyhedron” and “nonconvex” here.  But since this is a search and/or geometry challenge, any readers who do not know the meaning of these 3D geometry terms can still participate. I would be particularly delighted if someone who did not understand the question initially was able to find a solution.

Update: An answer has been found. Congratulations, Francine. However I realize I mixed up two searches, and this one isn’t as hard as I thought I remembered.