Yesterday was my third evening without electric power. At 8pm this time of year, it's pretty dark in Rhode Island, and candle light is not very bright. What can one do to while away the time when there is no electricity?
Communication relies more on hearing and less on seeing. Music can be played in the dark, but it requires having memorized the piece. Telling stories can happen in the dark, but it requires remembering a story in detail. That is why rote memorization used to be such an important part of education! Information (the text of a piece of music for example) was much less available before the advent of the internet, and even more scarce before electrical light. Information had to be stored in one's brain. Thanks to electrical power, information could then be stored in remote locations such as books and sheet music. Thanks to the internet, information now is in locations that have the dual advantages of vastly increased storage space and of much more ready access.
When I moved to the US, at a parent-teacher meeting I complained that children did not seem to learn any poetry, and that they were missing out on a piece of culture. The Indian parents in the room nodded their head in approval, but the teacher brushed off my remark somewhat dismissively: "We no longer teach in that way. Pedagogy has moved beyond rote memorization. We now know how to focus our efforts more wisely."
Actually, pedagogical values are not timeless. Developing this or that part of our brains is a choice that depends on current needs, and those needs depend on the technology currently available. Rote memorization was valuable 200 years ago, but is out because nowadays, our brains have become superfluous for storage.
Wednesday, August 31, 2011
Tuesday, August 30, 2011
How to number offices?
The floors of the Brown CS department are roughly square. Most offices have a window to the outside. A few windowless offices, classrooms, meeting rooms, etc., are in the inside of the building, which is organized in square or rectangular blocks.
Some of the new PhD students complained about the numbering system for the offices: offices that are contiguous or that face each other do not necessarily have contiguous or near-contiguous numbers.
How can one number offices to avoid this problem?
Some of the new PhD students complained about the numbering system for the offices: offices that are contiguous or that face each other do not necessarily have contiguous or near-contiguous numbers.
How can one number offices to avoid this problem?
A series of unfortunate events
Stolen purse + earthquake + Irene = No passport. No credit cards. No IDs. No phones. No driver's license. No power. Broken plates. No functioning fridge. No car. No internet. No TV. Out of cash. Almost out of food.
Yesterday at the supermarket, for the first time in at least 25 years, I had to carefully select what food to buy with my last $10 of cash.
Today I come to work, and here, everything is normal. Eery!
Yesterday at the supermarket, for the first time in at least 25 years, I had to carefully select what food to buy with my last $10 of cash.
Today I come to work, and here, everything is normal. Eery!
Monday, August 15, 2011
The formation of the scientific mind
Browsing through the family library and looking for a book to take with me on vacation, I stumbled upon a book by Gaston Bachelard on the formation of the scientific mind. Here is the exciting first paragraph.
"One who studies the psychological conditions of scientific progress quickly becomes convinced that the problem of scientific knowledge must be posed in terms of obstacles, by which I mean neither external obstacles such as the complexity of phenomena, nor the weakness of the senses and of the human mind; it is in the intimate act of acquiring knowledge that, by some sort of functional necessity, appear troubles and slowdowns. There, we will show some causes of stagnation and even regression. There, we will distinguish some causes of inertia that we will call epistemological obstacles. The knowledge of reality is a light that must always project shadows somewhere. It is never immediate and full. The revelations about reality are always recurrent. Reality is never "what one might believe" but it is always what one should have thought. Empirical thought is clear a posteriori, once the machinery of reasoning has been tuned. It is by going over a past of errors that we can find truth, in a genuine act of intellectual repentance. In fact we acquire knowledge against a prior knowledge, by destructing poorly built knowledge, by moving on beyond what, in our own intellect, is an obstacle to intellectualisation."
"One who studies the psychological conditions of scientific progress quickly becomes convinced that the problem of scientific knowledge must be posed in terms of obstacles, by which I mean neither external obstacles such as the complexity of phenomena, nor the weakness of the senses and of the human mind; it is in the intimate act of acquiring knowledge that, by some sort of functional necessity, appear troubles and slowdowns. There, we will show some causes of stagnation and even regression. There, we will distinguish some causes of inertia that we will call epistemological obstacles. The knowledge of reality is a light that must always project shadows somewhere. It is never immediate and full. The revelations about reality are always recurrent. Reality is never "what one might believe" but it is always what one should have thought. Empirical thought is clear a posteriori, once the machinery of reasoning has been tuned. It is by going over a past of errors that we can find truth, in a genuine act of intellectual repentance. In fact we acquire knowledge against a prior knowledge, by destructing poorly built knowledge, by moving on beyond what, in our own intellect, is an obstacle to intellectualisation."
Sunday, August 14, 2011
Staying connected
The French TV news in August focus on the following topics, that come up every day: the weather, especially in popular vacation areas; the traffic on main highways to and from popular vacation spots; and various news related to vacation. The other day the report was about professionals on vacation: the majority now bring their laptop with them and stay connected to the internet throughout their vacation. Cybercafes and areas with free wifis are booming. The latest must of private beaches on the riviera: free wifi available on the beach. 30 percent of those professionals feel pressure from their company to stay on top of their emails even while they are away. One interviewee talked about how hard it is to fight against an addiction to internet connection. Unions are becoming interested in the topic. There was a brief mention of a man who sued his company and who, based on his phone bills, got paid for hundreds of hours overtime.
Saturday, August 13, 2011
Poisson process
Poisson means fish in French.
Fish like water.
Water drops falling in a puddle in the rain are like a two-dimensional Poisson process.
That's why the process is called "Poisson".
And that's why watching the rain falling is a way of learning mathematics.
Fish like water.
Water drops falling in a puddle in the rain are like a two-dimensional Poisson process.
That's why the process is called "Poisson".
And that's why watching the rain falling is a way of learning mathematics.
Friday, August 12, 2011
Layers
The OSI model organizes networks in layers. Each layer communicates via an interface with the layer "above" it and with the layer "below" it. A layer is unaware of anything beyond those two neighboring layers, which helps greatly simplify things.
Last Sunday at the Cluny museum I saw the tapestries of the licorn and their description of the five senses. I experience the world around me, that communicates with me via the interface of my five senses. I communicate back via talking, writing, and otherwise expressing myself. My internal (conscious) state is a layer, the outside world around me is another layer. If Freud was still in vogue, I would say that my internal conscious state also has an interface with my subconscious, that would be another layer underneath it, or that there is a small voice in my heart that could be heard when all is still. If one took science-fiction seriously, we could also say that there is a world beyond the one that we experience with our senses, or make all sorts of wild conjectures. But the only layers that have a hope of being accessible to our minds are the one immediately above and the one immediately below it - the physical world, and the world of the unconscious.
Last Sunday at the Cluny museum I saw the tapestries of the licorn and their description of the five senses. I experience the world around me, that communicates with me via the interface of my five senses. I communicate back via talking, writing, and otherwise expressing myself. My internal (conscious) state is a layer, the outside world around me is another layer. If Freud was still in vogue, I would say that my internal conscious state also has an interface with my subconscious, that would be another layer underneath it, or that there is a small voice in my heart that could be heard when all is still. If one took science-fiction seriously, we could also say that there is a world beyond the one that we experience with our senses, or make all sorts of wild conjectures. But the only layers that have a hope of being accessible to our minds are the one immediately above and the one immediately below it - the physical world, and the world of the unconscious.
Thursday, August 11, 2011
The Online Parking game (part 3)
Once I ran into trouble trying to retrieve my car from the train station parking garage late at night after a day in Paris.
The machine to pay my fee rejected my U.S. credit card. It refused my cash because I did not have exact change. A gate blocked the exit and my car could not leave the garage without me paying. No one was in the employee booth. When I called using the help line next to the booth, someone answered at first, but as soon as I explained my predicament, the line went dead. When I tried again, the line kept having a busy signal. What to do?
I had an idea: get a new ticket from the machine at the entrance gate, pay it immediately, (I had exact change for that small amount), and use that ticket to get out. Unfortunately the machine delivering tickets by the entrance barrier was only activated by the weight of a car in front of the barrier. With just one pedestrian, even jumping up and down was not enough to make the machine spit out a new ticket. I considered abandoning my car until the next day, but the last bus was long gone, there were no taxis in sight, the taxis whose numbers I had did not answer, and I was not eager to walk 5 miles in the forest in pitch dark. What to do?
My car was the last car in the garage, and I was the last person in the garage - almost. There was also a big black man wandering about for no apparent reason. He once asked me the time, then asked: "Is everything all right?", and I answered coldly: "Fine, thank you" while nervously keeping my distance. Some time later, he asked me if I had a problem, and, having run out of ideas, I explained it to him while still avoiding getting close. This was not a situation I wanted to be in... but what to do?
The man said: "Easy; one can just lift the gate". I tried with some scepticism, but the bar resisted my efforts. He said: "I can do it. Just bring the car here and I'll let you through." I got my car, drove it to the gate, he huffed and puffed and managed to lift the bar just high enough that I could finally get out of the garage. I thanked him and left.
The net result was that I got a day of parking for free. The incident also helped re-evaluate my unconscious prejudices against blacks. It also reminded me that in France, things often don't work the way they're supposed to work, but then people help one another. Less efficiency, more solidarity.
The machine to pay my fee rejected my U.S. credit card. It refused my cash because I did not have exact change. A gate blocked the exit and my car could not leave the garage without me paying. No one was in the employee booth. When I called using the help line next to the booth, someone answered at first, but as soon as I explained my predicament, the line went dead. When I tried again, the line kept having a busy signal. What to do?
I had an idea: get a new ticket from the machine at the entrance gate, pay it immediately, (I had exact change for that small amount), and use that ticket to get out. Unfortunately the machine delivering tickets by the entrance barrier was only activated by the weight of a car in front of the barrier. With just one pedestrian, even jumping up and down was not enough to make the machine spit out a new ticket. I considered abandoning my car until the next day, but the last bus was long gone, there were no taxis in sight, the taxis whose numbers I had did not answer, and I was not eager to walk 5 miles in the forest in pitch dark. What to do?
My car was the last car in the garage, and I was the last person in the garage - almost. There was also a big black man wandering about for no apparent reason. He once asked me the time, then asked: "Is everything all right?", and I answered coldly: "Fine, thank you" while nervously keeping my distance. Some time later, he asked me if I had a problem, and, having run out of ideas, I explained it to him while still avoiding getting close. This was not a situation I wanted to be in... but what to do?
The man said: "Easy; one can just lift the gate". I tried with some scepticism, but the bar resisted my efforts. He said: "I can do it. Just bring the car here and I'll let you through." I got my car, drove it to the gate, he huffed and puffed and managed to lift the bar just high enough that I could finally get out of the garage. I thanked him and left.
The net result was that I got a day of parking for free. The incident also helped re-evaluate my unconscious prejudices against blacks. It also reminded me that in France, things often don't work the way they're supposed to work, but then people help one another. Less efficiency, more solidarity.
Wednesday, August 10, 2011
Another good open problem?
A criticism often heard coming from scientists in other disciplines is that we put too much emphasis on worst-case analysis. But where else would we go? I have an interest in reconstruction problems, when the input is a noisy version of some hidden ground truth.
Recently I was looking at a paper by Magen and Moharrami about independent set in near-planar graphs, that is, planar graphs with o(n) extraneous edges.
Now, how about reconstructing a planar graph?
The problem would take as input a graph and remove the fewest edges to make it planar (minimum non-planar deletion). Think about Kleinberg's original small world networks: they consisted of a planar graph plus a moderate number of random "long" edges. So, such graphs have been considered. The problem is APX-hard. The complementary problem has a constant factor approximation (Calinescu, Fernandes, Finkler and Karloff). Here's the question. Consider a graph built as follows: first, pick an arbitrary planar graph -- the ground truth. Then, take a random graph G(n,p) where p=o(1)/n -- the noise. The superposition of those two graphs is the input. Given the input, is it possible to reconstruct the ground truth or at least a close approximation to it?
Why this may be a good open question:
- The broad area of reconstruction is exciting
- It is not inconceivable that a good algorithm might interest people outside Theory.
- The problem has not been studied that much, so there are not yet walls of impossibly hard questions in every direction.
- The probabilistic question feels doable. It has never been considered before.
- Little background is needed
- It is a chance to learn about: elementary random graph techniques and perhaps basic FPT techniques
Recently I was looking at a paper by Magen and Moharrami about independent set in near-planar graphs, that is, planar graphs with o(n) extraneous edges.
Now, how about reconstructing a planar graph?
The problem would take as input a graph and remove the fewest edges to make it planar (minimum non-planar deletion). Think about Kleinberg's original small world networks: they consisted of a planar graph plus a moderate number of random "long" edges. So, such graphs have been considered. The problem is APX-hard. The complementary problem has a constant factor approximation (Calinescu, Fernandes, Finkler and Karloff). Here's the question. Consider a graph built as follows: first, pick an arbitrary planar graph -- the ground truth. Then, take a random graph G(n,p) where p=o(1)/n -- the noise. The superposition of those two graphs is the input. Given the input, is it possible to reconstruct the ground truth or at least a close approximation to it?
Why this may be a good open question:
- The broad area of reconstruction is exciting
- It is not inconceivable that a good algorithm might interest people outside Theory.
- The problem has not been studied that much, so there are not yet walls of impossibly hard questions in every direction.
- The probabilistic question feels doable. It has never been considered before.
- Little background is needed
- It is a chance to learn about: elementary random graph techniques and perhaps basic FPT techniques
Tuesday, August 9, 2011
The Online Parking game (part 2)
The other day I parked on the street of Avon, a town adjoining Fontainebleau, not far from Paris. As I was looking for change for the parking meter, a woman of a certain age stopped to tell me that parking was free in August. I pointed out to her that there was no mention of that on any signs, but she insisted that she knew that fact for sure, at least for Fontainebleau. Convinced that it was worth taking a chance, I left my car without paying anything for the meter.
I had many reasons for that.
First, since parking in August was free in Fontainebleau, and since Avon was essentially the same urban center, that was probably true in Avon as well.
Second, even if parking was not free in Avon, in August so many people are on vacation that the parking enforcement officers are probably also on vacation, like everybody else, and the few remaining ones must not have time to check every parking spot every day.
Third, even if I was given a ticket, I could always contest it and argue that I was in good faith, since I naturally assumed that the Fontainebleau August rule also held for Avon.
Fourth, even if that argument did not convince and my ticket stuck, it's not that expensive anyway (less than 20 euros -- parking for the day cost 2.30 euros).
Fifth, even if I got a ticket, if I decided not to pay it, I have heard that these outstanding tickets are not being chased from one region to a different region. What are the odds that they would go to the French consulate of Boston to find my folder? Nil.
Thus, with five excellent reasons not to put money in the parking meter, I left my car for the day with not a worry in the world. In the evening, when I got back, my car was intact and there was no ticket: so far I've only had to appeal to the first or second reasons (I'm still not sure which). Success!
I had many reasons for that.
First, since parking in August was free in Fontainebleau, and since Avon was essentially the same urban center, that was probably true in Avon as well.
Second, even if parking was not free in Avon, in August so many people are on vacation that the parking enforcement officers are probably also on vacation, like everybody else, and the few remaining ones must not have time to check every parking spot every day.
Third, even if I was given a ticket, I could always contest it and argue that I was in good faith, since I naturally assumed that the Fontainebleau August rule also held for Avon.
Fourth, even if that argument did not convince and my ticket stuck, it's not that expensive anyway (less than 20 euros -- parking for the day cost 2.30 euros).
Fifth, even if I got a ticket, if I decided not to pay it, I have heard that these outstanding tickets are not being chased from one region to a different region. What are the odds that they would go to the French consulate of Boston to find my folder? Nil.
Thus, with five excellent reasons not to put money in the parking meter, I left my car for the day with not a worry in the world. In the evening, when I got back, my car was intact and there was no ticket: so far I've only had to appeal to the first or second reasons (I'm still not sure which). Success!
Monday, August 8, 2011
L'union fait la force
That's the moral of a fable by La Fontaine, inspired by Aesop:
An old man on the point of death summoned his sons around him to give them some parting advice. He ordered his servants to bring in a faggot of sticks, and said to his eldest son: "Break it." The son strained and strained, but with all his efforts was unable to break the Bundle. The other sons also tried, but none of them was successful. "Untie the faggots," said the father, "and each of you take a stick." When they had done so, he called out to them: "Now, break," and each stick was easily broken. "You see my meaning," said their father. Union gives strength.
Oded Regev recently gave me a mathematical illustration of that principle .
Given n independent random variables x(1), x(2), ..., x(n), the mutual information between the collection of all x(i)'s taken together and some other variable m is greater than the sum of the mutual informations between each variable x(i) and m:
I(x(1)x(2)...x(n):m) ≥ Σ I(x(i):m)
For example, imagine x(1) and x(2) are independent random bits, and m=x(1) XOR x(2). Then x(1) alone gives no information about m, so I(x(1):m)=0. Similarly, x(2) alone gives no information about m, so I(x(2):m)=0. However, x(1) and x(2) together determine m, so they give full information about it: I(x(1)x(2):m)=1. It is not hard to check that 1 is indeed greater than 0+0.
An old man on the point of death summoned his sons around him to give them some parting advice. He ordered his servants to bring in a faggot of sticks, and said to his eldest son: "Break it." The son strained and strained, but with all his efforts was unable to break the Bundle. The other sons also tried, but none of them was successful. "Untie the faggots," said the father, "and each of you take a stick." When they had done so, he called out to them: "Now, break," and each stick was easily broken. "You see my meaning," said their father. Union gives strength.
Oded Regev recently gave me a mathematical illustration of that principle .
Given n independent random variables x(1), x(2), ..., x(n), the mutual information between the collection of all x(i)'s taken together and some other variable m is greater than the sum of the mutual informations between each variable x(i) and m:
I(x(1)x(2)...x(n):m) ≥ Σ I(x(i):m)
For example, imagine x(1) and x(2) are independent random bits, and m=x(1) XOR x(2). Then x(1) alone gives no information about m, so I(x(1):m)=0. Similarly, x(2) alone gives no information about m, so I(x(2):m)=0. However, x(1) and x(2) together determine m, so they give full information about it: I(x(1)x(2):m)=1. It is not hard to check that 1 is indeed greater than 0+0.
Sunday, August 7, 2011
How to do research without doing anything
If I don't have a good problem to work on, how to I decide what to work on next? Some people have an inherent solid taste or a well-defined agenda, but for people like me who are more attracted to the pleasure of problem-solving than to some larger goal, it is somewhat more haphazard. One way is to smell the wind. Going to a conference, I can notice which talks attract the most attendees, which questions are most vividly discussed in the hallways, and which papers, in that broad fashionable area, are coming up with new problems and partial results. With a bit of experience, that gives plenty of material for promising questions to work on.
How do I figure out what's been done? Thanks to search engines, it is now not challenging to trace back papers, read abstracts and introductions, and quickly figure out the state of the art. It's not particularly difficult, but it's still hard work that takes some incompressible time and requires sustained focus and energy. For people like me, who are seldom focused enough for a long enough interval of time, graduate students are a great resource.
How do I figure out how to attack the problem? The key to make up for my lack of culture is to have friends who know a lot. (I could also try to acquire additional new knowledge, but my brain seems to refuse to retain new information; an inconvenient but not uncommon phenomenon in mid-career researchers.) Then I simply draw on their knowledge. Whenever I have a question in probability, I ask Yuval Peres. If it's in analytical combinatorics, until recently I would have asked Philippe Flajolet. If it's in computational geometry, I send email to David Eppstein, if it's in scheduling, I drop a line to Yossi Azar, if it's related to bin packing, David Johnson is the man, etc. I thus have a short list of "oracles" who each know pretty much everything that's ever been done in their own area of specialty, and who can give me pointers to papers or to techniques that they think might apply to my problem.
What about using previous work and trying out some techniques to actually launch the attack? There is a systematic way to go about it - strike a balance between looking for increasingly harder input examples and looking for increasingly stronger algorithms, favor an axiomatic approach, extract clean mathematical sub-problems from the larger, more challenging question, etc. This rather entertaining exploration can be done jointly with one or several colleagues and students, and the brainstorming aspect is quite fun.
Then comes the hard, grungy work of actually pinning down the proofs of the lemmas, spelling out the calculations, etc. That can be delegated to studious students (because, you know, they need to learn, it's good for them); and it only remains to criticize their attempts (because, you know, they need feedback, it's good for them) before declaring the result proved.
How about writing a paper? Good writing is not easy, and for me it takes more and more time as I have become more and more of a perfectionist. It takes me forever to write a simple proof of a simple lemma, because I try to find just the right wording. Instead, I have resorted to a solution that takes much less effort: a student writes, I criticize what he or she wrote, and we iterate until some deadline happens.
And that is how, with good enough students and a little bit of experience, it is possible to output research, and even sometimes good research, without really doing much.
How do I figure out what's been done? Thanks to search engines, it is now not challenging to trace back papers, read abstracts and introductions, and quickly figure out the state of the art. It's not particularly difficult, but it's still hard work that takes some incompressible time and requires sustained focus and energy. For people like me, who are seldom focused enough for a long enough interval of time, graduate students are a great resource.
How do I figure out how to attack the problem? The key to make up for my lack of culture is to have friends who know a lot. (I could also try to acquire additional new knowledge, but my brain seems to refuse to retain new information; an inconvenient but not uncommon phenomenon in mid-career researchers.) Then I simply draw on their knowledge. Whenever I have a question in probability, I ask Yuval Peres. If it's in analytical combinatorics, until recently I would have asked Philippe Flajolet. If it's in computational geometry, I send email to David Eppstein, if it's in scheduling, I drop a line to Yossi Azar, if it's related to bin packing, David Johnson is the man, etc. I thus have a short list of "oracles" who each know pretty much everything that's ever been done in their own area of specialty, and who can give me pointers to papers or to techniques that they think might apply to my problem.
What about using previous work and trying out some techniques to actually launch the attack? There is a systematic way to go about it - strike a balance between looking for increasingly harder input examples and looking for increasingly stronger algorithms, favor an axiomatic approach, extract clean mathematical sub-problems from the larger, more challenging question, etc. This rather entertaining exploration can be done jointly with one or several colleagues and students, and the brainstorming aspect is quite fun.
Then comes the hard, grungy work of actually pinning down the proofs of the lemmas, spelling out the calculations, etc. That can be delegated to studious students (because, you know, they need to learn, it's good for them); and it only remains to criticize their attempts (because, you know, they need feedback, it's good for them) before declaring the result proved.
How about writing a paper? Good writing is not easy, and for me it takes more and more time as I have become more and more of a perfectionist. It takes me forever to write a simple proof of a simple lemma, because I try to find just the right wording. Instead, I have resorted to a solution that takes much less effort: a student writes, I criticize what he or she wrote, and we iterate until some deadline happens.
And that is how, with good enough students and a little bit of experience, it is possible to output research, and even sometimes good research, without really doing much.
Saturday, August 6, 2011
A good open problem?
What makes a open problem a good problem to work on? What are the criteria? Let me take an example and try to argue for it. I think that the 2010 paper by Chlamtac, Krauthgamer and Raghavendra is a good research direction. That paper is only a first step, with much room left for improvements. Here are some questions raised by that paper.
- (Improve) Is there hope that by vastly increasing the number of levels of lifting in the LP, the approximation ratio is reduced to a constant independent of the treewidth, so that the treewidth appears in the runtime only?
- (Simplify) Now that there is one proof, extracting its key ideas, is it possible to design a direct, possibly more efficient argument that would not rely on lift-and-project?
- Is there a version that would work in the framework of branch decomposition instead of treewidth?
- (Generalize)The authors present a table of related results and techniques. The diversity of algorithmic techniques is surprising. Is there a way to unify them and provide a single general-purpose algorithm based on Sherali-Adams lift-and-project, that would simultaneously solve many of cases listed in the table? As a warmup question, how does the algorithm perform in the (previously solved) case of uniform demands?
- (Same inputs, other problems) Can a similar approach be tried for other non-local non-trivial problems on graphs of bounded treewidth, for example Steiner forest (recently Ptas'ed in bounded treewidth graphs by Bateni Hajiaghayi and Marx) or bandwidth problems?
- (Same problem, other inputs) Many planar graph algorithms work by a reduction to graphs of bounded tree width. Can the result be extended to planar graphs?
Here is why I think it's a good research topic. First, network cuts and connectivity problems are the bread and butter of approximation algorithms. That's where much of the action is, where a lot of the significant progress happens, and seems to be an inspiration for exciting research. Second, related to the first, it's an area where many people are interested in whatever new result comes up, and where it's relatively easier than other subfields to get papers accepted. Third, this particular problem has not been looked at by that many people, so it is possible that improving on the Chlamtac et al result is within reach. Fourth, there's a range of questions that come to mind when looking at that paper, some hard, some easier, so it ought to be possible to work on this in a mixed breadth-first-search/depth-first-search manner so as to avoid being fruitlessly stuck with a smooth wall blocking all progress and all ideas: go in depth in the most promising direction, until one gets stuck, then branch off to another less hopeless direction, etc. Fifth, for people doing algorithms, it requires only a modest investment: read in depth a mere couple of background papers in addition to the Chlamtac et al paper. Sixth, if worst comes to worst and you do not get any new result out of your endeavour, at least you will have learnt about lift-and-project and about treewidth. Learning new tools and techniques is a net plus even if no research result comes out of that failed project. (http://terrytao.wordpress.com/career-advice/learn-the-power-of-other-mathematicians-tools/).
- (Improve) Is there hope that by vastly increasing the number of levels of lifting in the LP, the approximation ratio is reduced to a constant independent of the treewidth, so that the treewidth appears in the runtime only?
- (Simplify) Now that there is one proof, extracting its key ideas, is it possible to design a direct, possibly more efficient argument that would not rely on lift-and-project?
- Is there a version that would work in the framework of branch decomposition instead of treewidth?
- (Generalize)The authors present a table of related results and techniques. The diversity of algorithmic techniques is surprising. Is there a way to unify them and provide a single general-purpose algorithm based on Sherali-Adams lift-and-project, that would simultaneously solve many of cases listed in the table? As a warmup question, how does the algorithm perform in the (previously solved) case of uniform demands?
- (Same inputs, other problems) Can a similar approach be tried for other non-local non-trivial problems on graphs of bounded treewidth, for example Steiner forest (recently Ptas'ed in bounded treewidth graphs by Bateni Hajiaghayi and Marx) or bandwidth problems?
- (Same problem, other inputs) Many planar graph algorithms work by a reduction to graphs of bounded tree width. Can the result be extended to planar graphs?
Here is why I think it's a good research topic. First, network cuts and connectivity problems are the bread and butter of approximation algorithms. That's where much of the action is, where a lot of the significant progress happens, and seems to be an inspiration for exciting research. Second, related to the first, it's an area where many people are interested in whatever new result comes up, and where it's relatively easier than other subfields to get papers accepted. Third, this particular problem has not been looked at by that many people, so it is possible that improving on the Chlamtac et al result is within reach. Fourth, there's a range of questions that come to mind when looking at that paper, some hard, some easier, so it ought to be possible to work on this in a mixed breadth-first-search/depth-first-search manner so as to avoid being fruitlessly stuck with a smooth wall blocking all progress and all ideas: go in depth in the most promising direction, until one gets stuck, then branch off to another less hopeless direction, etc. Fifth, for people doing algorithms, it requires only a modest investment: read in depth a mere couple of background papers in addition to the Chlamtac et al paper. Sixth, if worst comes to worst and you do not get any new result out of your endeavour, at least you will have learnt about lift-and-project and about treewidth. Learning new tools and techniques is a net plus even if no research result comes out of that failed project. (http://terrytao.wordpress.com/career-advice/learn-the-power-of-other-mathematicians-tools/).
Friday, August 5, 2011
Research and the meaning of life
When a surprising new result comes out, we often try to understand what happened: What is new about this? How come we could not solve the problem earlier? Then a pattern appears. Often, exciting new results happen by making a connection between the problem at hand and a seemingly unrelated field. Connections between a problem and other fields can work magic, and gives insight into the hidden meaning of mathematical phenomena. Researchers who are transfers from a different field can have a great impact in that way, since they can "see" structure that is invisible to other, more mainstream researchers.
How can we hope to make such connections? A broad mathematical education is crucial for that. Knowing, not only the standard tools of our trade, but also results and techniques from related fields and even from unrelated fields (if one hopes to get lucky). That's why, before students start doing research and while they are doing research in the course of their PhD, they take courses not just in their area of specialty but also in other areas. In fact, in some departments I have visited (Berkeley, U. Washington,...), the faculty also sit on one another's lectures to try to broaden their knowledge. Mathematical culture enables one to find more meaning in casual remarks so as to develop them to create theorems.
If I don't have it, I don't know what I am missing. Then, at best, I prove results 'by hand' without being aware of the larger frame into which they fit.
Similarly culture enables one to find more meaning in life; but if I don't have it, I don't know what I am missing. Then I think that, say, museums are boring, and I cannot understand what people find in them.
How can we hope to make such connections? A broad mathematical education is crucial for that. Knowing, not only the standard tools of our trade, but also results and techniques from related fields and even from unrelated fields (if one hopes to get lucky). That's why, before students start doing research and while they are doing research in the course of their PhD, they take courses not just in their area of specialty but also in other areas. In fact, in some departments I have visited (Berkeley, U. Washington,...), the faculty also sit on one another's lectures to try to broaden their knowledge. Mathematical culture enables one to find more meaning in casual remarks so as to develop them to create theorems.
If I don't have it, I don't know what I am missing. Then, at best, I prove results 'by hand' without being aware of the larger frame into which they fit.
Similarly culture enables one to find more meaning in life; but if I don't have it, I don't know what I am missing. Then I think that, say, museums are boring, and I cannot understand what people find in them.
Thursday, August 4, 2011
What is the point of education?
This morning in Paris I walked from Gare de Lyon to my office.
As I got off the train, I looked at the metal and glass roof covering the 19th century station, taking in the monumental design of the construction and giving a brief thought to the industrial revolution. In the main hall I glanced at the tiny Doric-style pilasters on the upper wall, thinking about the original builders' efforts to beautify the place in spite of its purely utilitarian purpose, and trying to decide whether they looked good or kitsch. As I walked over to the next indoor space, the ceiling suddenly became a dark, uneven mass of modern insulation material, whose ugliness immediately made it obvious that the pilasters had indeed been beautiful.
The Charles de Gaulle bridge was blocked to traffic by a police car. The policeman was outside his car, half laying on the hood -- and he was holding a gun pointed at some guy standing just a few feet from him! I parsed the scene quickly. No other policeman around him. Some people nearby were walking peacefully, unaware of what was going on. And what was the guy doing? -- ah. Holding a camera and talking a picture of the policeman!
Farther on, a truck was lying on its side, all blackened and smoking, and next to it was a filmcrew. I stopped and gaped for a while as they were shooting a scene. Next year I will look for a police movie taking place in Paris, and try to recognize it. Meanwhile everyone ignored me. When I was a student, I could never stop on a Paris street for more than a moment before being rudely propositioned by strange men. What has changed in the intervening 25 years? Surely the only possible explanation, as I decided, was that Paris men must have become more considerate.
By the bridge, there was an old barge marked "Armée du Salut" and covered with graffiti. The Salvation Army in Paris used to have a barge designed by Le Corbusier, to provide sleeping quarters for homeless people in the winter. I wondered if that was it.
Walking along Gare d'Austerlitz, I admired the sculptures on the building's facade, as well as the coats of arms of the cities served by the trains from that station. Too bad I don't know the interpretation of their symbolism!
I passed several signs about officers who died fighting for the liberation of Paris from the German Occupation in August 1944. I tried vaguely to picture what it must have been like then, but my imagination failed me.
A sober-looking middle-aged beggar was sitting on the sidewalk. In front of him, two yellow coins were shining against the bright red felt of his hat. I did not add anything to it, but nodded hello in acknowledgement of his existence.
At the entrance of Jardin des plantes I was greeted by a stern-looking statue of Lamarck, with a sign claiming that he founded the theory of evolution. For the first time I noticed a funny inscription engraved on the base: "La postérité vous admirera. Elle vous vengera, mon père." (Posterity will admire you. It will be your revenge, my father.)
There is so much to see, everywhere in Paris! It is a feast for the eyes. The past, the present and the future meet in an amazingly stimulating mix.
The book Factory girls raises a question: what is the point of education? Today I thought of one answer. When we look around us, what we see awakens echoes in our mind, memories of things read in books or learned in school. Old ruins "speak" to us, events take on deeper meaning through references to other events. That knowledge adds an invisible dimension to our experience. In that way, it makes our life richer. The more culture we have, the more vivid those experiences. Ultimately, education helps us live a fuller life.
That's the answer which I plan to propose to my group of freshman students when we meet in September.
As I got off the train, I looked at the metal and glass roof covering the 19th century station, taking in the monumental design of the construction and giving a brief thought to the industrial revolution. In the main hall I glanced at the tiny Doric-style pilasters on the upper wall, thinking about the original builders' efforts to beautify the place in spite of its purely utilitarian purpose, and trying to decide whether they looked good or kitsch. As I walked over to the next indoor space, the ceiling suddenly became a dark, uneven mass of modern insulation material, whose ugliness immediately made it obvious that the pilasters had indeed been beautiful.
The Charles de Gaulle bridge was blocked to traffic by a police car. The policeman was outside his car, half laying on the hood -- and he was holding a gun pointed at some guy standing just a few feet from him! I parsed the scene quickly. No other policeman around him. Some people nearby were walking peacefully, unaware of what was going on. And what was the guy doing? -- ah. Holding a camera and talking a picture of the policeman!
Farther on, a truck was lying on its side, all blackened and smoking, and next to it was a filmcrew. I stopped and gaped for a while as they were shooting a scene. Next year I will look for a police movie taking place in Paris, and try to recognize it. Meanwhile everyone ignored me. When I was a student, I could never stop on a Paris street for more than a moment before being rudely propositioned by strange men. What has changed in the intervening 25 years? Surely the only possible explanation, as I decided, was that Paris men must have become more considerate.
By the bridge, there was an old barge marked "Armée du Salut" and covered with graffiti. The Salvation Army in Paris used to have a barge designed by Le Corbusier, to provide sleeping quarters for homeless people in the winter. I wondered if that was it.
Walking along Gare d'Austerlitz, I admired the sculptures on the building's facade, as well as the coats of arms of the cities served by the trains from that station. Too bad I don't know the interpretation of their symbolism!
I passed several signs about officers who died fighting for the liberation of Paris from the German Occupation in August 1944. I tried vaguely to picture what it must have been like then, but my imagination failed me.
A sober-looking middle-aged beggar was sitting on the sidewalk. In front of him, two yellow coins were shining against the bright red felt of his hat. I did not add anything to it, but nodded hello in acknowledgement of his existence.
At the entrance of Jardin des plantes I was greeted by a stern-looking statue of Lamarck, with a sign claiming that he founded the theory of evolution. For the first time I noticed a funny inscription engraved on the base: "La postérité vous admirera. Elle vous vengera, mon père." (Posterity will admire you. It will be your revenge, my father.)
There is so much to see, everywhere in Paris! It is a feast for the eyes. The past, the present and the future meet in an amazingly stimulating mix.
The book Factory girls raises a question: what is the point of education? Today I thought of one answer. When we look around us, what we see awakens echoes in our mind, memories of things read in books or learned in school. Old ruins "speak" to us, events take on deeper meaning through references to other events. That knowledge adds an invisible dimension to our experience. In that way, it makes our life richer. The more culture we have, the more vivid those experiences. Ultimately, education helps us live a fuller life.
That's the answer which I plan to propose to my group of freshman students when we meet in September.
Wednesday, August 3, 2011
Algorithms using lift-and-project
I was happy that my post on lift-and-project seemed to arouse interest. Since then, I browsed through a few papers to see how teaching lift-and-project might continue from there. I now have a plan:
Lecture 1: Introduction to lift-and-project, see previous post
Lecture 2: (Bienstock and Ozbay 2004) Consider independent set. If the underlying input graph has tree width bounded by a constant, then the Sherali-Adams lifted linear program is exact after only a constant number of lifts, meaning that its integrality gap equals 1 and that every solution of the lifted linear program is a convex combination of integer solutions.
Remember that the lifted variables can be interpreted as defining a distribution of integer solutions over the local set of vertices under consideration.
Then rounding a solution is easy: first pick the values v1,v2,...,vc (zero or one) of c variables in a first bag (x1,x2,...,xc) so that the "probability" y(x1=v1,x2=v2,...,xc=vc) is positive. Then repeatedy extend the values of a bag to a neighboring bag: if the neighboring bag has some variables (x1,x2,...,xd) in common with the old bag and some new variables (x'(d+1),...,x'c), pick the values for the new variables in a consistent manner, that is, so that
y(x1=v1,x2=v2,..xc=vc,x'(d+1)=v'(d+1),...,x'c=v'c) is positive.
Lecture 3: (Chlamtac Krauthgamer and Raghavendra 2010) Consider general demand sparsest cut. If the underlying input graph has tree width bounded by a constant r, then the Sherali-Adams lifted linear program has integrality gap O(1) after only a constant number of lifts. (The O(1) depends on r).
Then rounding a solution is easy: first sample the values v1,v2,...,vc (zero or one) of c variables in a first bag (x1,x2,...,xc) according to the distribution defined by the lifted variables y(x1=v1,x2=v2,...,xc=vc). Then repeatedy extend the values of a bag to a neighboring bag: if the neighboring bag has some variables (x1,x2,...,xd) in common with the old bag and some new variables (x'(d+1),...,x'c), sample the values for the new variables in a consistent manner, that is, according to the conditional distribution of the lifted LP variables for (x1,x2,...,xd,x'(d+1),...,x'c) given the values already chosen for variables (x1,x2,...,xd).
I believe that this sequence is a relatively simple presentation of lift-and-project for algorithms: the part about independent set is exact and, if reduced to its core and looked at from the right perspective, it can be made straightforward (maybe that will be material for another post). The part about sparsest cut is a new algorithmic result, the algorithm is a natural extension and the analysis, seen from a distance, feels right although it is a little bit technical - it uses a Markov flow graph, and going through that proof in class might be painful, but it's the best compromise I have found between the need for simplicity and elegance, and the desire to bring the class right at the threshold of open problems.
Lecture 1: Introduction to lift-and-project, see previous post
Lecture 2: (Bienstock and Ozbay 2004) Consider independent set. If the underlying input graph has tree width bounded by a constant, then the Sherali-Adams lifted linear program is exact after only a constant number of lifts, meaning that its integrality gap equals 1 and that every solution of the lifted linear program is a convex combination of integer solutions.
Remember that the lifted variables can be interpreted as defining a distribution of integer solutions over the local set of vertices under consideration.
Then rounding a solution is easy: first pick the values v1,v2,...,vc (zero or one) of c variables in a first bag (x1,x2,...,xc) so that the "probability" y(x1=v1,x2=v2,...,xc=vc) is positive. Then repeatedy extend the values of a bag to a neighboring bag: if the neighboring bag has some variables (x1,x2,...,xd) in common with the old bag and some new variables (x'(d+1),...,x'c), pick the values for the new variables in a consistent manner, that is, so that
y(x1=v1,x2=v2,..xc=vc,x'(d+1)=v'(d+1),...,x'c=v'c) is positive.
Lecture 3: (Chlamtac Krauthgamer and Raghavendra 2010) Consider general demand sparsest cut. If the underlying input graph has tree width bounded by a constant r, then the Sherali-Adams lifted linear program has integrality gap O(1) after only a constant number of lifts. (The O(1) depends on r).
Then rounding a solution is easy: first sample the values v1,v2,...,vc (zero or one) of c variables in a first bag (x1,x2,...,xc) according to the distribution defined by the lifted variables y(x1=v1,x2=v2,...,xc=vc). Then repeatedy extend the values of a bag to a neighboring bag: if the neighboring bag has some variables (x1,x2,...,xd) in common with the old bag and some new variables (x'(d+1),...,x'c), sample the values for the new variables in a consistent manner, that is, according to the conditional distribution of the lifted LP variables for (x1,x2,...,xd,x'(d+1),...,x'c) given the values already chosen for variables (x1,x2,...,xd).
I believe that this sequence is a relatively simple presentation of lift-and-project for algorithms: the part about independent set is exact and, if reduced to its core and looked at from the right perspective, it can be made straightforward (maybe that will be material for another post). The part about sparsest cut is a new algorithmic result, the algorithm is a natural extension and the analysis, seen from a distance, feels right although it is a little bit technical - it uses a Markov flow graph, and going through that proof in class might be painful, but it's the best compromise I have found between the need for simplicity and elegance, and the desire to bring the class right at the threshold of open problems.
Tuesday, August 2, 2011
Factory girls
Like every time I travel across many time zones, I spent the last few days waiting for the fog to clear from my brain. In the meantime I finished the book that is mandated reading for all Brown freshmen: Factory girls: from village to city in a changing China by Leslie Chang.
In September the new students will meet in small groups, one of them moderated by me, to discuss this year's book. The goal is to help new students make friends more quickly by giving them a conversation topic when they meet other students for the first time. Before the meeting I will receive a cheat-sheet outlining suggestions. During the summer, the students write an essay about the book, and I will also receive a copy of their essays. I will use them to help the discussion (and also to raise an early red flag if some student shows poor writing skills).
I wonder if the choice of books reflects the character of the university. On previous summers, we read: The places in between by Rory Stewart, about walking across Afghanistan right after the defeat of the Talibans, and The beak of the finch: a story of evolution in our time by Jonathan Weiner, a book that I didn't manage to finish -- on that year I heavily relied on the cheat-sheet! All of those books are about traveling to far away countries, perhaps showing Brown's support of its study-abroad program. Both Afghanistan and China are currently the subject of keen interest, perhaps a sign of Brown's involvment with political affairs.
What could we talk about during our discussion?
- At the most basic level, I could point out that the most common question asked by job interviewers in that book is: "Do you know computers?", and unashamedly take that opportunity to advertise for our CS course for non-majors.
- Another possible direction: why have a formal education? The girls from rural China succeed faster, in terms of money, if they don't waste time in college. They can send large amounts of money back home to their parents instead of being a drain on family finances. They go up the hierarchical ladder at work. If lack of formal education does not prevent professional success, then what is the point?
- The book mentions changing family dynamics: as the girls bring home lots of money, they also start having a say in family affairs. Will Brown students gain higher status in their families after a few months in college, and should they?
-------------------------------------------
In terms of the book itself, unfortunately it bears the mark of journalists-turned-writers. It's a good story, but I cannot say that I got much out of the 500-page book that I had not already understood in the first 100 pages. It did not build to any kind of climax, and the author carefully stayed away from fiction, refusing to say anything about her characters except as a scrupulous reporter, and refusing to pass judgment or express any personal opinion herself. Although the anecdotes are entertaining, they are not fully developped and after a while it becomes tiresome. I am not really recommending it to anyone who does not have a particular interest in the subject. But let's let the book speak for itself: here's an excerpt.
That day Chunming had stumbled on a new method of meeting men. Someone had posted a photograph of a beautiful woman on a matchmaking Web site but listed Chunming's phone number next to it. She wasn't sure if it was a mistake or a prank, but all day long she had been bombarded with phone calls from suitors.
Are you the woman in the picture?
Do you have long hair?
Are you 1.66 meters tall?
After dinner, Chunming went into the living room to watch a television serial about doctors in ancient Korea struggling to aid the residents of a leper colony. Chunming found their humanitarian efforts very moving, but she was constantly interrupted by phone calls from strange men.
"Hello," she would say. "Who is this?"
Listening. Then: "Yes, someone posted that picture and that information but it isn't mine. Only the phone number is mine."
Pause. "Never mind, we can still make friends," she would say in honeyed tones. "Where are you from? What do you do?"
(...)
"That woman must be really beautiful," Chunming said as she scrolled through her list of messages and missed calls.
"And yet when you tell them it's not you," I said, "they still go on talking to you."
"So many people in this city are so lonely," Ah Ning said.
In September the new students will meet in small groups, one of them moderated by me, to discuss this year's book. The goal is to help new students make friends more quickly by giving them a conversation topic when they meet other students for the first time. Before the meeting I will receive a cheat-sheet outlining suggestions. During the summer, the students write an essay about the book, and I will also receive a copy of their essays. I will use them to help the discussion (and also to raise an early red flag if some student shows poor writing skills).
I wonder if the choice of books reflects the character of the university. On previous summers, we read: The places in between by Rory Stewart, about walking across Afghanistan right after the defeat of the Talibans, and The beak of the finch: a story of evolution in our time by Jonathan Weiner, a book that I didn't manage to finish -- on that year I heavily relied on the cheat-sheet! All of those books are about traveling to far away countries, perhaps showing Brown's support of its study-abroad program. Both Afghanistan and China are currently the subject of keen interest, perhaps a sign of Brown's involvment with political affairs.
What could we talk about during our discussion?
- At the most basic level, I could point out that the most common question asked by job interviewers in that book is: "Do you know computers?", and unashamedly take that opportunity to advertise for our CS course for non-majors.
- Another possible direction: why have a formal education? The girls from rural China succeed faster, in terms of money, if they don't waste time in college. They can send large amounts of money back home to their parents instead of being a drain on family finances. They go up the hierarchical ladder at work. If lack of formal education does not prevent professional success, then what is the point?
- The book mentions changing family dynamics: as the girls bring home lots of money, they also start having a say in family affairs. Will Brown students gain higher status in their families after a few months in college, and should they?
-------------------------------------------
In terms of the book itself, unfortunately it bears the mark of journalists-turned-writers. It's a good story, but I cannot say that I got much out of the 500-page book that I had not already understood in the first 100 pages. It did not build to any kind of climax, and the author carefully stayed away from fiction, refusing to say anything about her characters except as a scrupulous reporter, and refusing to pass judgment or express any personal opinion herself. Although the anecdotes are entertaining, they are not fully developped and after a while it becomes tiresome. I am not really recommending it to anyone who does not have a particular interest in the subject. But let's let the book speak for itself: here's an excerpt.
That day Chunming had stumbled on a new method of meeting men. Someone had posted a photograph of a beautiful woman on a matchmaking Web site but listed Chunming's phone number next to it. She wasn't sure if it was a mistake or a prank, but all day long she had been bombarded with phone calls from suitors.
Are you the woman in the picture?
Do you have long hair?
Are you 1.66 meters tall?
After dinner, Chunming went into the living room to watch a television serial about doctors in ancient Korea struggling to aid the residents of a leper colony. Chunming found their humanitarian efforts very moving, but she was constantly interrupted by phone calls from strange men.
"Hello," she would say. "Who is this?"
Listening. Then: "Yes, someone posted that picture and that information but it isn't mine. Only the phone number is mine."
Pause. "Never mind, we can still make friends," she would say in honeyed tones. "Where are you from? What do you do?"
(...)
"That woman must be really beautiful," Chunming said as she scrolled through her list of messages and missed calls.
"And yet when you tell them it's not you," I said, "they still go on talking to you."
"So many people in this city are so lonely," Ah Ning said.
Subscribe to:
Posts (Atom)