How to pick research problems (UPDATED)

(Scroll down to the end for update with Valerie King's contribution.)

[07/01/11] Glencora Borradaile: Hi Claire
[07/01/11] Claire Mathieu: Hi Cora!
[07/01/11] Claire Mathieu: Today we are meeting on skype to discuss how one picks research problems. There are two categories of problems I work on: the problems that I come up with, and the problems that are given to me. When a problem is offered to you, how do you gauge whether it's a "good" problem?
[07/01/11] Glencora Borradaile: If the problem given to you is already a theory problem - distilled to a clean problem - then it should be easier. Have you worked on any problems that weren't already in that form?
[07/01/11] Claire Mathieu: Sometimes but not with great success. Modeling a problem is not my forte.
[07/01/11] Glencora Borradaile: Well, there are problems like the planar PTASes we've worked on - there was a good deal of evidence to believe that the result was possible.
[07/01/11] Claire Mathieu: I would say that it has to catch my interest, so that I happily spend time mulling over it; that I have to have some skills suited to it so that I have a good chance of making progress; and that some other people have to be interested in my solution afterwards, so that I get positive feedback from the community.
[07/01/11] Glencora Borradaile: What makes it catch your interest? Interest must go beyond your second two points, yes?
[07/01/11] Claire Mathieu: It has to be clean and mathematically simple, most of the time. But it has to be not purely recreational. It has to fit in some kind of context where I have a sense that it makes sense. Typically, some long-term hypothetical application... I get impatient with pure combinatorial mathematical problems.
[07/01/11] Glencora Borradaile: Really? You think what we work on has some long-term application?
[07/01/11] Claire Mathieu: I have the sense that combinatorial optimization problems on planar graphs is a subject that matters.
[07/01/11] Glencora Borradaile: I'm certainly arguing as much in my proposal ...
[07/01/11] Claire Mathieu: Now, a PTAS developed for one of those, maybe not so much a priori, but it fits in -- it gives insight into the complexity of the problem.
[07/01/11] Claire Mathieu: Also, I forgot an important criterion!
[07/01/11] Glencora Borradaile: Someone interesting to work with?
[07/01/11] Claire Mathieu: It has to be a problem that some colleagues around me are interested in, so that we can collaborate
[07/01/11] Claire Mathieu: Jinx
[07/01/11] Glencora Borradaile: I remember you talking about not caring to work alone.
[07/01/11] Claire Mathieu: I can't push myself to work on a problem alone
[07/01/11] Claire Mathieu: Jinx
[07/01/11] Claire Mathieu: How about you?
[07/01/11] Glencora Borradaile: A challenge I'm becoming very familiar with at OSU. So it's interesting - I'm not sure of the criterion of what would be a "good" choice. Right now I (know, ill-advisedly) am hung up on "good for career" as opposed to "good for self". Where sometimes those things are different.
[07/01/11] Claire Mathieu: As in... do you have some specific example of a problem which you would like to work on if, say, you were in heaven, with not a care in the world? And infinite time
[07/01/11] Glencora Borradaile: I would go in one of two extremes - much more theoretical or much more applied
[07/01/11] Claire Mathieu: Would you work on P vs. NP? You'd have infinite time to get acquainted with the existing literature
[07/01/11] Glencora Borradaile: I don't think I would work on that - I think I don't want to know the answer to that. I think the field is made interesting by the fact that we don't know it. I might work on things like the 4-colour theorem (a simple proof for it, I mean). Or anything where I didn't have to worry about publishing for a while. *or* I would go and try to solve a real traffic engineering problem, say - propose a good (mathematically sound) solution and see it through to completion.
[07/01/11] Claire Mathieu: The problem is that, even if you don't have to worry about it, if you don't publish, you have no feedback to encourage you, and how do you stay self-motivated? One thing that helps a lot, that I learned from Karp, is to always keep the rate of progress positive. That is, always have an interesting example, or observation...
[07/01/11] Glencora Borradaile: Hmmm. Well, I think that for the "puzzle" aspect, I don't need external motivation.
[07/01/11] Claire Mathieu: Really? For me it quickly becomes sterile if I don't have something else to keep me at it: progress, collaborators, or outside feedback. For planar graphs, I guess I am piggy-backing on Phil Klein's enthusiasm. He provides the fuel, the energy that keeps us going.
[07/01/11] Glencora Borradaile: Perhaps people like you are more likely to be successful in the community. I mean: if you are driven (at least partly) by problems that will be accepted by the community - so as to get that feedback - then you're more likely to get that positive feedback (which we need for accolades and reference letters, etc.)
[07/01/11] Claire Mathieu: Right, on the other hand the researchers who revolutionize our field do not work that way.
[07/01/11] Glencora Borradaile: risk v. reward
[07/01/11] Glencora Borradaile: Do you think that's true?
[07/01/11] Claire Mathieu: Well, there's something to be said about being a problem-solver. Conceivably such a type of researchers could bring in techniques from other areas, their flexibility would make it easy for them to adjust to several fields and then see connections that might have escaped the people who are more driven in a single direction.
[07/01/11] Claire Mathieu: One thing I don't do is attack a big open problem upfront. If people have failed at it for a long time, then it's probably a waste of time to go at it directly. On the other hand changing perspective might make the problem doable and, since it would still be close to a recognized big question, still could be very interesting.
[07/01/11] Glencora Borradaile: But isn't that the opposite of working on problems that are not necessarily accepted by the community? If it's big and open, then there is a history to it?
[07/01/11] Glencora Borradaile: How about open v. new? How do you introduce a new problem to the community?
[07/01/11] Claire Mathieu: If it's not big and open, how do you know it's any good?
[07/01/11] Claire Mathieu: I'm not sure. I'm very tentative on those grounds. Last year Adrian Vladu worked with me on online ranking. It was new - no one had ever worked on that before, although plenty of people had worked on ranking. The reviews for our submission said that it was a "natural" question. What made it natural? I'm not sure. We were in some kind of void where I have to rely on such vague things as "taste" and I have no confidence that I have good "taste".
[07/01/11] Glencora Borradaile: natural = "well studied area A" + "well studied area B"?
[07/01/11] Claire Mathieu: + "putting A and B together makes sense"
[07/01/11] Glencora Borradaile: game theoretic network flows
[07/01/11] Claire Mathieu: A=game theory, B=network flows, A+B="people make decisions with themselves in mind when choosing traffic routes?"
[07/01/11] Glencora Borradaile: ah yes, that's true ... why didn't I think of that? That was the price of anarchy example too ... so much for being funny
[07/01/11] Claire Mathieu: and complexity of Nash equilibrium, A=equilibrium, B=computational complexity, A+B=computing equilibrium
[07/01/11] Glencora Borradaile: i've been grant writing and there are some problems which I would like to know the answer to, and would even like to work on, but can't list them because I don't have the background for it
[07/01/11] Claire Mathieu: I had my first grant proposal summarily rejected because I didn't know a basic bibliographical reference. I think it reflects very poorly on the applicant when she does not have the background and it shows. I would say that you need to have already one paper in an area before you can apply for a grant with a good chance of being funded (but what do I know)
[07/01/11] Glencora Borradaile: I had a confidence boost when myself and a colleague here at OSU got a grant from Google to work on a theoretical problem that I modelled (with my colleague's expert input). So, I guess that external motivation was nice.
[07/01/11] Claire Mathieu: Yes. What was your problem funded by google?
[07/01/11] Glencora Borradaile: The modelled version is a 2D analogue of string edit distance. It models the problem of comparing two spreadsheets. We have an unanalyzed algorithm that does very well when the two spreadsheets (arrays) have a common parent.
[07/01/11] Claire Mathieu: you want a fast algorithm? Good data structure? Average case analysis on some input model?
[07/01/11] Glencora Borradaile: Aiming for correct with high probability. Using a planted model.
[07/01/11] Claire Mathieu: I see. Nice. You might need some probability for that, though.
[07/01/11] Glencora Borradaile: Um. Yes.
[07/01/11] Claire Mathieu: And on work funded by google, you can't come to the MSR Theory group to leverage their expertise!!
[07/01/11] Glencora Borradaile: Maybe that's true.
[07/01/11] Claire Mathieu: Are you excited about it? It sounds like it might fit my description of a "good" problem.
[07/01/11] Glencora Borradaile: I am. I had an REU implement it last summer and it was great seeing this algorithmic idea exceed expectations. And beating the software engineer's solution (more external feedback ... I'm such a liar!). She (the REU) is back with me as an M.Sc. student. We have some theoretical explanations of simple cases ...
[07/01/11] Claire Mathieu: Sounds great. Now all you need is some nice mathematical structure
[07/01/11] Glencora Borradaile: It's a definite case of trying to design an algorithm with a view to an analysis.
[07/01/11] Claire Mathieu: But you already implemented it before knowing how to analyze it
[07/01/11] Glencora Borradaile: Yes. That's true. Well, *I* did not implement it. But, had it performed terribly, it would have saved me a lot of time.
[07/01/11] Claire Mathieu: "You" includes your students, Professor Borradaile. (Your undergrads, at least)
[07/01/11] Glencora Borradaile: Heh. The royal "you".
[07/01/11] Claire Mathieu: Ok. How about wrapping it up? I have that SODA submission to prepare...
[07/01/11] Glencora Borradaile: Likewise.
[07/01/11] Claire Mathieu: ok. Bye!
[07/01/11] Glencora Borradaile: Enjoy the long weekend. Bye!

UPDATE

Valerie King couldn't participate in our last discussion because she was in Europe, but sent her part of it afterwards. Here it is.

Hi Claire and Cora

I liked Karp's comment about always making positive progress. It's really saying keep a positive perspective. Little obervations can be useful. Hamming says: Plant acorns. I like to go for big problems that don't require a lot of background, because I like the stimulation of trying to come up with a completely new approach but I'm lazy. I like the spreadsheet problem, but it seems fundamentally different from string edit distance since there usually is a well understood structure in a spreadsheet. Or it's string edit distance where a structure is understood on the strings. I've seen some stuff like that. Software engineers look at program evolution and reengineering,trying to determine a common ancestor., especially in my CS dept (Hausi Muller, Margaret Storey). And I love working with people. When it reaches the point when you're together in this space creating something--very in tune with each other's thoughts. Last time I experienced this was a year ago, and it doesn't come frequently enough for me. And then I actually enjoy presenting the work, finding the right words and pictures to convey this new thing..

But every now and then I wonder why anyone is doing this. Whether the work is valuable at all. How one can stay focussed on a problem like the Dynamic Optimality Conjecture for decades without getting bored or losing faith in its importance.