The problem we should all be working on

Thomas Edison was one of the greatest inventors of all time. He invented everything from the phonograph, to the motion picture camera, and to a practical electric light bulb.

Today I want to talk about what I think is the most important open problem in all of computing. It is not P${\neq}$NP.

Inventing is hard. Even Edison had trouble with inventions—at least at the beginning of his career. His first invention was an electric voting machine. He envisioned that Congress, for example, would want to speed up votes that they took many times a day. He noticed that voting was by “roll call,” which was slow and cumbersome. Edison built a electric system that tallied the votes. Given how primitive electric systems were in 1869, this was a great feat: he was granted patent number #90,646.

While his voting machine was a brilliant machine sales were poor. Actually, there were no sales. He sold zero of his machines. It turned out that congressmen did not mind that voting was slow; actually they liked that it took time. During the vote they could discuss the vote, “twist arms,” and make deals. They did not want an instant vote.

Edison learned an important lesson: only invent something if there is a potential market. Only invent something, if there are potential users. From then on his inventions all solved practical and important problems.

The Problem

Here is the most important problem in my opinion.

${\bullet }$ The Projector Problem: Simply put:

How do we make screen projectors work?

I believe that we are sorely in need of an Edison who can invent a projector system that actually works.

I cannot count the number of times I have sat in a room waiting for the speaker to figure out how to get their computer to talk with the projector. Sometimes we get no signal, sometimes we get a garbled signal, and sometimes we get a “projector is warming up” message. I believe that billions of hours of productive time are lost because projectors do not work properly.

In one of our buildings at Tech the projectors have a built in timer. This makes them turn off after about 90 minutes. I cannot tell you how much fun it is to be in the middle of a long meeting and have the projector decide to quit. Very neat feature.

While we are talking about projectors I have a suggestion for Microsoft. In the “old days” we had the ability to move a plastic slide up so the audience could see the bottom of a slide. I believe this is impossible today—at least I have no idea how to make Powerpoint move a slide up. My suggestion is simple: add a feature that allows the speaker to move slides around the screen. I think this is within known technology, and I think it would be quite useful. This would help, for example, at some conferences where the room is flat. Those in the back of a large room have no way to see any formula written at the bottom of a slide.

Open Problems

Is the projector problem as important as I claim? What is your favorite open practical problem? I hope you do not mind a less technical than usual discussion.

1. August 31, 2010 9:59 pm

They’ve already attempted to solve this problem with such items as Microsoft Surface ( http://www.microsoft.com/surface/en/us/default.aspx ). You could take that, and configure it such that it’s display is a projector, and then just have your presentation downloadable as a PDF or similar, and you are ready to go.

The problem you’re really asking about is interoperability between devices. Of course, any given setup will work when all the parts have been tested togther, but when you bring in old devices and match them to new devices you are bound to see issues.

The answer is obvious: Standardise everything. Of course, it doesn’t happen. There is no “standard” install of all programs on a computer. So while that is true, it means random programs, errors in hardware will cause issues.

The simplest solution, then, is redundancy and as much interoperability as possible. If you go to present, have an online pdf available, so you can use someone elses computer. Have your document in many formats. Make sure your VGA works. Bring appropriate cables, and so on. And if you are hosting presenters, have several machines available, have one connected that is minimal and connects to the internet, to do the backup presentations via online systems, and so on and so forth.

I do think there is work to do be done in an idealised presentation system (a-la surface, where it can be like a blackboard for writing as well as for talking), but even some/(most?) laptops allow this natively.

2. September 1, 2010 12:53 am

Apart from hand-shaking (mainly man-made), the second problem (technical) is the heat generated by the light source – which is why the projector may have a timer. This too is being addressed by the development of low-power high-lumen LEds. This should eventually lead to every mobile computing and communication device having a built-in projector.

3. September 1, 2010 2:56 am

Well, as for moving the slides wish, take a look at the http://www.prezi.com/ it might be the thing you are looking for, and then some.

4. September 1, 2010 4:11 am

I’m sure Apple will eventually build one into the iphone

September 1, 2010 4:54 am

Yes the solution to your problem is within known technology. It is: not using Powerpoint.

Some people like to have their presentations as HTML documents and present them in a web browser (in fullscreen mode). Others like to have their slides as PDF, and present them in any PDF viewer. Many PDF viewers have a presentation mode, and in any case you can scroll the image and magnify parts of the slides if you need.

The beamer and chaksem packages for LaTEX are made for making presentation slides.

September 1, 2010 5:21 am

Hi,

I was attending an AI conference (on video game (actually some challenging AI stuffs have to be done there)) a few month ago, and one guy made its own “projector” software… It’s open source, available on mac only (but really nice… If you can handle to “code” your presentation as he did). At least you can slide your slides in any directions 🙂
see http://digestingduck.blogspot.com/2010/07/my-paris-game-ai-conference.html

7. September 1, 2010 5:36 am

Two of my favorite presentation-related open problems each have well-known confections associated to them. Google will find both of them.

The first confection is Peter Norvig’s The Gettysburg Powerpoint Presentation (2000). Norvig’s presentation is hugely funny .. but *why* is it funny? That is this post’s first open problem.

The second confection is Scott Manley’s recent video Asteroid Discovery From 1980 – 2010 (on YouTube, and elsewhere). Manley’s video is not funny … it is awe-inspiring.

Is Manley’s already-renowned video really showing us asteroid discoveries? Or perhaps gene discoveries? Protein interactions in embryogenesis? Evolving connections in an infant brain? … gosh … is it maybe the future of the Complexity Zoo? So this post’s second open problem is, how do we grasp these ubiquitous complexities?

With humor (as in Norvig’s presentation)? For sure. Dynamically (as in Manley’s video)? Yes.

Then I have a vague idea that “naturality” is a third necessary ingredient. … but am still trying to grasp what it is, exactly, that naturality might be (Dick’s April 2010 column, Natural, Natural, and Natural, is all about this topic).

Any talk where the audience comes away feeling that the problem is natural, the proof technology is natural and the answer is (likely to be) natural, is a pretty good talk. So this post’s third open question is, how does a good talk help audiences (students especially) to a natural understanding of a topic?

AFAICT, mathematicians understand naturality better than any other STEM discipline. At least, a full-text search of arxiv preprints shows that mathematicians use the word “naturality” *far* more often than any other research community. So perhaps mathematicians know something, that other STEM disciplines need to learn.

September 1, 2010 8:39 am

chalk -> chalkboard

marker -> whiteboard

transparencies -> slide projector

there, now you have 3 solutions.

(1-o(1)) serious,

s.

9. September 1, 2010 11:13 am

Regarding the third part of showing the bottom of the slide, you can use ‘zoom’ animation to zoom into a part of the slide, and then zoom out.

10. September 1, 2010 12:52 pm

Dick asked a pretty general question: “What is your favorite open practical problem?”

Is it really true that all the world’s open practical problems are associated to screen projectors?

If so … then we must be living in Paradise! 🙂

I can name another … it isn’t very elegant, but it is darn irritating … won’t someone please fix the bug (maybe it’s a bug in LAPACK?) that causes sporadic (silent) failure of Mathematica’s SingularValueDecomposition[] routine? This irritating bug has been hanging around for far too many years!

As for problems that are mathematically natural *and* fun *and* practical … hmmm … I’ll have to think about that for awhile.

September 1, 2010 2:00 pm

Projectors and projection screens seem to be going obsolete in their own right. We ditched our projector at work a year or so ago and replaced it with a big-screen TV/monitor. It cost about the same, looks a lot better, doesn’t really take much more space (though it’s certainly less portable), and is a lot less hassle to use.

12. September 1, 2010 5:54 pm

Dear Professor Dic:
I know you are an excellent scienst. But I really think the next words deserve your attention. These words were written by the next Professor:
Lane A. Hemaspaandra
Professor
Computer Science Department
University of Rochester
Rochester, NY 14627-0226
Email: ID = lane; DOMAIN = cs.rochester.edu
Phone +1-585-275-1203; Fax +1-585-273-4556
these words are:

below is the information on a paper that was posted to arxiv.org a week and a half ago (to see why this is such a surprising claim, please keep in mind that testing whether a graph has a Hamilton (Hamiltonian) cycle is NP-complete, and so if this paper if correct would yield P=NP). One interesting line of the paper is this line (and the italics are not mine—the author italicizes that part of that sentence): “This is our big breakthrough (it cost me many years time for getting the algorithm and the proof method).” I just noticed this paper and so for all I know maybe it is right, and if so, the world will transformed (by having thousands of crucial optimization tasks perfectly, exactly solved)… but don’t bet on the paper’s proof being correct; perhaps that will be a question for next year’s CSC200H students to take on. Anyway, the paper can be found at here, and here is the title/abstract:
· arXiv:1004.3702 (*cross-listing*)

· Date: Mon, 12 Apr 2010 04:39:27 GMT (76kb)

·

· Title: A Polynomial Time Algorithm for Hamilton Cycle and Its Proof

· Authors: Lizhi Du

· Categories: cs.DS cs.CC

· We present a polynomial time algorithm for finding a Hamilton

· Cycle(Path) in an undirected graph and proves its correctness. A

· program is developed according to this algorithm and it works very

· well. This paper declares the algorithm, its proof, and the experiment

· data. Even only our experiment data is a breakthrough.

September 1, 2010 7:41 pm

Oh no not again! 🙂

• September 3, 2010 9:56 am

Dear Ram:

Can you tell me the reason why not again? I can give you the program and more detail about my paper.

Sincerely, Lizhi Du

September 4, 2010 11:29 pm

Ram, Lizhi Du’s proof that P=NP was accepted into the cited research literature in April 2010. You can find it here: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
as item #58.

13. September 2, 2010 4:48 am

The 10-15 minutes at the beginning of a typical talk when people try to make the projector and computer talk to each other, create an atmosphere of friendship and comaradeship between the paticipants who face together the strong power of technology. Often this part is even better than the talk itself. Do we really want to live in a world where the projector problem is resolved? Doesn’t a solution of the projector problem really means that creativity can be automatized?

• September 2, 2010 6:11 am

Gil’s comment was (IMHO) … the … best … comment … ever!

Even in the old days, it was moderately gratifying to the audience—the more juvenile members of the audience, anyway—whenever an occasional slide was projected upside down, sideways, or reversed left-to-right.

But Gil is right … short, randomized projector breaks are even better.

This summer, the Northwest Passage has melted open, and various expeditions are sailing through it. One expedition is two Royal Marines (Kev Oliver and Tony Lancashire) who are sailing a tiny Viking longboat west-to-east. Another is Mathieu Bonner, who is rowing the passage east-to-west. Both expeditions are traveling very slowly … they see-and-understand everything … and they share what they see-and-understand on their web sites.

Then there is a group of Wall Street financiers who are zooming through the passage at 40 knots in a triple-engined powerboat. Their expedition’s goal is to cover maximum distance in minimum time. They have a website too … but its content is *not* particularly interesting (IMHO).

We have all been to plenty of the “triple-engined powerboat” kind of talks.

September 2, 2010 3:09 pm

I believe the solution to this problem has come into my brain in a flash of illumination this very afternoon, and here I shall relate it to you.

We have so many useful, networked devices: printers, storage drives, servers of all manner and degree, toasters. What the world needs now is the networked projector. By this I do not mean some triviality such as litter our conference rooms today, where tangled apparatus afford the projector and our laptop some transient mingling. No, the true solution is to have a projector (or even, working in parallel, many banks of projectors!) in a separate, isolated, remote room — a thought-garden tended by a cadre of mendicants with a Zen-like mu-focus.

Thus one’s presentations are freed! Simply send the presentation to the monks. They will ensure its projection, each slide upon slide in slow and stately measure, against the finest blank wall that human artifice can contrive. The projectors shall be lovingly maintained and never, ever in disrepair; the presentations shall start on time; the presentations shall finish on time. No presentation shall be sullied by the presence of anything so mundane as an audience, nor ever reified through the gross act of viewing. Thus one’s presentations are freed!