The theme of the afternoon: FPT-type algorithms.
Daniel Marx gave a survey talk on FPT and approximation algorithms. Very interesting for me, because it is very close to my research area even though I have not been following what was happening. There are lots of results coming out, and some of them seem quite clever. Most of the results he mentioned were for optimization problems on graphs. Unfortunately there were almost no proofs, but the ingredients, according to his keywords, seems quite close to techniques for approximation schemes.
Why are FPT results interesting? One reason: because they seem to give some insight into the structure of those basic problems; at least, that's my impression, although, without an actual detailed proof, it's kind of hard to tell. Another reason: because they can conceivably lead to actual implementations. But Daniel was kind of vague about that; it's not the direction in which his personal interests are taking him, and I am maybe with the wrong crowd this week to get a good answer to that question. (One might also wonder: why do I, a pure theoretician, care?) Certainly, the area seems to be taking off these days.
Klaus Jansen and Ildi Schlotter both talked about the most famous bin packing/cutting stock problem: is there an approximation algorithm with additive approximation +1? Klaus talked about the special case where there are only a constant number k of distinct item sizes, and Ildi talked about the special case where there are only a constant number k of bins available, and their runtimes were of the form f(k)*poly(input size), where the polynomial was independent of k: in that sense, their algorithms were FPT-type. Because of the famous open problem driving research in that area, I did not need further motivation, so I was pretty interested in those results. After that I had had enough and skipped the last talk of the day.
Monday, February 28, 2011
How not to do research
(1) Fix a deadline (say, 3pm).
(2) Wait until time gets short (say, 2pm)
(3) Make a plan to get to your goal (say, a chapel on a hill with a view)
(4) Get going according to your plan (say, on a bike)
(5) Keep going even though you are suspecting you may have missed your goal, just because continuing on the uphill road, even though it's work, require less thought than getting out your map and reconsidering your plan in more detail.
(6) Once you run out of time, you are eventually forced to stop and wonder whether you were just being stubborn. With the additional knowledge you gained along the way, it is immediately apparent that you went the wrong way a long time ago - and that, had you stopped much earlier, things would already have been clear and you would have saved yourself a lot of pointless effort. Moreover you now have a much better idea of what the right way is.
(7) By that time it is too late to go there in time, so you just give up altogether.
(2) Wait until time gets short (say, 2pm)
(3) Make a plan to get to your goal (say, a chapel on a hill with a view)
(4) Get going according to your plan (say, on a bike)
(5) Keep going even though you are suspecting you may have missed your goal, just because continuing on the uphill road, even though it's work, require less thought than getting out your map and reconsidering your plan in more detail.
(6) Once you run out of time, you are eventually forced to stop and wonder whether you were just being stubborn. With the additional knowledge you gained along the way, it is immediately apparent that you went the wrong way a long time ago - and that, had you stopped much earlier, things would already have been clear and you would have saved yourself a lot of pointless effort. Moreover you now have a much better idea of what the right way is.
(7) By that time it is too late to go there in time, so you just give up altogether.
Dagstuhl - Monday morning
I'm attending a Dagstuhl workshop on scheduling etc. This morning we had three talks. The main theme seemed to be defining new scheduling problems.
Kirk Pruhs talked about green computing. To conserve energy, current architectures have heterogeneous processors, so scheduling with related machines are problems of current interest. Speed-scaling is also of interest. The problems sucessfully studied in that realm seem to have mostly straighforward algorithmic solutions, and the theoretically interesting part is in the analysis rather than in the design. The main open question currently is to define "good" problems.
Samir Khuller talked about busy times minimization. Busy times are times when at least one processor is active. Thus one tries to schedule jobs simultaneously as much as possible, given various traditional scheduling constraints.
Tami Tamir talked about bullying. Replace the usual notion of precedence constraint (job j can only start once job i has finished) by "bullying" precedence constraints (job j can only start once job i has started), and study various traditional scheduling problems when one adds this new type of constraints.
Maybe I'm blase, but so far I have not seen a problem that I'd like to work on or a result whose proof I' am curious to understand in depth. It would be nice if the speakers could formally define a nice, compelling open problem, even if that problem is beyond our reach at present. What is driving the field? Is there an open problem whose answer would be a breakthrough, and why? That'll be my question for our session on the future of scheduling.
Kirk Pruhs talked about green computing. To conserve energy, current architectures have heterogeneous processors, so scheduling with related machines are problems of current interest. Speed-scaling is also of interest. The problems sucessfully studied in that realm seem to have mostly straighforward algorithmic solutions, and the theoretically interesting part is in the analysis rather than in the design. The main open question currently is to define "good" problems.
Samir Khuller talked about busy times minimization. Busy times are times when at least one processor is active. Thus one tries to schedule jobs simultaneously as much as possible, given various traditional scheduling constraints.
Tami Tamir talked about bullying. Replace the usual notion of precedence constraint (job j can only start once job i has finished) by "bullying" precedence constraints (job j can only start once job i has started), and study various traditional scheduling problems when one adds this new type of constraints.
Maybe I'm blase, but so far I have not seen a problem that I'd like to work on or a result whose proof I' am curious to understand in depth. It would be nice if the speakers could formally define a nice, compelling open problem, even if that problem is beyond our reach at present. What is driving the field? Is there an open problem whose answer would be a breakthrough, and why? That'll be my question for our session on the future of scheduling.
Sunday, February 27, 2011
Life as a professor
Occasionally a student asks me diffidently: "So, when you are not in the classroom teaching... what exactly do you do? I understand that class preparation takes a lot of time. Do you also do, like, research?"
Here is a list of the kind of things I do (or feel guilty about not doing) at work.
Preparing lectures, giving lectures, writing lecture notes, holding office hours.
Meeting TAs, preparing (or helping to prepare) assignments, grading (or helping to grade) assignments.
Advising undergraduates.
Attending faculty meetings, doing department committee work and university committee work.
Organizing workshops and conferences.
Journal editor work, Conference program committee work.
Reviewing conference submissions.
Reviewing journal submissions.
Writing recommendation letters at various levels.
Applying for grants, writing grant reports.
Preparing talks, giving talks, traveling to give talks.
Attending seminars, workshops, conferences; traveling there.
Reading paper, just for the sake of learning.
Meeting with students and research collaborators to do research together.
Writing conference papers.
Writing and revising journal papers.
Reading, processing, sorting email.
That is more than full time, so some things end up not getting done. For example, I almost never read a paper just for the sake of learning.
My favorite activities by far: meeting other people to discuss research, and lecturing. Because those activities form the core of this profession, it is my impression that it is a good profession for me. However it also requires managerial skills that I just do not possess, and that tends to spoil my life.
Here is a list of the kind of things I do (or feel guilty about not doing) at work.
Preparing lectures, giving lectures, writing lecture notes, holding office hours.
Meeting TAs, preparing (or helping to prepare) assignments, grading (or helping to grade) assignments.
Advising undergraduates.
Attending faculty meetings, doing department committee work and university committee work.
Organizing workshops and conferences.
Journal editor work, Conference program committee work.
Reviewing conference submissions.
Reviewing journal submissions.
Writing recommendation letters at various levels.
Applying for grants, writing grant reports.
Preparing talks, giving talks, traveling to give talks.
Attending seminars, workshops, conferences; traveling there.
Reading paper, just for the sake of learning.
Meeting with students and research collaborators to do research together.
Writing conference papers.
Writing and revising journal papers.
Reading, processing, sorting email.
That is more than full time, so some things end up not getting done. For example, I almost never read a paper just for the sake of learning.
My favorite activities by far: meeting other people to discuss research, and lecturing. Because those activities form the core of this profession, it is my impression that it is a good profession for me. However it also requires managerial skills that I just do not possess, and that tends to spoil my life.
Thursday, February 17, 2011
More raving about tablets
I find myself using the tablet more and more.
I have started using it as a substitute, not just for a black board, but also for paper. When I meet with students in my office, we write on the tablet. Here are some immediate advantages:
- from one meeting to the next, I can recover my notes from the previous meeting. It saves us from having to write notes or finding my loose sheets from the previous meeting. It's a good antidote to my lack or organization. Some people have a different notebook for each research project: the tablet is the digital equivalent
- pens of all colors are readily available (whereas, when I use pen and paper, I seldom have more than a few colors at my disposal)
- ability to send my collaborators the current file at any time
- as we discuss problems, often we want to change the order of the argument. When you say "oh, we should have defined x before doing this operation", on paper it requires an ugly margin addition; when these modifications accumulate, it becomes unreadable. Whereas, on the tablet, it's easy to move things around or to create an extra page. At the same time, it does not distract me from thinking about the problem we're discussing (in the way a standard editor would).
I am currently working on a paper and it seems to help organize our thoughts and our writing. Often the arguments of a proof come in the wrong order, or are mixed up, perhaps with algorithm and analysis discussed all together, or defining an object and proving things about it simultaneously (as happens when one is developping ideas), and then one needs to separate them cleanly for a rigorous and clearer writing. On a tablet that can be done by moving objects with the stylus.
The other day my son had a question about his Math homework, and I got out the tablet to explain it to him!
The only advantage of pen and paper over the tablet are the physical constraints: using a tablet requires having a tablet. It's heavy, it diffuses heat, and it needs to be plugged in after a short time.
I read that many are dubious about the stylus and do not consider it a good invention, but, in my view, using a finger instead of a stylus is like using fingerpaint instead of a paintbrush.
I have started using it as a substitute, not just for a black board, but also for paper. When I meet with students in my office, we write on the tablet. Here are some immediate advantages:
- from one meeting to the next, I can recover my notes from the previous meeting. It saves us from having to write notes or finding my loose sheets from the previous meeting. It's a good antidote to my lack or organization. Some people have a different notebook for each research project: the tablet is the digital equivalent
- pens of all colors are readily available (whereas, when I use pen and paper, I seldom have more than a few colors at my disposal)
- ability to send my collaborators the current file at any time
- as we discuss problems, often we want to change the order of the argument. When you say "oh, we should have defined x before doing this operation", on paper it requires an ugly margin addition; when these modifications accumulate, it becomes unreadable. Whereas, on the tablet, it's easy to move things around or to create an extra page. At the same time, it does not distract me from thinking about the problem we're discussing (in the way a standard editor would).
I am currently working on a paper and it seems to help organize our thoughts and our writing. Often the arguments of a proof come in the wrong order, or are mixed up, perhaps with algorithm and analysis discussed all together, or defining an object and proving things about it simultaneously (as happens when one is developping ideas), and then one needs to separate them cleanly for a rigorous and clearer writing. On a tablet that can be done by moving objects with the stylus.
The other day my son had a question about his Math homework, and I got out the tablet to explain it to him!
The only advantage of pen and paper over the tablet are the physical constraints: using a tablet requires having a tablet. It's heavy, it diffuses heat, and it needs to be plugged in after a short time.
I read that many are dubious about the stylus and do not consider it a good invention, but, in my view, using a finger instead of a stylus is like using fingerpaint instead of a paintbrush.
Tuesday, February 15, 2011
Glimpse of another life
Overheard today on the bus: "I'm not going there alone. I get scared when I am alone!" - coming from a grown man, in his fifties, chatting with his neighbors.
That caused my brain to go into "Something's not normal" mode. I took another look at him and at his two neighbors. I noticed similar jackets and similar hats. I then imagined that they might be special needs adults living in a group home. Pure, hasty speculation - but why else would a grown man say that he gets scared? Since my stop was coming up, there was no time for me to figure things out, so I don't know.
Had it been a child or a woman, I would not have noticed. But for a man, in our society that kind of language is taboo in public.
That caused my brain to go into "Something's not normal" mode. I took another look at him and at his two neighbors. I noticed similar jackets and similar hats. I then imagined that they might be special needs adults living in a group home. Pure, hasty speculation - but why else would a grown man say that he gets scared? Since my stop was coming up, there was no time for me to figure things out, so I don't know.
Had it been a child or a woman, I would not have noticed. But for a man, in our society that kind of language is taboo in public.
Monday, February 14, 2011
What happens when I have an idea for a proof
"Then, as he rode along, he composed a sonnet, fitting to his case, the strength and rhythm of which seemed to him, as he sat on his horseback, to be almost perfect. Unfortunately, when he was back at Clavering, and sat in his room with the pen in his hand, the turn of the words escaped him."
Trollope's words would just as well describe what happens to me after I have had an idea in a setting where there is no pen handy.
Trollope's words would just as well describe what happens to me after I have had an idea in a setting where there is no pen handy.
Glimpse of another life
"And he said to me: "Don't give me soup! I just got out of jail!""
(Overheard on the bus this morning)
(Overheard on the bus this morning)
Friday, February 11, 2011
Best memories of being on a program committee
The first program committee on which I served was SODA in the last 1990s. It was eye-opening for me. Never before had I heard frank discussions about what made some research questions "good" and others not so good. Never before had I heard in-depth discussions on what made a result worthwhile. It was a great education.
Previously, it was always a mystery to me how one would pick a problem to work on, and my choices were impulsive and not reasoned out. My criteria used to be: "Is it fun? Do I feel like working on it? And [after working on it a while:] Am I getting anywhere?" Afterwards, I could assess possible research directions in a much more systematic way.
In addition I also learned that many of those questions are discussed by mulling over the introduction of the submissions, and that helped me organize my writing and figure out what to put in the introductions of my subsequent papers.
For people who went to graduate school at a place where there is a tradition of forming PhD students in those matters, being on a program committee might not be such a big deal, but for me, it was a great experience that affected my research methodology.
Previously, it was always a mystery to me how one would pick a problem to work on, and my choices were impulsive and not reasoned out. My criteria used to be: "Is it fun? Do I feel like working on it? And [after working on it a while:] Am I getting anywhere?" Afterwards, I could assess possible research directions in a much more systematic way.
In addition I also learned that many of those questions are discussed by mulling over the introduction of the submissions, and that helped me organize my writing and figure out what to put in the introductions of my subsequent papers.
For people who went to graduate school at a place where there is a tradition of forming PhD students in those matters, being on a program committee might not be such a big deal, but for me, it was a great experience that affected my research methodology.
Friday, February 4, 2011
Soft-spoken?
I have learned indirectly that some students find that I am soft-spoken in class, so they have trouble hearing me.
A long time ago, I was a really loud teacher. Then I took a few voice lessons, became protective of my vocal chords, and dropped a good number of decibels. Not enough voice practice to learn to project my voice far while keeping it nice and relaxed, unfortunately.
I also like to believe that a relaxed voice sets the tone for a more relaxed classroom atmosphere, where people are less nervous about asking questions. Whether that's true or not, I have no idea. (Has it been studied, even?)
So, what to do about this?
I suppose that a microphone could be the answer, although I am not sure what effect it has on class dynamics. It might become more like a show and less like a group endeavour.
A long time ago, I was a really loud teacher. Then I took a few voice lessons, became protective of my vocal chords, and dropped a good number of decibels. Not enough voice practice to learn to project my voice far while keeping it nice and relaxed, unfortunately.
I also like to believe that a relaxed voice sets the tone for a more relaxed classroom atmosphere, where people are less nervous about asking questions. Whether that's true or not, I have no idea. (Has it been studied, even?)
So, what to do about this?
I suppose that a microphone could be the answer, although I am not sure what effect it has on class dynamics. It might become more like a show and less like a group endeavour.
Thursday, February 3, 2011
Combinatorial enumeration in society
In casual conversation, it is normal to automatically pick up small clues to figure out people's relationship to one another. A glance of mutual understanding, a disparaging remark often suffice to identify couples. How much information is needed to figure out who is paired with whom?
In a group of six people, three men and three women, it usually doesn't take long to figure it out. Indeed, there are only 3.2.1=6 possibilities. But recently, conversing with a group of gay men, I was surprised to find that I couldn't do inferences as usual. Why not? It's simply a matter of combinatorial enumeration: with six men there are 5.3.1=15 possibilities instead of 6.
In general, assuming perfect matchings, with k men and k women there are k(k-1)(k-2)... 1 possibilities. With 2k gay men, there are (2k-1)(2k-3)...3.1 possibilities.
In a group of six people, three men and three women, it usually doesn't take long to figure it out. Indeed, there are only 3.2.1=6 possibilities. But recently, conversing with a group of gay men, I was surprised to find that I couldn't do inferences as usual. Why not? It's simply a matter of combinatorial enumeration: with six men there are 5.3.1=15 possibilities instead of 6.
In general, assuming perfect matchings, with k men and k women there are k(k-1)(k-2)... 1 possibilities. With 2k gay men, there are (2k-1)(2k-3)...3.1 possibilities.
Wednesday, February 2, 2011
How program committees shape the field
Today I got a STOC submission rejected. It's a technical result on which I (along with my coauthors) spent many months to build a fragile construction of techniques that had to be tweaked to fit together in just the right way. I had been working on it off and on since 2007, if not earlier. From a purely technical viewpoint, it may be my most intricate paper ever. So, what to make of this rejection?
Maybe they didn't like the paper because of all of its technicalities. In which case, in order to get papers accepted in the future, I should stick to less complicated projects.
Maybe they couldn't follow the arguments. In which case, in order to get papers accepted in the future, I should stick to less complicated projects.
Maybe they didn't appreciate the difficulties and thought it was poorly written. In which case, in order to get papers accepted in the future, I should stick to less complicated projects.
Maybe they didn't care for the result. In which case perhaps my time was not well invested - huge amounts of time spent solving a problem that people apparently don't care about. In which case, in order to get papers accepted in the future, I should stick to projects with a more immediate appeal.
Maybe the paper really was poorly written. Yet we spent months just on the writing, which was almost beyond us. Am I up to spending another couple of months on this proof to try and see if it can be streamlined? I don't think so. In which case, in order to get papers accepted in the future, I should stick to less complicated projects, where I master the big picture.
Maybe they were not impressed. I only imagine it's difficult because my brain doesn't work as fast as it used to when I was a student, but, actually, that result is not that hard. Hmm... I don't like that idea. I will need more evidence before I'm ready to entertain that possibility!
I had been planning to devote a good part of my time working on follow-up projects, digging deeper in even more technical developments. Maybe I should reconsider.
Or maybe I don't care. After all, what's tenure good for, if not to pursue our research interests even when the wind of fashion (or the majority's taste) blows in a different direction?
But maybe - gasp - a reviewer found a mistake in the proof! Since that proof is a bit too big to fit in the cache in my brain, I was only able to check it one part at a time, so an error is a real possibility. That's a worrisome thought... what if the result of our efforts fell apart?
Then, there is also the problem of advising students: maybe this rejection suggests that this research direction is not a good one to steer them towards, because it's high-effort, low-reward, and would not be good for their future job applications. That's another concern.
And that is how program committees shape the field.
Maybe they didn't like the paper because of all of its technicalities. In which case, in order to get papers accepted in the future, I should stick to less complicated projects.
Maybe they couldn't follow the arguments. In which case, in order to get papers accepted in the future, I should stick to less complicated projects.
Maybe they didn't appreciate the difficulties and thought it was poorly written. In which case, in order to get papers accepted in the future, I should stick to less complicated projects.
Maybe they didn't care for the result. In which case perhaps my time was not well invested - huge amounts of time spent solving a problem that people apparently don't care about. In which case, in order to get papers accepted in the future, I should stick to projects with a more immediate appeal.
Maybe the paper really was poorly written. Yet we spent months just on the writing, which was almost beyond us. Am I up to spending another couple of months on this proof to try and see if it can be streamlined? I don't think so. In which case, in order to get papers accepted in the future, I should stick to less complicated projects, where I master the big picture.
Maybe they were not impressed. I only imagine it's difficult because my brain doesn't work as fast as it used to when I was a student, but, actually, that result is not that hard. Hmm... I don't like that idea. I will need more evidence before I'm ready to entertain that possibility!
I had been planning to devote a good part of my time working on follow-up projects, digging deeper in even more technical developments. Maybe I should reconsider.
Or maybe I don't care. After all, what's tenure good for, if not to pursue our research interests even when the wind of fashion (or the majority's taste) blows in a different direction?
But maybe - gasp - a reviewer found a mistake in the proof! Since that proof is a bit too big to fit in the cache in my brain, I was only able to check it one part at a time, so an error is a real possibility. That's a worrisome thought... what if the result of our efforts fell apart?
Then, there is also the problem of advising students: maybe this rejection suggests that this research direction is not a good one to steer them towards, because it's high-effort, low-reward, and would not be good for their future job applications. That's another concern.
And that is how program committees shape the field.
Subscribe to:
Posts (Atom)