Tuesday, April 5, 2011

Martin Luther King on Networks

Yesterday was the anniversary of the assassination of Martin Luther King Jr. What did King have to say about theoretical computer science?

All I'm saying is simply this, that all life is interrelated, that somehow we're caught in an inescapable network of mutuality tied in a single garment of destiny. Whatever affects one directly affects all indirectly. For some strange reason, I can never be what I ought to be until you are what you ought to be. You can never be what you ought to be until I am what I ought to be. This is the interrelated structure of reality.

What do David Easley and Jon Kleinberg respond to that?

Over the past decade there has been a growing public fascination with the complex "connectedness" of modern society. This connectedness is found in many incarnations: in the rapid growth of the Internet and the Web, in the ease with which global communication now takes place, and in the ability of news and information as well as epidemics and financial crises to spread around the world with surprising speed and intensity. These are phenomena that involve networks, incentives, and the aggregate behavior of groups of people; they are based on the links that connect us and the ways in which each of our decisions can have subtle consequences for the outcomes of everyone else.

Update: Another related quote, from Pope Benedict XVI: “We should recall that no man is an island, entire of itself. Our lives are involved with one another, through innumerable interactions they are linked together. No one lives alone.”

Monday, April 4, 2011

Fukushima update

The news of the weekend: "Radiation below legal limits found in farm, sea products near Fukushima". When one makes news of the fact that the radiation is within legal limits, the situation is dire.

Water, fire hoses, sandbags, shredded newspapers: the efforts of the best nuclear engineers are surprisingly amateurish. What happened to robots and modern sophistication? Is our modern technology yet so far from being useful in a non-lab environment? I should have known, after seeing our little robot dogs awkwardly playing soccer in the CS department at the wee hours of the morning, but somehow I was deluded into thinking that technology had better answers than the dismal response that we are now witnessing. Getting robots to work in an averse environment is still largely in the domain of research, I guess.

Meanwhile I found a list of Theory researchers in Japan. It dates from 2008, but might still be useful. One is from Fukushima University. I wonder if he'd be interested in visiting some host laboratory for a while, or some students of his. I can't do it, but maybe someone else will.

Sunday, April 3, 2011

Oh, the joys of traveling

I just flew back to the US. On this trip I got a direct flight, to avoid problems.

When I got to Heathrow airport, I followed the signs to Step 1: a machine that asked me to put my passport under the scanner, left me waiting a while, then instructed me to go to Step 2: the bag drop area.

At the bag drop area, the woman who was checking my bag said I had not checked in in Step 1. I said I had, but she repeated that I had not checked in, cut short my explanations, asked for my address and routine information, and then, as she gave me my boarding pass, said once again: "Why did you tell me you checked in? You did not check in!"

I was slow to catch on and realize that she believed, not that there had been a malfunction, but that I was lying. After leaving the counter, as I thought about that unhappy exchange and wondered why she had repeated her complaint *after* checking me in, it occured to me to look at my boarding pass: my seat assignment had been changed, and I now had a middle seat on the last row of the flight! Clearly she had punished me for lying by giving me the worst seat possible.

Why do I have such bad luck when flying? The frequency of my bad experiences suggests that I may have an attitude problem. The airline and airport staff hold passengers in their power and are free to control their travel in whichever way pleases them. I lack the instinct to apologize profusely when an incident happens such as a malfunctioning scanner. I tend to consider that it's their problem, not mine -- and that shows in my indifferent, carefree responses. Obviously, I need to be punished so as to correct that arrogant attitude. Wise passengers know to adapt to the situation, show their constant worry that they may accidentally have done something wrong, and display appropriately submissive humility. But I am a slow learner.

Friday, April 1, 2011

Women in math and theoretical computer science

This week at the Newton institute, I had few technical discussions in the hallways since the subject of the workshop (discrete harmonic analysis) was really outside my sphere of competence.

So we talked about, mostly, the same things that always come up: food; job openings; who got a new job where, got married, had kids, got divorced, or died; comparative quality of life as an academic across various countries; teaching conditions at various universities; Java versus Scheme; quality versus quantity in publications; theoretical versus applied research; mathematics versus theoretical computer science; beauty; why we do what we do; the meaning of life; and the lack of women in science.

It's amazing that I have had discussions about women in science at pretty much every conference for more than 20 years, have even been to a couple of events that were dedicated to women issues, and yet, I have absolutely nothing to say about it. I can make an effort and repeat what I have heard, and maybe spew out a few half-forgotten, half-made-up statistics, but I have never had a single thought of my own on the subject.

I see that there are very few women in academia.
I hear that the masculine gender predominates in language.
I listen with sympathy or indignation, as the case may be, to stories of sexism and discrimination.
But I am unable to abstract the problems, hypothesize the reasons, propose possible solutions, and design a mechanism to implement them and to evaluate their effectiveness.

Could it be that I am just not interested?

Mood and Math

The participants in this workshop are of two different moods, reflected by the choices of Mathematical vocabulary and topics.

One large group is fascinated by expansion, dictators, and how use one's influence to manipulate people. Their outlook is aggressive.

But in a second group, there is also a discrete current of pessimism, focused on diminishment, contraction, decay, and uselessness: there is just not enough time to do anything, they say.

New guidelines for the FOCS program committee

I am a member of the FOCS program committee this year, and today we received guidelines for our upcoming work. There are several noteworthy changes.

In particular, this year the program committee will produce, not merely a list of accepted papers, but a total ordering of accepted papers. This will greatly serve the field by giving each conference participant a quick way to choose which talks to attend, in areas outside their specialty. It will also give much more accurate information to put in people's vita. For this year, it is experimental only, but if it becomes mainstream, they will now be able to say, not merely: "I had 5 papers accepted at STOC/FOCS in the past four years", but can add: "... and the average rank of my accepted papers was 34.7". This will give researchers a powerful incentive to strive for quality work, by rewarding them for putting in the extra effort, in write up style and in generality of result, so as to make the difference between a borderline paper and a clear accept.

Moreover, the program committee is also requested to produce a ranking of the top 25 rejected submissions; however that ranking will only be sent to the authors confidentially; some may choose to keep it quiet, but others might be able to boast that "in the past four years, not only did I have 2 papers accepted at STOC/FOCS, but I also had 4 papers that almost made it, including the FOCS'11 best rejected paper." In particular, this may help PhD students in their job search, by showing their productivity. It eliminates the inherent unfairness of the 0-1 law coming from the accept-reject cutoff, and creates a relaxed version of "acceptance". As we know, fractional relaxations are much better behaved than integer problems.

I must say that I am a little bit surprised that such a significant change was not discussed at the business meeting beforehand. However, the guidelines made it clear that this is experimental only, and the attendees will be able to assess it at the next business meeting. In the worst case, I suppose that the program committee could decide to amend the guidelines and give a partial ordering only. If, on the other hand, this innovation is well received, since the information is also on file for the last several years, IEEE may also apply this change retroactively.

I am glad that our flagship conferences are always evolving and striving for improvements!

Thursday, March 31, 2011

Defining the reading level of a text

How does one estimate the accessibility of a text? What leads to labels such as "This is at the 9th grade reading level"?

Apparently one big factor is the distribution of the number of syllables in the words. Another factor is the length of sentences. Here's a typical formula:
You can use a formula to calculate Flesch-Kincaid reading level on your own. This is a good tool to determine whether a book is going to challenge you.
1. Select a few paragraphs to use as your base.
2. Calculate the average number of words per sentence. Multiply the result by 0.39
3. Calculate the average number of syllables in words (count and divide). Multiply the result by 11.8
4. Add the two results together
5. Subtract 15.59

More on http://www.micropowerandlight.com/rd.html

I have reservations about these tools, at least as applied to material for adults. A text is difficult if it contains many unknown words, of course. One of the tools proposed maintains a database of words; perhaps they are ranked according to frequency in the English language, and one reasonable measure of difficulty would be the frequent occurrence of rare words.

But a text is also difficult if its structure is convoluted. Doing a grammatical analysis and parenthesizing relative clauses, one could compute the levels of nested parentheses, thus measuring the number of partial sentences that the reader must simultaneously keep in mind as he or she is reading. That should be an important factor in readability.

Examining vocabulary is similar to examining the number of notations that the reader of a scientific paper must familiarize himself with and must memorize as he is reading. Studying the nested structure is similar to studying the number of assumptions that the reader must keep in mind while processing a proof ("This is a proof by contradiction, with a case-by-case analysis, and we are in the "else" part of the "if" statement of case 2"...). Shouldn't there be a rigorous way to measure and analyze those parameters in readability?

Wednesday, March 30, 2011

Ehud and Avi on Fukushima

Avi Wigderson: "-Why tolerate errors [in outputs of randomized algorithms]?
-We tolerate uncertainty in life."

Ehud Friedgut: "You have to realize that, when people say: "This is very tiny", sometimes they mean 1/100 and sometimes they mean one over ten billion."

Neither realized it at the time, but they could have been commenting on the Fukushima nuclear plant accident!

Monday, March 28, 2011

Newton Institute: Monday

The people who are here at the Newton Institute (Cambridge, UK) this week are largely the same ones who were in Paris last week, or at Dagstuhl earlier, or in Jerusalem last year. Why do we go from place to place like a flock of migratory birds? What instinct prevents us from settling down anywhere in particular?

Here is what Christopher Lasch writes in his book "The revolt of the elites":
"Ambitious people understand that a migratory way of life is the price of getting ahead. It is a price they gladly pay, since they associate the idea of home with intrusive relatives and neighbors, small-minded gossip, and hidebound conventions. [...] Those who covet membership in the new aristocracy of brains tend to congregate on the coasts, turning their back on the heartland and cultivating ties with the international market [...] Patriotism, certainly, does not rank very high in their hierarchy of virtues. "Multiculturalism", on the other hand, suits them to perfection, conjuring up the agreeable image of a global bazaar in which exotic cuisines, exotic styles of dress, exotic music, exotic tribal customs can be savored indiscriminately, with no questions asked and no commitments required. The new elites are at home in transit, en route to a high-level conference, to the grand opening of a new franchise, to an international film festival, or to an undiscovered resort. Theirs is essentially a tourist's view of the world -- not a perspective likely to encourage a passionate devotion to democracy."
"Their loyalties -- if the term is not itself anachronistic in this context -- are international rather than regional, national, or local. They have more in common with their counterparts in Brussels or Hong Kong than with the masses of Americans not yet plugged into the network of global communication."

Ouch. Thankfully, I cannot possibly fit that description since I am staying in a dorm with a shared bath!

Sunday, March 27, 2011

The beggars of Paris

During my visit to Paris my two offices and my studio were all essentially on the same block, that I got to know by heart.

By the bakery on rue Gay-Lussac, there is a beggar, not always the same one. One day there was a woman and child, who I noticed looked at the chocolate bun that I had bought for breakfast. I gave the child half of my bun, whereupon the adult immediately said: "She is thirsty, too." I answered: "I can't give her that" and went on my way, annoyed for some obscure reason.

By the sea and water institute, there sometimes is a man begging and looking sad. After emptying the tiny fridge in my studio and checking out, as I walked by him with my bag of leftover groceries, his eye caught mine and I was compelled to offer him some of my extra food. But he refused my offer of a box of microwavable lentils and bacon dish: "I have no way to reheat it", he explained. I looked again in my bag, but there was nothing edible without cooking. "Sorry, I don't have anything else", I said regretfully. "It's all right, never mind. Have a nice day!", he answered gracefully. I continued on my way, wondering about the one thing that I could have given him but chose not to take out of the bag and offer him: a bottle of wine...

On rue Pierre et Marie Curie, there are often traces of a presence on the street: empty beer bottles, a sleeping bag drying on a railing, and sometimes an indistinct human form buried in layers of cloth. When I stayed late in the office, once or twice I heard loud drunken noises coming from the street.

At the corner of rue d'Ulm, there is a phone booth that was inhabited last January, but that is currently available. On the other hand, a woman seems to be spending many of her days sitting on a heat grate on the sidewalk. Late one night, I saw a shape in a sleeping bag, set up in the middle of the street, on the piece of pavement off limits to traffic that marked the middle of the intersection! Was it her? Was that her way of setting up some boundaries?

Further down rue d'Ulm, there is a university whose main entrance cuts off the first floor of the building diagonally, providing a shelter. A beggar is set up there. Sometimes he is sleeping. Other times, some large pieces of cardboard are set out and dozens of books are on display, as an improvised streetcorner bookstore. I wish I had looked at it more closely.

Closer to the RER, by the side entrance of the church of St Jacques d Haut Pas, there is a beggar, usually but not always an older woman. One day she was selling daffodils and I bought a bunch, happy with that creative way to generate an income. But she was indifferent to my presence and never raised her eyes to my face. She is only there during the day: perhaps she has a home to go back to at night.

The main entrance of that church also has occasional beggars, two men, but they're not regulars. Maybe they're only there at night and to ask for charity at Mass time.

The beggars in Paris are diverse. Men and women, young and old, with dog or child. I have seen an old woman reading a prayer book, oblivious to her environment. I have seen a young woman, her hair carefully covered with a scarf, in a silent kneeling posture, full of dignity. Her body is there, but her mind seems absent. According to statistics 17 percent of homeless people in Paris are women.

I often wonder what kind of beggar I would be.