As I am revising the draft of a paper, I am going over a section entitled "Terminology". Like many sections entitled "Basic definitions and notations" that I have written or read in the past, it is boring and seems pointless - until at some point in the paper you suddenly encounter an uncertainty about a precise definition, whose subtler details, heretofore unnoticed, could invalidate correctness, and you suddenly rush back to the definition to check that the details are consistent with your understanding.
The terminology section is like vegetables: a dreary but necessary part of the meal. Is there any way to put a little spice into it, I wonder?
Thursday, June 30, 2011
Visiting Microsoft Research
I am visiting the Theory group at Microsoft Research in Redmond, and this week it has shifted to summer mode: a plethora of visitors at all levels of seniority, talks and research discussions in every corner of our section of the building, and plans for a group weekend hike in the Alpine Lakes Wilderness area. It is a little bit like the French Riviera: quiet in the winter, overflowing with visitors in the summer. The only difference is that the visitors are not here to meet movie celebrities but to work with one another.
The research group is headed by Yuval Peres, formerly of Berkeley and the Hebrew university, and spans a diverse mix of areas: theoretical computer science, theoretical physics, probability and combinatorics, algorithmic game theory. The common theme is what gave the group its name, and collaborations developed there have spurred some of the nicest papers at the intersection of those areas.
The absence of Oded Schramm, virtual Fields medalist (meaning that everyone knew that he would have been awarded a Fields medal if he had not been over 40 years old, and that he would not have been over 40 years old if he had not been Israeli and obligated to spend a few years of his youth doing military service), still leaves a big gap. He died in a mountain accident on Labor day a couple of years ago. Now there is no one to solve people's hard problems with quite the same ease, nor to lead us to ping-pong or fussball after lunch. It's funny how quiet he was in life, yet what a big shadow he leaves.
The research group is headed by Yuval Peres, formerly of Berkeley and the Hebrew university, and spans a diverse mix of areas: theoretical computer science, theoretical physics, probability and combinatorics, algorithmic game theory. The common theme is what gave the group its name, and collaborations developed there have spurred some of the nicest papers at the intersection of those areas.
The absence of Oded Schramm, virtual Fields medalist (meaning that everyone knew that he would have been awarded a Fields medal if he had not been over 40 years old, and that he would not have been over 40 years old if he had not been Israeli and obligated to spend a few years of his youth doing military service), still leaves a big gap. He died in a mountain accident on Labor day a couple of years ago. Now there is no one to solve people's hard problems with quite the same ease, nor to lead us to ping-pong or fussball after lunch. It's funny how quiet he was in life, yet what a big shadow he leaves.
Wednesday, June 29, 2011
Sandpiles
Sandpiles. Just the name suggests recreational science. The science in question is a mix of combinatorics and probability. I believe that the model came from statistical physics, although that does not necessarily mean much in terms of relevance to reality, although I am not sure I know what "reality" means anyway. No matter. What matters is that it's supersimple to define - even your kindergarten child could understand it - and yet it leads to strikingly beautiful, complex pictures that look like infinitely elaborate mosaics in mosques.
There is a board game called "chaos" that's based on sandpiles. The board is a grid, two players each have n grains of sand, they take turns placing a grain on the board, making little piles with the grains, and whenever a pile reaches height 4, it topples: each of the 4 grains gets moved to one of the 4 neighbors (in a predetermined order, in the case of the board game). Repeat toppling as needed. Any grain that falls off the board gets returned to its owner, and the winner is the player who first gets rid of all of their grains. That's the board game. Level: 8 years old and up.
In reality (by which I now mean, in the mathematical model), the grid is infinite, we start with n grains at the origin, keep toppling, and look at the final configuration as n goes to infinity, where every vertex holds a pile of grains of height 0,1, 2 or 3. The challenge is to analyze the convergence rate and the final configuration. Level: Math PhD and up.
Programming this might be a good first project: straightforward to implement, yet gives pretty pictures.
There is a board game called "chaos" that's based on sandpiles. The board is a grid, two players each have n grains of sand, they take turns placing a grain on the board, making little piles with the grains, and whenever a pile reaches height 4, it topples: each of the 4 grains gets moved to one of the 4 neighbors (in a predetermined order, in the case of the board game). Repeat toppling as needed. Any grain that falls off the board gets returned to its owner, and the winner is the player who first gets rid of all of their grains. That's the board game. Level: 8 years old and up.
In reality (by which I now mean, in the mathematical model), the grid is infinite, we start with n grains at the origin, keep toppling, and look at the final configuration as n goes to infinity, where every vertex holds a pile of grains of height 0,1, 2 or 3. The challenge is to analyze the convergence rate and the final configuration. Level: Math PhD and up.
Programming this might be a good first project: straightforward to implement, yet gives pretty pictures.
Tuesday, June 28, 2011
Hotels, and the marginal utility of wealth
I have stayed in three different hotels in the past seven days.
High-end hotel. Unctuous staff. Complimentary wine. Airport music in the lobby and elevator. Lemon-flavored water. High-tech light switches that require a college degree to use. Abstract art. Everything is made to stand out ostentatiously. Elongated shampoo bottle, zig-zaging floor pattern, and a bed big enough to get lost in. A good place to feel dizzy. No ironing board.
Comfortable business hotel ($160 plus tax). Bland in the extreme. Staff blends in with the walls. No colors. Nothing stands out at all. Clean, anonymous, comfortable, it could be situated anywhere in the world. A good place for an out-of-body experience. Ironing board.
Hostel ($17.10 including breakfast). Small bouncy bed. Matter-of-fact staff. Friendly people gathering around the outdoor pool. Room-sharing with a stranger who turns out to be, of all things, an assistant professor of computer science who asked me what I worked on and who, when I mentioned bin packing, said it reminded her of knapsack problems that come up in cryptography!! A good place to make friends. No ironing board.
In my case the marginal utility of money for lodging is negative.
High-end hotel. Unctuous staff. Complimentary wine. Airport music in the lobby and elevator. Lemon-flavored water. High-tech light switches that require a college degree to use. Abstract art. Everything is made to stand out ostentatiously. Elongated shampoo bottle, zig-zaging floor pattern, and a bed big enough to get lost in. A good place to feel dizzy. No ironing board.
Comfortable business hotel ($160 plus tax). Bland in the extreme. Staff blends in with the walls. No colors. Nothing stands out at all. Clean, anonymous, comfortable, it could be situated anywhere in the world. A good place for an out-of-body experience. Ironing board.
Hostel ($17.10 including breakfast). Small bouncy bed. Matter-of-fact staff. Friendly people gathering around the outdoor pool. Room-sharing with a stranger who turns out to be, of all things, an assistant professor of computer science who asked me what I worked on and who, when I mentioned bin packing, said it reminded her of knapsack problems that come up in cryptography!! A good place to make friends. No ironing board.
In my case the marginal utility of money for lodging is negative.
Monday, June 27, 2011
Program committees on the weekend: a question of priorities
Why do program committee meetings often take place during the weekend? Because people have other work commitments during the week, and it is hard to get them all together at the same time.
But what about family commitments? Those don't count. People have some flexibility and can always shift things around, it is assumed.
Why can't people shift things around at work as well? Because some of those are hard constraints.
But at home also, some constraints are hard: of a child is performing on a school play for example, that cannot be moved to another date.
I think that there is an unspoken assumption that gives priority to work over family time.
But what about family commitments? Those don't count. People have some flexibility and can always shift things around, it is assumed.
Why can't people shift things around at work as well? Because some of those are hard constraints.
But at home also, some constraints are hard: of a child is performing on a school play for example, that cannot be moved to another date.
I think that there is an unspoken assumption that gives priority to work over family time.
Sunday, June 26, 2011
Selling your honor for a job
How does one get an academic job in a competitive environment, surrounded by many equally qualified candidates? How can one have an edge, without actually changing one's research folder in any way? The book "Influence" suggests a number of marketing techniques that can presumably be applied to that setting, for example, while attending a conference just prior to hiring season.
One technique is called reciprocation. If someone does us a small favor, we are much more inclined to do them a favor later, even if it is completely out of proportion. So, at that conference, the eager job candidate can do all sorts of small favors for the members of hiring committees in attendance: call the elevator for them and hold the door; give them your umbrella if it's raining out; pay the tip at the restaurant; lend them your laptop, phone, connector, etc. Be on the lookout for small favors, and make sure to refuse to have them repaid to you in any way.
Another technique is called "commitment and consistency". If you can make them say something positive about your research, they will be much more likely later, when they review your folder, to think well of it, because they will want to be consistent with themselves. For example, ask them: "What would you say are my strong points?", or manage to extract some mention of a harmless commitment: say, if you happen to be in town or on campus for some other reason, could you come by at the same time? Or you could tell the person how much you appreciate the attention they pay to all candidates, how they are particularly careful to be fair towards this or that category of applicants to avoid discrimination, or otherwise clothe them with some quality of character that they might accept; then later, for consistency, the will feel obligated to act in that way.
Another technique is "social proof": if someone is unsure how to evaluate a situation or person, they will look at other people's reactions to form their own opinions. You could enroll some other student who could subtly intimate, by their attitude or words, that you are an awesome star. You could have "clappers" in the audience when you give your talk: plant some friends who will clap or ask questions that will make you look good.
Another technique is "liking": you can make yourself likeable by, for example, being good-looking, being taller (wear heels), or trying to be similar to the people you want to suck up to. Dress like them, talk like them, watch them attentively and discover common interests in golf or books or whatever. Discover some connections. Go to their talk, know their work, find connections to your interests.
Another technique is "Authority": get a trusted authority to say good words on your behalf. I'm not sure how that can be done independently of the quality of your research, but maybe someone with more imagination than me can come up with it.
Another technique is "scarcity": convey the impression that you are sought after. You could have a busy schedule. You could have some fellow student mention that the department of x is showing much interest in you. You could say that you have some upcoming informal visit to some prestigious place.
My impression is that those marketing techniques are used very little in academia. Certainly, when I recognize an attempt at one of those, I am disgusted and write off the person doing it. But I can see how the skillful manipulator may be able to use them to have an edge.
One technique is called reciprocation. If someone does us a small favor, we are much more inclined to do them a favor later, even if it is completely out of proportion. So, at that conference, the eager job candidate can do all sorts of small favors for the members of hiring committees in attendance: call the elevator for them and hold the door; give them your umbrella if it's raining out; pay the tip at the restaurant; lend them your laptop, phone, connector, etc. Be on the lookout for small favors, and make sure to refuse to have them repaid to you in any way.
Another technique is called "commitment and consistency". If you can make them say something positive about your research, they will be much more likely later, when they review your folder, to think well of it, because they will want to be consistent with themselves. For example, ask them: "What would you say are my strong points?", or manage to extract some mention of a harmless commitment: say, if you happen to be in town or on campus for some other reason, could you come by at the same time? Or you could tell the person how much you appreciate the attention they pay to all candidates, how they are particularly careful to be fair towards this or that category of applicants to avoid discrimination, or otherwise clothe them with some quality of character that they might accept; then later, for consistency, the will feel obligated to act in that way.
Another technique is "social proof": if someone is unsure how to evaluate a situation or person, they will look at other people's reactions to form their own opinions. You could enroll some other student who could subtly intimate, by their attitude or words, that you are an awesome star. You could have "clappers" in the audience when you give your talk: plant some friends who will clap or ask questions that will make you look good.
Another technique is "liking": you can make yourself likeable by, for example, being good-looking, being taller (wear heels), or trying to be similar to the people you want to suck up to. Dress like them, talk like them, watch them attentively and discover common interests in golf or books or whatever. Discover some connections. Go to their talk, know their work, find connections to your interests.
Another technique is "Authority": get a trusted authority to say good words on your behalf. I'm not sure how that can be done independently of the quality of your research, but maybe someone with more imagination than me can come up with it.
Another technique is "scarcity": convey the impression that you are sought after. You could have a busy schedule. You could have some fellow student mention that the department of x is showing much interest in you. You could say that you have some upcoming informal visit to some prestigious place.
My impression is that those marketing techniques are used very little in academia. Certainly, when I recognize an attempt at one of those, I am disgusted and write off the person doing it. But I can see how the skillful manipulator may be able to use them to have an edge.
Saturday, June 25, 2011
A primal-dual analysis of the Ranking algorithm
The other day I was sitting next to Kamal Jain on a flight, and he told me about a neat primal-dual analysis (due to Nikhil Devanur, Bobby Kleinberg, and him) of the Karp-Vazirani-Vazirani Ranking algorithm for online matching. Since the adwords result also has a primal-dual analysis, this is a step towards unifying the results.
The n vertices on one side of the bipartite graph (indexed by i) are known in advance, the n vertices on the other side (indexed by j) arrive online, and the edges adjacent to j are revealed upon j's arrival.
Here is one way to present the Ranking algorithm: each i picks a random value y(i) independently drawn from the uniform distribution over [0,1]. When j arrives, is at least one of its neighbors is not yet matched, j gets matched to the available neighbor with smallest value y(i). Every time an edge e is added to the matching the corresponding variable x(e) is set to 1 in the standard linear programming formulation for maximum bipartite matching.
Here is how the dual is defined. There is one variable b(i) for each i, which stays at 0 as long as i is not matched, and one variable a(j) for each j, which will be set upon j's arrival. We use a water-level algorithm, so initially every i is filled with water up to level 0, and the level only goes up. When j arrives, consider the available neighbors of j. In a continuous manner, take the ones filled to the lowest level, and raise their water level together (new available neighbors of j may join in along the way if the water level reaches their current water level.) This stops when some i reaches level y(i). At that time, (j is matched to i), we set variable b(i) to (exp(y(i))/(e-1), and variable a(j) to (e-exp(y(i))/(e-1). If j stays unmatched, we set a(j) to 0.
To relate the value of the primal (number of matching edges) to the value of the dual (sum over i of a(i) plus sum over j of a(j)), we consider two cases: if j is not matched, neither the primal nor the dual change values. If j is matched, the primal increases by 1 and the dual increases by (exp(y(i))/(e-1)+(e-exp(y(i))/(e-1), which equals 1/(1-1/e), as desired. This the value of the primal is at least (1-1/e) times the value of the dual.
Obviously, the primal is feasible: it's a matching.
Unfortunately the dual might be unfeasible: the dual constraints, a(j)+b(i)>= 1 for each edge {i,j}, might be violated. The idea is that the dual solution is feasible on average. Then the expected value of the output matching will be at least (1-1/e) times the expected value of the dual, which, by feasibility of the average, is greater than (1-1/e) times OPT.
To prove that the dual is feasible on average, focus on one edge {i,j}, fix the value of y(i') arbitrarily for all i' different from i, and consider the executions of the algorithms as y(i) ranges through all values in [0,1]. In addition, consider an artificial execution in which i is not present, and for that execution, let L denote the water level at which j is matched, if there is such a level; L=1 if j stays unmatched. For that artificial execution, a(j) equals (e-exp(L))/(e-1). Now, put i back into the system and continuously decrease y(i) from 1 to zero. By monotonicity of the Ranking algorithm, a decrease in y(i) cannot decrease a(j), so a(j) will be at least (e-exp(L))/(e-1) in all executions. On the other hand, as soon as y(i) goes below L, edge {i,j} appears in the matching, and by monotonicity, a decrease in y(i) cannot cause vertex i to go from being matched to being unmatched, so b(i)=exp(y(i))/(e-1) for all values of y(i) in [0,L]. Integrating over y(i), we obtain that the value of E(a(j))+E(b(i)) is at least 1, so constraint {i,j} is satisfied. This proves feasibility of the average of the duals.
The n vertices on one side of the bipartite graph (indexed by i) are known in advance, the n vertices on the other side (indexed by j) arrive online, and the edges adjacent to j are revealed upon j's arrival.
Here is one way to present the Ranking algorithm: each i picks a random value y(i) independently drawn from the uniform distribution over [0,1]. When j arrives, is at least one of its neighbors is not yet matched, j gets matched to the available neighbor with smallest value y(i). Every time an edge e is added to the matching the corresponding variable x(e) is set to 1 in the standard linear programming formulation for maximum bipartite matching.
Here is how the dual is defined. There is one variable b(i) for each i, which stays at 0 as long as i is not matched, and one variable a(j) for each j, which will be set upon j's arrival. We use a water-level algorithm, so initially every i is filled with water up to level 0, and the level only goes up. When j arrives, consider the available neighbors of j. In a continuous manner, take the ones filled to the lowest level, and raise their water level together (new available neighbors of j may join in along the way if the water level reaches their current water level.) This stops when some i reaches level y(i). At that time, (j is matched to i), we set variable b(i) to (exp(y(i))/(e-1), and variable a(j) to (e-exp(y(i))/(e-1). If j stays unmatched, we set a(j) to 0.
To relate the value of the primal (number of matching edges) to the value of the dual (sum over i of a(i) plus sum over j of a(j)), we consider two cases: if j is not matched, neither the primal nor the dual change values. If j is matched, the primal increases by 1 and the dual increases by (exp(y(i))/(e-1)+(e-exp(y(i))/(e-1), which equals 1/(1-1/e), as desired. This the value of the primal is at least (1-1/e) times the value of the dual.
Obviously, the primal is feasible: it's a matching.
Unfortunately the dual might be unfeasible: the dual constraints, a(j)+b(i)>= 1 for each edge {i,j}, might be violated. The idea is that the dual solution is feasible on average. Then the expected value of the output matching will be at least (1-1/e) times the expected value of the dual, which, by feasibility of the average, is greater than (1-1/e) times OPT.
To prove that the dual is feasible on average, focus on one edge {i,j}, fix the value of y(i') arbitrarily for all i' different from i, and consider the executions of the algorithms as y(i) ranges through all values in [0,1]. In addition, consider an artificial execution in which i is not present, and for that execution, let L denote the water level at which j is matched, if there is such a level; L=1 if j stays unmatched. For that artificial execution, a(j) equals (e-exp(L))/(e-1). Now, put i back into the system and continuously decrease y(i) from 1 to zero. By monotonicity of the Ranking algorithm, a decrease in y(i) cannot decrease a(j), so a(j) will be at least (e-exp(L))/(e-1) in all executions. On the other hand, as soon as y(i) goes below L, edge {i,j} appears in the matching, and by monotonicity, a decrease in y(i) cannot cause vertex i to go from being matched to being unmatched, so b(i)=exp(y(i))/(e-1) for all values of y(i) in [0,L]. Integrating over y(i), we obtain that the value of E(a(j))+E(b(i)) is at least 1, so constraint {i,j} is satisfied. This proves feasibility of the average of the duals.
Friday, June 24, 2011
Writing a proof is like translating
When you try to translate a text from one language to another, you are often faced with words that have no exact translation. The exact concept does not exist in the receptor language. So you have to make do with an approximate translation, either keeping the nuances that you judge to be more important and reluctantly dropping the others, or writing long, cumbersome sentences that cram in every notion you can think of, at the cost of the entire disappearance of the original elegance of style.
When you try to write a mathematical proof, it's a little bit of the same process. You have an idea in your head, an organized ensemble of mathematical notions, and you try to communicate them with symbols and English words, but what is written can never be exactly what was in your mind, and you have to make compromises. Sometimes you can spend hours, no, days, going back and forth: "I want to say this first. But then, that forces me to make a certain other choice. And then, there are further consequences. Oh well, at this point the changes are extensive and overall I am not sure I gained anything; I lost that other aspect that I really wanted to convey...", and it is really easy to go around in circles.
That's where our training in runtime and tradeoffs between efficiency and approximation ought to come into play! We can use hard constraints on runtime: "I will stop writing and send out what I have on Friday, regardless of how far it is from perfect"; or on quality: "As soon as the proof is written in full detail and hangs together with no gaps, I will put it on arxiv, even if it's unnecessarily cumbersome". Soft constraints are dangerous: "I will stop tinkering with the paper as soon as I see that an extra day of work does not lead to any significant improvements". When co-authors have different standards, it can lead to tensions.
The better written it is, the more readers there will be. In the limit, if it's perfectly well written, which takes infinite time, then everyone will read it.
When you try to write a mathematical proof, it's a little bit of the same process. You have an idea in your head, an organized ensemble of mathematical notions, and you try to communicate them with symbols and English words, but what is written can never be exactly what was in your mind, and you have to make compromises. Sometimes you can spend hours, no, days, going back and forth: "I want to say this first. But then, that forces me to make a certain other choice. And then, there are further consequences. Oh well, at this point the changes are extensive and overall I am not sure I gained anything; I lost that other aspect that I really wanted to convey...", and it is really easy to go around in circles.
That's where our training in runtime and tradeoffs between efficiency and approximation ought to come into play! We can use hard constraints on runtime: "I will stop writing and send out what I have on Friday, regardless of how far it is from perfect"; or on quality: "As soon as the proof is written in full detail and hangs together with no gaps, I will put it on arxiv, even if it's unnecessarily cumbersome". Soft constraints are dangerous: "I will stop tinkering with the paper as soon as I see that an extra day of work does not lead to any significant improvements". When co-authors have different standards, it can lead to tensions.
The better written it is, the more readers there will be. In the limit, if it's perfectly well written, which takes infinite time, then everyone will read it.
Thursday, June 23, 2011
Women, academia, tenure, children, life
Last week Valerie King and I, later joined by Cora Borradaile, had a conversation on skype about women, academic job choices, and tenure. Here is the transcript of our conversation.
[06/17/11] Claire Mathieu: Hi Val! Here's the quote you sent me from the Barnard Commencement speech.
Sheryl Sandberg
Chief operating officer, Facebook
Barnard College
Women almost never make one decision to leave the work force. It doesn't happen that way. They make small little decisions along the way that eventually lead them there. Maybe it's the last year of med school when they say, I'll take a slightly less interesting specialty because I'm going to want more balance one day. Maybe it's the fifth year in a law firm when they say, I'm not even sure I should go for partner, because I know I'm going to want kids eventually.These women don't even have relationships, and already they're finding balance, balance for responsibilities they don't yet have. And from that moment, they start quietly leaning back.
So, my heartfelt message to all of you is, and start thinking about this now, do not leave before you leave. Do not lean back; lean in. Put your foot on that gas pedal and keep it there until the day you have to make a decision, and then make a decision. That's the only way, when that day comes, you'll even have a decision to make.
[06/17/11] Valerie King: When I read the quote, I felt it described to some extent what I had done myself. That is, I thought, I should get a job at a university where I could raise a family and get tenure at the same time, without worrying too much about it. I decided this even before I was marrried!
[06/17/11] Claire Mathieu: Were you worried about not having time for a family if you went to a fiercely competitive place like, say, MIT?
[06/17/11] Valerie King: I don't think I ever had the option to take a prof position at MIT but I did have an offer to go to Brown for example. Way before I did the postdocs and NEC stint.
[06/17/11] Claire Mathieu: Did you really think that a postdoc was a safer choice than Brown?
[06/17/11] Valerie King: I was scared to take a permanent position somehow, being single. I think the family idea was always in the back of my mind.
[06/17/11] Claire Mathieu: It's scary for a man too.
[06/17/11] Valerie King: You mean the idea of settling in one place?
[06/17/11] Claire Mathieu: Yes, especially while still single.
[06/17/11] Valerie King: Hmm, maybe you're right about that. But I do know that I wanted to go to a place where I could be reasonably sure of getting tenure while raising kids. I wonder if that quote actually contains good advice? I mean, when I think about the women who have done well, a lot of them have established themselves at research labs first and then gone straight to tenured jobs.
[06/17/11] Claire Mathieu: You mean, Anna Karlin, Joan Feigenbaum,...?
[06/17/11] Valerie King: Yup, I'm trying to think of examples. Can you imagine someone going to a high pressure place, trying to juggle children and tenure, getting denied tenure, and then having to look, with little kids?? When I had little kids, I would get maybe 4 hours of sleep, get up at 5:00 in the morning, start class preparation. I was a walking zombie, not really able to plan things, or do research much.
[[06/17/11] Claire Mathieu: No, it's very stressful. I was so lucky that in France my job was tenured right away. I never had to face those worries. Also, I could take it easy when my children were very little. I joined CNRS, that had no teaching, in 1990, and stayed until 1997, and my children were born in 1991 and 1994. During those years, if they had a bad night's sleep, for example, I could sleep late in the morning. I taught a little bit every year, just for fun, but not much. My parents helped take care of the children when I traveled to conferences, and I could spend several months each year in the US (taking my children with me) visiting other departments and building research connections. The pay was minimal but it was an ideal position to get started in research, and the stress was inexistent. So that quote doesn't really resonate with me. I never had to make, or even face the possibility of having to make, hard choices between children and career.
[06/17/11] Valerie King: Wow. So if one was to follow the advice given in that quote, one would just go off to a high stress place, and then when and if one had kids, and felt the pressure, one would just try to find another job, I guess.
[06/17/11] Claire Mathieu: That requires a lot of trust that things will work out somehow. Maybe it's ok if there are things that you know you enjoy and are confident that you could always do. Some fallback plan. For example if you know you'd enjoy being a high school teacher, that's a fallback plan if your research career ambitions don't work out. I always knew I liked teaching, and that I could be good at teacher if I put my heart into it, so that was always my plan B...
06/17/11] Valerie King: I see. Go for the high risk position. Then fall back if it's necessary.
[06/17/11] Claire Mathieu: You have a law degree: aren't there other things you would have done if academia didn't work out for you?
[06/17/11] Valerie King: It's hard to know. I certainly didn't think that way. Because law is not that different from academia. If I had stayed so many years away from the law, who would have hired me? And in Canada, being a US lawyer? It's also a competitive occupation.
[06/17/11] Claire Mathieu: I have a friend, an academic, who had some interest in early childhood education and could imagine working in a kindergarten.
[06/17/11] Valerie King: Have you heard of many academics around our age who are considering changing careers?
[06/17/11] Claire Mathieu: Um... you mean, not becoming dean or provost or university president and all that stuff? Maria Klawe. David Dobkin.
[06/17/11] Valerie King: Right. There's the admin route.
[06/17/11] Claire Mathieu: Right. Oh, horror!
[06/17/11] Valerie King: Horror for you?
[06/17/11] Claire Mathieu: (Yes). I have a neighbor, Richard Schwartz, a mathematician, who wrote a book for children that was bestseller on Amazon. Maybe he could switch and become a writer!
[06/17/11] Valerie King: Wow. I have a friend who is considering piecing together an alternate career made up of tutoring, teaching yoga, consulting.
[06/17/11] Claire Mathieu: Why?
[06/17/11] Valerie King: I'm not sure. Too much stress. For me, it would be boredom of doing the same thing (teaching) in the same place with the same people year after year (20! years)
[06/17/11] Claire Mathieu: I admire Jon Kleinberg. The way in which he just moved forward in the direction he was interested in.
[06/17/11] Valerie King: What Kleinberg does though is not necessarily theoretical computer science. To some extent it's sociology
[06/17/11] Claire Mathieu: I agree, it's not necessarily TCS, but does that matter? Jon Kleinberg was not thinking about how other academics would see him, I think. He's just doing what interests him, whatever happens. It's daring. He wasn't advocating about how people ought to do research in this or that: he just does it. His attitude is great.
[06/17/11] Valerie King: I think Les Valiant is the same, and great for the same reason.
[06/17/11] Claire Mathieu: Cora Borradaile is online. Should I invite her to join in?
[06/17/11] Valerie King: Sure, is she interested?
[06/17/11] Glencora Borradaile: Hello?
[06/17/11] Valerie King: Hi Cora!
[06/17/11] Claire Mathieu: Hi Cora, welcome!
[06/17/11] Glencora Borradaile: Hi!
[06/17/11] Claire Mathieu: What's the stress when you have tenure? John Savage told me that if what I do is not satisfying, then I can always find other ways to find fulfillment in academia. For example, I could think about writing a book (technical or broader), or focus on advising first-year undergrads.
[06/17/11] Valerie King: I find that when I'm teaching two courses at the same time, I'm kind of unable to do much extra. I seem to get caught up in the daily grind with teaching, admin etc. maybe since I still have my kids at home. I don't seem to have that much time for changing direction.
[06/17/11] Claire Mathieu: Oh I see. You can teach a different course, or sit on a different committee, or go to a different conference, but that's about the extent of your flexibility. Well, what would you like to do? If you had the time? Professionally, I mean.
06/17/11] Valerie King: I don't know. Maybe get out of the university.
[06/17/11] Glencora Borradaile: When I hear these reasons for women "opting out" or "opting for a less high-profile position", it is almost always linked to kids, but there is something there even if kids aren't in the picture
[06/17/11] Valerie King: I'm reaching the age where the kids will be out of the house, so I'm contemplating what to do next. I suppose I would like to think and work on problems in a broader context. I'd love to be in a think tank.
[06/17/11] Glencora Borradaile: i've started getting involved in Corvallis - that's been really satisfying - to help things happen in the city
[06/17/11] Valerie King: I've thought about getting involved with local planning in Victoria. What are you doing in Corvallis?
[06/17/11] Glencora Borradaile: Mostly it is boring meetings, but there is actually interesting issues and i can't help but think of mathematical solutions.
[06/17/11] Claire Mathieu: Like the stuff Pascal van Hentenryck does, constraint programming in real life?
[06/17/11] Glencora Borradaile: More like route design, Claire. I'm involved in bicycle and pedestrian advocacy. There's room for really changing the structure of the city by putting in bike paths and multi-use paths. If you could drop all the traffic lights and one-way streets, how would you make traffic move? if you have X dollars, what is the best bicycle boulevard you could build? [06/17/11] Claire Mathieu: Perfect for you!
[06/17/11] Glencora Borradaile: Yes! Unfortunately it's not a clean problem - too many rules and land-use issues
[06/17/11] Valerie King: I do think this is related to having children or not. With kids at home, I felt obligated to spend time with them in the evenings. Probably it was not a good idea to do this exclusively. The mother role together with the academic role was fine, totally consuming. I couldn't have imagined doing extra work. Though now I have time. And I did start to do some volunteer work around 6 years ago.
[06/17/11] Glencora Borradaile: So are you talking about replacing the outside-academia work, or replacing the academia work?
[06/17/11] Claire Mathieu: I was thinking academia. You're right, let's stay focused.
[06/17/11] Glencora Borradaile: I might have not absorbed the whole of the earlier conversation - why are you dissatisfied with academia that makes you want to replace it?
[06/17/11] Valerie King: For me, it's because I'm bored with doing it for the past 20 years.
[06/17/11] Claire Mathieu: Me too but I won't say it
[06/17/11] Valerie King: You just did
[06/17/11] Claire Mathieu: No I didn't :)
[06/17/11] Valerie King: Why won't you say it?
[06/17/11] Claire Mathieu: Well, I don't know. I'm not THAT bored. When I start discussing a problem with someone, it's always fun
[06/17/11] Valerie King: So the funny thing is that tenure doesn't change anything that much. People say you're like a trained rat.
[06/17/11] Glencora Borradaile: Dan Spielman told me it's worse when you have tenure
[06/17/11] Valerie King: Really? why?
[06/17/11] Glencora Borradaile: Because of the committee work and added letter writing (and there may have been other things that I don't remember)
[06/17/11] Claire Mathieu: He sounds like a very responsible person
[06/17/11] Valerie King: Oh there's a ton of stuff that fills up your time
[06/17/11] Glencora Borradaile: Heh
[06/17/11] Claire Mathieu: The thing is, if you start slacking, once you have tenure, nothing bad happens to you so it's your choice just how much time you spend on things; besides, if you give all your energy to work, how can they expect more?
[06/17/11] Glencora Borradaile: Maybe Dan can't say no.
[06/17/11] Claire Mathieu: And then he feels obligated to do it
[06/17/11] Valerie King: I think the committee work is really up to the individual. Some people work hard on it, some don't. But I do feel obligated to write letters, help out my students, do some refereeing, etc.
[06/17/11] Claire Mathieu: Writing letters is a big and important chore. Helping students is fun for me. Refereeing... well... maybe I've done enough at this point. Better say no right away than let it drag for months because I'm not really into it, right?
[06/17/11] Valerie King: Do you think we can stop refereeing now, with a clear conscience?
[06/17/11] Glencora Borradaile: Noooo! that would just mean more for the rest of us!
[06/17/11] Claire Mathieu: What do you mean, conscience? If you spend your time doing some other work, it's just replacing work by work. I hope that if we do more of the things we enjoy and less of the things we can't bear any more, our job will be more fun
[06/17/11] Valerie King: Really? But I thought no one wants to do this, so if we don't pitch in, it won't get done
[06/17/11] Valerie King: Maybe I'll stop refereeing
[06/17/11] Glencora Borradaile: i've started counting ... for every paper I submit, I will review 3 papers and feel perfectly happy saying no to any requests after my quota is met
[06/17/11] Valerie King: What about program committees? Do you see any point of being on one of these?
[06/17/11] Claire Mathieu: I used to find that task really interesting: I've past that stage, I think, so I may say no from now on.
[06/17/11] Valerie King: Every year, I agree to 1-3 or so. I don't like it either.
[06/17/11] Claire Mathieu: I mean, why should you do anything? If boredom prevents you from doing your work, shouldn't you re-evaluate? Maybe eliminate the worst chores and emphasize others?
[06/17/11] Valerie King: I don't know where this comes from. A desire to prove myself still?
[06/17/11] Claire Mathieu: Val, I think that that's John Savage's point: you get to define the job. If you don't like it, re-define it.
[06/17/11] Glencora Borradaile: You agree to 1-3 PC's EVERY year, Valerie?
[06/17/11] Valerie King: Yes. You know, in my department, in other areas, people are doing a lot more than this. SODA, FOCS and STOC take a lot of time. Others take half as much or less.
06/17/11] Valerie King: Should we tie it up? I have to make dinner.
[06/17/11] Claire Mathieu: Ok, what do we conclude?
[06/17/11] Valerie King: We conclude that we're not sure about the quote. It seems it's very risky to do what she's proposing in academia.
[06/17/11] Claire Mathieu: Unless you have a plan B.
[06/17/11] Valerie King: And we need to take steps to keep up our interest. Change jobs, change the tasks we do, give up the things we don't like to do.
[06/17/11] Glencora Borradaile: i have a problem with any advice that advocates work before all else - in the absence of the kid question
[06/17/11] Valerie King: I only get creative when the work is really on my mind, at least temporarily. This does interfere with kids though
[06/17/11] Claire Mathieu: Work before all else? Did we advocate that? Even the quote, I think, advocated work before "the potential unknown". not work before something else that would be well-defined.
[06/17/11] Valerie King: Right, Claire.
[06/17/11] Glencora Borradaile: "Put your foot on that gas pedal and keep it there" isn't a healthy phrase for me
[06/17/11] Claire Mathieu: Biker
[06/17/11] Glencora Borradaile: Haha
[06/17/11] Valerie King: It's hard to imagine research done that way. I have to take naps every few hours when I'm really working. But I am pretty one track minded. Maybe it's a question of personality.
[06/17/11] Claire Mathieu: When I'm "really working", the social part of my life, limited as it is, takes a toll. I find find harder and harder to accept, with time. The thrill of understanding a mathematical structure, compared to the steady pleasure of seeing my kids or talking to regular people... the balance is changing. I can imagine stopping to do research at some point if I find something else that I love, even if it's not as much of an intellectual stimulation.
[06/17/11] Glencora Borradaile: Something i've wondered - if you do "lean in" would you even recognize that your life could be different and you want to have kids or join a motorcycle gang or whatever it is? Would you be able to make such a change?
[06/17/11] Claire Mathieu: Huh?
[06/17/11] Valerie King: And I was thinking I would do more research when the kids left. I don't know yet. I was also thinking of doing more sociological type research.
[06/17/11] Valerie King: Better end this.
[06/17/11] Claire Mathieu: Ok. Bye?
[06/17/11] Glencora Borradaile: i have to run (not literally)
[06/17/11] Claire Mathieu: Ok, bye.
[06/17/11] Claire Mathieu: Hi Val! Here's the quote you sent me from the Barnard Commencement speech.
Sheryl Sandberg
Chief operating officer, Facebook
Barnard College
Women almost never make one decision to leave the work force. It doesn't happen that way. They make small little decisions along the way that eventually lead them there. Maybe it's the last year of med school when they say, I'll take a slightly less interesting specialty because I'm going to want more balance one day. Maybe it's the fifth year in a law firm when they say, I'm not even sure I should go for partner, because I know I'm going to want kids eventually.These women don't even have relationships, and already they're finding balance, balance for responsibilities they don't yet have. And from that moment, they start quietly leaning back.
So, my heartfelt message to all of you is, and start thinking about this now, do not leave before you leave. Do not lean back; lean in. Put your foot on that gas pedal and keep it there until the day you have to make a decision, and then make a decision. That's the only way, when that day comes, you'll even have a decision to make.
[06/17/11] Valerie King: When I read the quote, I felt it described to some extent what I had done myself. That is, I thought, I should get a job at a university where I could raise a family and get tenure at the same time, without worrying too much about it. I decided this even before I was marrried!
[06/17/11] Claire Mathieu: Were you worried about not having time for a family if you went to a fiercely competitive place like, say, MIT?
[06/17/11] Valerie King: I don't think I ever had the option to take a prof position at MIT but I did have an offer to go to Brown for example. Way before I did the postdocs and NEC stint.
[06/17/11] Claire Mathieu: Did you really think that a postdoc was a safer choice than Brown?
[06/17/11] Valerie King: I was scared to take a permanent position somehow, being single. I think the family idea was always in the back of my mind.
[06/17/11] Claire Mathieu: It's scary for a man too.
[06/17/11] Valerie King: You mean the idea of settling in one place?
[06/17/11] Claire Mathieu: Yes, especially while still single.
[06/17/11] Valerie King: Hmm, maybe you're right about that. But I do know that I wanted to go to a place where I could be reasonably sure of getting tenure while raising kids. I wonder if that quote actually contains good advice? I mean, when I think about the women who have done well, a lot of them have established themselves at research labs first and then gone straight to tenured jobs.
[06/17/11] Claire Mathieu: You mean, Anna Karlin, Joan Feigenbaum,...?
[06/17/11] Valerie King: Yup, I'm trying to think of examples. Can you imagine someone going to a high pressure place, trying to juggle children and tenure, getting denied tenure, and then having to look, with little kids?? When I had little kids, I would get maybe 4 hours of sleep, get up at 5:00 in the morning, start class preparation. I was a walking zombie, not really able to plan things, or do research much.
[[06/17/11] Claire Mathieu: No, it's very stressful. I was so lucky that in France my job was tenured right away. I never had to face those worries. Also, I could take it easy when my children were very little. I joined CNRS, that had no teaching, in 1990, and stayed until 1997, and my children were born in 1991 and 1994. During those years, if they had a bad night's sleep, for example, I could sleep late in the morning. I taught a little bit every year, just for fun, but not much. My parents helped take care of the children when I traveled to conferences, and I could spend several months each year in the US (taking my children with me) visiting other departments and building research connections. The pay was minimal but it was an ideal position to get started in research, and the stress was inexistent. So that quote doesn't really resonate with me. I never had to make, or even face the possibility of having to make, hard choices between children and career.
[06/17/11] Valerie King: Wow. So if one was to follow the advice given in that quote, one would just go off to a high stress place, and then when and if one had kids, and felt the pressure, one would just try to find another job, I guess.
[06/17/11] Claire Mathieu: That requires a lot of trust that things will work out somehow. Maybe it's ok if there are things that you know you enjoy and are confident that you could always do. Some fallback plan. For example if you know you'd enjoy being a high school teacher, that's a fallback plan if your research career ambitions don't work out. I always knew I liked teaching, and that I could be good at teacher if I put my heart into it, so that was always my plan B...
06/17/11] Valerie King: I see. Go for the high risk position. Then fall back if it's necessary.
[06/17/11] Claire Mathieu: You have a law degree: aren't there other things you would have done if academia didn't work out for you?
[06/17/11] Valerie King: It's hard to know. I certainly didn't think that way. Because law is not that different from academia. If I had stayed so many years away from the law, who would have hired me? And in Canada, being a US lawyer? It's also a competitive occupation.
[06/17/11] Claire Mathieu: I have a friend, an academic, who had some interest in early childhood education and could imagine working in a kindergarten.
[06/17/11] Valerie King: Have you heard of many academics around our age who are considering changing careers?
[06/17/11] Claire Mathieu: Um... you mean, not becoming dean or provost or university president and all that stuff? Maria Klawe. David Dobkin.
[06/17/11] Valerie King: Right. There's the admin route.
[06/17/11] Claire Mathieu: Right. Oh, horror!
[06/17/11] Valerie King: Horror for you?
[06/17/11] Claire Mathieu: (Yes). I have a neighbor, Richard Schwartz, a mathematician, who wrote a book for children that was bestseller on Amazon. Maybe he could switch and become a writer!
[06/17/11] Valerie King: Wow. I have a friend who is considering piecing together an alternate career made up of tutoring, teaching yoga, consulting.
[06/17/11] Claire Mathieu: Why?
[06/17/11] Valerie King: I'm not sure. Too much stress. For me, it would be boredom of doing the same thing (teaching) in the same place with the same people year after year (20! years)
[06/17/11] Claire Mathieu: I admire Jon Kleinberg. The way in which he just moved forward in the direction he was interested in.
[06/17/11] Valerie King: What Kleinberg does though is not necessarily theoretical computer science. To some extent it's sociology
[06/17/11] Claire Mathieu: I agree, it's not necessarily TCS, but does that matter? Jon Kleinberg was not thinking about how other academics would see him, I think. He's just doing what interests him, whatever happens. It's daring. He wasn't advocating about how people ought to do research in this or that: he just does it. His attitude is great.
[06/17/11] Valerie King: I think Les Valiant is the same, and great for the same reason.
[06/17/11] Claire Mathieu: Cora Borradaile is online. Should I invite her to join in?
[06/17/11] Valerie King: Sure, is she interested?
[06/17/11] Glencora Borradaile: Hello?
[06/17/11] Valerie King: Hi Cora!
[06/17/11] Claire Mathieu: Hi Cora, welcome!
[06/17/11] Glencora Borradaile: Hi!
[06/17/11] Claire Mathieu: What's the stress when you have tenure? John Savage told me that if what I do is not satisfying, then I can always find other ways to find fulfillment in academia. For example, I could think about writing a book (technical or broader), or focus on advising first-year undergrads.
[06/17/11] Valerie King: I find that when I'm teaching two courses at the same time, I'm kind of unable to do much extra. I seem to get caught up in the daily grind with teaching, admin etc. maybe since I still have my kids at home. I don't seem to have that much time for changing direction.
[06/17/11] Claire Mathieu: Oh I see. You can teach a different course, or sit on a different committee, or go to a different conference, but that's about the extent of your flexibility. Well, what would you like to do? If you had the time? Professionally, I mean.
06/17/11] Valerie King: I don't know. Maybe get out of the university.
[06/17/11] Glencora Borradaile: When I hear these reasons for women "opting out" or "opting for a less high-profile position", it is almost always linked to kids, but there is something there even if kids aren't in the picture
[06/17/11] Valerie King: I'm reaching the age where the kids will be out of the house, so I'm contemplating what to do next. I suppose I would like to think and work on problems in a broader context. I'd love to be in a think tank.
[06/17/11] Glencora Borradaile: i've started getting involved in Corvallis - that's been really satisfying - to help things happen in the city
[06/17/11] Valerie King: I've thought about getting involved with local planning in Victoria. What are you doing in Corvallis?
[06/17/11] Glencora Borradaile: Mostly it is boring meetings, but there is actually interesting issues and i can't help but think of mathematical solutions.
[06/17/11] Claire Mathieu: Like the stuff Pascal van Hentenryck does, constraint programming in real life?
[06/17/11] Glencora Borradaile: More like route design, Claire. I'm involved in bicycle and pedestrian advocacy. There's room for really changing the structure of the city by putting in bike paths and multi-use paths. If you could drop all the traffic lights and one-way streets, how would you make traffic move? if you have X dollars, what is the best bicycle boulevard you could build? [06/17/11] Claire Mathieu: Perfect for you!
[06/17/11] Glencora Borradaile: Yes! Unfortunately it's not a clean problem - too many rules and land-use issues
[06/17/11] Valerie King: I do think this is related to having children or not. With kids at home, I felt obligated to spend time with them in the evenings. Probably it was not a good idea to do this exclusively. The mother role together with the academic role was fine, totally consuming. I couldn't have imagined doing extra work. Though now I have time. And I did start to do some volunteer work around 6 years ago.
[06/17/11] Glencora Borradaile: So are you talking about replacing the outside-academia work, or replacing the academia work?
[06/17/11] Claire Mathieu: I was thinking academia. You're right, let's stay focused.
[06/17/11] Glencora Borradaile: I might have not absorbed the whole of the earlier conversation - why are you dissatisfied with academia that makes you want to replace it?
[06/17/11] Valerie King: For me, it's because I'm bored with doing it for the past 20 years.
[06/17/11] Claire Mathieu: Me too but I won't say it
[06/17/11] Valerie King: You just did
[06/17/11] Claire Mathieu: No I didn't :)
[06/17/11] Valerie King: Why won't you say it?
[06/17/11] Claire Mathieu: Well, I don't know. I'm not THAT bored. When I start discussing a problem with someone, it's always fun
[06/17/11] Valerie King: So the funny thing is that tenure doesn't change anything that much. People say you're like a trained rat.
[06/17/11] Glencora Borradaile: Dan Spielman told me it's worse when you have tenure
[06/17/11] Valerie King: Really? why?
[06/17/11] Glencora Borradaile: Because of the committee work and added letter writing (and there may have been other things that I don't remember)
[06/17/11] Claire Mathieu: He sounds like a very responsible person
[06/17/11] Valerie King: Oh there's a ton of stuff that fills up your time
[06/17/11] Glencora Borradaile: Heh
[06/17/11] Claire Mathieu: The thing is, if you start slacking, once you have tenure, nothing bad happens to you so it's your choice just how much time you spend on things; besides, if you give all your energy to work, how can they expect more?
[06/17/11] Glencora Borradaile: Maybe Dan can't say no.
[06/17/11] Claire Mathieu: And then he feels obligated to do it
[06/17/11] Valerie King: I think the committee work is really up to the individual. Some people work hard on it, some don't. But I do feel obligated to write letters, help out my students, do some refereeing, etc.
[06/17/11] Claire Mathieu: Writing letters is a big and important chore. Helping students is fun for me. Refereeing... well... maybe I've done enough at this point. Better say no right away than let it drag for months because I'm not really into it, right?
[06/17/11] Valerie King: Do you think we can stop refereeing now, with a clear conscience?
[06/17/11] Glencora Borradaile: Noooo! that would just mean more for the rest of us!
[06/17/11] Claire Mathieu: What do you mean, conscience? If you spend your time doing some other work, it's just replacing work by work. I hope that if we do more of the things we enjoy and less of the things we can't bear any more, our job will be more fun
[06/17/11] Valerie King: Really? But I thought no one wants to do this, so if we don't pitch in, it won't get done
[06/17/11] Valerie King: Maybe I'll stop refereeing
[06/17/11] Glencora Borradaile: i've started counting ... for every paper I submit, I will review 3 papers and feel perfectly happy saying no to any requests after my quota is met
[06/17/11] Valerie King: What about program committees? Do you see any point of being on one of these?
[06/17/11] Claire Mathieu: I used to find that task really interesting: I've past that stage, I think, so I may say no from now on.
[06/17/11] Valerie King: Every year, I agree to 1-3 or so. I don't like it either.
[06/17/11] Claire Mathieu: I mean, why should you do anything? If boredom prevents you from doing your work, shouldn't you re-evaluate? Maybe eliminate the worst chores and emphasize others?
[06/17/11] Valerie King: I don't know where this comes from. A desire to prove myself still?
[06/17/11] Claire Mathieu: Val, I think that that's John Savage's point: you get to define the job. If you don't like it, re-define it.
[06/17/11] Glencora Borradaile: You agree to 1-3 PC's EVERY year, Valerie?
[06/17/11] Valerie King: Yes. You know, in my department, in other areas, people are doing a lot more than this. SODA, FOCS and STOC take a lot of time. Others take half as much or less.
06/17/11] Valerie King: Should we tie it up? I have to make dinner.
[06/17/11] Claire Mathieu: Ok, what do we conclude?
[06/17/11] Valerie King: We conclude that we're not sure about the quote. It seems it's very risky to do what she's proposing in academia.
[06/17/11] Claire Mathieu: Unless you have a plan B.
[06/17/11] Valerie King: And we need to take steps to keep up our interest. Change jobs, change the tasks we do, give up the things we don't like to do.
[06/17/11] Glencora Borradaile: i have a problem with any advice that advocates work before all else - in the absence of the kid question
[06/17/11] Valerie King: I only get creative when the work is really on my mind, at least temporarily. This does interfere with kids though
[06/17/11] Claire Mathieu: Work before all else? Did we advocate that? Even the quote, I think, advocated work before "the potential unknown". not work before something else that would be well-defined.
[06/17/11] Valerie King: Right, Claire.
[06/17/11] Glencora Borradaile: "Put your foot on that gas pedal and keep it there" isn't a healthy phrase for me
[06/17/11] Claire Mathieu: Biker
[06/17/11] Glencora Borradaile: Haha
[06/17/11] Valerie King: It's hard to imagine research done that way. I have to take naps every few hours when I'm really working. But I am pretty one track minded. Maybe it's a question of personality.
[06/17/11] Claire Mathieu: When I'm "really working", the social part of my life, limited as it is, takes a toll. I find find harder and harder to accept, with time. The thrill of understanding a mathematical structure, compared to the steady pleasure of seeing my kids or talking to regular people... the balance is changing. I can imagine stopping to do research at some point if I find something else that I love, even if it's not as much of an intellectual stimulation.
[06/17/11] Glencora Borradaile: Something i've wondered - if you do "lean in" would you even recognize that your life could be different and you want to have kids or join a motorcycle gang or whatever it is? Would you be able to make such a change?
[06/17/11] Claire Mathieu: Huh?
[06/17/11] Valerie King: And I was thinking I would do more research when the kids left. I don't know yet. I was also thinking of doing more sociological type research.
[06/17/11] Valerie King: Better end this.
[06/17/11] Claire Mathieu: Ok. Bye?
[06/17/11] Glencora Borradaile: i have to run (not literally)
[06/17/11] Claire Mathieu: Ok, bye.
Wednesday, June 22, 2011
Marketing a paper: flattery
The book "Influence" by Robert Cialdini, that I read recently, has a short section on flattery, explaining that it is an effective way to get people to buy your product. This has been known forever, of course, but apparently it is effective even when the flattery is blatant.
How to apply that to marketing a paper: we know that the paper will most likely be reviewed by people who have done previous work in the same area. Thus, instead of presenting the results by contrasting them to previous results, with the implied message "Previous work was faulty, my work is much better", the writer should find a style that gives generous credit to previous work. For example, give ample credit to whoever "introduced the problem", "raised the question", "took the first steps", and, for intermediate results, "enhanced our understanding" or "made significant progress". Perhaps that it why we are told to cite the authors by name instead of merely referring to the article by number.
How to apply that to marketing a paper: we know that the paper will most likely be reviewed by people who have done previous work in the same area. Thus, instead of presenting the results by contrasting them to previous results, with the implied message "Previous work was faulty, my work is much better", the writer should find a style that gives generous credit to previous work. For example, give ample credit to whoever "introduced the problem", "raised the question", "took the first steps", and, for intermediate results, "enhanced our understanding" or "made significant progress". Perhaps that it why we are told to cite the authors by name instead of merely referring to the article by number.
Tuesday, June 21, 2011
Better than 3/2 for TSP
I just saw the video of a talk by Mohit Singh presenting the TSP result discussed on the Fortnow-Gasarch blog a few months ago.
The input is the metric given by shortest paths in an undirected unweighted graph. The output is a traveling salesman tour with length less than
OPT*1.4999999999999999999999999999999999999999999999999996.
Ever since my student days, I have heard of this - beating the factor of 1.5 for metric TSP - as a major open problem. I even spent some time working on this as a young graduate student, under Andy Yao's guidance (and with no luck whatsoever), so this is exciting, even if it's restricted to graph metrics.
The plan follows the Christofides algorithm, but finds a particular MST such that the minimum weight matching of odd degree vertices is a better than .5 approximation. The algorithm studies the following two LP relaxations:
First, the Held-Karp LP relaxation of TSP, LP1: minimize the sum of d(u,v)x(u,v), where for every vertex u the sum over v of x(u,v)=2, and for every cut, the sum over cut edges {u,v} of x(u,v) is at least 2. Here x(u,v) is non-negative.
Second, given a spanning tree T, the following LP relaxation to build a minimum weight perfect matching over vertices that have odd degree in T, LP2(T): minimize the sum of d(u,v)y(u,v), where for every cut crossed by an odd number of edges of T, the sum S over cut edges {u,v} of y(u,v) is at least 1. Here y(u,v) is non-negative.
It is known that the minimum spanning tree has value less than OPT(LP1), which is less than the OPT tour. It is known that the minimum weight perfect matching of odd degree vertices has value exactly equal to OPT(LP2(T)). Observe that if x is feasible for LP1, then for every T, y=x/2 is feasible for LP2(T), so OPT(LP2(T)) is at most (1/2)OPT(LP1). This proves the 1.5 bound of Christofides.
Now, here is the first idea: imagine that instead of defining y(u,v) as x(u,v)/2, we defined it as x(u,v)/(2.001). Would this still be feasible for LP2(T)? Yes, if for every cut that contained edge {u,v}, either the sum S was greater than 2.001, or the cut was crossed by an even number of edges of T. If we could find such a minimum spanning tree T, then OPT(LP2(T)) would be less than (1/2.001)LPT(LP1) and we'd have a better-than-1.5 approximation.
Studying OPT(LP1), the authors can show that (except for the special case when the solution of LP1 is near integral, dealt with separately) for a significant number of edges called "good" edges, the number of cuts containing that edge and such that the sum S is less than 2.001 is bounded by a constant c. So all we need is a tree T such that for many of those edges, every one of the c cuts of interest is crossed by an even number of edges.
Unfortunately it is difficult to construct a tree T having such a nice property, so instead, (as in the SODA 2010 paper by Asadpour, Goemans, Madry, Gharan and Saberi) the authors pick a random tree from the following distribution: there exists a unique distribution of trees s.t. for each edge uv, the probability that uv is in the tree is x(u,v), and such that for every tree T, the probability of T is proportional to the product of x(u,v) for each edge uv of T. In fact, that's the weighted uniform distributon defined as follows: scale the x's up so that they're all integers, replace the graph by a multigraph where each edge {u,v} is replaced by x(u,v) identical edges between u and v, then generate a uniform spanning tree of the resulting graph. Consider the random tree T thus obtained.
It only remains to study, for each good edge, the probability that all c cuts of interest are crossed by an even number of edges of T. For each edge {u,v}, the probability that the edge is in T is x(u,v). For each set of k edges, the probability that all of those k edges are in T is known to be given by a certain determinant. A lot is known about weighted uniform spanning trees. The very vague intuition is that if the average number of edges crossing a cut is between 2 and 2.001, since the weighted spanning tree distribution is very roughly similar to picking edges independently at random (except for the tree constraint...), there is a significant probability that the number of edges crossing the cut will be, not 1, not 3, but exactly 2. Since 2 is even, we're in good shape.
It is beautiful how this puts together techniques from the study of linear programs, and recent advances on random trees and discrete probability.
The input is the metric given by shortest paths in an undirected unweighted graph. The output is a traveling salesman tour with length less than
OPT*1.4999999999999999999999999999999999999999999999999996.
Ever since my student days, I have heard of this - beating the factor of 1.5 for metric TSP - as a major open problem. I even spent some time working on this as a young graduate student, under Andy Yao's guidance (and with no luck whatsoever), so this is exciting, even if it's restricted to graph metrics.
The plan follows the Christofides algorithm, but finds a particular MST such that the minimum weight matching of odd degree vertices is a better than .5 approximation. The algorithm studies the following two LP relaxations:
First, the Held-Karp LP relaxation of TSP, LP1: minimize the sum of d(u,v)x(u,v), where for every vertex u the sum over v of x(u,v)=2, and for every cut, the sum over cut edges {u,v} of x(u,v) is at least 2. Here x(u,v) is non-negative.
Second, given a spanning tree T, the following LP relaxation to build a minimum weight perfect matching over vertices that have odd degree in T, LP2(T): minimize the sum of d(u,v)y(u,v), where for every cut crossed by an odd number of edges of T, the sum S over cut edges {u,v} of y(u,v) is at least 1. Here y(u,v) is non-negative.
It is known that the minimum spanning tree has value less than OPT(LP1), which is less than the OPT tour. It is known that the minimum weight perfect matching of odd degree vertices has value exactly equal to OPT(LP2(T)). Observe that if x is feasible for LP1, then for every T, y=x/2 is feasible for LP2(T), so OPT(LP2(T)) is at most (1/2)OPT(LP1). This proves the 1.5 bound of Christofides.
Now, here is the first idea: imagine that instead of defining y(u,v) as x(u,v)/2, we defined it as x(u,v)/(2.001). Would this still be feasible for LP2(T)? Yes, if for every cut that contained edge {u,v}, either the sum S was greater than 2.001, or the cut was crossed by an even number of edges of T. If we could find such a minimum spanning tree T, then OPT(LP2(T)) would be less than (1/2.001)LPT(LP1) and we'd have a better-than-1.5 approximation.
Studying OPT(LP1), the authors can show that (except for the special case when the solution of LP1 is near integral, dealt with separately) for a significant number of edges called "good" edges, the number of cuts containing that edge and such that the sum S is less than 2.001 is bounded by a constant c. So all we need is a tree T such that for many of those edges, every one of the c cuts of interest is crossed by an even number of edges.
Unfortunately it is difficult to construct a tree T having such a nice property, so instead, (as in the SODA 2010 paper by Asadpour, Goemans, Madry, Gharan and Saberi) the authors pick a random tree from the following distribution: there exists a unique distribution of trees s.t. for each edge uv, the probability that uv is in the tree is x(u,v), and such that for every tree T, the probability of T is proportional to the product of x(u,v) for each edge uv of T. In fact, that's the weighted uniform distributon defined as follows: scale the x's up so that they're all integers, replace the graph by a multigraph where each edge {u,v} is replaced by x(u,v) identical edges between u and v, then generate a uniform spanning tree of the resulting graph. Consider the random tree T thus obtained.
It only remains to study, for each good edge, the probability that all c cuts of interest are crossed by an even number of edges of T. For each edge {u,v}, the probability that the edge is in T is x(u,v). For each set of k edges, the probability that all of those k edges are in T is known to be given by a certain determinant. A lot is known about weighted uniform spanning trees. The very vague intuition is that if the average number of edges crossing a cut is between 2 and 2.001, since the weighted spanning tree distribution is very roughly similar to picking edges independently at random (except for the tree constraint...), there is a significant probability that the number of edges crossing the cut will be, not 1, not 3, but exactly 2. Since 2 is even, we're in good shape.
It is beautiful how this puts together techniques from the study of linear programs, and recent advances on random trees and discrete probability.
Monday, June 20, 2011
Dropbox, svn, and self-discipline
Applications such as Dropbox or svn help me work on papers with my coauthors. It allows us to edit our paper in parallel, with frequent (or even automatic and transparent, in the case of Dropbox) updates to the common repositary that ensures continued consistency. In the old days, we used to email our draft back and forth, with message headers such as: "I am taking the token on the paper. Let no one else edit it!" and "I am now releasing the token". Instead, Dropbox saves us the work of coordinating our schedule and jointly planning when each of us is going to edit the paper. It gives us a lot more freedom.
But here is something I noticed the other day. I was editing a draft, went through about three quarters of it, then when I got tired of editing, I stopped and updated the repositary.
In the old days, I would have pushed myself and finished editing before releasing the token.
In the old days, when conference deadlines were approaching, we had to be very organized to synchronize our work so as to be done in time. Now each author can work more or less independently from the others, and the observed effect is that people wait until much closer to the deadline.
In the old days, writing a paper used to happen in waves: we'd write a first draft, then correct it to make a second draft, then go over it once or twice more at most, and then we'd call it good enough for submission. Now there is no sense of "version number i": the draft is updated continuously, and it can never really be said to be finished. Further improvements are always possible.
So in the old days, there were many synchronization constraints that forced us to be organized, or else the cost was high: one small misstep often meant that a whole day was lost. Now things are much more robust: missteps can be corrected instantaneously, so the cost of making mistakes is low, and careful planning is no longer necessary. Instead can almost entirely live in the present. We have enormously more freedom.
What is the result? One result is that I currently have a large number of drafts in various stages of being close to completion. When I am 3/4 done and feel a bit tired, there is no reason not to stop. Moreover, I am reluctant to call a paper "ready for submission", since there is always one more small improvement that is possible and easy to make.
More freedom, unless coupled with more self-discipline, results in decreased efficiency.
But here is something I noticed the other day. I was editing a draft, went through about three quarters of it, then when I got tired of editing, I stopped and updated the repositary.
In the old days, I would have pushed myself and finished editing before releasing the token.
In the old days, when conference deadlines were approaching, we had to be very organized to synchronize our work so as to be done in time. Now each author can work more or less independently from the others, and the observed effect is that people wait until much closer to the deadline.
In the old days, writing a paper used to happen in waves: we'd write a first draft, then correct it to make a second draft, then go over it once or twice more at most, and then we'd call it good enough for submission. Now there is no sense of "version number i": the draft is updated continuously, and it can never really be said to be finished. Further improvements are always possible.
So in the old days, there were many synchronization constraints that forced us to be organized, or else the cost was high: one small misstep often meant that a whole day was lost. Now things are much more robust: missteps can be corrected instantaneously, so the cost of making mistakes is low, and careful planning is no longer necessary. Instead can almost entirely live in the present. We have enormously more freedom.
What is the result? One result is that I currently have a large number of drafts in various stages of being close to completion. When I am 3/4 done and feel a bit tired, there is no reason not to stop. Moreover, I am reluctant to call a paper "ready for submission", since there is always one more small improvement that is possible and easy to make.
More freedom, unless coupled with more self-discipline, results in decreased efficiency.
Sunday, June 19, 2011
On Lecturing: introduction
I just read a document that I think can be interpreted via the lens of teaching. Instead of bits and pieces of observations about teaching, it gives a general framework. Here is the beginning of my attempt to cast it in that light.
Classes are an essential part of the student's education. We need to be effective lecturers. There are three elements coming together: the scientific content (the result or technique that we wish to teach), the teacher, and the students. Effective teaching requires us to know our students, so that we can communicate to them what they are ready to learn. If we are not in touch with our students' current level of understanding, what we say will not be heard. Our students' diverse level is a challenge. Many students have an intuitive understanding of problem-solving, but are unable to articulate it rigorously, and one of our tasks is to provide them with a vocabulary to express their concepts and refine them. When the students are presented with a scientific publication, usually it does not "talk to them". Our role is to be the mediator between the scientific content and the students, interpreting it so that it reaches another level of meaning for them.
Classes are an essential part of the student's education. We need to be effective lecturers. There are three elements coming together: the scientific content (the result or technique that we wish to teach), the teacher, and the students. Effective teaching requires us to know our students, so that we can communicate to them what they are ready to learn. If we are not in touch with our students' current level of understanding, what we say will not be heard. Our students' diverse level is a challenge. Many students have an intuitive understanding of problem-solving, but are unable to articulate it rigorously, and one of our tasks is to provide them with a vocabulary to express their concepts and refine them. When the students are presented with a scientific publication, usually it does not "talk to them". Our role is to be the mediator between the scientific content and the students, interpreting it so that it reaches another level of meaning for them.
Saturday, June 18, 2011
An advanced search
The other day I was looking for the text of the 1940 French-German armistice in the original German language (don't ask). How could I find it without knowing any German? Here is how I did it:
1. I opened google, my default search engine, and entered the keywords "1940 French German armistice original German text". Among the answers, I did not see the German original, but there was an English translation.
2. I used google translate to translate the words "1940 French German armistice original German text" into German.
3. I entered the resulting string of German words back into google search.
4. Among the answers, there was a wikipedia page: I clicked on it.
5. It was in German, so I could not understand a word of it, but it ended with some references, as wikipedia pages usually do, and I clicked on the first reference.
6. What I saw then was the scan of a text in German, with paragraphs labeled 1 through 24. Since I could see, from the English translation, that the armistice text was supposed to have 24 items, I knew I had found what I was looking for.
I am so proud of myself.
Now, the next challenge: a Japanese text?
1. I opened google, my default search engine, and entered the keywords "1940 French German armistice original German text". Among the answers, I did not see the German original, but there was an English translation.
2. I used google translate to translate the words "1940 French German armistice original German text" into German.
3. I entered the resulting string of German words back into google search.
4. Among the answers, there was a wikipedia page: I clicked on it.
5. It was in German, so I could not understand a word of it, but it ended with some references, as wikipedia pages usually do, and I clicked on the first reference.
6. What I saw then was the scan of a text in German, with paragraphs labeled 1 through 24. Since I could see, from the English translation, that the armistice text was supposed to have 24 items, I knew I had found what I was looking for.
I am so proud of myself.
Now, the next challenge: a Japanese text?
Friday, June 17, 2011
Who to kiss when
The other day, here in the US, a man came to my house to be paid for some work he did in my yard. We chatted for a few minutes, then, as he was taking his leave, he unexpectedly kissed me on the cheek.
Later I realized the reason behind his action: he knew that I was French and that the French greet one another by kissing, and he wanted to thus show his knowledge of the world!
What he did not know is that we French women do not kiss our painters, plumbers, electricians, or gardeners, -- unless they happen to also be our friends of course. Otherwise, the proper protocol is to shake hands.
Many Americans, when they are in France, enthusiastically kiss everyone in sight. Not so fast! The boundary between who gets a handshake and who gets a kiss can be subtle. The first time it happens, we make eye contact: one person silently says with their eyes: "I think we have reached the stage in our acquaintance where we can now kiss instead of shaking hands, don't you agree?", and the other person silently assents. When there is any risk of ambiguity, the first person will smile and tentatively ask: "On se fait la bise?", but it would be quite embarrassing if the other person said no, so, if there is any doubt, the safe route is to go for a handshake.
I would say that the people who get a kiss are: family, except perhaps for remote extended family when met for the first time; friends; friends of friends, if they are introduced to us by our friends and if the context is not too formal; acquaintances and colleagues, once a casual friendship starts to develop; and all children. I don't make a difference between blood relatives and other relatives, but some people only kiss the relatives who share some of their genes. I don't kiss my pastor, out of residual respect for some remnant of tradition of authority that he symbolizes, but some people do. The older people are, the more hesitant I am to go for a kiss, and the more I wait for their cue. There are people with whom I go both ways, exchanging either a kiss or a handshake, depending on how formal the context is when we meet. No one I know kisses their garagist, supermarket cashier, or children's schoolteachers. But the boundary is subtle and, I think, very much depends on one's social class.
UPDATE: Here's a simple rule: do not kiss anyone whom you would not befriend on Facebook!
Later I realized the reason behind his action: he knew that I was French and that the French greet one another by kissing, and he wanted to thus show his knowledge of the world!
What he did not know is that we French women do not kiss our painters, plumbers, electricians, or gardeners, -- unless they happen to also be our friends of course. Otherwise, the proper protocol is to shake hands.
Many Americans, when they are in France, enthusiastically kiss everyone in sight. Not so fast! The boundary between who gets a handshake and who gets a kiss can be subtle. The first time it happens, we make eye contact: one person silently says with their eyes: "I think we have reached the stage in our acquaintance where we can now kiss instead of shaking hands, don't you agree?", and the other person silently assents. When there is any risk of ambiguity, the first person will smile and tentatively ask: "On se fait la bise?", but it would be quite embarrassing if the other person said no, so, if there is any doubt, the safe route is to go for a handshake.
I would say that the people who get a kiss are: family, except perhaps for remote extended family when met for the first time; friends; friends of friends, if they are introduced to us by our friends and if the context is not too formal; acquaintances and colleagues, once a casual friendship starts to develop; and all children. I don't make a difference between blood relatives and other relatives, but some people only kiss the relatives who share some of their genes. I don't kiss my pastor, out of residual respect for some remnant of tradition of authority that he symbolizes, but some people do. The older people are, the more hesitant I am to go for a kiss, and the more I wait for their cue. There are people with whom I go both ways, exchanging either a kiss or a handshake, depending on how formal the context is when we meet. No one I know kisses their garagist, supermarket cashier, or children's schoolteachers. But the boundary is subtle and, I think, very much depends on one's social class.
UPDATE: Here's a simple rule: do not kiss anyone whom you would not befriend on Facebook!
Thursday, June 16, 2011
"It talks to you"
The contractor repainting my house told me that, to find potential problems with the house, you look at the siding and "you've got to let it talk to you". You stare at the shingles and "they talk to you": chipped corner, darker stain, soft wood, insect holes, faded colors. They're all symptoms of a variety of problems. You see the problems, put two and two together, and figure out where they come from.
What he described was an approach to problem-solving that can readily be applied to mathematical problems. You look at a series of examples. You stare at them attentively, you let them "talk to you", and the structure of the problem comes through.
What he described was an approach to problem-solving that can readily be applied to mathematical problems. You look at a series of examples. You stare at them attentively, you let them "talk to you", and the structure of the problem comes through.
Wednesday, June 15, 2011
"Is it a good idea to..."
That's how I was starting a query into my search engine with the idea of exploring the pros and cons of students borrowing money to pay for college. I got stopped in my tracks by the automatic completions proposed by the search engine:
-Is it a good idea to microwave an airbag?
-Is it a good idea to lease a car?
-Is it a good idea to join the marines?
-Is it a good idea to get back with your ex?
-Is it a good idea to invest in gold?
Now I can't stop staring at them. Microwave an airbag?!?? These automatic completions of search queries offer amazing snapshots of the public mind.
And here's the big question: what does it all mean? If the first thing an internet user is wondering about is whether to microwave an airbag, is it a sign that this society is bored to death?
UPDATE: I changed my search settings to turn off the automatic completion option. It's fun, but very distracting!
-Is it a good idea to microwave an airbag?
-Is it a good idea to lease a car?
-Is it a good idea to join the marines?
-Is it a good idea to get back with your ex?
-Is it a good idea to invest in gold?
Now I can't stop staring at them. Microwave an airbag?!?? These automatic completions of search queries offer amazing snapshots of the public mind.
And here's the big question: what does it all mean? If the first thing an internet user is wondering about is whether to microwave an airbag, is it a sign that this society is bored to death?
UPDATE: I changed my search settings to turn off the automatic completion option. It's fun, but very distracting!
Tuesday, June 14, 2011
Fighting internet addiction
At my house, we are experimenting with a new rule to fight internet addiction: no internet connection between 10pm and 7am. It is very easy to implement since it's just a matter of switching a button. It has the immediate consequence that we get more sleep. It's a measure of how much we rely on the internet that it has taken some discussion and required an effort of will.
I suppose that that could be embedded in Verizon, Cox, and other internet service providers. They could give us an option to have a subscription that excludes nights and Sundays, for example.
I suppose that that could be embedded in Verizon, Cox, and other internet service providers. They could give us an option to have a subscription that excludes nights and Sundays, for example.
Monday, June 13, 2011
The cost of tuition
This is the cost of tuition at Brown University: nominal, and, in parenthesis, inflation adjusted (2010 dollars)
2011 $41328 (not yet known)
2010 $39928 ($39928)
2009 $38048 ($39469)
2008 $36828 ($37267)
2007 $35584 ($37377)
2006 $33888 ($36592)
2005 $32864 ($36373)
2004 $30672 ($35101)
2003 $29200 ($34520)
2002 $27856 ($33556)
2001 $26568 ($32773)
2000 $25600 ($32084)
1999 $24624 ($31910)
Does this mean that this college has become more money-elitist, restricting admission except to the wealthy?
At the same time financial aid has increased from $34 millions in 2002 ($40 millions inflation adjusted dollars) to $81 millions in 2010, thus basically doubling. Does this mean that this college has become less money-elitist, redistributing more income so as to provide admission to the less wealthy as well?
If we take this to the limit, the tuition could be set at infinity, financial aid could be at near-infinity, and the financial aid office could decide arbitrarily how much each student has to pay out of their own pocket. The main result is that the college has more control over who pays what. That is, those numbers are reflecting reality less and less.
2011 $41328 (not yet known)
2010 $39928 ($39928)
2009 $38048 ($39469)
2008 $36828 ($37267)
2007 $35584 ($37377)
2006 $33888 ($36592)
2005 $32864 ($36373)
2004 $30672 ($35101)
2003 $29200 ($34520)
2002 $27856 ($33556)
2001 $26568 ($32773)
2000 $25600 ($32084)
1999 $24624 ($31910)
Does this mean that this college has become more money-elitist, restricting admission except to the wealthy?
At the same time financial aid has increased from $34 millions in 2002 ($40 millions inflation adjusted dollars) to $81 millions in 2010, thus basically doubling. Does this mean that this college has become less money-elitist, redistributing more income so as to provide admission to the less wealthy as well?
If we take this to the limit, the tuition could be set at infinity, financial aid could be at near-infinity, and the financial aid office could decide arbitrarily how much each student has to pay out of their own pocket. The main result is that the college has more control over who pays what. That is, those numbers are reflecting reality less and less.
Sunday, June 12, 2011
Marketing a paper
As I am reading the book "Influence" about marketing and manipulation, I am wondering if that's of any relevance to writing papers.
One of the first points is the efficiency of trying to push onto the client, first, something that he will probably refuse, then, something more acceptable. Compared to starting right off with the final suggestion without the preliminary phase, this is much, much more successful (for some experiements the success rate goes from 20% to 50% or so). Can we imagine something similar for marketing a paper?
For example, in the introduction, to present the results it might be a good strategy to first expose the weaker results. The reviewer, reading that, thinks: "Well, this paper is not good enough to be accepted" -- but then, at the end of the introduction, suddenly, here come significantly stronger results. Then the reviewer might think: "Wow. This paper is actually much stronger than I thought at first!" Is this a better marketing strategy than starting right off with one's main result?
I must say that it goes against the way in which I write, the way in which my coauthors write, and the way in which I teach my students to write. I always try to go for the straightforward statement, going to the main point as quickly and with as much clarity as possible. But if I believe this book, it is possible that papers that put more thought into the marketing perspective are much more successful at selling themselves, independently of the results themselves and of how well the paper is written from terms of readability, clarity, etc. That's a disturbing thought!
One of the first points is the efficiency of trying to push onto the client, first, something that he will probably refuse, then, something more acceptable. Compared to starting right off with the final suggestion without the preliminary phase, this is much, much more successful (for some experiements the success rate goes from 20% to 50% or so). Can we imagine something similar for marketing a paper?
For example, in the introduction, to present the results it might be a good strategy to first expose the weaker results. The reviewer, reading that, thinks: "Well, this paper is not good enough to be accepted" -- but then, at the end of the introduction, suddenly, here come significantly stronger results. Then the reviewer might think: "Wow. This paper is actually much stronger than I thought at first!" Is this a better marketing strategy than starting right off with one's main result?
I must say that it goes against the way in which I write, the way in which my coauthors write, and the way in which I teach my students to write. I always try to go for the straightforward statement, going to the main point as quickly and with as much clarity as possible. But if I believe this book, it is possible that papers that put more thought into the marketing perspective are much more successful at selling themselves, independently of the results themselves and of how well the paper is written from terms of readability, clarity, etc. That's a disturbing thought!
Saturday, June 11, 2011
Fukushima three months later: the sorcerer's apprentice
Three months after the nuclear power plant accident at Fukushima, how far is Japan along the plan to recovery?
At the plant, the situation is "stable" in the sense that there is no more risk of sudden degradation than there was a month ago. The workers may be becoming worn out, the rain season and associated risk of typhoon are worrisome, the work is hampered by the accumulation of radiation in every object on site, but there is some progress. For example, containers for radioactive water are being brought in; measurement instruments have been set up, humans and robots have entered the buildings a couple of times for a few minutes. Information is little by little coming out to reveal that the catastrophic events three months ago were much worse than first assessed, so the present looks better in comparison. There is no clear plan forward, so in a way this is like a "new frontier" for science.
In the region, the situation is slowly degrading as radioactivity is spreading in air, water, soil, and food, in a spotty, haphazard manner. However the long term effects of non-acute radioactivity are not well known. There are almost no casualties at present, and everyone is in the dark regarding the potential casualties in 20 or 30 years (the number of deaths attributable to Chernobyl varies from 64 to 985000, depending on what you read). The media are split between systematic under-reporting of the seriousness of the situation, systematic fear-mongering, and plain and simple silence as they have moved on to other topics.
Wondering about nuclear power, I am irresistibly reminded of the scene in Fantasia where Mickey Mouse, apprentice magician, uses magic brooms to do his chores for him, as an illustration of the dangers of power over wisdom.
Raw data: http://atmc.jp/plant/rad/?n=1
News aggregator: http://enenews.com
Japanese blog: http://ex-skf.blogspot.com
UPDATE: Italians have voted against developing nuclear power again in Italy. Their vote, by referendum, was quasi-unanimous: 94.05% of the votes!
At the plant, the situation is "stable" in the sense that there is no more risk of sudden degradation than there was a month ago. The workers may be becoming worn out, the rain season and associated risk of typhoon are worrisome, the work is hampered by the accumulation of radiation in every object on site, but there is some progress. For example, containers for radioactive water are being brought in; measurement instruments have been set up, humans and robots have entered the buildings a couple of times for a few minutes. Information is little by little coming out to reveal that the catastrophic events three months ago were much worse than first assessed, so the present looks better in comparison. There is no clear plan forward, so in a way this is like a "new frontier" for science.
In the region, the situation is slowly degrading as radioactivity is spreading in air, water, soil, and food, in a spotty, haphazard manner. However the long term effects of non-acute radioactivity are not well known. There are almost no casualties at present, and everyone is in the dark regarding the potential casualties in 20 or 30 years (the number of deaths attributable to Chernobyl varies from 64 to 985000, depending on what you read). The media are split between systematic under-reporting of the seriousness of the situation, systematic fear-mongering, and plain and simple silence as they have moved on to other topics.
Wondering about nuclear power, I am irresistibly reminded of the scene in Fantasia where Mickey Mouse, apprentice magician, uses magic brooms to do his chores for him, as an illustration of the dangers of power over wisdom.
Raw data: http://atmc.jp/plant/rad/?n=1
News aggregator: http://enenews.com
Japanese blog: http://ex-skf.blogspot.com
UPDATE: Italians have voted against developing nuclear power again in Italy. Their vote, by referendum, was quasi-unanimous: 94.05% of the votes!
Wednesday, June 8, 2011
What experience teaches you
Hemon in The New Yorker:
"When he was young, like me, he [Macalister] said, he had thought that all the great writers knew something he didn’t. He’d thought that if he read their books he would learn something, get better. He’d thought that he would acquire what those writers had: the wisdom, the truth, the wholeness, the real shit. He had been burning to write, hungry for that knowledge. But now he knew that that hunger was vainglorious; now he knew that writers knew nothing, really—most of them were just faking it. He knew nothing. There was nothing to know, nothing on the other side. There was no walker, no path, just walking. This was it, whoever you were, wherever you were, whatever it was, and you had to make peace with that fact."
Read more http://www.newyorker.com/fiction/features/2008/09/22/080922fi_fiction_hemon#ixzz1OdPdoG9f
"When he was young, like me, he [Macalister] said, he had thought that all the great writers knew something he didn’t. He’d thought that if he read their books he would learn something, get better. He’d thought that he would acquire what those writers had: the wisdom, the truth, the wholeness, the real shit. He had been burning to write, hungry for that knowledge. But now he knew that that hunger was vainglorious; now he knew that writers knew nothing, really—most of them were just faking it. He knew nothing. There was nothing to know, nothing on the other side. There was no walker, no path, just walking. This was it, whoever you were, wherever you were, whatever it was, and you had to make peace with that fact."
Read more http://www.newyorker.com/fiction/features/2008/09/22/080922fi_fiction_hemon#ixzz1OdPdoG9f
Tuesday, June 7, 2011
Faster program committees
Why not have the following procedure to select papers?
Day 1: submission deadline
Day 1 to day 3: assignment of submitted papers to PC members
Day 4 to day 9: physical PC meeting at some location such as Dagstuhl or NSF to read, discuss, and select the papers
Day 10: list of accepted papers is made public.
Pros:
The work for PC members would be concentrated in a single week, more efficient.
Authors would get results almost immediately.
There would be much more interaction between PC members, which would be a much more efficient way to read, learn and form an opinion about submissions.
There would be a clearer distinction between conference and journal evaluation.
The total amount of work per PC member would be reduced.
Cons:
There wouldn't be time to get outside expertise except for emergencies.
The type-A PC members might dominate the decisions.
PC members would be spending that time away from their families.
Would any conference center be willing to let a committee use their space for that?
Day 1: submission deadline
Day 1 to day 3: assignment of submitted papers to PC members
Day 4 to day 9: physical PC meeting at some location such as Dagstuhl or NSF to read, discuss, and select the papers
Day 10: list of accepted papers is made public.
Pros:
The work for PC members would be concentrated in a single week, more efficient.
Authors would get results almost immediately.
There would be much more interaction between PC members, which would be a much more efficient way to read, learn and form an opinion about submissions.
There would be a clearer distinction between conference and journal evaluation.
The total amount of work per PC member would be reduced.
Cons:
There wouldn't be time to get outside expertise except for emergencies.
The type-A PC members might dominate the decisions.
PC members would be spending that time away from their families.
Would any conference center be willing to let a committee use their space for that?
Monday, June 6, 2011
The easiest primal-dual algorithm
What is a good algorithm to teach the primal-dual technique for the design of approximation algorithms? One simple algorithm is in Charikar and Panigrahy's 2001 paper on clustering. This particular solution contains all the basic ideas of primal-dual algorithms, but none of the technical issues that come up in most applications. It's like a baby version of the facility location primal dual algorithm.
The input is a finite metric space and a cost f for each cluster opening. The output is a collection of balls (clusters), each ball B(i,r) centered at some point i and of some radius r, so as to cover all points. The value to minimize is f times the number of clusters, plus the sum of cluster radii.
First they design a linear programming relaxation, where x(i,r) indicates whether the ball B(i,r) is in the solution, and where there is one constraint for each point j, indicating that there has to be at least one ball B(i,r) selected for some r and some i within distance r of j. Then they write the dual. The dual linear program simply has one variable a(j) for each point j, and one constraint for each ball B(i,r), stating that the a(j)'s for j in that ball must sum to at most f+r.
The algorithm picks an arbitrary feasible dual solution that is a local maximum w.r.to changing a single coordinate a(j). In other words, the dual solution (a(j)) is such that for every j, there exists a ball B(i,r) containing j, such that the dual constraint is tight. Then, to deduce a feasible primal solution, let T be the set of such balls B(i,r). The algorithm greedily goes through all balls of T by order of non-increasing radius, to construct a subset S of disjoint balls of T. Finally, the primal output solution consists of the balls B(i,3r) for each ball B(i,r) in S.
For the analysis, they first need to prove that the output is feasible, that is, that the output balls cover every j. Fix a j: it's in some ball B(i,r) of T. If that ball is not in S, it's because it intersects some ball B(i',r') that is in S, so the output contains ball B(i',3r'). By the greedy definition of S, r' is larger than r, so the ball B(i',3r') covers j.
Then they need to bound the cost of the output balls. It's at most three times the cost of the balls in S. Since the balls in S are a disjoint subset of T, the corresponding tight constraints sum to give that the cost of S is at most the sum of all a(j)'s, which is less than OPT by linear programming duality. That concludes the proof of a 3-approximation.
The input is a finite metric space and a cost f for each cluster opening. The output is a collection of balls (clusters), each ball B(i,r) centered at some point i and of some radius r, so as to cover all points. The value to minimize is f times the number of clusters, plus the sum of cluster radii.
First they design a linear programming relaxation, where x(i,r) indicates whether the ball B(i,r) is in the solution, and where there is one constraint for each point j, indicating that there has to be at least one ball B(i,r) selected for some r and some i within distance r of j. Then they write the dual. The dual linear program simply has one variable a(j) for each point j, and one constraint for each ball B(i,r), stating that the a(j)'s for j in that ball must sum to at most f+r.
The algorithm picks an arbitrary feasible dual solution that is a local maximum w.r.to changing a single coordinate a(j). In other words, the dual solution (a(j)) is such that for every j, there exists a ball B(i,r) containing j, such that the dual constraint is tight. Then, to deduce a feasible primal solution, let T be the set of such balls B(i,r). The algorithm greedily goes through all balls of T by order of non-increasing radius, to construct a subset S of disjoint balls of T. Finally, the primal output solution consists of the balls B(i,3r) for each ball B(i,r) in S.
For the analysis, they first need to prove that the output is feasible, that is, that the output balls cover every j. Fix a j: it's in some ball B(i,r) of T. If that ball is not in S, it's because it intersects some ball B(i',r') that is in S, so the output contains ball B(i',3r'). By the greedy definition of S, r' is larger than r, so the ball B(i',3r') covers j.
Then they need to bound the cost of the output balls. It's at most three times the cost of the balls in S. Since the balls in S are a disjoint subset of T, the corresponding tight constraints sum to give that the cost of S is at most the sum of all a(j)'s, which is less than OPT by linear programming duality. That concludes the proof of a 3-approximation.
Sunday, June 5, 2011
Unsynchronized elevators and selfishness
My building has two elevators, each with its own call button, independent of each other. My office is on the top floor, and when I want to take the elevator, I systematically push both buttons, so as to minimize my waiting time. Then I simply go into the first elevator that makes it up to my floor, and my waiting time is the minimum of the two waiting times.
This week I got chided by my visitor for that behavior. He claimed that I was increasing everyone's waiting time, because I was making both elevators come to my floor, but one of them was just coming up for nothing. That slows things down for everyone in the building, he argued. If everyone does the same as me, it is almost as if there were twice as many people in the building as there really are, so my behavior induces dynamics that are very far from the social optimum. In other words, I am violating Kant's universal moral law: "Act only in accordance with that maxim through which you can at the same time will that it become a universal law." Instead, I am selfishly choosing my actions so that, if everyone else's actions are fixed, I am minimizing my personal waiting time.
Some remarks:
- I have been doing this for close to seven years, but never thought about it, and no one had mentioned it to me before. Are selfish choices so ingrained in the culture here in the US that we don't even think to question them?
- My visitor was from France, where there is a tradition of being socially minded (as in: people on the street tend to support strikers even if it causes them hours of delays). Are social-minded choices so ingrained in that culture that it is natural for them to first look for actions that realize the social optimum (that is, apply Kant's law)?
- It is not possible to modify the current layout and synchronize the elevator buttons because of some security reason, or so the elevator company claims. Could we modify the system to give some kind of reward to not push both buttons? For example, if pushing the button gave us a slight electric jolt, or if the buttons were slightly gooey, or if we had to swipe our card and had a daily quota of button calls...
This week I got chided by my visitor for that behavior. He claimed that I was increasing everyone's waiting time, because I was making both elevators come to my floor, but one of them was just coming up for nothing. That slows things down for everyone in the building, he argued. If everyone does the same as me, it is almost as if there were twice as many people in the building as there really are, so my behavior induces dynamics that are very far from the social optimum. In other words, I am violating Kant's universal moral law: "Act only in accordance with that maxim through which you can at the same time will that it become a universal law." Instead, I am selfishly choosing my actions so that, if everyone else's actions are fixed, I am minimizing my personal waiting time.
Some remarks:
- I have been doing this for close to seven years, but never thought about it, and no one had mentioned it to me before. Are selfish choices so ingrained in the culture here in the US that we don't even think to question them?
- My visitor was from France, where there is a tradition of being socially minded (as in: people on the street tend to support strikers even if it causes them hours of delays). Are social-minded choices so ingrained in that culture that it is natural for them to first look for actions that realize the social optimum (that is, apply Kant's law)?
- It is not possible to modify the current layout and synchronize the elevator buttons because of some security reason, or so the elevator company claims. Could we modify the system to give some kind of reward to not push both buttons? For example, if pushing the button gave us a slight electric jolt, or if the buttons were slightly gooey, or if we had to swipe our card and had a daily quota of button calls...
Saturday, June 4, 2011
Why go to college? An education
I just watched the movie "An education". One question that kept coming up but never got a satisfactory answer: "Why go to college?"
The private high school teachers claimed that learning (Latin, in that case), although it was "hard and boring", was worthwhile, but I didn't see that they offered a compelling answer.
I disagree with the "boring" part. It propagates a prejudice. Learning is hard, but it is not boring. It carries in itself a lot of its reward. I could imagine the girl in the movie, or her teacher, coming up with just the right way to translate some Latin text written thousands of years ago so as to convey just the right nuances of meaning, and getting excited about it. Or the girl could be spending hours and hours working on a difficult passage with her cello, until she finally masters it, and getting thrilled by the music or by her accomplishment. The movie does not give any hint of what is good about learning, besides getting students into Oxford (and finding a husband, as was apparently the girl's father's ultimate goal for her).
Even for the other side of the girl's "education", the description was not that compelling either. She describes it as "going to restaurants and concerts" and generally going out and having fun, as though that was all that there was about the world outside the (perceived) drudgery of school and work. She could have talked about the excitement of meeting people who are older and who have more experience, more ideas, and more conversation. There was much talk of the excitement of going to Paris on a trip, but what was exciting about it? We have no idea. The couple of snapshots of Paris were just enough to indicate that she was there, but not to imply any particular kind of discovery. The aspects of physical awakening were also underplayed (although surely on purpose, in this case).
I thought the movie was going to show a conflict of values and offer some perspective on the question: "What is the point of getting an education? What is the point of going out into the real world?", but it didn't address that question except at the shallowest level.
The private high school teachers claimed that learning (Latin, in that case), although it was "hard and boring", was worthwhile, but I didn't see that they offered a compelling answer.
I disagree with the "boring" part. It propagates a prejudice. Learning is hard, but it is not boring. It carries in itself a lot of its reward. I could imagine the girl in the movie, or her teacher, coming up with just the right way to translate some Latin text written thousands of years ago so as to convey just the right nuances of meaning, and getting excited about it. Or the girl could be spending hours and hours working on a difficult passage with her cello, until she finally masters it, and getting thrilled by the music or by her accomplishment. The movie does not give any hint of what is good about learning, besides getting students into Oxford (and finding a husband, as was apparently the girl's father's ultimate goal for her).
Even for the other side of the girl's "education", the description was not that compelling either. She describes it as "going to restaurants and concerts" and generally going out and having fun, as though that was all that there was about the world outside the (perceived) drudgery of school and work. She could have talked about the excitement of meeting people who are older and who have more experience, more ideas, and more conversation. There was much talk of the excitement of going to Paris on a trip, but what was exciting about it? We have no idea. The couple of snapshots of Paris were just enough to indicate that she was there, but not to imply any particular kind of discovery. The aspects of physical awakening were also underplayed (although surely on purpose, in this case).
I thought the movie was going to show a conflict of values and offer some perspective on the question: "What is the point of getting an education? What is the point of going out into the real world?", but it didn't address that question except at the shallowest level.
Thursday, June 2, 2011
The job market in my state
Today someone told me happily that they had gotten a job, four hours a week of paid work -- on condition that they also do four hours a week of (unpaid) volunteer work at the same place. That's the current state of the job market in Rhode Island.
Subscribe to:
Posts (Atom)