# Mark Wegman

## contact information

Thomas J. Watson Research Center, Yorktown Heights, NY USA

+19149454900

## links

### Professional Associations

**Professional Associations:**ACM | IEEE | National Academy of Engineering

### more information

**More information:**IBM Research Division Accomplishments

Some folks have been interested in stories I've told about my experience as a researcher and how I go about doing research. If this appeals to you, read on. For many I fear this might seem obvious. These folks should obviously stop reading. This is intended for relatively new researchers. I'm sufficiently far from that designation that perhaps I can offer advice. I'm also far enough from my intended audience that I don't know if this is helpful, so comments would be appreciated.

I've found that different people have different strengths and how they do research should relate to their strengths. I say strengths, not weaknesses, because I've found that I choose collaborators with very different strengths than my own to compensate for my weak points. Even when working alone, it's more important to improve strengths as original work is about something that others have not been able to do.

I was once asked at the end of a lecture in China what was the hardest problem I ever solved. I didn't think of the right answer at the time, but I should have said that what is hard for me is not necessarily hard for others. For example, I would find what you just did, listening to someone lecture in a foreign language, much harder than any problem I've ever solved. Find the problems that are easy for you and hard for everyone else. That doesn't mean that you can't improve yourself. When I was growing up my father kept repeating the saying, "Every day, in every way, I get better and better". Making sure that's true as you learn to be a researcher is important.

I learned at school that the most important lesson your professors can teach is how to think. The specific lesson they present is less important than seeing how they think about, and then solve, the problem. One of my favorite professors at Berkeley was Manuel Blum, whose advice people might also like to read. He later won a Turing Award.

The first engineering problem I worked on was at a summer job at my uncle's firm. His firm was designing the biggest garbage incinerator ever planned for New York City. The garbage was going to be shipped to the incinerator by barge in huge containers. The question was how to get the garbage out of the containers. When the problem was given to me I was told garbage was too messy to use hinges. They had come up with a complex pulley system to turn the container over and wanted me to draw it up. I thought of a better way, using a chain that could be put over a sprocket on the container to lift and then turn the container. I spent several weeks coming up with that solution, and I was proud of it. In the end they used a system that opened the container from the bottom using a hinge, as a different company had shown that the hinge on their product could withstand the messiness of garbage. The decision to go with the hinge was absolutely the right one as it made the whole design was much simpler. I learned a couple of lessons. One, no matter how clever your solution, it may not be adopted, and two, do not trust authority absolutely about what is the right problem to solve. This is a bigger version of the lesson some people learn from the following problem. Without letting your pen leave the paper, draw 4 lines that connect the following dots:

** . . . . . . . . . **

Understanding what the right problem is, is something even senior researchers often get wrong. Appealing problems are fun to solve but may do nothing for the world. Often spending a few hours or days at the beginning making sure you are solving the right problem can save weeks or months later. Of course you may not be able to find the right problem until you've done some background work looking at the first problem you learn about, so it's important to always keep an open mind and be willing to change your research direction. People often fall in love with the hard or even impossible problem they are trying to solve and ignore the more important easy problem that's right next to it. The classical story of Alexander the Great solving the problem of the Gordian knot is a reminder of this principle.

Another specific instance of the more general issue of how best to do research is the following. If you are going to fail at something, it's best to fail quickly. That way you've wasted little effort and can go on to something else. Often solving a research problem involves solving several sub-problems. You may not even know what the sub-problems are when you start, but for purposes of pedagogy, assume they are parts *a* and *b*. In any research problem you are taking a risk. This requires great courage. Don't think for a moment that it doesn't. Each of the sub-problems might stump you and you might fail at the whole task. Often people think, say, part *b* will be fast and *a* will take some time. This might be because they are more familiar with problems like *a*. They might even have been working on something like *a* very recently. So while they've got the rudiments of *a* in mind they plunge into *a* until they finish, only to find that *b* is insoluble. The right approach to a risky endeavor is to go more breadth first. Do a bit of work on *b* to understand it better, then go back to *a*. People resist this approach because they like doing things they know and are good at, and switching contexts can also be expensive. If success at *b* were guaranteed then finishing *a* first would have been more efficient. If you aren't failing often in research, you aren't solving hard enough problems and taking enough risks. If there's a reasonable chance of failure, then a breadth first approach to the problem allows the faster failure and consequent saving of effort.

I went to a talk many years ago on a probabilistic algorithm for nearest neighbor. I thought it was a great talk, but afterward Ashok Chandra pointed out that the result was wrong because it relied on the existence of what we later called Universal Hash Functions, which were not known to exist at the time. I thought about the issue, defined to some extent what the properties of these functions would have to be, and concluded that they couldn't exist. I thought there would have to be too many of them for them to execute with enough efficiency. I went to Larry Carter and asked him how to show there would be a lot of them. He used the mechanisms of projective planes, which I didn't know about, to show the number would be reasonable and that I was wrong. But the projective planes didn't give a good enough hash function when the output was small, which is most of what happens when you want to do hashing. We found a different projective plane that could have a small output. Then we found something that was implementable in real computers. At the end I looked at it and said that the proof with the reasoning we used would end up being at least one hundred pages. Larry looked at me strangely and said it's a two-line proof, and indeed there was one. The two-line proof uses very simple linear algebra and doesn't mention projective planes. One lesson is, you must understand something fully before you can do something simply. It's okay to go through complex solutions and then simplify later, at least on really hard problems. John Vlissides always told me you need to implement something at least 3 times before you can generalize. Understanding something fully before generalizing and simplifying it is as important in software engineering as in theoretical problems.

Another lesson is that sometimes you find something important that you weren't looking for. There's a bit of a conflict between this statement and my earlier statement that you should solve an important problem. Finding an unexpected use is not just a question of luck. You can improve your odds. It may well be that our result on universal hashing is much more important for cryptography than for our original hash tables application. However, the saving grace here is the problem we were solving was simply stated and very general. Hence people could apply it to domains very different from our original application. Often if you can't come up with a plausible single value proposition and it's not simply describable, then there will not be a use for it that you have not thought of. A senior researcher may be better at this than someone who is just starting out. That's what advisors and mentors are for. If you don't know whether you should be working on a problem, ask for help.

When in grad school I took a date up to the Lawrence Hall of Science. (I know I'm a nerd and have no idea what might be romantic, but there is a lovely view from there of the whole Bay area.) There was a game there with pegs in half the board and empty holes in the other half. In this diagram x's contain pegs and o's are holes:

xooooo

xxoooo

xxxooo

xxxxoo

xxxxxo

The gosl was to jump one peg over another until all but one of the pegs were on the opposite side. I couldn't solve it. I got embarrassed because I wanted to show off how bright I was and I couldn't even solve a problem that 8-year-olds apparently could. I realized that if I wanted to do better than an 8-year-old, I should use resources they don't have. So I used some of my formal training. As those of you who solve the problem will understand, Lawrence changed the game shortly thereafter. The point of this story is, use what you have as an "unfair advantage" to solve problems. This brings us to the next topic, choosing the right problem to attack.

## Choosing the right problem

I took a course with Manuel in which he pulled off an amazing feat. In most of his lectures he went to the board, wrote down a theorem and asked the class to solve the problem. Lecture after lecture we solved a famous theorem in just an hour or so. We had a number of "unfair advantages". Manuel stated the exact theorem. He ordered the presentations of the theorems so the techniques of the last one were helpful in the current task. Remarkably, I never noticed him giving us hints during the lecture, but he told me on the side that he would often cut off discussion heading in directions that were not likely to succeed.

The point is, attack problems where you have an "unfair advantage". Other people are trying to do research. If you tackle something everyone else is looking at in the same way, the only way you might succeed where they fail is to be much smarter and harder-working than they. The odds are against you. If you are among the first to find a problem that will become important, if you build on a foundation that is less available to others or if you have access to unusual expertise in the field, you are ahead of everyone else.

There are two other important criteria for selecting problems. Choose a problem that will move you in a direction you want to go. In other words, choose a problem that will teach you something useful as you tackle it, or have you build something that will also be helpful in future work, regardless of whether you succeed or fail on this problem. The other criteria is, some sort of success is likely.

## Some extra resources

I'm not the first person to write an essay akin to this one. Manuel's page is referenced above. The Heilmeier Catechism is famous in some circles and a very fast read. An additional compilation of advice that may also be relevant can be found here .