## Thursday, December 30, 2010

### What people search for

## Sunday, December 26, 2010

### Business with unreliable partners

## 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?

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 (http://math.mit.edu/~goemans/PAPERS/bmst-focs06.pdf). 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

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

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?

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.

ACM STOC 2010

"QIP=PSPACE," and "An Improved LP-based Approximation for Steiner Tree."

ACM STOC 2009

"A Constructive Proof of the Lovasz Local Lemma", and "Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem".

ACM STOC 2008

"Optimal Hierarchical Decompositions for Congestion Minimization in Networks", and "Algorithms and Inapproximability Results for Every CSP?".

ACM STOC 2007

"Faster Integer Multiplication", and "Towards 3-Query Locally Decodable Codes of Subexponential Length".

ACM STOC 2006

"The PCP Theorem via Gap Amplification".

ACM STOC 2005

"Undirected ST-connectivity in log-space".

ACM STOC 2004

"Expander Flows, Geometric Embeddings, and Graph Partitionings", and "Multi-linear formulas for permanent and determinant are of super-polynomial size".

IEEE FOCS 2010

"Subexponential Algorithms for Unique Games and Related problems".

IEEE FOCS 2009

Best Paper Award: none?

IEEE FOCS 2008

"Two Query PCP with Sub-Constant Error"

IEEE FOCS 2007

"Space-Efficient Identity Based Encryption without Pairings"

IEEE FOCS 2006

"Settling the Complexity of 2-Player Nash-Equilibrium"

IEEE FOCS 2005

"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".

IEEE FOCS 2004

“Hardness of Approximating the Shortest Vector Problem in Lattices”, and “Cryptography in NC0”.

## Wednesday, December 15, 2010

### How not to write code

*if condition then true else false*

instead of

*condition*

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

### Minnesota

### What is an algorithm?

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

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

### SDP

## Saturday, December 4, 2010

### Email rant

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

### Evaluations

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

### Voting

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

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

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

### Infinity

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

tablet +

chord +

a few days =

a big sticky mess.

## Friday, October 1, 2010

### Grading efficiently

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

## Wednesday, September 29, 2010

### Heartbreaking

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

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

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

## Saturday, September 11, 2010

### 9/11

## Friday, September 10, 2010

### WAOA

## Wednesday, September 8, 2010

### Email surge

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

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

- 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

### Tablets

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

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

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.