Thursday, December 30, 2010

What people search for

Without the internet, how would I have learnt how to (last week) patch a pair of jeans, or how to (this week) open fresh oysters? With the internet, all knowledge is at my fingertips. I never cease to be amazed.

Here in France, when I start entering the phrase "How to" in Google, the first suggestions that are coming up today are:
- how to make it in America
- how to train your dragon
Normally, if I remember correctly, in the US the first suggestions are:
-how to make love
-how to tie a tie

Curious, I entered the French analog, "Comment", in Google. First suggestions:
-how to make love,
-how does it work,
-how to write a vita,
-how to become rich.

I guess that the French know how to tie a tie.

Sunday, December 26, 2010

Business with unreliable partners

How can we communicate with a business partner at an unequal footing to ensure that they are keeping their side of the contract?

For example, say that you are flying with and airline company that claims that they closed the door on you for safety or other reasons. How can we verify that our seat on the flight has not been given to a standby passenger, and that this is not a lie? When they say that they tried to reschedule on another flight on the same day but failed, how can we verify that that is not a ure lie? When they say thay also looked at departures from other companies but that everything was full, how do we know it is the truth? When they claim that we cannot get our luggage back, or that the seats they are finally giving us are the last ones available on that flight, how do we know it is the truth?

When trust is gone, we need a way to make sure that the contract between company and customer is not breached by the side that has more power and a monopoly on information. How? Should air passengers unionize? Or is there some cryptographic procedure that would help verify the company's claims?

Friday, December 24, 2010

How United Airlines stole our Christmas

My teenage children and myself, living in the US, were going to spend Christmas with our family in France. We got tickets to fly from Boston to Paris via Washington Dulles, leaving on December 23, the last day of school, and arriving the next day.

On December 23, we arrived at the airport four hours early, ready to start our holiday. Our problems started when our airplane left the gate. It was bumped off its spot in the queue for taking off, and spent time off to the side. When its turn came back again, a mechanical problem, caused by a flap that wouldn't close, caused it to return to the gate. After mechanics had closed it manually while we waited anxiously, we finally took off, a little after 4pm (our scheduled departure time was 2:16pm). During the flight, one steward gathered information, told each person their connection gate, suggested we study the map of the airport in the flight magazine, and, upon arrival, pleaded for other passengers to let the ones in a rush go ahead and make a run for it.

"As soon as we become aware of a service interruption, we will relay information to affected customers, and we will work proactively to help them reach their intended destinations."

It was 5:09pm when we landed. Eight passengers were going on to Paris, with a connection at 5:25pm. After taxiiing, the door opened, we rushed out of the airplane and ran madly to our departure gate. Fortunately all of us arrived before 5:25. But to our great dismay, the door was closed! In fact the first two of the eight had arrived early enough to see the door closing in front of them! We stared at one another in disbelief. How could that be? Impossible! We begged the staff to reopen to door, but to no avail. They said that they had received a "direct order from Chicago" to close the door. One passenger, flushed by her run, got out her asthma inhaler and took deep breaths. A child was bravely putting on a good face, silently holding back tears. As our little group was standing angrily in front of the closed door, we were advised to go to customer service. We were told that we were just wasting time by staying there, diminishing our chances for a good alternative flight plan.

At United, the only acceptable customer experience is one in which you arrive at your intended destination safely, comfortably and on time. When events and obstacles beyond our control, such as severe weather or Air Traffic Control delays, prohibit us from achieving this standard, we strive to minimize customer inconvenience however possible.

At customer service, we joined the long line. The representatives were busy rescheduling people on flights for the following day. We would leave on Christmas Eve, on the exact same flight but 24 hours later than originally planned. We would spend the evening and night of Christmas on the flight, and arrive in Paris on the 25th.

The service representative gave us a hotel reservation and a $15 meal voucher for dinner. "What about breakfast and lunch?", I asked. "I'm sorry, but we can only give you one meal voucher", answered the United airlines representative. "What about our bags?", I asked. "I have already rescheduled them and you will get them when you get to Paris." Apparently other people were given the choice to wait for their bags and pick them up, but not us.

"In the air and on the ground, online and on the telephone, our customers have the right to expect — to demand — respect, courtesy, fairness and honesty from the airline they have selected for travel."

I left the customer service counter seething with anger. We waited in the cold for a shuttle, that took us to an upscale golf resort twenty miles away. Meanwhile I decided to calm down and try to make the best of it. "Life is a journey, travel it well", says United in their slogan. At the hotel, we spent a small fortune on ill-fitting swimming suits and relaxed at the pool for a while. After a dinner at the one place at the hotel that was still open (and where the cost of three sandwiches easily exceeded our vouchers), we paid another $15 to watch a movie before calling it a day. Since we had no toiletries with us, I asked the front desk for help, but theirs were only available for purchase. I noted that it violated United's written policy to provide stranded passengers with complimentary toiletries, but to no avail.

This year, for us, there will be no decorating the tree, no putting together the creche with our cousins, no singing carols, no midnight Mass. Instead, there is waiting in line in the hellish atmosphere of a crowded airport.

At Christmas, we celebrate the birth of Christ. In the mayhem of holiday airport travel, when I think of United slamming its door to our face, it calls to mind the innkeeper in Bethlehem who refused to make room for a 9-month old pregnant woman.

And that is United Airlines's way: "Fly the friendly skies of United". Merry Christmas!

Tuesday, December 21, 2010

Examples of well-written papers?

Yesterday I found this comment on this blog: "As a young researcher trying hard to write nice papers, I don't find many role models."

Forget the introduction, and look at the technical content: what are examples of particularly well-written papers?

I personally like the papers (and lecture notes) by Michel Goemans. I find them clean, rigorous, concise and crisp, elegant in a minimalistic way. For example, his 2006 paper on minimum bounded degree spanning tree ( But there may be a cultural bias. Maupassant would be my ideal role model. In his short stories, he always uses precisely the right word to convey the correct meaning. He reputedly spent much time trimming his texts and eliminating all unnecessary adjectives. Why not aim to do the same for technical writing? Write exactly what is necessary for the readers' understanding, no less but no more. Each word should have a purpose, each notation a justification, each sentence a reason for being there. For example each mathematical concept, in my ideal world, is defined exactly twice, once with words and once with symbols, because some readers are more comfortable with words and some with Mathematical notation, and because the two presentations are mutually reinforcing, and help remove possible ambiguities. More than twice is a waste of words, in my ideal world.

Monday, December 20, 2010

Writing dynamic programs

I think of dynamic programming as a bottom-up computation, but that view can be slightly misleading. For example, consider keeping track of the connected components of a forest F in a graph of bounded treewidth.

For a bag B, let G(subtree(B)) denote the subgraph induced by the nodes appearing in bag B (let's call those portal nodes) and in all of its descendant bags as well. Let G(B) denote the constant size graph induced by just the portals.

Consider the connected components of (F intersect G(subtree(B))). They induce a partition pi(B) of the portals.
- for a leaf bag, pi(B) = the connected components of (F intersect G(B))
- for a bag B with two children B1 and B2, pi(B) is obtained by "combining" pi(B1), pi(B2), and (F intersect G(B)).
It's a bottom-up recurrence.

Consider instead the connected component of F, the global forest. They also induce a partition sigma(B) of the portals.
- for the root bag, sigma(B)=pi(B)
- for a bag B with parent bag B', sigma(B) is obtained by "combining" sigma(B'), pi(B), and (F intersect G(B union B')).
It's a top-down recurrence.

Since all recurrence formulas are local, a dynamic program can do both computations at the same time, and thus a DP algorithm can be assumed, while it is working on a bag B, to have access to the partition of the portals in the global forest: working bottom up, it makes guesses that will be validated later at a higher level of the tree. Thus, one recurrence is of the form: compute, then memorize a summary of the computation done in G(subtree(B)). The other recurrence is of the form: guess a summary of the future computation, then verify. In the DP the two computations are intertwined.

Borradaile, Klein and myself are using something much like this in a paper on Euclidean Steiner forest. Bateni, Hajiaghayi and Marx are using essentially this in a paper on Steiner forest in planar graphs and graphs of bounded treewidth. Writing up the details of such dynamic programs is a bit messy, yet it is conceptually simple. I think that the difficulty in presentation comes from this mix of bottom-up and top-down.

Are there other examples of such dynamic programs? Are there models of good writing for that?

Friday, December 17, 2010

Writing proofs: avoiding case analysis

As a student I learned a number of ways to prove lemmas: contradiction, induction, case analysis, etc.

Case analysis, when there are more than two cases, tends to make me feel like a mindless computer. It is more like checking than like understanding, and for me it is not a good way to get insight.

The direct proof is my favorite proof organization for short pieces of argument: assumption A implies B, B implies C, C implies D, D implies the final statement E. The proof should give a brief justification for each implication. With this kind of proof it is easier for me to get insight.

For example, in Trevisan's 2005 SDP algorithm for unique games, one small piece of the analysis is proved by doing a separation into three cases.

The claim: if three vectors r,u,v are such that u.v=0, (r-u)2>(r-v)2, and the vectors satisfy a "triangle inequality" constraint, then (r-u)2 > (1/2) (r)2.

The proof has three cases:
- either (Case 1) (u)2 < (1/2) (r)2,
- or (Case 2) (v)2<(1/2)(r)2,
- or (Case 3) (u)2 and (v)2 are both > (1/2) (r)2.
Each case is short, but it feels a little bit redundant and dissatisfying.

Instead, here is a direct proof (how does one do math in html, I wonder.):
- By the triangle inequality constraints,
(A1) (r)2 < (u-v)2+(v)2 and (A2) (r)2<(r-u)2+(u)2.
-Summing, (B) 2 (r)2 < (r-u)2+(r-v)2+(u)2+(v)2.
-Since u.v=0, we have (C) (u)2+(v)2=(u-v)2.
-By the triangle inequality constraints again, (D) (u-v)2<(u-w)2+(w-v)2.
-Substituting that in (B) gives (E) 2 (r)2 < 2(r-u)2 + 2(r-v)2.
-By assumption (r-u)2>(r-v)2, so (F) 2(r)2<4(r-u)2, hence the result.

The proof is essentially the same, but it is organized differently, and I like this presentation better.

Thursday, December 16, 2010

On which topics is there progress in Theoretical Computer Science?

Here are the best papers at STOC and FOCS in the last few years, as best as I could gather. What picture does that paint of research activity in core theoretical computer science? Crypto, approximation, and hardness of approximation are progressing swiftly, but also error-correcting codes. Structural space complexity continues strong. (Some outliers: discrete math, game theory, and the paper on faster integer multiplication.)

Are those the areas where new ideas are emerging, where things are happening, and therefore where one might consider hiring? I'm just considering the core here, not the exploding areas of interdisciplinary research.

"QIP=PSPACE," and "An Improved LP-based Approximation for Steiner Tree."
"A Constructive Proof of the Lovasz Local Lemma", and "Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem".
"Optimal Hierarchical Decompositions for Congestion Minimization in Networks", and "Algorithms and Inapproximability Results for Every CSP?".
"Faster Integer Multiplication", and "Towards 3-Query Locally Decodable Codes of Subexponential Length".
"The PCP Theorem via Gap Amplification".
"Undirected ST-connectivity in log-space".
"Expander Flows, Geometric Embeddings, and Graph Partitionings", and "Multi-linear formulas for permanent and determinant are of super-polynomial size".

"Subexponential Algorithms for Unique Games and Related problems".
Best Paper Award: none?
"Two Query PCP with Sub-Constant Error"
"Space-Efficient Identity Based Encryption without Pairings"
"Settling the Complexity of 2-Player Nash-Equilibrium"
"The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into L1", and "Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time".
“Hardness of Approximating the Shortest Vector Problem in Lattices”, and “Cryptography in NC0”.

Wednesday, December 15, 2010

How not to write code

Grading for my freshman programming course, I saw this and similar horrors:

if condition then true else false

instead of


My TAs did not think that should be penalized, "because it's not a big deal". Indeed, I have taught that code ought to be (1) correct, (2) readable, and (3) efficient. The piece of code above is correct; having seen much more mysterious constructions, I cannot argue that it's not readable; and the loss of efficiency is negligible. But it's not elegant! That is just one example of bad style among many. I forgot to stress one important aspect in class: code should always be (4) beautiful!

Perhaps we should have some "beauty points" in our grading scale, and I should have some exercises of the form: take this ugly piece of code, and make it beautiful. Students would complain about possible discrepancies between different TAs' esthetics, of course, but I suspect that there is a hidden yet broad consensus to recognize beauty in code: we know it when we see it... the challenge is to define it!

Similarly, in math, particularly in courses on how to write proofs, perhaps there should be some exercises of the form: "take this ugly proof and make it beautiful".

Tuesday, December 14, 2010


Heard this morning on the bus: "In Minnesota, it gets so cold that when you spit, it is frozen by the time it reaches the ground."

What is an algorithm?

Q: Why does no one implement my algorithms?
A: Because almost invariably there is a step that says: "By exhaustive search over a space S of size some-huge-constant, compute some optimum".

I've been mistaken all along. I should not write "by exhaustive search" but simply "compute some optimum over S". Who am I to tell a programmer that he absolutely must use exhaustive search? If he finds a better way to compute the optimum, so much the better. In the section analyzing running time, I could always state: "Using exhaustive search for example, the optimum over S can trivially be computed in constant time."

The theorem is the interface between me and the complexity theorist (who does not care how the problem is solved algorithmically, but only that the problem is solved and about the related structural insights).

The algorithm is the interface between me and the hypothetical programmer who might some day be interested in implementing my algorithm (and who does not care about why, in the analysis, the algorithm works). That's what should drive what to specify and what not to specify in the description of the algorithm.

If I mix in some critical ideas with some steps where I just threw in the first thing that came to my mind to solve that subproblem, how is he supposed to separate the wheat from the chaff and know which of my instructions should be followed carefully and which ones are open for him to play with and optimize?

Sunday, December 12, 2010

How not to present algorithms

I decided to look at the award-winning Arora-Boaz-Steurer paper giving a subexponential algorithm for unique games. I first wanted to take a look at the algorithm itself, temporarily ignoring the analysis and focusing on the algorithmic techniques only.

According to the plan in the intro, the algorithm is in section 5. There, first, without loss of generality they assume that the graph is regular -- for that, the reader can simply check Appendix A. I go there and review the construction. Going back to section 5, they then make the graph lazy by adding self-loops - I skim the construction.

We are then sent to section 4 and Theorem 4.5. Going there, we are redirected to Theorem 4.1 "using Theorem 3.2 instead of 2.3". Making a mental note of that and going to Theorem 4.1, I see that the proof starts with a Lemma, 4.2, whose proof is a mere call to Theorem 2.3 for some particular value of a parameter. Thus it is time to go to Theorem 3.2. Going there, I am redirected to Theorem 2.3. Going there, I am redirected to Theorem 3.1. Going to its proof, I see that the lemmas are just doing an analysis, without algorithmic contents, until I get to a comment "... moreover, following the proof we see that if the condition is violated we can get a set S ...". Aaargh!

Giving up on that for now and going back to the thread of the proof of Theorem 4.1, I skim the next couple of lemmas, that seem to do some combination of greedy partitioning and of iteratively re-partitioning parts into smaller pieces a few times. Going back to section 5, the next step, in my impression, assigns labels independently for each part of the partition. More precisely, for each label-extended part of the partition, it redirects us to the algorithm of Theorem 2.2. Miraculously, the proof of Theorem 2.2 is basically self-contained: take the subspace spanned by eigenvectors of the large eigenvalues, put an epsilon-net in its unit ball, and, for each vector v in that epsilon-net, use its "large enough" coordinates to define a subset S(v) of vertices of the graph. Going back to section 5, apparently for each set S(v) there will be a mysterious assignment, and the algorithm exhaustively enumerates the v's and picks the assignment satisfying the most constraints.

What have I learned? Basically nothing so far. Frustrating! If the result was not so good, I would give up on that paper. Instead, I may consider setting aside a few days solely for deciphering it...

Monday, December 6, 2010


Linear programming was in fashion long before approximation algorithms. Linear programming exactly solves all sorts of important problems such as shortest paths, max flow, min cut, various kinds of preemptive scheduling, etc. What about semidefinite-definite programming? What is it good for, other than for approximation algorithms? What problems can be solved exactly by semi-definite programming?

Saturday, December 4, 2010

Email rant

People keep coming up with new, better technology: applications that are smarter at helping you deal with email and make you more efficient. I think that it’s the wrong approach. As soon as that happens, the number of emails immediately increases so that you spend just as much time on it as before, if not more.

I have been thinking about the following anti-technology approaches instead:
- close my mailbox on weekends, so that it won’t accept any email but send an automatic reply “this email is disabled on weekends”.
- automatically dump emails at the end of the day or week. Any email not dealt with on the same day or week that it arrived is destroyed at midnight (or on Friday night).
- have a noise-maker than randomly deletes 20% of the emails before they even get to me.
- put an automatic lag of 24 hours so that emails arrive in my mailbox no sooner than 24 hours after being sent.
- put an automatic cap of, say, 50 emails per day (or however many I can reasonably deal with). Any email beyond that gets automatically rejected with the message “email deleted before reaching the recipient: recipient’s quota reached for the day”.

Monday, November 29, 2010


The STACS program committee meeting has ended. We have a couple of days to digest the results before they get sent out to authors. The way in which the committee virtual meeting was run was an impressive case of efficiency. We were given internal deadlines that we were actually supposed to respect, with no slack. That was stressful!

The life of a professor is very much driven by deadlines. The next item: recommendation letters that need to be written and sent out, many of them before December 1. A few days later, several referee reports are due. Then, wrapping up the semester's courses and deciding on final grades. Some of the intervals in between will be filled by attempts to bring my mailbox under control.

So much of our lives is occupied by evaluations. It is rather striking considering that that is neither teaching nor research proper.

Friday, November 5, 2010


When I voted in the village in France where I used to live, we did it the old-fashioned way: go in an isolated space whose privacy is protected by curtains, put a paper ballotin a small envelope, and drop it in the glass bin. On several occasions I volunteered to help count.

That Sunday evening (voting in France is always on Sundays), the volunteers gather, and we form 3 tables of four actors. The other people present are just watching the counting as it happens, to help guarantee its integrity.

The chair of the meeting unlocks the glass bin and envelopes are gathered in packets of one hundred. Our table gets a few of those packets. For each envelope, I open it, take out the bulletin and pass it to the person across the table from me. He looks at the name written on the ballot and reads it aloud. The two other persons, who each have a sheet of paper, record the vote. After each packet, they compare their tally and we check that the total sum is correct.

It's a mesmerizing procedure. Extremely easy, but we have to stay focused. By myself, I would perhaps make one or two mistakes in the 600 votes that my table counts. With the four of us controlling the process (plus onlookers), the rare mistakes get noticed right away. Everyone is focused: we're all conscious of the importance of the act. Democracy in action! I am also fascinated by the tallies, trying to predict who will win, looking for patterns and trying to explain them. Overall, voting is so much more satisfying in France. In the morning, we vote, and in the evening, we watch the votes being counted, knowing that ours is one of them even though we don't know which one it is. The results are gathered with the other voting places in town, and the tallies are posted at the city hall. They are then aggregated with results from other towns, and posted at the regional center. They are then further aggregated to sum to the national numbers. A beautiful hierarchical tree!

Thursday, October 28, 2010

Fleas and Galton-Watson

Consider an ennemy Galton-Watson process where each node has 20 offsprings on average. If you kill 90% of the nodes, is that a success? No really: the remaining nodes are still a rather impressive number. How to destroy them, then? The solution is to repeat the destructive process a second time. If the second attack kills 90% of the remaining nodes, then you will be left with just a few sparse isolated surviving individuals who can then be killed one by one as they come out of their hiding places.

Apply this to flea infestation: I am lauching my second chemical weapons attack today, with stronger chemicals that leave a residue on floor and furniture, so that any egg that might still hatch in the near future would then be killed as soon as it is born.

Tuesday, October 26, 2010

Flea war

I have launched a massive chemical weapon attack in my house, ongoing as I write.

Fleas are a good example of an exponential process. One day, you think you might have gotten a bite but are not sure. The next day, you spot a flea. The next day, 5, the next day, your son complains that he can't work on the computer because fleas keep jumping on his ankles. Time to declare war! And that's why my house is currently being filled with toxic gas.

Where do those fleas come from? From a litter of kittens who were in my house for a few weeks. I knew they had fleas, but the fleas politely stayed on them and did not bother anyone else. I half-heartedly tried to bathe them and comb them with a flea comb, but my efforts were ineffective, and because of the youth of the kittens, there was no other possibility. After the kittens were gone, the flea eggs were left behind, and must have hatched in the last few days.

Wednesday, October 13, 2010


Toothpaste I always thought of as an image of infinity: no matter how long you've been using a toothpaste tube, there is always a little bit more that can be squeezed out if you try hard enough. There is definitely a first time, but then you can always use it one more time. You never get to the end.

But last week I reached the end of my tube. It made a sucking noise, a hole appeared in the toothpaste, and, squinting through it, I could see the empty inside of the tube. First time in my entire life. Somehow, it makes me think of death.

Friday, October 8, 2010

Sour patch candies

One sour patch candy loose at the bottom of a backpack +
tablet +
chord +
a few days =
a big sticky mess.

Friday, October 1, 2010

Grading efficiently

Here is how I grade Theory homeworks.
1. Grade everybody's answer to problem 1, then everybody's answer to problem 2, etc. This goes much faster than grading all problems of the first homework, then all problems of the second homework, etc.
2. Read a couple of solutions by students who I know will probably get it mostly right.
3. After that, sketch a model solution; figure out the key points/keywords.
4. When reading a proof, scan it briefly to find the keywords. Ideally, someone using the right keywords has to have done the proof right, and someone missing a keyword has to be missing something in their argument.
5. Grade at a high level. Too much granularity means wasting time on unimportant details; some experiments have also shown, I have heard, that grades of the same exams by independent graders yield (paradoxically) more consistent results if the grading is more global. This means that I have to have a clear sense of "what really matters".
6. Occasionally give up. I typical spend the majority of my time on a tiny fraction of the homeworks (the ones that come up with a completely different approach, or from students who are unusually wordy and obscure, or a combination). Sometimes, if after some amount of time I still cannot figure out what their solution is about, I just add a note in the margin: "No credit -- I can't understand this. Come see me at office hours and if you can explain it to me you may get some credit."
7. Design homeworks so that they are easy to grade by the above method. In particular each question should have a reason for being there: it should test something specific, and then when I grade I am just looking for that key point. Example: ask for a proof by induction, in an application where there is a risk that the student may list the base cases wrong. When grading, I can then scan the whole proof and just zoom on the base cases. The rest is "noise" and I will essentially ignore it, although the student does not know it when he writes his solution. Some students then get annoyed because they will receive almost no credit even though, in their view, they got most of the question right; but they didn't figure out the one part I cared about...

Thursday, September 30, 2010

Kittens and fleas

I am acquiring valuable knowledge on cat fleas. This time I have figured out that the kittens I'm fostering have fleas, before I got bitten even once.
1. They groom themselves more often than I am comfortable with
2. I closely examine the fur of the whitest kitten and spot some suspicious specks of black dirt
3. I pluck one speck, put it on a piece of white paper, wet it with water, wait a few moments: it dissolves and becomes reddish. That's the proof! It's not dirt, but flea excrement, made from kitten blood. How strangely gratifying it is to witness the definitive confirmation of one's fears.

Now that I have a head start on identifying the problem, I should be able to control it before we get infested. I hope.

Wednesday, September 29, 2010


The other night in downtown Providence, on Kennedy Plaza, I saw an older homeless couple. The man was carrying several heavy bags, and the woman was pulling a carriage. They crossed the street slowly, with slightly shuffling steps. On the other side, as the woman was having trouble pulling her carriage up, the man turned to her, saw what was delaying her, gently took the handle from her and pulled the carriage up the curb. They then resumed their share of the load and their slow walk.

A few minutes later, I saw them again, wandering back by the park, indistinct in the shadows but recognizable by their uncertain gait, before they finally disappeared out of sight.

Friday, September 24, 2010

More on technology

One more thing to worry about: I must not accidentally misplace my tablet pen - else lecture preparation becomes a real challenge!

A small miracle happened today: setting up my (borrowed) tablet in an unknown classroom with unfamiliar technological equipment, I followed the directions printed by the projector etc., pushed the buttons that had a big highlighted label, according to directions, and everything worked without a hitch. Amazing.

The alternative would have been a black board, and I hate chalk dust, so I was highly motivated to do it right.

Wednesday, September 22, 2010

How to take a break, past and present

After intensive work for a couple of hours, I am usually mentally exhausted and need a short break.

Nowadays: I get some coffee and surf the web idly.

In the old days: I got some coffee and sat by the coffee machine to chat with whoever else was taking a break at that time.

Does the web make us socialize less with the people who work just down the hall from us?

Saturday, September 18, 2010

The problem with technology

- Must not lose my tablet charger
- Must not get my tablet pen stuck inside the tablet
- Must not get my laptop separated into two pieces after going through customs in checked luggage
- Must not wash my cell phone in the washing machine
- Must not forget my apple laptop connector when giving a talk
Why are we so worried about software? Hardware is the problem.

Saturday, September 11, 2010


Flying on September 11: just like any other day.

One of the most popular and lively conversation topics among computer science researchers: the comparative qualities of various airports. Many people would think we're dreadful snobs showing off our travels, but that's not the reason: we're simply disconnected from the reality of a world in which, for many, flying is still a very rare treat. When I am not in the company of fellow academics, I have learnt to refrain from complaining about the unpleasantness of air travel; in fact, best to avoid mentions of air travel altogether.

Friday, September 10, 2010


Liverpool, UK. Outside the hotel there is a small plaza shaped like a mini roman amphitheater. I stood in the center and spoke up. The acoustics made my voice resonate as if I had a microphone. Incredible.

The Thai restaurant where we had dinner had a big fish pond next to our table with goldfish swarming, obviously eagerly waiting to be fed. I gave them some bits of the flower that was in a vase on our table, and they ate it hungrily. As soon as my hand approached the surface of the water, they all rushed towards it, mouths wide open. It's almost scary!

Wednesday, September 8, 2010

Email surge

During most of August, thanks to slow internet traffic and more time to clean up my desk, I was able to contain the size of my mailbox to about 50 or less. Now, with the new semester starting, in spite of my efforts the number of messages has shot up to over 100.

Email seem impossible to contain more than temporarily. It's like malaria --with constant care, it's possible to contain it in spite of occasional feverish bouts, but it's always threatening to overwhelm at the next crisis.

Monday, September 6, 2010

May 1

Today is May 1, or rather, Labor day, the US analog. But here it is a chance to exalt work as an ethical (?) value, not to review inequalities at work nor to have street demonstrations.

Classes at Brown start on Wednesday September 1, but Monday September 6 is a holiday in the US (it's their version of May 1), complicating the schedule already in the first week. It's odd how the semester begins: three days of classes, and then immediately a long weekend. Why not start on Tuesday September 7?

I don't think it's by chance. The same thing happens every year in the local high school. It must be by design. But what's the reason?

Friday, September 3, 2010

CS 17: a learning experience

What I learned today in class:
- that writing code on a screen in real time is horrendous. I should always have the next slide ready with the resulting code, so that after my efforts to write, a cleaner and complete version appears on the next screen.
- that freshmen have never seen truth tables before!!

What I already knew but learned again:
- that rushing to cover planned material before the end of class is not worth it! Better go slowly and carefully.

Thursday, September 2, 2010


I dislike technology. Only in 2005 did I reluctantly shift from using transparencies to computer slides. But the tablet enables me to go backwards in time. Now I can use a pen, see my own handwriting appear on the screen, and update the content of the slide during the lecture as I see fit. Soon we'll be able to do without mouse or keyboard altogether. I am thrilled!

Current students, however, might not be so thrilled since they grew up with keyboards and do not resent their presence, so there is only a small window of opportunity for tablet development before the pen-loving generations disappear.

Next goal: when will we go backwards to the time of my beloved fountain pen?

Wednesday, September 1, 2010

Defining constants

To day in class I showed an example of constant definition in Racket (formerly Scheme)

Student's question: Can you change it later?

Answer: no, you define that identifier once and for all. Once chosen, you cannot change it. It's like a baptism.

Actually that's not quite true, in fact it's the reverse. If a child is baptized "David", then his name will be David forever. But it is possible to use the name "David" for other children.

In Racket when you write: (define myfavoriteconstant 45), you take a number: 45, and give it a name: "myfavoriteconstant". From now on "myfavoriteconstant" refers to 45; that cannot be changed. However, nothing prevents you from choosing other names as well: you may next write
(define ilikethisnametoo 45)

First class of the semester

I was teaching using a tablet PC today, for the first time; the tablet is borrowed from a colleague.

What I learnt today: in order to connect with the projector, I should press Function F4.

What I could have done better: I could have learnt this earlier than 10 minutes into class.