There is the flea, who jumps from question to question in a seemingly haphazard manner, looking for food. Or the butterfly. We admire its speed, its brilliance, and its ability to connect seemingly disconnected ideas. It's like exploring the world of possibilities by breadth-first-search.

There is the mole, slowly digging forward with obstination, going into one direction and never giving up. We admire its obstination and courage to go through even horrible calculations or case analyses. It's like exploring the world of possibilities by depth-first-search.

Then there is the rest of us. We do some kind of mixture. When we collaborate with a mole, we get frustrated by its doggedness at times, when it is clear to us that the way forward to blocked and that those heavy-handed attempts will most likely be fruitless. When we collaborate with a butterfly, we get frustrated at times, because it keeps giving up and switching directions before we've had time to see whether that previous idea had any promise.

The best collaborators are those who are in a narrow range around our own style of research: when we switch questions, they are willing to give up because they're getting tired of getting nowhere. When we keep going, they follow happily because they think there might still be something to that idea, and, although they personally would give up, are willing to give it one more try for our sake.

## Monday, October 31, 2011

## Sunday, October 30, 2011

### Microphone education

You have been raised to put your hand over your mouth when you cough and bend your head slightly so that the possible viruses are projected downwards instead of towards your neighbors. It also muffles the noise of coughing by redirecting the noise down instead of across from you.

Do not apply this etiquette if you have a microphone attached to your shirt collar with the volume amplification set on "high"!

Do not apply this etiquette if you have a microphone attached to your shirt collar with the volume amplification set on "high"!

## Saturday, October 29, 2011

### The importance of being well connected

In politics, it is well known that connections are critical. When a

well-connected person needs something, they simply pick up their phone,

and give a quick call to a friend in the right place.

In research, being well connected is also an important asset. I have a

short list of "oracles" who can help me with thorny questions, each in

their respective area of specialty.

For example, the other day I was working with a colleague on a question

related to expanders and combinatorics on graphs. After we thought about

it for a bit, and searched the internet without success, I dropped an

email to Noga Alon. Less than an hour later, I got an answer!

Informative, precise, and with a reference to a directly relevant

paper. For efficient research, how precious it is to have the right

connections at the right time!

well-connected person needs something, they simply pick up their phone,

and give a quick call to a friend in the right place.

In research, being well connected is also an important asset. I have a

short list of "oracles" who can help me with thorny questions, each in

their respective area of specialty.

For example, the other day I was working with a colleague on a question

related to expanders and combinatorics on graphs. After we thought about

it for a bit, and searched the internet without success, I dropped an

email to Noga Alon. Less than an hour later, I got an answer!

Informative, precise, and with a reference to a directly relevant

paper. For efficient research, how precious it is to have the right

connections at the right time!

## Friday, October 28, 2011

### How to get an academic job?

How should students go about getting a job? The question came up in some recent comment. It's a tough one, but brought back a memory.

Once a relative asked her uncle: "You are so successful. How did you do it? How should I go about it? What job should I have, and what career should I pursue?" I waited with interest to hear what he might have to say. Here is what the successful young man answered: "No matter what you do, you will not be successful if you are not really into it. You've got to enjoy your work. So, why don't you figure out the things that interest you the most and make a list of the four or five most exciting jobs for you? Then, within that short list, you can look at other criteria such as opportunities, salary and career paths. But you've got to first give priority to your personal interests."

I loved that answer.

So, by analogy I would say: I believe that there is no way for people to be leading researchers unless they love what they do. A student thinking about going into academia should first think of the research areas that he or she is most interested in, make a short list of the fields that are most exciting for him or her personally. Then they can take into consideration the job market, trying to estimate, five years down the line, which subjects will be most important and will have the most openings.

That's my little piece of wisdom for the day! Not particularly surprising, not particularly unorthodox, but it might be good advice.

Once a relative asked her uncle: "You are so successful. How did you do it? How should I go about it? What job should I have, and what career should I pursue?" I waited with interest to hear what he might have to say. Here is what the successful young man answered: "No matter what you do, you will not be successful if you are not really into it. You've got to enjoy your work. So, why don't you figure out the things that interest you the most and make a list of the four or five most exciting jobs for you? Then, within that short list, you can look at other criteria such as opportunities, salary and career paths. But you've got to first give priority to your personal interests."

I loved that answer.

So, by analogy I would say: I believe that there is no way for people to be leading researchers unless they love what they do. A student thinking about going into academia should first think of the research areas that he or she is most interested in, make a short list of the fields that are most exciting for him or her personally. Then they can take into consideration the job market, trying to estimate, five years down the line, which subjects will be most important and will have the most openings.

That's my little piece of wisdom for the day! Not particularly surprising, not particularly unorthodox, but it might be good advice.

## Thursday, October 27, 2011

### Teaching a second programming language

If a Chinese person who has been learning French for a year now wants to learn Italian, how do you go about teaching them Italian? You don't start from scratch and painfully relate Italian to Chinese: instead, you leverage their knowledge of French and teach Italian as, roughly, a variant of French: you highlight the delta between those two relatively close languages.

Similarly, after 6 weeks of teaching Racket I have now switched to OCAML: last year the way in which I did it was to teach OCAML from scratch, only going much more quickly than when I started Racket 6 weeks before. As I was doing it, I realized that it was largely redundant and boring. So this year, I simply show OCAML and corresponding Racket code side by side, so that the students see that many of the differences are simply syntactic details that can be translated automatically. That gives me more time to focus on the differences and try to figure out the reasons for those differences.

In hindsight, it is obvious.

I wonder if there are any web resources to serve that kind of requests: "I want to learn computer language X; I already know computer language Y".

Similarly, after 6 weeks of teaching Racket I have now switched to OCAML: last year the way in which I did it was to teach OCAML from scratch, only going much more quickly than when I started Racket 6 weeks before. As I was doing it, I realized that it was largely redundant and boring. So this year, I simply show OCAML and corresponding Racket code side by side, so that the students see that many of the differences are simply syntactic details that can be translated automatically. That gives me more time to focus on the differences and try to figure out the reasons for those differences.

In hindsight, it is obvious.

I wonder if there are any web resources to serve that kind of requests: "I want to learn computer language X; I already know computer language Y".

## Wednesday, October 26, 2011

### Angry birds: a universal culture

I have recently met a surprisingly broad set of people who play Angry Birds on their iphone. Usually new things attract a specific age group, and might later propagate beyond the target group. But for Angry Birds, every age group seems to have been hit at the same time. The people who told me about their playing were of the following approximate ages: 8, 17, 20, 37, 58, and 72 years old. Even Bishop Tobin, the Catholic bishop of Providence, wrote about reaching level 6.

I tried in vain to think of an analog. Maybe in France in the late 19th century, when limericks making fun of current events were the fashion, a new facetious song or limerick would appear and rapidly spread through the population.

Maybe the game is good enough to attract every single person who has an addictive streak, regardless of their state in life.

Maybe it's a way to fill the empty moments of one's day. Boredom will disappear from our vocabulary. The time I spend staring at cracks in the wall of the dentist waiting room and finding patterns, standing at the bus stop watching the clouds, or sitting a a red light trying to plan my day, can now be filled playing Angry Birds instead. No more waste of any minute of our lives.

I tried in vain to think of an analog. Maybe in France in the late 19th century, when limericks making fun of current events were the fashion, a new facetious song or limerick would appear and rapidly spread through the population.

Maybe the game is good enough to attract every single person who has an addictive streak, regardless of their state in life.

Maybe it's a way to fill the empty moments of one's day. Boredom will disappear from our vocabulary. The time I spend staring at cracks in the wall of the dentist waiting room and finding patterns, standing at the bus stop watching the clouds, or sitting a a red light trying to plan my day, can now be filled playing Angry Birds instead. No more waste of any minute of our lives.

## Tuesday, October 25, 2011

### A luddite encounters Cool Whip

A friend, who I had asked for some whipped cream, brought me something called "Cool Whip" instead.

I examined it with perplexity. What was I supposed to do with it? The labels did not help:

The image showed a strawberry stuck in some white whipped-cream-like

thing. I opened the tub, stared at the white content, cautiously tried some:

definitely not the same consistency as whipped cream. The people around me

were equally ignorant (my social group does not intersect the Cool

Whip subculture, I guess). We prudently decided to not risk spoiling the

food by using it. So here it is now, sitting in my fridge until I am in a

bold, innovative mood, and willing to give it a try.

The same phenomenon occurs with technological gadgets and software. The

designer lives in a world full of those gadgets, and cannot imagine the

extent of the luddite's ignorance. It's an additional obstacle for us.

I examined it with perplexity. What was I supposed to do with it? The labels did not help:

*Now richer and creamier* (*among customers with a preference)!*

Original. Contains milk. Whipped topping net wt 8oz. Serving size 2 tbsp.

To thaw: [Place in fridge]. Storage: [in fridge]. For best results: [do not

thaw on countertop].Original. Contains milk. Whipped topping net wt 8oz. Serving size 2 tbsp.

To thaw: [Place in fridge]. Storage: [in fridge]. For best results: [do not

thaw on countertop].

The image showed a strawberry stuck in some white whipped-cream-like

thing. I opened the tub, stared at the white content, cautiously tried some:

definitely not the same consistency as whipped cream. The people around me

were equally ignorant (my social group does not intersect the Cool

Whip subculture, I guess). We prudently decided to not risk spoiling the

food by using it. So here it is now, sitting in my fridge until I am in a

bold, innovative mood, and willing to give it a try.

The same phenomenon occurs with technological gadgets and software. The

designer lives in a world full of those gadgets, and cannot imagine the

extent of the luddite's ignorance. It's an additional obstacle for us.

## Monday, October 24, 2011

### Microwaved lectures

This weekend I prepared a lecture on probabilistic embeddings of metrics by tree metrics (section 8.5 of the Williamson-Shmoys book). I streamlined the presentation a bit to get to a point where I may have the shortest, clearest proof (although still too complicated for a blog post), near-optimal from an NP perspective: the students will hopefully be able to follow easily.

However, it is not satisfactory. Why not? Because the students cannot lead. They have to follow me.

What would I want instead? In the P perspective, I would like the students to discover the algorithm and proof by themselves, perhaps by successive approximations, designing progressively more sophisticated algorithms, where each algorithm encounters an obstacle in the form of some hard input, and the hard input is dealt with by refining the algorithm. When the process is broken down in manageable pieces, the students can do their own design, like someone cooking from basic ingredients.

Unfortunately, in the present case, to teach in that way I am lacking in lecture time, preparation time, and depth of understanding, so the students will have to make do with a ready-made, pre-packaged proof that I will merely microwave during class.

However, it is not satisfactory. Why not? Because the students cannot lead. They have to follow me.

What would I want instead? In the P perspective, I would like the students to discover the algorithm and proof by themselves, perhaps by successive approximations, designing progressively more sophisticated algorithms, where each algorithm encounters an obstacle in the form of some hard input, and the hard input is dealt with by refining the algorithm. When the process is broken down in manageable pieces, the students can do their own design, like someone cooking from basic ingredients.

Unfortunately, in the present case, to teach in that way I am lacking in lecture time, preparation time, and depth of understanding, so the students will have to make do with a ready-made, pre-packaged proof that I will merely microwave during class.

## Sunday, October 23, 2011

### ITCS: where is the innovation?

I am debating whether to attend ITCS 2012. It's a chance to socialize with the research community. The big plus is that it's in my backyard. I wouldn't need to fly there. I wouldn't have to miss classes. I wouldn't even need to stay at a hotel.

How is it different from STOC/FOCS/SODA? With "innovative" in the title, I am looking for bold, daring, novel features in every aspect of the conference. The classic format has its value, but frankly, it can feel a bit staid. This "innovations" conference may be an opportunity to open the windows and let in some fresh air. This can happen, not only in the research, but also in the organization.

- What if they gathered the slides in advance and put them online so that we can look at the slides before attending a talk to help us decide whether we want to attend?

- What if people could attend the talks remotely? What if they had a mirror site in Seattle or Tsinghua, where there would be a secondary meeting gathering the locals?

- What if the audience could vote for the most interesting talks, and at the end of each day we would have the "best talk of the day" prize with a little gold star for the winner, like in kindergarden?

- What if people could, during the talk, send anonymous remarks such as "You just lost me there" in real time, so that the speaker may adjust his talk to his audience?

- What if each speaker gave two short talks, the first summarizing his contributions and the other one (maybe the next day) answering questions, with an interval in between for people to send in their questions? If there were no questions, then the second talk would simply be cancelled.

- What if the talk was given, not by the author, but by one of the program committee members, and the author was only there to contribute the slides and help answer questions?

- What if the contributions were paired up (as happens in economics), each of the two authors gave a 5-minute summary of their paper, and then they would argue about their results for the next half hour, with the help of the moderator and of the audience to steer the discussion in interesting directions with good questions?

There are so many possible innovations. Since this conference, unlike STOC or FOCS, is unencumbered by the constraints of tradition, why not try one innovation, and if it doesn't work, try another one next year? How else are we going to get away from the rut of mind-numbing sequences of technical talks? I wish this conference was less ponderous and took itself less seriously, was more willing to take risks even on the organizational side. I don't really care which innovation is chosen, as long as they do attempt to do something different.

The problem is the decisional structure. Who is going to take this kind of decisions? For any proposed innovation, any committee is sure to shoot it down, and the only consensual decision would be the status quo. So, I don't know how change can happen other than in tiny increments. Being bold may be impossible.

How is it different from STOC/FOCS/SODA? With "innovative" in the title, I am looking for bold, daring, novel features in every aspect of the conference. The classic format has its value, but frankly, it can feel a bit staid. This "innovations" conference may be an opportunity to open the windows and let in some fresh air. This can happen, not only in the research, but also in the organization.

**Innovation in the schedule.**Is the format going to be the usual sequence of 20-minute talks with no questions and an audience that is for the most part not fully engaged? Will I learn anything there, or will it simply be the usual - primarily a chance to catch up with my friends and colleagues? Microsoft Research, that is helping organize, has the technical power to try out some technical innovations. They could impress us.- What if they gathered the slides in advance and put them online so that we can look at the slides before attending a talk to help us decide whether we want to attend?

- What if people could attend the talks remotely? What if they had a mirror site in Seattle or Tsinghua, where there would be a secondary meeting gathering the locals?

- What if the audience could vote for the most interesting talks, and at the end of each day we would have the "best talk of the day" prize with a little gold star for the winner, like in kindergarden?

- What if people could, during the talk, send anonymous remarks such as "You just lost me there" in real time, so that the speaker may adjust his talk to his audience?

- What if each speaker gave two short talks, the first summarizing his contributions and the other one (maybe the next day) answering questions, with an interval in between for people to send in their questions? If there were no questions, then the second talk would simply be cancelled.

- What if the talk was given, not by the author, but by one of the program committee members, and the author was only there to contribute the slides and help answer questions?

- What if the contributions were paired up (as happens in economics), each of the two authors gave a 5-minute summary of their paper, and then they would argue about their results for the next half hour, with the help of the moderator and of the audience to steer the discussion in interesting directions with good questions?

There are so many possible innovations. Since this conference, unlike STOC or FOCS, is unencumbered by the constraints of tradition, why not try one innovation, and if it doesn't work, try another one next year? How else are we going to get away from the rut of mind-numbing sequences of technical talks? I wish this conference was less ponderous and took itself less seriously, was more willing to take risks even on the organizational side. I don't really care which innovation is chosen, as long as they do attempt to do something different.

**Innovation in the local organization.**Is it going to be another of those expensive events, an unmemorable, overpriced banquet at some high-end hotel? Instead, how about something completely different? For example, in this time of economic recession, how about paying $25 for each participant and taking them for dinner at a local soup kitchen (list here)? I bet almost no one among the participants has ever eaten at a soup kitchen, so it could be an interesting experience and would also subsidize the local social services.The problem is the decisional structure. Who is going to take this kind of decisions? For any proposed innovation, any committee is sure to shoot it down, and the only consensual decision would be the status quo. So, I don't know how change can happen other than in tiny increments. Being bold may be impossible.

## Saturday, October 22, 2011

### Creativity

Cris Moore once tried to teach me some English idioms that I, not being a native English speaker, was not familiar with. For example:

Isn't this the way in which creative thoughts often come up in research? We're kicking around random ideas, then someone says: "How about using x for xx?" or "Does this x remind you of xx?", relating x and xx, two completely different areas, techniques or results. Such remarks can be the source of great, original papers. That is why, when we evaluate PhD applications, I tend to give a bonus to students who have a strength outside CS: my hope is that one day they'll find a way to leverage in research their non-standard knowledge and bring in ideas from their other field of expertise.

*You're barking up both ends of the wrong stick.*

Never look a greek house in the mouth when he's down!

It took me a while to catch on to the fact that he was making fun of me by mixing and matching unrelated expressions.Never look a greek house in the mouth when he's down!

Isn't this the way in which creative thoughts often come up in research? We're kicking around random ideas, then someone says: "How about using x for xx?" or "Does this x remind you of xx?", relating x and xx, two completely different areas, techniques or results. Such remarks can be the source of great, original papers. That is why, when we evaluate PhD applications, I tend to give a bonus to students who have a strength outside CS: my hope is that one day they'll find a way to leverage in research their non-standard knowledge and bring in ideas from their other field of expertise.

## Friday, October 21, 2011

### Revenge

I am going to to participate in a discussion about women in academia, organized by the group "Feminists at Brown", but do not have much to say about discrimination against women in academia. I am not aware of having experienced it.

However, once, when I was a beginning researcher, I gave a talk at a Dimacs workshop. After the talk, a senior researcher came to me. I waited for him to speak up, eager to hear what he thought of my work and of my talk. He opened his mouth and said:

Many years passed before I took my revenge. A couple of years ago I heard Costis Daskalakis, then a beginning researcher, give a talk at a conference. Afterwards, we happened to take the elevator together. I turned to him, smiled and said sweetly:

How satisfying it is to be mean sometimes. Now there is one more man in the world who has experienced how things are sometimes for women. Sweet is revenge!

However, once, when I was a beginning researcher, I gave a talk at a Dimacs workshop. After the talk, a senior researcher came to me. I waited for him to speak up, eager to hear what he thought of my work and of my talk. He opened his mouth and said:

*"I liked your talk. You have a nice shirt."*I stared at him blankly, too disconcerted to know what to say. In that context, it was quite an offensive comment.Many years passed before I took my revenge. A couple of years ago I heard Costis Daskalakis, then a beginning researcher, give a talk at a conference. Afterwards, we happened to take the elevator together. I turned to him, smiled and said sweetly:

*"I liked your talk. You have a nice shirt."*He stared at me blankly, disconcerted, not knowing what to say.How satisfying it is to be mean sometimes. Now there is one more man in the world who has experienced how things are sometimes for women. Sweet is revenge!

## Thursday, October 20, 2011

### Some presidential pre-candidates on education

Herman Cain on education: "Education is the key to unlocking a prosperous future. At the heart of education should always be the students. Unfortunately, education has become weighed down with administration that has shifted the focus from educating students to maintaining an excessive level of bureaucracy through expanded unionization and regulation. It’s time to unbundle education from the federal government down to the local level."

Mitt Romney on education: "Our conservative agenda strengthens our family in part by, by putting our schools on track to be the best in the world again, because great schools start with great teachers. We'll insist on hiring teachers from the top third college graduates and we'll give better teachers better pay. School accountability, school choice, cyber schools will be priorities and we'll put parents and teachers back in charge of education, not fat-cat CEOs of the teachers' unions."

Rick Perry on education: " In 2026, I picture a nation filled with diverse people bound together by a commitment to liberty and a devotion to working hard to give their children a better life than their parents gave them. I see a people who can pray in their schools as they wish and towns across America that can publicly celebrate Christmas, Hanukkah, or nothing at all. I see an education system that is the envy of the world, controlled by parents and the people according to the beliefs of the communities in which they live. I see an energetic mix of public, charter, and private schools, delivering options so people can choose what is best for their children, rather than getting stuck because a too-powerful teachers' union or government bureaucrat tells them how they must learn. The result is an important balance of academic excellence, local values, and a firm understanding of our nation's core founding principles--all of which will carry our nation forward with new generations of American achievement."

Barack Obama on education (2008): "We’ll make sure that every child in this country gets a world-class education from the day they’re born until the day they graduate from college. What McCain is offering amounts to little more than the same tired rhetoric about vouchers. We need to move beyond the same debate we’ve been having for the past 30 years when we haven’t gotten anything done. We need to fix & improve our public schools, not throw our hands up and walk away from them. We need to uphold the ideal of public education, but we also need reform. That’s why I’ve introduced a comprehensive strategy to recruit an army of new quality teachers to our communities--and to pay them more & give them more support. We’ll invest in early childhood education programs so that our kids don’t begin the race of life behind the starting line and

(2009): "In a global economy where the most valuable skill you can sell is your knowledge, a good education is no longer just a pathway to opportunity--it is a prerequisite. And yet, we have one of the highest high school dropout rates of any industrialized nation. And half of the students who begin college never finish. This is a prescription for economic decline. So tonight, I ask every American to commit to at least one year or more of higher education or career training. This can be community college or a four-year school; vocational training or an apprenticeship. But every American will need to get more than a high school diploma. And dropping out of high school is no longer an option. It's not just quitting on yourself, it's quitting on your country. That's why

Words, words, words.

Mitt Romney on education: "Our conservative agenda strengthens our family in part by, by putting our schools on track to be the best in the world again, because great schools start with great teachers. We'll insist on hiring teachers from the top third college graduates and we'll give better teachers better pay. School accountability, school choice, cyber schools will be priorities and we'll put parents and teachers back in charge of education, not fat-cat CEOs of the teachers' unions."

Rick Perry on education: " In 2026, I picture a nation filled with diverse people bound together by a commitment to liberty and a devotion to working hard to give their children a better life than their parents gave them. I see a people who can pray in their schools as they wish and towns across America that can publicly celebrate Christmas, Hanukkah, or nothing at all. I see an education system that is the envy of the world, controlled by parents and the people according to the beliefs of the communities in which they live. I see an energetic mix of public, charter, and private schools, delivering options so people can choose what is best for their children, rather than getting stuck because a too-powerful teachers' union or government bureaucrat tells them how they must learn. The result is an important balance of academic excellence, local values, and a firm understanding of our nation's core founding principles--all of which will carry our nation forward with new generations of American achievement."

Barack Obama on education (2008): "We’ll make sure that every child in this country gets a world-class education from the day they’re born until the day they graduate from college. What McCain is offering amounts to little more than the same tired rhetoric about vouchers. We need to move beyond the same debate we’ve been having for the past 30 years when we haven’t gotten anything done. We need to fix & improve our public schools, not throw our hands up and walk away from them. We need to uphold the ideal of public education, but we also need reform. That’s why I’ve introduced a comprehensive strategy to recruit an army of new quality teachers to our communities--and to pay them more & give them more support. We’ll invest in early childhood education programs so that our kids don’t begin the race of life behind the starting line and

**offer a $4,000 tax credit to make college affordable for anyone who wants to go**. Because as the NAACP knows better than anyone, the fight for social justice and economic justice begins in the classroom."(2009): "In a global economy where the most valuable skill you can sell is your knowledge, a good education is no longer just a pathway to opportunity--it is a prerequisite. And yet, we have one of the highest high school dropout rates of any industrialized nation. And half of the students who begin college never finish. This is a prescription for economic decline. So tonight, I ask every American to commit to at least one year or more of higher education or career training. This can be community college or a four-year school; vocational training or an apprenticeship. But every American will need to get more than a high school diploma. And dropping out of high school is no longer an option. It's not just quitting on yourself, it's quitting on your country. That's why

**we will provide the support necessary for all young Americans to complete college**and meet a new goal: By 2020, America will once again have the highest proportion of college graduates in the world."Words, words, words.

## Wednesday, October 19, 2011

### Testing Sortedness

Sofya Raskhodnikova, in a talk, presented a problem that could be taught at the end of the semester of my undergraduate Algorithms course. It can be solved by elementary means using randomization. (It can also be tied to the problem of finding the longest increasing subsequence of an input sequence, a classic illustration of algorithmic techniques.) This builds on two papers, "Improved testing algorithms for monotonicity" by Dodis-Goldreich-Lehman-Raskhodnikov-Ron-Samorodnitsky, and "Transitive-Closure Spanners" by Bhattacharyya-Grigorescu-Jung-Raskhodnikova-Woodruff.

Given an array A of n items (numbers), you wish to check, quickly, whether the items are sorted or nearly sorted. By "check", I mean, with reasonable confidence (say, you're correct with probability 99%). By "quickly", I mean in logarithmic time. By "nearly sorted", I mean that only a few of the numbers are out of place: if we ignore 4% of the numbers (outliers), the rest is sorted.

Why would you wish to check that? Maybe, if you have some data that used to be sorted but that, after some lazy updates, is now slightly out of order, to test whether you should bother sorting your data again; or, if you're about to resort, to decide which sorting algorithm to use.

Here is the algorithm.

- Define a set S of n log n "edges" (pairs of items). Assuming A is in sorted order, those are the pairs that would have been compared if you had sorted using Quicksort and if your pivot was always the median of the subset of numbers being sorted in the current recursive call. Thus there are edges between A[n/2] and everybody else, edges between A[n/4] and everyone in the range [1...n/2], edges between A[3n/4] and everyone in the range (n/2..n], etc.

- Repeat log n times: pick an edge {i,j} from S uniformly at random, and check whether A[i] and A[j] are in the correct order relative to each other.

- Output "The array is nearly sorted" if and only if all the checks are successful.

Here is the analysis.

- If A is sorted then obviously all checks are successful and the output is correct

- If A is not sorted but is nearly sorted, with fewer than 4% of the items out of order, then the output could go either way.

- If A is far from being sorted, the central claim is that at least 0.01 n edges of S would fail the check. Then one of those edges would (probably) be found after a logarithmic number of tries.

Why does the claim hold?

Create a graph with vertex set A and with an edge between every pair {i,j} such that {A[i],A[j]} are in the wrong order. Note that the outliers are a minimum cardinality vertex cover of that graph. It is known (basic approximation algorithms fact) that the maximum matching M has size at least 1/2 times the minimum vertex cover, |M| >= |S|/2.

Mark the two endpoints of every edge of S that would fail the check. The number of edges of S that would fail the check is at least half of the number of marked vertices. For each {i,j} in the matching M defined above, by definition of Quicksort there is a k between i and j such that {i,k} and {k,j} are both in S. The central observation is that, since {A[i],A[j]} are in the wrong order, it must be that {A[i],A[k]} or {A[k],A[j]} are in the wrong order, so either i or j or both are marked. So the number of marked vertices is greater than or equal to |M|.

Putting those observations together, the number of edges of S that would fail the check is at least half of the number of marked vertices, so it is at least half the size of M, so it is at least a quarter of the number of outliers. So, if there are at least .04 n outliers, then there are at least .01 n edges of S that would fail their check. This proves the claim.

Given an array A of n items (numbers), you wish to check, quickly, whether the items are sorted or nearly sorted. By "check", I mean, with reasonable confidence (say, you're correct with probability 99%). By "quickly", I mean in logarithmic time. By "nearly sorted", I mean that only a few of the numbers are out of place: if we ignore 4% of the numbers (outliers), the rest is sorted.

Why would you wish to check that? Maybe, if you have some data that used to be sorted but that, after some lazy updates, is now slightly out of order, to test whether you should bother sorting your data again; or, if you're about to resort, to decide which sorting algorithm to use.

Here is the algorithm.

- Define a set S of n log n "edges" (pairs of items). Assuming A is in sorted order, those are the pairs that would have been compared if you had sorted using Quicksort and if your pivot was always the median of the subset of numbers being sorted in the current recursive call. Thus there are edges between A[n/2] and everybody else, edges between A[n/4] and everyone in the range [1...n/2], edges between A[3n/4] and everyone in the range (n/2..n], etc.

- Repeat log n times: pick an edge {i,j} from S uniformly at random, and check whether A[i] and A[j] are in the correct order relative to each other.

- Output "The array is nearly sorted" if and only if all the checks are successful.

Here is the analysis.

- If A is sorted then obviously all checks are successful and the output is correct

- If A is not sorted but is nearly sorted, with fewer than 4% of the items out of order, then the output could go either way.

- If A is far from being sorted, the central claim is that at least 0.01 n edges of S would fail the check. Then one of those edges would (probably) be found after a logarithmic number of tries.

Why does the claim hold?

Create a graph with vertex set A and with an edge between every pair {i,j} such that {A[i],A[j]} are in the wrong order. Note that the outliers are a minimum cardinality vertex cover of that graph. It is known (basic approximation algorithms fact) that the maximum matching M has size at least 1/2 times the minimum vertex cover, |M| >= |S|/2.

Mark the two endpoints of every edge of S that would fail the check. The number of edges of S that would fail the check is at least half of the number of marked vertices. For each {i,j} in the matching M defined above, by definition of Quicksort there is a k between i and j such that {i,k} and {k,j} are both in S. The central observation is that, since {A[i],A[j]} are in the wrong order, it must be that {A[i],A[k]} or {A[k],A[j]} are in the wrong order, so either i or j or both are marked. So the number of marked vertices is greater than or equal to |M|.

Putting those observations together, the number of edges of S that would fail the check is at least half of the number of marked vertices, so it is at least half the size of M, so it is at least a quarter of the number of outliers. So, if there are at least .04 n outliers, then there are at least .01 n edges of S that would fail their check. This proves the claim.

## Tuesday, October 18, 2011

### PPAD complaint

The other day I complained to Christos Papadimitriou about the name of the complexity class PPAD. He answered that he had not realized beforehand that one could see a reference to his own name embedded into it. Surprised, I asked: Really? Yes, really, he said. The first person to point it out was a reviewer. In fact, he added, if people were not allowed to define complexity classes by giving them names that were subsequences of their last name, then it wouldn't be fair to him!

## Monday, October 17, 2011

### Global warming inaction

Socolow (prof at Princeton) published an article explaining the cost of inaction regarding global warming. Pacala (also prof at Princeton) and him wrote a paper in

The cost of inaction

*Science*in 2004 proposing a way forward. Nothing was done, and seven years went by. The result: global warming mitigation will now be more difficult than seven years ago, and, even of stabilization within fifty years is achieved, there will be an additional 50 parts per million in equilibrium concentration of carbon dioxide.The cost of inaction

## Sunday, October 16, 2011

### The uncounting method

How do you write a program to list all words in {a,b} with x a's and y b's? You need to find a recursive structure.

How do you find a recursive structure? You write it out in full, for example, for x=2 and y=3, and you stare at the list until a pattern appears.

What do you do if the pattern does not appear?

That was my challenge in class the other day. I resolved it using the following uncounting method.

First, counting.

How many words are there? C(x+y,x), the binomial number.

Do you know any recursive formula for the binomial numbers? Yes: the Pascal triangle.

Let us write out the first few rows. How does one compute the next numbers?

With little effort, students remember or rediscover the recursive formulae C(n,x)=C(n-1,x)+C(n-1,x-1) .

Apply it here: C(x+y,x)=C(x+y-1,x)+C(x+y-1,x-1).

And now comes the uncounting method.

Step 1.

C(x+y,x) counts the number of words in {a,b} with x a's and y b's. Note that

C(x+y-1,x) counts the number of words in {a,b} with x a's and y-1 b's, and that

C(x+y-1,x-1) counts the number of words in {a,b} with x-1 a's and y b's.

Step 2.

So the recursive formula can be restated as:

the number of words in {a,b} with x a's and y b's equals

the number of words in {a,b} with x a's and y-1 b's plus

the number of words in {a,b} with x-1 a's and y b's.

Step 3.

Remove "number of" -- that's the

the words in {a,b} with x a's and y b's equal (i.e. are in bijection with)

the words in {a,b} with x a's and y-1 b's plus (i.e. disjoint union)

the words in {a,b} with x-1 a's and y b's.

Now, with this big hint, back to the pattern problem. You have written your list in full for x=2 and y=3. You stare at the list until a pattern appears, where now, the pattern you're looking for is a decomposition into two subsets: one corresponding to words with x=2-1=1 and y=3, and the other corresponding to words with x=2 and y=3-1=2. At this point, students see the pattern, and we are done.

I learned this from a course on bijective combinatorics, one of my favorite courses ever, taught by Viennot when I was a student.

How do you find a recursive structure? You write it out in full, for example, for x=2 and y=3, and you stare at the list until a pattern appears.

What do you do if the pattern does not appear?

That was my challenge in class the other day. I resolved it using the following uncounting method.

First, counting.

How many words are there? C(x+y,x), the binomial number.

Do you know any recursive formula for the binomial numbers? Yes: the Pascal triangle.

Let us write out the first few rows. How does one compute the next numbers?

With little effort, students remember or rediscover the recursive formulae C(n,x)=C(n-1,x)+C(n-1,x-1) .

Apply it here: C(x+y,x)=C(x+y-1,x)+C(x+y-1,x-1).

And now comes the uncounting method.

Step 1.

C(x+y,x) counts the number of words in {a,b} with x a's and y b's. Note that

C(x+y-1,x) counts the number of words in {a,b} with x a's and y-1 b's, and that

C(x+y-1,x-1) counts the number of words in {a,b} with x-1 a's and y b's.

Step 2.

So the recursive formula can be restated as:

the number of words in {a,b} with x a's and y b's equals

the number of words in {a,b} with x a's and y-1 b's plus

the number of words in {a,b} with x-1 a's and y b's.

Step 3.

Remove "number of" -- that's the

**uncounting**:the words in {a,b} with x a's and y b's equal (i.e. are in bijection with)

the words in {a,b} with x a's and y-1 b's plus (i.e. disjoint union)

the words in {a,b} with x-1 a's and y b's.

Now, with this big hint, back to the pattern problem. You have written your list in full for x=2 and y=3. You stare at the list until a pattern appears, where now, the pattern you're looking for is a decomposition into two subsets: one corresponding to words with x=2-1=1 and y=3, and the other corresponding to words with x=2 and y=3-1=2. At this point, students see the pattern, and we are done.

I learned this from a course on bijective combinatorics, one of my favorite courses ever, taught by Viennot when I was a student.

## Saturday, October 15, 2011

### How to create extra work for other people

In this time of recession and high unemployment, it is important to create job opportunities. I found a new way to create extra work for other people, thus contributing in a modest way to the need for additional jobs at Brown.

After class the other day, I picked up all my stuff and left the classroom in a hurry. The next day I got the following email from the Media Technology Services at Brown:

I returned it immediately. Because I am a Full Professor, no one expressed any disapproval of my actions. Who knows how much time they spent looking for it? But none of that showed in the graceful way in which they took it back and thanked me for bringing it back. It's the privilege of high Status. There is so much respect for faculty around here. I've been at Brown a number of years, but I still can't get used to it. At Brown, Professors Can Do No Wrong. I am always disturbed when an incident such as that one reminds me how sheltered we are.

After class the other day, I picked up all my stuff and left the classroom in a hurry. The next day I got the following email from the Media Technology Services at Brown:

*"When securing the room last evening, my technician was unable to locate the wireless microphone for Salomon 001. I'm wondering if you used the clip-on microphone during your class yesterday or saw it on the teaching podium."*I looked in my backpack, and there it was!I returned it immediately. Because I am a Full Professor, no one expressed any disapproval of my actions. Who knows how much time they spent looking for it? But none of that showed in the graceful way in which they took it back and thanked me for bringing it back. It's the privilege of high Status. There is so much respect for faculty around here. I've been at Brown a number of years, but I still can't get used to it. At Brown, Professors Can Do No Wrong. I am always disturbed when an incident such as that one reminds me how sheltered we are.

## Friday, October 14, 2011

### When you are not Steve Jobs

In high school, you are impatient to be in college, to focus on the subjects that interest you.

When you are in college, you are eager to be in graduate school, to do research full time.

When you are in graduate school, you are impatient to solve an interesting problem and get an assistant professor job.

When you are assistant professor, you are impatient to find a big result and get tenure.

When you are a tenured professor, you are impatient to develop a research group.

When you have a research group, you are always impatient to finish your current project in time for the next conference deadline.

And the next one.

And the next one.

And the next one.

...

And the next one.

One day someone will bring up the subject of retirement or death or promotion to higher administration. You will be shocked! You haven't yet gotten around to working on the things that you were most interested in. There was always some higher-priority task that needed to be done first. You had all those ideas that you wanted to explore later, once you had some free time, but that never happened. You will have been busy for many years, but will not have had a chance to do what you wanted. Perhaps you never even had a chance to figure out what those things were.

I look at my students hard at work. Surely no more than a dozen or two can be passionate enough about the material that they delight in spending long hours on it. I read the news about the dismal economic predictions. Most of them work hard, because they are afraid for their future. I see the relentless schedule of assignments - just for my course, this semester they will get 26 grades. It is one deadline after another, and there is never any time to step back. And they have four courses to take! Thanks to the fear-mongering media and to the crushing workload, they are already being trained, and are on their way to not becoming the next Steve Jobs.

When you are in college, you are eager to be in graduate school, to do research full time.

When you are in graduate school, you are impatient to solve an interesting problem and get an assistant professor job.

When you are assistant professor, you are impatient to find a big result and get tenure.

When you are a tenured professor, you are impatient to develop a research group.

When you have a research group, you are always impatient to finish your current project in time for the next conference deadline.

And the next one.

And the next one.

And the next one.

...

And the next one.

One day someone will bring up the subject of retirement or death or promotion to higher administration. You will be shocked! You haven't yet gotten around to working on the things that you were most interested in. There was always some higher-priority task that needed to be done first. You had all those ideas that you wanted to explore later, once you had some free time, but that never happened. You will have been busy for many years, but will not have had a chance to do what you wanted. Perhaps you never even had a chance to figure out what those things were.

I look at my students hard at work. Surely no more than a dozen or two can be passionate enough about the material that they delight in spending long hours on it. I read the news about the dismal economic predictions. Most of them work hard, because they are afraid for their future. I see the relentless schedule of assignments - just for my course, this semester they will get 26 grades. It is one deadline after another, and there is never any time to step back. And they have four courses to take! Thanks to the fear-mongering media and to the crushing workload, they are already being trained, and are on their way to not becoming the next Steve Jobs.

## Thursday, October 13, 2011

### Bored on the bus

Yesterday on the bus I was bored. I got out my tablet and copied the titles of every ad lining the sides of the bus.

- Drug recovery study: subjects wanted. Earn up to $200 by completing the study.

- Project Restore helps parents get back on track. You must have a child support order to participate. "I really love my kids and want to take care of them, but right now I can't pay my child support."

- Need health insurance? necesita Seguro Medico?

- Problems with both alcohol and smoking?

- You wouldn't let your kids eat THIS much sugar, so, why do you let them drink it?

- Looking for a job?

- "Going to bat for you!" List of services: [...] www.ricommunityaction.org

- Are you concerned about your drinking?

- Got questions? Get answers! AskRI.com

- pagaste para su viaje hoy con efectivo? e-fare 101

- Muchos cosas pueden suceder en un segundo - programa de prevencion de lesiones.

- Are you bothered by panic attacks, anxiety or worry? Brown university is looking for people for a study on anxiety.

What a selection. Just reading those ads is enough to make me slightly anxious!

- Drug recovery study: subjects wanted. Earn up to $200 by completing the study.

- Project Restore helps parents get back on track. You must have a child support order to participate. "I really love my kids and want to take care of them, but right now I can't pay my child support."

- Need health insurance? necesita Seguro Medico?

- Problems with both alcohol and smoking?

- You wouldn't let your kids eat THIS much sugar, so, why do you let them drink it?

- Looking for a job?

- "Going to bat for you!" List of services: [...] www.ricommunityaction.org

- Are you concerned about your drinking?

- Got questions? Get answers! AskRI.com

- pagaste para su viaje hoy con efectivo? e-fare 101

- Muchos cosas pueden suceder en un segundo - programa de prevencion de lesiones.

- Are you bothered by panic attacks, anxiety or worry? Brown university is looking for people for a study on anxiety.

What a selection. Just reading those ads is enough to make me slightly anxious!

## Wednesday, October 12, 2011

### From mountaineering to setting up a laptop

How do you untangle a rope? When the knots are few and loose, it is very easy, and just about any way will work. But climbers are as obsessed with runtime optimization as algorithms researchers. I learned this summer that the fastest way is to shake it.

How do you uncoil your power cord as you set up your laptop for class? Last year I used to do it by quickly undoing the loops one by one. This year, inspired by my mountaineering vacation, I have realized that the fastest way is to shake it. It works! I am saving at least a couple of seconds of preparation time at every lecture.

How do you uncoil your power cord as you set up your laptop for class? Last year I used to do it by quickly undoing the loops one by one. This year, inspired by my mountaineering vacation, I have realized that the fastest way is to shake it. It works! I am saving at least a couple of seconds of preparation time at every lecture.

## Tuesday, October 11, 2011

### On the cost of a college education

I have recently heard of a friend of a friend who is at a prestigious university (not Brown). She is a pre-med. She has no resources, but the university has been providing her with financial aid and helping her find paid work.

This year, as a junior, to save money she lives off-campus and commutes 2 hours a day. To earn money she has side jobs working 18 hours a week. It turns out that her grades in science are not quite good enough for her to go to med school, so she is considering becoming a physician's assistant instead. By the time she is done with her physician's assistant degree, she will be about 300000 dollars in debt. Three hundred thousand dollars!!

She thought of transferring to a cheaper school, but she would not get the diploma with the high-status university name that goes on it. As she is now a junior, it seems like a big waste of money to forsake that diploma by not doing the last leg of her studies there. At one point she thought of joining the army solely as a way to alleviate her mounting debt. When she becomes a physician's assistant, she will earn 90000 to 100000 dollars a year. She imagines that she will be able to use 60000 per year to pay back her debt, and then she could be done in five years. I imagine that, if she is careful, she will be able to use 30000 per year (already a heavy burden) to pay back her debt, and then, ten years down the line, perhaps, in her mid-thirties, she will finally be free.

Her parents, who are clearly not money-wise, did not advise her on that. She, young and euphoric about being admitted to a top school, did not see it coming. The university, proud of its generous need-blind policy, probably feels good about giving her no-interest or low-interest loans.

In reality she has fallen into a trap. Regarding the extra-curricula opportunities that her university offers - student life and clubs, athletic facilities, subsidized outings, travels and shows, etc. - she has no time to take advantage of them. The wealthy students can take some time for those, but as for her, all she does is study and work. The wealthy students, if their academic level is borderline for med school, can focus all of their energy on improving their grades, but as for her, she has to, for about 30 hours per week (if one includes the commute time), take care of money worries. In a way she, who is poor, is subsidizing the education of the richer students.

This year, as a junior, to save money she lives off-campus and commutes 2 hours a day. To earn money she has side jobs working 18 hours a week. It turns out that her grades in science are not quite good enough for her to go to med school, so she is considering becoming a physician's assistant instead. By the time she is done with her physician's assistant degree, she will be about 300000 dollars in debt. Three hundred thousand dollars!!

She thought of transferring to a cheaper school, but she would not get the diploma with the high-status university name that goes on it. As she is now a junior, it seems like a big waste of money to forsake that diploma by not doing the last leg of her studies there. At one point she thought of joining the army solely as a way to alleviate her mounting debt. When she becomes a physician's assistant, she will earn 90000 to 100000 dollars a year. She imagines that she will be able to use 60000 per year to pay back her debt, and then she could be done in five years. I imagine that, if she is careful, she will be able to use 30000 per year (already a heavy burden) to pay back her debt, and then, ten years down the line, perhaps, in her mid-thirties, she will finally be free.

Her parents, who are clearly not money-wise, did not advise her on that. She, young and euphoric about being admitted to a top school, did not see it coming. The university, proud of its generous need-blind policy, probably feels good about giving her no-interest or low-interest loans.

In reality she has fallen into a trap. Regarding the extra-curricula opportunities that her university offers - student life and clubs, athletic facilities, subsidized outings, travels and shows, etc. - she has no time to take advantage of them. The wealthy students can take some time for those, but as for her, all she does is study and work. The wealthy students, if their academic level is borderline for med school, can focus all of their energy on improving their grades, but as for her, she has to, for about 30 hours per week (if one includes the commute time), take care of money worries. In a way she, who is poor, is subsidizing the education of the richer students.

## Monday, October 10, 2011

### Eli Upfal is my cousin!

As I am deciding not to go to a workshop in memory of Philippe Flajolet this December, I have looked at my academic ancestry using the Mathematics genealogy project. It only takes five generations to go from me, via him, back in time until one goes across from computer science to mathematics, to Schutzenberger. Then we quickly get to a dense sequence of illustrious ancestors, all the way back to Poisson, Lagrange, and finally Euler, who had more than 60000 descendants.

I wondered: with so many people tracing their genealogy back to Euler, is Euler an academic Eve? Are we all cousins via him?

For example Eli Upfal is a distant cousin: we have Darboux (PhD 1866) as our closest common ancestor.

But the answer is negative: Yuval Peres's lineage takes him back to Gauss and Leibniz, but we are not related.

I wondered: with so many people tracing their genealogy back to Euler, is Euler an academic Eve? Are we all cousins via him?

For example Eli Upfal is a distant cousin: we have Darboux (PhD 1866) as our closest common ancestor.

But the answer is negative: Yuval Peres's lineage takes him back to Gauss and Leibniz, but we are not related.

## Sunday, October 9, 2011

### Algorithms: a success story (Part 3/2)

To recap:

1- an applied problem was modeled as a standard combinatorial optimization graph problem (prize-collecting Steiner tree).

2- an algorithm was designed for it, and the authors write that this was critical to the project's success. It is based on a general-purpose algorithmic design paradigm that is just now starting to receive a little bit of attention in TCS.

3 - the algorithm was implemented.

4- the program was used for the input arising from the applied problem. That input was neither random nor grid-like nor anything so well structured (in which cases some ad hoc heuristic might have been better suited than general-purpose algorithmic techniques), but seemed like a pretty arbitrary graph.

Is this about algorithms? Yes.

Did this work have impact? Yes.

Is this good work? I believe so.

Would it have found its place at SODA? No.

I never see any paper of that type at SODA. It would not fit in, because it does not have a theorem. When I go to Operations Research conferences, I see some presentations of the type: "Here is a problem that came up in my company (for example, a scheduling problem). Here is how I modeled it, and the heuristic I used to solve it. Here are my experimental results after implementation. We beat the previous results by x%." But I never see that kind of presentations at SODA. Isn't that regrettable? Even if such presentations are sometimes not so exciting theoretically, wouldn't they serve an important role in keeping us grounded, connected to the real world, and in helping guide our taste?

The ALENEX workshop might serve that purpose, but in reality I don't think it does. As far as I can tell, it's mostly about implementing algorithms - taking the proof-of-concept that a high-level algorithm really is, and translating it into a real program, dealing along the way with a host of issues that come up. A necessary step for sure, to prevent sophisticated algorithms from becoming disconnected from programs, but it's only about linking steps 2 and 3 in the above list, not about the context given by steps 1 and 4 in the above list.

The thing that I find really challenging is step 4. Step 1 is easier. We do, once in a while, read papers from other fields and try to make up a theoretical model to capture what seems to us to be the interesting features. But then we go off and merrily design and analyze algorithms for that model, without ever going to step 4 (actually, we usually don't even get to step 3). All it gives us is a good motivational story for the introduction, and a way to feel good, reassuring ourselves that what we do potentially matters and is hypothetically relevant to something. But that hypothesis is never put to the test.

If that was just my research

1- an applied problem was modeled as a standard combinatorial optimization graph problem (prize-collecting Steiner tree).

2- an algorithm was designed for it, and the authors write that this was critical to the project's success. It is based on a general-purpose algorithmic design paradigm that is just now starting to receive a little bit of attention in TCS.

3 - the algorithm was implemented.

4- the program was used for the input arising from the applied problem. That input was neither random nor grid-like nor anything so well structured (in which cases some ad hoc heuristic might have been better suited than general-purpose algorithmic techniques), but seemed like a pretty arbitrary graph.

Is this about algorithms? Yes.

Did this work have impact? Yes.

Is this good work? I believe so.

Would it have found its place at SODA? No.

I never see any paper of that type at SODA. It would not fit in, because it does not have a theorem. When I go to Operations Research conferences, I see some presentations of the type: "Here is a problem that came up in my company (for example, a scheduling problem). Here is how I modeled it, and the heuristic I used to solve it. Here are my experimental results after implementation. We beat the previous results by x%." But I never see that kind of presentations at SODA. Isn't that regrettable? Even if such presentations are sometimes not so exciting theoretically, wouldn't they serve an important role in keeping us grounded, connected to the real world, and in helping guide our taste?

The ALENEX workshop might serve that purpose, but in reality I don't think it does. As far as I can tell, it's mostly about implementing algorithms - taking the proof-of-concept that a high-level algorithm really is, and translating it into a real program, dealing along the way with a host of issues that come up. A necessary step for sure, to prevent sophisticated algorithms from becoming disconnected from programs, but it's only about linking steps 2 and 3 in the above list, not about the context given by steps 1 and 4 in the above list.

The thing that I find really challenging is step 4. Step 1 is easier. We do, once in a while, read papers from other fields and try to make up a theoretical model to capture what seems to us to be the interesting features. But then we go off and merrily design and analyze algorithms for that model, without ever going to step 4 (actually, we usually don't even get to step 3). All it gives us is a good motivational story for the introduction, and a way to feel good, reassuring ourselves that what we do potentially matters and is hypothetically relevant to something. But that hypothesis is never put to the test.

If that was just my research

*modus operandi*for me personally, it would not be a big deal: I concentrate on the section of the work where my skills lie, I do my part there and others will do their part as well, and altogether the field can advance smoothly. But when it is the entire field that seems to share my lack of concern for demonstrated ultimate practical impact, then I think that we might have a problem.## Saturday, October 8, 2011

### Students at Brown are impressive

This week I taught higher-order procedures and anonymous procedures (lambda). I said, among other things, that a high-order procedure is a procedure that takes a procedure as one of its arguments. I said, among other things, that lambda enables you to define a function anonymously, without giving it a name. Here are some of the very first questions I got:

1 - Can a higher-order procedure be called with itself as its own argument?

2 - How do you write a recursive procedure using lambda? Since it does not have a name, how do you write the recursive call?

I was just blown away. My students are so smart. A little bit on the crazy side, but amazingly creative.

1 - Can a higher-order procedure be called with itself as its own argument?

2 - How do you write a recursive procedure using lambda? Since it does not have a name, how do you write the recursive call?

I was just blown away. My students are so smart. A little bit on the crazy side, but amazingly creative.

## Friday, October 7, 2011

### Steve Jobs

Steve Jobs and Henry Ford: revolutionary American entrepreneurs. Ford was antisemitic; Jobs, I am sure, also had his flaws. But both transformed society in previously unforeseen ways.

### Algorithms: a success story (Part 2/2)

The paper is called: "Finding undetected protein associations in cell signaling by belief propagation", the method is belief propagation, and the authors are Bailly-Bechet, Borgs, Braunstein, Chayes, Dagkessamanskaia, Francois and Zecchina. On benchmarks, their algorithm, compared to some CPLEX-based algorithm, finds Steiner tree solutions that are marginally better (by about 1%), but more importantly, the runtime is also better, by almost two orders of magnitude. So, how do they "solve" prize-collecting Steiner tree with belief propagation? Here is the idea, as far as I understand it.

Consider two adjacent vertices j and i. Let P(d(j),p(j), i) be defined as the probability that j is in the state (d(j),p(j)) in a certain graph: in the case where p(j) is different from i, it is the graph where every edge adjacent to i is removed; in the case where p(j)=i, it is the graph where every edge adjacent to i is removed, except {i,j}. Then the tree has to pay the cost of the edge from j to p(j), and, given the state of j, the states of the other neighbors k of j are essentially independent from one another, or at least, we hallucinate that that is the case, as if vertex {j} was a cut:

P(d(j),p(j),i)= exp(-b cost({j,p(j)}))*prod[ Q(k,d(j),p(j))],

where the product is over every neighbor k of j other than i, and Q is the probability that, in a certain graph, k is in a state consistent with (d(j),p(j)):

Q(k,d(j),p(j))=sum P(d(k),p(k),i),

where the sum is over (d(k),p(k)) compatible with (d(j),p(j)).

When the graph is a tree, if we write those equations going bottom up in the tree, we see that they are equivalent to a simple dynamic program to compute the distribution, so these equations exactly capture the distribution. When the graph has only one cycle, this approach has also been shown to be correct. When the graph is sparse with high girth and the influence of values on the objective decays quickly, one intuitively expects this to work reasonably well, but theoretically it's a big mess, both in terms of convergence and in terms of guarantees on the limit solution.

P(d(j),p(j),i)[t+1] = exp(-b cost({j,p(j)}))*prod[ Q(k,d(j),p(j))[t]]

Q(k,d(j),p(j))[t+1] = sum P(d(k),p(k),i)[t],

That fixed point can then be reinterpreted as a particular Steiner tree.

That's it!

**Step one:**model the problem locally. Consider a Steiner tree. Root it at some vertex r and label each vertex i of the tree with its distance d(i) to r on the tree and its parent p(i) in the tree; label each vertex i not in the tree with some convention, for example, d(i) arbitrary and p(i)=0. A configuration consists of a value (d(i),p(i)) for each vertex of the graph, such that d(r)=0 and such that neighboring vertices have consistent values (in particular d(p(i))=d(i)-1 for i in the tree and not equal to r). We now have a banal constraint programming problem.**Step two:**borrow intuition from statistical physics. Take a parameter b and define a distribution on Steiner trees, such that each tree T has probability proportional to exp(-b cost(T)). When b goes to infinity, the distribution is concentrated on the optimal Steiner tree. The crucial step: we now write the mysterious-looking, mysterious-sounding "cavity equations". (Those have nothing to do with the Brown CAVE project.)Consider two adjacent vertices j and i. Let P(d(j),p(j), i) be defined as the probability that j is in the state (d(j),p(j)) in a certain graph: in the case where p(j) is different from i, it is the graph where every edge adjacent to i is removed; in the case where p(j)=i, it is the graph where every edge adjacent to i is removed, except {i,j}. Then the tree has to pay the cost of the edge from j to p(j), and, given the state of j, the states of the other neighbors k of j are essentially independent from one another, or at least, we hallucinate that that is the case, as if vertex {j} was a cut:

P(d(j),p(j),i)= exp(-b cost({j,p(j)}))*prod[ Q(k,d(j),p(j))],

where the product is over every neighbor k of j other than i, and Q is the probability that, in a certain graph, k is in a state consistent with (d(j),p(j)):

Q(k,d(j),p(j))=sum P(d(k),p(k),i),

where the sum is over (d(k),p(k)) compatible with (d(j),p(j)).

When the graph is a tree, if we write those equations going bottom up in the tree, we see that they are equivalent to a simple dynamic program to compute the distribution, so these equations exactly capture the distribution. When the graph has only one cycle, this approach has also been shown to be correct. When the graph is sparse with high girth and the influence of values on the objective decays quickly, one intuitively expects this to work reasonably well, but theoretically it's a big mess, both in terms of convergence and in terms of guarantees on the limit solution.

**Step three:**To solve the cavity equations, use an iterative method from some perhaps random starting point, until a fixed point is reached.P(d(j),p(j),i)[t+1] = exp(-b cost({j,p(j)}))*prod[ Q(k,d(j),p(j))[t]]

Q(k,d(j),p(j))[t+1] = sum P(d(k),p(k),i)[t],

That fixed point can then be reinterpreted as a particular Steiner tree.

**Step four:**to make the method effective, use various tricks, clever ideas and hacks to speed it up and make it more convergent: take logs, simplify the set of variables, get rid of the "guess" of r, add some small random perturbation to eliminate possible cycles.That's it!

## Thursday, October 6, 2011

### How not to teach runtime analysis

The design and analysis of algorithms is my area of specialty: I know it like the back of my hand, and do not need to prepare for a freshman level class on running time. I can always improvise examples to illustrate my points. Or so I thought.

Here is a question I asked in class.

Suppose you have a program that, on data of size n, takes one minute to complete. How long would it take on data of size 10n, if the runtime is:

a) T(n)= n (linear)

b) T(n)=n^2 (quadratic)

c) T(n)=2^n (exponential)

Here are the answers I got.

a) T(10n)=10n = 10 T(n) so it would take ten times as long: 10 minutes.

b) T(10n)=100n^2 = 100 T(n) so it would take one hundred times as long: 1 hour and 40 minutes.

c) T(10n)= 2^{10n}= (T(n))^{10} so it would take time 1^{10}, which equals one: 1 minute.

So much for my pedagogical presentation of the growth rate of functions.

Here is a question I asked in class.

Suppose you have a program that, on data of size n, takes one minute to complete. How long would it take on data of size 10n, if the runtime is:

a) T(n)= n (linear)

b) T(n)=n^2 (quadratic)

c) T(n)=2^n (exponential)

Here are the answers I got.

a) T(10n)=10n = 10 T(n) so it would take ten times as long: 10 minutes.

b) T(10n)=100n^2 = 100 T(n) so it would take one hundred times as long: 1 hour and 40 minutes.

c) T(10n)= 2^{10n}= (T(n))^{10} so it would take time 1^{10}, which equals one: 1 minute.

So much for my pedagogical presentation of the growth rate of functions.

## Wednesday, October 5, 2011

### Algorithms: a success story (Part 1 /2)

Protein interactions follow signaling pathways whose cascading effects cause some diseases. Past experiments have harvested much information, not always very reliable, on which pairs of proteins interact with each other. From that information, how can one infer entire subgraphs that, together, determine the function?

Define a graph where the vertices are proteins and the edges are interactions between proteins.

Give a cost to each edge, depending on how confident you are that the experimental data shows interaction -- cost zero if you know with certainty that there is interaction. Give a weight to each vertex, depending on the differential expression of that protein -- high weight if the protein is significant, weight zero if you are not interested in that protein.

Then the problem can be modeled as a prize-collecting Steiner tree problem. The objective is to find a min cost tree connecting the vertices of positive weight, where vertices can be omitted by paying a penalty equal to their weight:

Min (cost (tree) + weight(vertices not in tree)).

Since there is no natural absolute scale common to edge costs and to vertex weights, it makes sense to use a scaling parameter lambda and find:

Min (cost (tree) + lambda*weight(vertices not in tree)).

Then the human user can look at the outputs produced for a range of values of lambda (as lambda grows, fewer and fewer vertices are connected and the tree becomes smaller and smaller) and eyeball the most interesting one.

In a paper I looked at, the authors do just that. They ran a prize-collecting Steiner tree algorithm on a yeast protein network. They were able to find pathways that had already previously been found by other means. The Steiner tree, predictably, contains vertices of high weight ("proteins differentially expressed"), but also Steiner vertices, possibly of low weight but serving to bridge subparts of the tree. One of the Steiner vertices they found, COS8, was "a gene of unknown function" that people had not previously paid much attention to.

They then proceeded to run biological experiments in the lab to test COS8, and, lo and behold! They found that keeping or deleting COS8 from the strains had a critical effect.

What gets much of the credit for this success story? Algorithmic design. The reason why the authors were able to run their program on that data in such an effective manner was that their algorithm was faster and better than previous methods. In fact, this is an ideal setting for algorithmics: one does not need an exact answer, since a good enough approximation algorithm suffices; and the problem is a well-studied type of variant of a classic combinatorial optimization problem.

The questions that the interested reader will ask, I am sure, is: what was the algorithmic technique used to get this breakthrough? And who are the researchers, in the approximation algorithms community, who did this masterful piece of algorithmic design?

The answer will wait for another post.

Define a graph where the vertices are proteins and the edges are interactions between proteins.

Give a cost to each edge, depending on how confident you are that the experimental data shows interaction -- cost zero if you know with certainty that there is interaction. Give a weight to each vertex, depending on the differential expression of that protein -- high weight if the protein is significant, weight zero if you are not interested in that protein.

Then the problem can be modeled as a prize-collecting Steiner tree problem. The objective is to find a min cost tree connecting the vertices of positive weight, where vertices can be omitted by paying a penalty equal to their weight:

Min (cost (tree) + weight(vertices not in tree)).

Since there is no natural absolute scale common to edge costs and to vertex weights, it makes sense to use a scaling parameter lambda and find:

Min (cost (tree) + lambda*weight(vertices not in tree)).

Then the human user can look at the outputs produced for a range of values of lambda (as lambda grows, fewer and fewer vertices are connected and the tree becomes smaller and smaller) and eyeball the most interesting one.

In a paper I looked at, the authors do just that. They ran a prize-collecting Steiner tree algorithm on a yeast protein network. They were able to find pathways that had already previously been found by other means. The Steiner tree, predictably, contains vertices of high weight ("proteins differentially expressed"), but also Steiner vertices, possibly of low weight but serving to bridge subparts of the tree. One of the Steiner vertices they found, COS8, was "a gene of unknown function" that people had not previously paid much attention to.

They then proceeded to run biological experiments in the lab to test COS8, and, lo and behold! They found that keeping or deleting COS8 from the strains had a critical effect.

What gets much of the credit for this success story? Algorithmic design. The reason why the authors were able to run their program on that data in such an effective manner was that their algorithm was faster and better than previous methods. In fact, this is an ideal setting for algorithmics: one does not need an exact answer, since a good enough approximation algorithm suffices; and the problem is a well-studied type of variant of a classic combinatorial optimization problem.

The questions that the interested reader will ask, I am sure, is: what was the algorithmic technique used to get this breakthrough? And who are the researchers, in the approximation algorithms community, who did this masterful piece of algorithmic design?

The answer will wait for another post.

## Tuesday, October 4, 2011

### Side effects of the recession

The INS people tell me that most people cannot afford the few hundred dollars needed to apply for a green card or for naturalization. Their workload has decreased significantly One result is that we get better, more timely service, and most importantly, there has been a metamorphosis of the INS employees, from grumpy, harried people yelling abuse at non-citizens, to courteous, smiling, helpful staff.

My yard has become enormously popular with the local wildlife. Birds and squirrels congregate around the bird feeder as soon as I fill it up. Am I one of the rare ones who still buy wild bird seeds?

My yard has become enormously popular with the local wildlife. Birds and squirrels congregate around the bird feeder as soon as I fill it up. Am I one of the rare ones who still buy wild bird seeds?

## Monday, October 3, 2011

### Study guide for the naturalization test

The INS gives a booklet for people to study when they prepare the test taken to become a US citizen. There are one hundred questions whose answers must be memorized, of which about 30 pertain to history. On first look, the questions and answers seemed pretty well-written, simple but important.

Only upon reflection does one realize that what matters is not what is there but what is

The choices are guided by the following considerations: "By learning our shared history, you will be able to understand our nation's traditions, milestones, and common civic values. Our country is independent because of the strength, unity, and determination of our forefathers. It is important for future Americans to know this story. We are people working towards great ideals and principles guided by equality and fairness. This is important to keep our country free."

There are exactly 3 Q&A about the history before the war of Independence. Here they are:

- Q: What is one reason colonists came to America?

- A: Freedom, political liberty, religious freedom, economic opportunity, to practice their religion, or to escape persecution.

- Q: Who lived in American before the Europeans arrived?

- A: American Indians, or Native Americans.

- Q: What group of people was taken to American and sold as slaves?

- A: Africans, or people from Africa.

Christopher Columbus has disappeared from the list of basic facts of American history, as though his legacy did not matter.

There are 57 questions about the US federal and state governments, but not a single mention of the United Nations.

There is a question about who the US fought during WWII, but no mention of who the Allies were.

Only upon reflection does one realize that what matters is not what is there but what is

**not**there. It is those omissions that best reveal bias.The choices are guided by the following considerations: "By learning our shared history, you will be able to understand our nation's traditions, milestones, and common civic values. Our country is independent because of the strength, unity, and determination of our forefathers. It is important for future Americans to know this story. We are people working towards great ideals and principles guided by equality and fairness. This is important to keep our country free."

There are exactly 3 Q&A about the history before the war of Independence. Here they are:

- Q: What is one reason colonists came to America?

- A: Freedom, political liberty, religious freedom, economic opportunity, to practice their religion, or to escape persecution.

- Q: Who lived in American before the Europeans arrived?

- A: American Indians, or Native Americans.

- Q: What group of people was taken to American and sold as slaves?

- A: Africans, or people from Africa.

Christopher Columbus has disappeared from the list of basic facts of American history, as though his legacy did not matter.

There are 57 questions about the US federal and state governments, but not a single mention of the United Nations.

There is a question about who the US fought during WWII, but no mention of who the Allies were.

## Sunday, October 2, 2011

### A rant about Money

- At the Microsoft 20th anniversary celebration, there was a talk about optimizing hospital readmissions. Many Medicare patients are readmitted at a hospital within 30 days of being released from a previous stay, a frequent sign of improper handling of the situation. How can one do better? Some method apparently decreases the number of readmissions by 35%, by increasing the cost (of care for those patients, I imagine) by 5%. Instead, the method presented decreased the number of readmissions by only 20%, but, instead of increasing costs,

I wondered: is that the right measure? It is difficult to understand, first, why reducing the number of readmissions is the objective (it seems very different from "good health care", whatever that might be), second, if we accept that it is the objective, why reducing it less but saving money is better than reducing it more but spending money.

- Another talk was about news aggregators. Instead of reading news directly from their favorite newspaper, more and more people read news accessed via a news aggregator or facebook mentions from friends. The speaker asked: does that help newspapers, or does it hurt newspapers? Then he showed that people end up reading newspapers more than before. The implication seems to be that the evolution should be good for newspapers.

I wondered: is that the right measure? What interests me, as a user, is whether we are better informed. Does this change give us better access to better information? Are there fewer events out there that I would like to hear about but never even know exist? Are articles more thoughtful and better researched? The question of whether the evolution brings (or should bring) newspapers more or less money, although not independent, is in itself quite ancillary to that principal concern.

- The last issue of The Atlantic had an article, "Where the skills are", about cities.

- The Washington Post headline on Saturday: "As Nobel Prize season starts, who will get those lucky, lucrative calls?" So, the main reason why someone would hope to receive a Nobel Prize is the money.

- Americans, questioning the cost of college, look at the tradeoff between the expenses and debts incurred to earn a college degree, and the increased salary that a degree later gives you. So, apparently people go to college solely so that they will earn more later, and it is assumed that the benefits of college are captured by the change in pay.

Money is the ultimate measure of everything. It is no longer a means to an end but an end in itself, and everything else is subjected to it. Living longer is good if you retire late, because it gives you time to earn more money. Being married is good because the reduced costs of shared housing and other factors make people more wealthy. Going to church is good because it's correlated with higher grades in school and higher pay at work. Having children is bad because raising them costs a staggering amount of money. If you are handicapped so severely that you can earn no money, your life is literally speaking not worth living, and ending it would be a matter of compassion.

~~Economists have~~ Money has taken over the world.

*decreased*costs by 5%.I wondered: is that the right measure? It is difficult to understand, first, why reducing the number of readmissions is the objective (it seems very different from "good health care", whatever that might be), second, if we accept that it is the objective, why reducing it less but saving money is better than reducing it more but spending money.

- Another talk was about news aggregators. Instead of reading news directly from their favorite newspaper, more and more people read news accessed via a news aggregator or facebook mentions from friends. The speaker asked: does that help newspapers, or does it hurt newspapers? Then he showed that people end up reading newspapers more than before. The implication seems to be that the evolution should be good for newspapers.

I wondered: is that the right measure? What interests me, as a user, is whether we are better informed. Does this change give us better access to better information? Are there fewer events out there that I would like to hear about but never even know exist? Are articles more thoughtful and better researched? The question of whether the evolution brings (or should bring) newspapers more or less money, although not independent, is in itself quite ancillary to that principal concern.

- The last issue of The Atlantic had an article, "Where the skills are", about cities.

*"As highly skilled people concentrate in these places, the rate of innovation accelerates, new businesses are created, and productivity -- and, ultimately, pay -- grows."*So, apparently the*ultimate*measure of why cities are good is that people are paid more money.- The Washington Post headline on Saturday: "As Nobel Prize season starts, who will get those lucky, lucrative calls?" So, the main reason why someone would hope to receive a Nobel Prize is the money.

- Americans, questioning the cost of college, look at the tradeoff between the expenses and debts incurred to earn a college degree, and the increased salary that a degree later gives you. So, apparently people go to college solely so that they will earn more later, and it is assumed that the benefits of college are captured by the change in pay.

Money is the ultimate measure of everything. It is no longer a means to an end but an end in itself, and everything else is subjected to it. Living longer is good if you retire late, because it gives you time to earn more money. Being married is good because the reduced costs of shared housing and other factors make people more wealthy. Going to church is good because it's correlated with higher grades in school and higher pay at work. Having children is bad because raising them costs a staggering amount of money. If you are handicapped so severely that you can earn no money, your life is literally speaking not worth living, and ending it would be a matter of compassion.

## Saturday, October 1, 2011

### Cell phones and the demise of watches

Since getting a cell phone, I have lost the habit of wearing a watch. Is that change of habits part of a trend? Tthe other day, in the Boston financial district. I counted how many, among the people with short sleeves, were wearing a watch. Result of my quick sample: 18 people had a watch and 17 did not. Pretty close! Is the ratio evolving? Are watches on their way out?

Last month I spent a week in a group among which only one person had a watch. The group leader, in spite of having a cell phone, was constantly asking that person for the time: it is much easier to glance at a watch than to dig out one's cell phone. So this is an instance where the progress of technology results in a less convenient access to information (information about what time it is, in the present case.) What is surprising is that it does not have to be this way: people have a choice, and they could very well continue wearing watches, should they care.

If watches really are on their way out, and if it really makes it more difficult to check the time, then, does that imply that people are late more often?

UPDATE: What we, users of basic features of telephones, really need are wristwatch telephones. They're coming!

Last month I spent a week in a group among which only one person had a watch. The group leader, in spite of having a cell phone, was constantly asking that person for the time: it is much easier to glance at a watch than to dig out one's cell phone. So this is an instance where the progress of technology results in a less convenient access to information (information about what time it is, in the present case.) What is surprising is that it does not have to be this way: people have a choice, and they could very well continue wearing watches, should they care.

If watches really are on their way out, and if it really makes it more difficult to check the time, then, does that imply that people are late more often?

UPDATE: What we, users of basic features of telephones, really need are wristwatch telephones. They're coming!

Subscribe to:
Posts (Atom)