Applying for a job in France, part 2

For CNRS, good informal advice can be found in this text written by Bruno Durand a few years ago: here. In French, more recent information (for the year 2012) is here and there, with pointers to the current two sections in computer science, 6 and 7.

The diameter of the flip graph of triangulations

Consider the graph whose nodes correspond to triangulations of a convex n-vertex polygon and whose edges correspond to a "flip" of the diagonal edge between two adjacent triangles of the triangulation. In 1988 Sleator, Tarjan and Thurston proved, with an argument using hyperbolic geometry, that that graph has diameter 2n-10 for n large enough. Since then, finding a purely combinatorial proof has been an open problem.

A few years later, Thurston suggested to me a combinatorial approach based on a linear programming relaxation and a lower bound proved by writing the LP dual and exhibiting a dual feasible solution. I implemented his suggestions and the resulting draft was somewhat hastily submitted to a conference, from which it was rejected. Disappointed by the lack of interest of the community evidenced by that rejection, I put the manuscript in the bottom of a drawer and tried to forget about it.

But somehow, word got out, and every year or two I got a request for the manuscript. Some PhD student somewhere would want to work on the question, heard that I had worked on it, and contacted me about it. I systematically sent them the draft wile disclaiming the result since I had not proofread it and neither had anyone else. Eventually, I decided that I must resolve this and, last year, asked a student at Brown to look into it. He tried to read the manuscript with me, reconstructing the ideas, but got bogged down, as I had several times before, writing out the dual feasible solution. Undeterred, he proceeded to code it up, and then discovered that the construction was actually incomplete. I had left some dual variables undefined, and it was not clear how to define them while respecting all the constraints. He spent a good amount of time on it, but could not resolve it. It now appeared that the approach was problematic.

So, I was excited to hear a couple of months ago that Lionel Pournin found a purely combinatorial proof. Today he gave a seminar, and here are the slides. So simple ! In one hour at a slow pace, we got all the ideas and most of the proof details. Anyone junior level undergraduate could read it. And now, that long-standing open problem is finally resolved, with elementary means ! Amazing.

Anyone interested in the problem really should spend a few minutes pouring over those slides.

Sandy delays STOC

JUST IN:

The deadline for ACM STOC 2013 submissions has been extended to Monday, Nov 5 2012 5:00 p.m. EST. The change has been announced on the STOC website.

OLD NEWS:

1) Please read the Call for Papers carefully and pay special attention to length and formatting requirements, which have changed since last year:
a) Submissions must be no more than 10 pages in two-column ACM Proceedings format, including the bibliography.
b) Length and formatting requirements will be enforced strictly and literally; submissions that don't conform will be summarily rejected.
Note that you have the option of uploading a full-paper version, along with your 10-page extended abstract.

2) The online submission process will take more time than it has in the past for at least two reasons:
a) There are roughly three times as many Program-Committee members as in the past, and thus Conflicts of Interest will take longer to check off.
b) Each author is required to select one or more Topics (from a moderately long list) that describe his or her submission. Thus we strongly suggest that you create your user account on the submission server NOW and fill in a "start new paper" form for each submission, even if you have not yet finished writing it. Submissions can be modified any time between now and the deadline of Nov. 2, 2012 at 04:59 pm EDT.

Note that this and all other information about STOC 2013 can be found at http://theory.stanford.edu/stoc2013/

A probable "maître de conférences" job opening at ENS

Pour information: le département d'informatique de l'ENS aura très probablement un poste de maître de conférences à pourvoir pour la rentrée 2013. A priori ce poste sera complètement ouvert à tous les domaines de recherche dans toute l'informatique. Les postes d'enseignant-chercheur à l'ENS sont particulièrement désirables, à cause du public des élèves et étudiants suivant les cours, de la situation géographique, du cadre, et des conditions de travail au DIENS. A priori ce poste requiert d'être capable d'enseigner en français, mais on s'attend habituellement à ce que le candidat ait fait un séjour post-doctoral à l'étranger. Si parmi les gens lisant cette annonce il y en a qui pourraient être intéressés et qui souhaiteraient dans ce cadre éventuellement rejoindre l'équipe TAlgo, il serait bon qu'ils me contactent. Merci!

For information: the computer science department at ENS will very likely have an assistant professor position available, with a starting date of Fall 2013. It appears that the position will have a completely open profile, and all research areas within computer science will be considered. ENS assistant professor positions are particularly desirable because of the students who are being taught, of the location, of the architectural setting, and of the work conditions at ENS. A priori the position requires an ability to teach in French, but it is expected that the applicant will normally have completed a post-doctoral stay abroad. If, among the readers of this post, there are some who might be interested and who would then consider joining the Talgo group, it would be good for them to contact me. Thank you!

Applying for a job in France

If you are a foreigner interested in applying for a job in France, how does it work? Here is my understanding. (The rules change a little bit over time, so my knowledge might be not quite up to date.)

The jobs: in computer science, there are two types of research-only positions: CNRS and INRIA, called "charge de recherches" at the junior level and "directeur de recherches" at the senior level. Academic positions that combine research and teaching are called "maitre de conferences" at the junior level and "professeur" at the senior level, and usually require the applicant to speak French or show the ability to become fluent in French within a year or two so as to be able to teach in French. All of those positions are typically tenured.

Most foreign applicants are primarily interested in CNRS or INRIA positions, so I will focus on those. Pros: no mandatory teaching; no stress about job termination, since the job comes with tenure; living in France. Cons: low salary; living in France. INRIA tends to do research that is somewhat more applied than CNRS, so I will focus on CNRS.

CNRS typically gives funding for researchers to do their work in university labs, so that one is a "CNRS researcher working at University x", in the same way that in the US you can find an "NSF postdoc working at University x". It is possible for a CNRS researcher to change labs and move his job with him, giving the position great flexibility.

It is a national process, with a centralized selection of all CNRS researchers for the entire country. Researchers in theoretical computer science normally belong to "section 6" (unless they fit in one of the cross-disciplinary sections or in the somewhat more applied section number 7) and the selection will be done by the CNRS committee for that section. At what level should someone apply? The guideline is: if the starting date is less than 4 years after the PhD, one is expected to apply for a "CR2" (second class researcher) position, although exceptions can be argued (note that the French PhD is usually awarded after 8 years of higher education). For 4 years or a few more beyond PhD, the norm would be "CR1" (first class researcher). Someone at the tenured level would apply at the "DR2" level (second class research director). A mid-career researcher and beyond would apply at the "DR1" level (first class researcher), if such a position exists that year. It is possible to apply at several levels simultaneously. There are three things that the applicant must do, listed below.

1. Informal contacts. At the present stage - beginning of November - interested applicants must as soon as possible make contact with the places that they might wish to join. In France, departments are structured into research groups, and realistically there is no point in applying without the support of the research group that one wishes to join. A group realistically can support at most one applicant. Now is the time to work these things out. The CNRS applicant can list up to 3 departments that he or she would be willing to join, and gives an order of preference between the three.

2. Written application. The website to apply to CNRS opens on Dec 3, 2012. The deadline for applications to be in will be about a month later: last year it was on January 5 at 4pm. Regardless of what's written on the official application web page, an applicant must make sure to communicate to CNRS, in addition to the required forms, all the information that normally goes with a job application, for example, recommendation letters. After all applications are in, CNRS does a preliminary filter, then selects some applicants for an interview.

3. Interview. The interview will be short (half an hour, maybe) and include a presentation by the applicant and questions from members of the CNRS committee. In the presentation, the application will impress upon the committee how great he or she is. In the questions, those members of the CNRS committee who support other candidates, hence are against that applicant, will try to expose the candidate's weaknesses, so the questions are often on the tough side. CNRS does not pay for travel expenses for the interview.

Outcome. After the interview, the applicant's work is done and all they can do is keep their fingers crossed. The CNRS committee then chooses who to recruit, using some complicated combination of how strong their application looks, how compelling their research area, whether it's a high priority (for that, it's better to work in an area that is under-represented in France), whether or how they will fit in their research environment in France (for that, it is better to work in an area that is well represented in France). CNRS then assigns each successful applicant to one of the departments he or she listed, taking into account the applicant's ordering of the departments they listed, the quality of the fit, and the perception by the committee of national priorities (for example, CNRS often tries to fight centralization by preferring new hires to do research in labs outside Paris).

Unofficial news come through the grapevine right after the committee meeting, confirmed by the next level up a couple of months later (with occasional surprises: it is not unusual that the list of successful applications is changed a little bit), and eventually officially assigned by a formal letter that arrives much later, towards the end of summer, so that the successful applicant often moves to France, finds housing and gets settled before getting the official letter.

Counting permutations: an open question

Nati Linial is giving a talk in Lille. As I am typing, he is stating an elegant combinatorial result and open problem, that I had never seen before.

One dimension ({0,1} n*n matrix with exactly one 1 per row or column): The number of permutations satisfies Stirling's formula: it's [(1+o(1)(n/e)]^n

Two dimensions ({0,1} n*n*n matrix with exactly one 1 per row, column or shaft): The number of Latin squares, as seen from Van Lint and Wilson's book, is [(1+o(1))(n/e^2)]^{n^2}.

Conjecture: in d dimensions, it's [(1+o(1))(n/e^d)]^{n^d}

Linial and Zur Luria proved the "less than or equal to" side. The "greater than or equal to" is still open.

Poincaré and dynamical systems

Etienne Ghys, a famous French mathematician in dynamical systems, is giving a general audience talk in front of me in Lille as I type. He admires Henri Poincaré greatly. Here is one example of a problem studied by Poincaré. You are playing a lottery game with a wheel decomposed into sectors colored red and black in alternation, ask someone to give the wheel a push, wait until it stops, and win or lose according to the color of the outcome. How do you know that the probability of the outcome of the red is 1/2? This is really about studying a map from the initial velocity to the final effect, i.e. the total angle that the wheel will turn. The push will make the wheel turn perhaps up to 50 turns. What do we know about this map? Essentially nothing, but we know that it's a map with a "big derivative". That may sound crazy: what can that mean, when there is no unit? Well, sure there is: for the outcome of the system, the unit is one full turn, i.e. 360 degrees; for the initial velocity, the unit is the smallest difference in velocity that can be perceived. Poincaré: "Ce sont là des différences que le sens musculaire ne peut apprécier et qui échapperaient aux instruments de mesure les plus délicats. La différence dans la cause est imperceptible. La différence dans l'effet est pour moi de plus haute importance, puisqu'il y va de mon argent." Poincare proves that if the cause is distributed according to some diffuse probability measure, then the result is an equidistribution. He says: "You are asking me to predict future phenomena. If, quite unluckily, I happen to know the laws of these phenomena, I could achieve those goals only at the prize of inextricable computations, and I should renounce to answer you. But if I am lucky enough to not know them, I can answer you right away, and the most astonishing thing is that my answer will be correct".

Urban pedestrian projects

Walking Paris day after day gives an opportunity to acquire a deeper familiarity with the city. It takes a long time to get to know a street, and, even without paying attention to the people, I can walk it many times without exhausting its riches. Here are some of the angles that the wandering mind sometimes takes, depending on the day's mood. I have a feeling that they bear the mark of a scientific training, and that a, say, literature major, walking along the same streets and looking at the same buildings, would see completely different things.

Inside and outside plans. Infer the internal organization of a building from the outside setup of doors and windows. Where is the staircase? How many apartments are there? Where are the separations between apartments? Much of the building plan can be guessed from examining the disposition of the windows.

Ceiling heights. It happens that adjacent buildings have the same height yet a different number of floors: one has 7 floors, the one next to it has 8 floors, yet their roofs are lines up. Why? Because the floors have different heights. Correlate floor height to the age of the buildings.

Symmetry and near-symmetry. Find perfectly symmetrical patterns. Find patterns that are not symmetrical. Why not? Are those departures from perfect symmetry accidental or voluntary? Example: The central column of Notre Dame's facade, the tip of the roof behind it, and the tall steeple in the back, are not quite lined up, thus missing an opportunity for pleasing symmetry.

A tradition that deserves to die

How do you know whether you have been accepted to your dream college or university?

Yesterday I heard a microphone in the cloister-like courtyard outside my office. There was a small crowd around a man who was saying slowly, articulating carefully: "... Third: David Smith. [Sound of hands clapping]. Fourth: Jane Doe. [Sound of hands clapping]...": he was publicly proclaiming the results (in the humanities) of the entrance exam of Ecole Normale Superieure!

A few minutes later, I walked across the yard and saw people scattered about, some with a big smile on their face, others crying. Many people were on the phone.

I wonder: Results and rankings are public in France: they are published in the newspapers, and grades are posted on bulletin boards outside schools. But this ceremonial in the historical courtyard goes one more step towards delivering praise and humiliation, and maximizes anxiety among candidates. Could this setup be considered a form of hazing?

Deadlines

Days before a conference deadline (SODA, for this week) are marked by increasing intensity of work, gradually setting aside more secondary tasks as the deadline nears. I used to have a surge of adrenaline on the day of the deadline: now I'm just impatient with myself for not having tied loose ends much earlier.

Day after the conference deadline: goofing off.

Day after the day after the conference deadline: cleaning up. Taking stock of all the urgent tasks that got shoved aside to make room for the conference submission, apologizing for things that were not done and people who were ignored, and working at getting things back under control.

Almost every computer scientist I know works in that way. Almost none of the mathematicians or physicists I know work in that way. Why have we chosen such a stressful and unpleasant way of organizing our work? More importantly, why is it so hard to break the habit? Part of the reason is that the minority rules in that case: in a group of collaborators, it is enough that one person works in that mode to force all participants to adopt it. In the DAG of tasks that need to be done, as long as a few critical tasks belong to a person of that culture, all members of the project have to also follow the same pattern of behavior, I think.

So what can be done to change behavior? Getting rid of hard deadlines would change the way the field works. One possible direction is the possibility of rolling deadlines.

The small world phenomenon

Recently by coincidence I learned that one of my dad's friends from old times was the friend of a friend of a friend of a friend. It's a cycle of length 6. Such cycles are probably quite common, but how easy is it to detect them when there are no shortcuts? Another way to phrase this: how can I discover the people who are at distance 3 from me but have at least 2 paths from me to them? Distance 2 seems feasible: as I chat with my friends, they often tell me about their own friends, so I know a little bit about my friends' friends, and so I can with reasonable chance discover cycles of length 4. But I know nothing about my friends' friends' friends...

Homeless in Paris: a survival guide

It is estimated that about 80 homeless people live in my immediate neighborhood.

There are two kinds of homeless people in Paris. There are some men in their fifties surrounded by bags of stuff, and who look like out of control alcoholics. They have been around for as far as I remember. There are also some people who don't speak much French, who don't have stuff but often are accompanied by something to inspire compassion: women with young children, men with dog and puppies, person kneeling in an attitude of prayerful meditation. I am told that they are "roms" (some kind of gypsies?) and that they form a network similar to Fagin's beggar group.

Yesterday I saw someone different, an older woman with bags of stuff, who was begging without much energy. It was around midnight, on a pedestrian street, and I wondered where she was going to spend the night. I asked if she was going to sleep there. She said, no, of course not, because for a woman there was too much of a risk of being getting into trouble. Instead, she goes to a safe spot, a place right next to the police station. She gets together with two or three other women, and they all sleep near one another, so that they can help if one of them is attacked. Before going to sleep, she also waits until the men have gone to bed, so that they don't notice that there is a woman nearby. Finally, she takes care to wear gender-neutral clothes: a black wool hat and some baggy pants, so that, seen from the back, in the dark one might think that she is a man. Finally, she added that the place near the police station was protected from the rain, and gave me the address. I wished her good night and left.

The thought crossed my mind to offer her a bed for the night in my guest room, but it did not linger. The weather was nice, and sleeping outside did not seem like the worst thing in the world that evening.

Now I wonder if she thought I might be looking for a place where to crash. I was wearing old jeans and a slightly frayed T-shirt, and carrying a backpack. Perhaps she thought I had nowhere to go to, and was giving me advice? How considerate of her!

Priorities

Today the people on the streets in my neighborhood are expressing their joy: Italy won the Euro semi-final.

Today my friends in the US are expressing their joy: the project of reform of health insurance was not struck down by the Supreme Court.

To each their own priorities.

Find the intruder

Today is the start of summer sales in Paris, and the stores have been busy preparing their displays.

Yesterday, walking in Paris I saw four perfectly shaped plastic mannequins displayed on the street just outside a store, facing away from me. Next to them was a large woman, also facing away from me. They had a similar attitude, almost a pose, as if all five of them were idly waiting. I took an imaginary picture of the scene with the camera of my mind, and gazed at it with interest, trying to come up with an appropriate caption: "Find the intruder", perhaps? "Life is not fair"?

Then the woman, who had been talking with another woman, turned around and they both looked at me. Embarrassed, I realized that they had caught me staring. Worse, I suddenly understood that they were prostitutes and might be wondering if I was interested in their services. I hastily withdrew into my best "I'm not really here" look and passed them without another glance.

Travel woes: how the mighty fall

Flying back from Montréal overnight with a red eye, then proceeding to bring a suitcase back to relatives, stopping on the way to rent a moving truck. Driving a truck, maneuvering carefully (with some trepidation), loading boxes and furniture, wondering if I am building muscles in my arms (pure fantasy), and being the object of admiration for my ability to function, impervious to jet lag and to the tiredness of travel. Superwoman! Feeling powerful and in control... until, late at night, one thought suddenly pops up: "What happened to the suitcase?!?" - It turns out that I forgot said suitcase on the train, obviously because of a default of attention due to jet lag. Suddenly life is once again out of control... Now I am back to experiencing SNCF lost-and-found offices. Oh, how the mighty fall!

MoraleLesson: after a red eye, take a day off.

Numbering floors in buildings

Buildings in the US number their floors starting from 1 for the ground floor. Buildings in France number their floors starting from 0 for the ground floor. But this week, I encountered a new numbering system.

I stayed at the University of Montreal student housing, situated on the side of a hill. My room was on floor 17, but the building numbered its floors starting from 7 for the ground floor! Why 7?

Here is my explanation: There were 140 steps from my room to the ground floor: 14 steps per floor. Then, to go to the bottom of the hill I had to go down outdoor staircases, and counted 106 steps, meaning about 106/14 = 7 floors. So, my guess is that the university numbers floors starting from 0 for the bottom of the hill (where another student housing building is located). For my building, it constructs an imaginary extension down to the bottom of the hill and starts counting from there. In other words, the floor numbers are a substitute for altitude: they are not relative to the ground level of the place where the building stands, but have an absolute meaning.

Turing and the Turing award

According to Wikipedia, Alan Turing is known for the following achievements: Halting problem, Turing machine, Cryptanalysis of the Enigma, Automatic Computing Engine, Turing Award, Turing Test, Turing patterns.

So, Turing is known for the Turing award? Isn't that a little like saying that Washington is known for the city of Washington D.C.? That is, isn't it like saying that Turing is known for being known?

One triangulation = three trees

At AofA I saw a talk by Sarah Miracle who presented joint work with Dana Randall, Amanda Streib and Prasad Tetali, showing rapid mixing, for a planar triangulation with maximum degree 6, of a natural Monte Carlo Markov Chain to uniformly generate a random partition into three trees rooted at the 3 outer vertices. This reminded us of the following elementary but striking structural property of planar triangulations.

Theorem The internal edges of a planar triangulation can be partitioned into three trees that span all inner vertices and are rooted respectively at each of the three vertices incident to the outer face.

The proof is elementary and algorithmic, by induction on the number of vertices.

Algorithm
If G is a single triangle,
Then we are done.
Else
  Find an edge {u,v} with u on the outer boundary, v internal, and exactly two paths of length 2 from u to v.
  Contract edge {u,v} into a vertex u', creating a contracted graph G'.
  Recursively solve the problem for G', obtaining three trees, blue, white and red, where, say, the blue tree is rooted at u'.
  Uncontract edge {u,v}, color it blue; other edges inherit the color of the corresponding edge of G'.

Analysis
The only question is: does there always exist an edge {u,v} with the specified properties? The answer is elementary: For u, pick any of the three outer vertices. Let u1,u2,…,uk be the neighbors of u (u2 and uk are the other two outer vertices), and consider the cycle u1-u2-…-uk-u1. Any planar cycle on k vertices has at least two "ears" (vertices from which no chords originate), and only one of them can be u2 or uk, so for v we simply take the other ear.

Tom Trotter's view of Combinatorics

Other mathematicians compete about the complicated theorems that they are able to prove; combinatorialists like to compete about about the simplicity or self-evidence of statements they are unable to prove, i.e., ``I can't even prove ...''
  [As recalled and paraphrased by Mike Saks]

Avi at AofA: population recovery

Fans of "The Land Before Time" know that there are many kinds of dinosaurs: Apatosaurus, Tyrannosaurus, Triceratops, Saurolophus, Pteranodon, Stegosaurus, to mention a few. But is the movie an accurate representation of reality? Were they really in equal numbers, or were there, perhaps, more Triceratops dinosaurs? Enquiring minds want to know: what was the distribution of the various kinds of dinosaurs?

Here is a way to bring the problem into the more familiar realm of mathematics. Think of each dinosaur as a vector, and of each bone as a coordinate. Paleontologists unearth random dinosaur bones, identifying them as they go (somewhat unreliably: errors are not unheard of), and digs can be viewed as "queries". How can we mine the resulting data to recover the distribution of the dinosaur population? That's what Avi Wigderson talked about on Monday at the Analysis of Algorithms conference (AofA) here in Montreal, presenting joint ork with Amir Yehudayoff. (If you don't care for dinosaurs, think "Netflix" instead.)

The population recovery problem: Given k n-dimensional binary vectors, recover a hidden distribution (pv) that draws vector v with probability pv. The hidden distribution is accessed via lossy, noisy queries. Each query draws a vector v with probability pv, and reveals a lossy and noisy version of v: lossy, meaning that the algorithm only sees a random 1 percent of the coordinates; noisy, meaning that each coordinate seen by the algorithm is flipped with probability 49 percent.

The result: Avi gave an algorithm that estimates (p1,p2,…,pk) so that, (with high probability) for every v the estimate for pv is at most an additive error epsilon away from the correct value. The number of queries is polynomial in n and in 1/epsilon (but slightly super polynomial in k).

Here is the algorithm:
(0) Take a few queries.
(1) Find, for each vector v, a small set Sv of coordinates, such that the following condition holds:
  (*) Sv uniquely distinguishes v from every vertex u such that |Su|≤|Sv|.
Let Ambiguous(v) be the set of vectors u that are indistinguishable from v by looking at just the coordinates in Sv.
(2) Label the vectors 1,2,..,k by order of non-increasing |Sv|
(3) For v = 1 to k
  Let zv = the restriction of v to the coordinates in Sv.
  Compute qv, the fraction of the queries whose Sv coordinates are (roughly) zv.
  Let (**) estimate(pv)= qv- ∑ estimate(pu),
    where the sum is over every u in Ambiguous(v), other than v itself, of course
Output (estimate(p1),estimate(p2),…,estimate(pk)).

The first question that comes to the mind of the eager coder is the risk that the code may generate some "undefined" error: isn't there a risk of circularity? Step (3) computes estimates using estimates, but what if the estimates used have not yet been computed?
It turns out that this is not an issue. Why? Because, in step (3), the sum is over u's that are in Ambiguous(v). But by condition (*) we must have |Su|>|Sv|, and by step (2) they are been placed before v in the ordering, so estimate(pu) has already been computed by the time we need it in the right hand side. Hence, no circularity.

The second question is that estimates have errors, inevitably, and when using the algebraic expression (**), those errors will accumulate. To make up for that, more queries will be needed. Now we are worried: in order to have reliable estimates, isn't this algorithm going to require lots and lots of queries? Well, no. The main idea is that the sets Sv constructed in step (1) are small: they all have cardinality at most log(k). Then the graph that has an arc (u,v) whenever estimate(pu) occurs in the right hand side of (**) is a partial order with depth at most log(k), and so errors don't accumulate.

The main remaining difficulty is how to achieve (*) while maintaining sets Sv of cardinality at most log(k). Here is how to do it.

Algorithm for Step (1):
Start with the empty set for every Sv
Repeat
  While there exists an Sv and a coordinate i such that adding i to Sv decreases |Ambiguous(v)| by a factor of 2
    Add i to Sv
  If condition (*) is violated by some u and v,
  then replace Su by Sv
Until condition (*) holds.

Why does that work? By some elementary magic.

An interview of Avi Wigderson

Q: Do you consider yourself a Mathematician or a Computer Scientist?
A: Both. It is very clear that Theoretical Computer Science is a mathematical field. We prove theorems. The reason why we are in Computer Science is that the main mathematical object that we study is computation.
Q: How did you get interested in this?
A: In college, in computer science, the best teachers I had were in theoretical computer science, for example Shimon Even. I was also into Math beforehand.
Q: Why did you decide to do a PhD?
A: I didn't come from an academic background, but all the good students in my class went on to do a PhD, so I followed their example. Once, as a PhD student, I realized what research was, I knew that that was what I wanted to do. Dick Lipton, in Princeton, was my advisor. He's the most amazing guy. He was changing his field of interest almost every month, and I was following along and learning many things.
Q: What was your first research project?
A: An efficient algorithm to sqrt{n}-color 3-chromatic graphs. I also worked on succinct graph representations, cryptography, VLSI layout and parallel computing in collaboration with other PhD students.

Q: How do you work with your graduate students?
A: In the last decade I have been working mostly with postdocs, so I'll talk mainly about my time at the Hebrew University.
I don't let them wander off. I keep in constant touch with them. I started off as a young faculty member at the Hebrew University with an excellent group of 4 graduate students. We'd meet and talk. I like talking, as you know. They were into different types of problems, and we often learned an area together.
Q: Would you have advice for first year graduate students?
A: I would advise them to do things that they really like, things that they develop a passion for. There are students who try to find "hot" topics, others who try to find topics on which there won't be the stress of competition, but those are secondary reasons.
Q: How do you get your beginning students started with research?
A: I give them a bunch of papers in different areas that they might be interested in. Then I ask them: What did you feel? What are you most attracted to? Then we discuss the ones they liked and try to think of related problems in these areas.

Q: What makes a question a "good" research question?
A: I like a technical challenge, when the usual attempts don't work. More precisely, I like problems for which natural-to-apply techniques don't provide the answer. Then there is "taste". Taste is hard to define. I am usually motivated by some higher goal of understanding, so that the question is part of a journey towards some bigger goal to which it is potentially related. Sometimes I also simply develop trust in the taste of my friends. You know that, of course: if, say, Alistair Sinclair comes to you with a problem to work on, you'll be happy to work on it even if you yourself do not quite see immediately why he likes it or the larger context in which it fits.
Q: What is your favorite result in your own work?
A: Zero-knowledge. It's so much fun explaining it to people. It's very rewarding.
Q: Practical impact. What would you say about that?
A: It's not a strong motivating force for me. Many of the questions I study are fundamental in nature. The intellectual challenge is my primary motivation. Of course, in our field, I believe there is a strong correlation between fundamental questions and practical impact (eg theoretically defining and understanding computationally such basic notions of "secret", "knowledge", "randomness", "learning", "proof" yielded great benefits, both intellectual and practical)

Q: How much time do you spend reading papers?
A: When I was a student, I devoured journal papers. Now, not so much. After hearing a lecture, I read the paper when I want to learn a technique. Sometimes I go to a math textbook to learn a certain topic which may be useful to a research project.
Q: Do you have role models?
A: I had Dick Lipton, when I was a PhD student, of course. I also have great admiration for some people who have developed completely new models and notions, and thereby new areas of research that have changed the field: Valiant or Blum for example.

Q: You've been in the field for roughly 30 years. How has it changed?
A: It's much larger in many ways. The number of areas we study has increased a lot. Learning didn't exist. In crypto, Goldwasser, Micali and Yao had just started. Distributed computing was very limited. Few Probabilistic algorithms existed. Connections with statistical physics ideas, Monte Carlo methods, all that was not there. Mechanism design and other connections to economics did not exist. A large part of the growth was due to connections with other fields. There were also developments with subfields of Mathemetics such as analytic number theory, group theory, pseudorandomness...
A: The other way in which it has changed is the recognition by the mathematical community of the importance of the field, that just blasted. We are generating great questions for mathematicians, and they love it. They recognize that they are fundamental questions. They have to rethink a lot of what they're doing and use the computational lense.
Q: So, students have to be much more mathematicaly sophisticated?
A: Yes, but they can learn what they need. There are fantastic people in the field. The young people entering the field have phenomenal talent, both technically and conceptually. TCS is a primary field of interest for the best mathematically talented young people to go in. It is a great sign for the health of a scientific field when it attracts such talent.
Q: I actually find it a bit intimidating. How to advise students who are so talented?
A: I am not intimidated by talented people, young or old - they are great to learn from. When advising young people, age provides the advantage of experience. Sometimes we can predict which directions will be fruitful and which directions that will turn out to be dead ends (although we're sometimes wrong), sometimes we can tell which questions people will like (although we are sometimes wrong). But youth provides energy and fresh thought which can often be more important than experience and is always wonderful to be around. Our profession is among a few that allows real constant interaction with young people, and to me this is a great aspect of academia.
Q: Concretely, how did you go about attracting students to theoretical computer science?
A: Here's one method. I teach a graduate course in computer science, I open it to undergraduates, and I advertise it in the Math department. That's how I got Ran Raz, for example.

What is Ecole Normale Supérieure?

The French "Grandes Ecoles" system of higher education is very difficult to understand for foreigners. Pointing out the features that are unique to that system only creates perplexity and confusion. Instead, let me point out some features that are common with some schools in the US (the other system with which I am familiar).

Consider the "Ecole Normale Supérieure de la rue d'Ulm", quite a mouthful of a name! (It is also called "Ecole Normale Supérieure", "ENS", "ENS Ulm", "rue d'Ulm", or "Ulm" for short.)

It is old, dating from the late 18th century. Part of its fame comes from famous alumni in its long history. It has developed its own vocabulary and traditions.

It is primarily famous for its "undergraduate" students (roughly). For example, the totality of French-raised Fields medalists are ENS alumni, but their PhDs were obtained at a variety of universities, and their research work as graduate students was not done in the labs of ENS. As far as I can tell: Strasbourg (Schwartz, Thom), Sorbonne (Serre), Paris 6 (Connes, Lions, Werner), Ecole Polytechnique (Yoccoz), Paris 11 (Lafforgue), Paris-Dauphine (Villani).

It has sister schools that are independent of it but that have roughly similar goals and structure: ENS Lyon (also sometimes called "ENS" in context, for example when one is in the town of Lyon) and ENS Cachan.

It teaches academic subjects covering the spectrum of arts and sciences. No preeminence is given to science over the humanities.

It is tiny: only 2200 students! ENS Cachan and ENS Lyon are similarly small.

Traditionally it largely left students free to learn whatever they wanted and to follow their intellectual pursuits in whatever way they wanted, with the idea that they could be trusted to do something worthwhile with that great freedom. (But it is not clear how much of that tradition still exists nowadays.)

It is the best in its category: no student accepted at ENS ever turns it down, except for some scientists who choose to go to Ecole Polytechnique instead. (Ecole Polytechnique is for sciences only and has a different style)

Many of the students are very, um, aware that they "are the best"...

So I think that someone from the US and who would be looking for a rough and simple analogy could consider that ENS Ulm, ENS Lyon and ENS Cachan are the French Ivy League schools, and, among those, consider that ENS is the French Harvard. (Similarly one might perhaps consider that Ecole Polytechnique is analogous to CalTech.)

The single most outstanding difference between ENS and Harvard lies in their mission: Harvard educates students to serve society, but the particular ways in which they will serve are left undefined. In contrast, the three ENS schools (Ulm, Cachan, Lyon) exist to educate students who will serve society in well-defined careers: the students are primarily future academics, teachers, and researchers. (Thus, for example, Ivy League schools recruit students with excellent grades but who also additionally show some other, non-academic potential, whereas the ENS schools recruit solely on the basis of academic performance.)

The next most important difference is financial. The ENS are public, and the French state aims to offer the best possible conditions to help its most promising young people become leading academics: one way in which it does that is by paying for their studies for 4 years (in return, the students commit to serve the state for 10 years.) That is, the ENS pays the students, whereas Harvard asks the students to pay.

An interview of Maurice Herlihy

Q: You just received the Dijkstra prize for the second time. What did you receive this award for?
A: The Transactional Memory paper. The basic idea is that designing highly concurrent data structures is much too hard and people who work in that area have to focus on too many tricks. Mechanical tricks are too easily confused with essential issues, and that paper was an attempt to make it easier to deal with the mechanics, to allow researchers to focus on the core aspects of synchronization algorithms.
Q: What's the result?
A: Hardware designing.
Q: What do you mean?
A: A way of designing cache coherence protocols to allow the programmer to avoid conventional mechanisms such as locks. You can say what it is that you want to be atomic, without specifying how. It's an implementation of a very simple abstraction. The paper was very concrete, with hardware architecture.
Q: How did it have impact?
A: The paper is from 1993. For the first 10 years, nobody paid any attention to this paper. There was an average of 5 or 6 citations per year. Then in 2004 changes in technology meant that processor clock speeds could no longer improve, so people went to multicore where there is a lot of concurrency, and then they discovered that no one had any idea how to use them.
Q: You make programing multicore machines easier to do and to reason about?
A: It has other software engineering benefits, some performance benefits. The entire story is complicated but big picture is that it makes it much easier to write concurrent programs.
Q: Can you give an example of a concrete impact?
A: The Intel Haswell processor, their next processor, has transactional memory built into it. Intel laptops from now on have a machine that supports transactional memory in a form not much different from the 1993 paper.
Q: Do you have a patent?
A: I do but it's not mine. I gave it to my employer who was DEC. The patent may be expired.

Q: What did you think of it when you were doing it?
A: A very nice idea solving an important problem, but I knew no one would care about it. I was convinced that it could become a very important idea, and at the same time I was very surprised when it did.
Q: Do you have any other papers waiting to be discovered?
A: [...]
Q: How did you think about it?
A: It came up in a conversation with Eliot Moss, coauthor on the paper. I was interested in lock-free data structures and he was interested in architecture and we were talking about how difficult it was to do lock free data structures on modern architecture and Eliot asked whether one could use cache coherence protocols to address the problem.
Q: This piece of research was instantaneous?
A: We had been office mates as grad students at MIT before, so we would meet from time to time casually for conversation, so this is an example of why it's a good idea to talk to people from other areas. What made it so unusual at that time was that it was a linkage between concurrent data structures (very high level) and hardware design (very low level). It required a broad CS culture.
Q: What does that say about how to do research?
A: You need to have conversations with people who are not goal directed. Neither one of us working individually would have done this. We knew something about one another's areas but would not have concentrated enough to see this connection.

Q: Do you have any opinion of the streaming computational model?
A: It's something that has gone, in a very short time, from ad hoc to methods that are much better founded in theory.
Q: What about MapReduce?
A: It's been enormously successful, but it's very limited in what it can do, and everybody is trying to invent or discover the successor to MapReduce.
Q: Does it mean it's not worth investing a lot of time into it, say, designing algorithms for it?
A: Because MapReduce is so important, any improvement will have immediate impact, but it's something done better as a large company, in industry rather than in the academic world. There 's also a lot of engineering that goes on in this area.

Q: How do you go about doing research?
A: I am opportunistic. I have a general area of interest, namely, concurrency, but I worry about becoming too specialized, so I make an effort to balance my attention between more applied and more theoretical areas, because, often, that's where you have the opportunity to write the first "easy" paper and let the ones who write the difficult papers cite your paper.
Q: So you're a pioneer?
A: Maybe more of a vagabond.
Q: Are you ever tired of research?
A: No.
Q: Do you do research on vacation?
A: Yes, in my head.
Q: Do you always have some problems you're working on?
A: Yes, usually something that's good for in the shower, or for riding on the metro.
Q: Usually, do you work on several problems at once, or focus on a single one?
A: Usually several small problems at once, because when you get tired of one, then you can turn to the others.
Q: What are your current interests?
A: Right now, I'm writing a book on combinatorial topology and distributed computing, and I'm also interested in systems aspects of multicore. Since almost nobody is interested in both of these topics, it means that I can talk to twice as many people!
Q: Where are your collaborators?
A: Almost everywhere except at Brown. I'm writing the book with one coauthor in Mexico and the other in Germany. I am visiting several collaborators here in Paris. I work a day a week at Oracle labs in Boston.

Q: Distributed computing is not taught much in the undergrad curriculum. What do you think of that state of affairs?
A: I think that that will inevitably change. What will be taught will be multiprocess computing, because soon every computer will be multicore. Today I think that it is a little bit of a scandal that we don't teach parallel computing to our undergrads until late.
Q: Are you familiar with the CLRS textbook on Algorithms?
A: There is a chapter on parallel computing but it's an area that changes rapidly.
Q: So, what about distributed computing?
A: The problem with distributed computing is that there are many models of computation. We're trying to capture many different kinds of phenomena. The culture isn't one where people think standardization is important. Every time someone writes a paper, there is a tendency to use a slightly different model and we're not organized enough as a community to present a coherent story to the world. We're a little like European parliaments, we split into many small groups and argue with each other instead of presenting a unified front.
Q: I take it that that's a criticism?
A: It's an observation. This situation is exactly the reason why I'm writing the book. At present, when you work in this area, you have to read a dozen badly written papers. That presents a large barrier to students and outsiders, and the hope of the book is to present a single coherent story, at a level that's accessible to advanced undergraduates.
Q: When is it coming out?
A: End of this year?
Q: Have people been teaching from drafts of this book?
A: No, people teach from drafts of my other book, a much more applied textbook.
Q: What's your community, the conference where you feel most at home?
A: PODC and DISC, which are basically the same conference but on different continents.

Q: What got you interested in distributed computing?
A: As a grad student at MIT, Barbara Liskow had an opening (physical opening: a chair) in one of her offices, so I drifted into her group. Who you sit next to is perhaps the most important influence in your life. I was floating around looking for a group and the other groups on that floor weren't very friendly, but Barbara was happy to talk to a new student.
Q: Why did you go to MIT?
A: Because I was already living in Cambridge and my girlfriend didn't want to move.
Q: Why did you go to grad school?
A: I got a degree in pure math and I wasn't sure what I wanted to do and at the end of summer after I graduated I needed to start paying rent so I applied at random for jobs. I had one job offer to teach math at a boys school in Michigan, one to write Fortran programs for the DOT in Cambridge, then I went from there to working at a research group at the MIT business school, but one day they lost their grant money. They didn't fire me but they fired the guy who did the tape backups and told me I now had to do tape backups, and so I applied to grad school.

Q: What's your biggest regret in your career?
A: I think it's being slow on the intake. There are many ideas that turned out to be successful that should have been obvious much sooner. I could have gone to grad school right away instead of working as a Fortran programmer for 3 years.
Q: That was a waste of time?
A: Not really because, whenever I get frustrated, I remember that time and realize how fortunate I now am.

Eliza in 2012

My first year students had to program Eliza, a program to have a conversation with a human being. I just got a taste of what Eliza's capabilities are in 2012. Here is my conversation. I am not impressed! __________________________________________________________________

Please wait while we find an agent to assist you...

You have been connected to !Albert F.

Claire: Hello! I moved to France and want to close my account.

!Albert F: Welcome to T-Mobile live Chat. I’m Albert F and my rep ID is 1450719. I will be happy to asist you today.

Claire: I just moved to France and wish to close my T-mobile account

!Albert F: Hi Claire, I feel so sad to know that you want to close the account. May i know the reason why?

Claire: Because I just moved to France.

!Albert F: I can definitely assist you about your concern.

!Albert F: Let me first review the account and see what I can do for you today.

Claire: Are you a human being or an automated device?

!Albert F: Thank you for waiting.

!Albert F: Requests for cancellation must be processed over the phone to ensure that your concerns are fully addressed. We value your business and have Customer Care Representatives available to discuss your T-Mobile account. Simply Dial 1-800-937-8997 or 611 from your T-Mobile handset

Claire: I cannot call an 800 number from abroad

Claire: And my handset does not work in France, so I cannot do what you suggest.

!Albert F: You may call T-Mobile International Customer Care from a cell phone by dialing +1-505-998-3793, or (IDD Code) 1-505-998-3793 from a landline. It is a free call from a T-Mobile USA handset while roaming in another country but please be aware of international calling costs from a landline provider.

Claire: Ok

!Albert F: Is there anything else?

Claire: No, thank you.

Claire: Bye

!Albert F: You are welcome!

!Albert F: Thank you for choosing T-mobile Chat, We appreciate your business. Have a great day!

Thank you for using our online help. You may now close this window.

Your session has ended. You may now close this window.

Why did I decide to study theoretical computer science?

The question was posed in a comment a few days ago. Here is the answer: I wanted to study Math and was potentially interested in algebra, number theory, or some other area of Math dealing with concrete objects such as integers. But during my first year at Ecole Normale Superieure, I was forced to take a mandatory computer science course called "Cours de Sevres".

In 1983-84 the course, originally created by Jean Vuillemin, was taught primarily by Claude Puech (programming in Pascal, and basic algorithms and data structures), along with other instructors in analysis of algorithms (Jean Marc Steyaert), logic (Guy Cousineau), formal languages (Jean Berstel, Jean-Michel Autebert), and Petri nets (I have forgotten the instructor's name: Guy Vidal-Naquet, maybe?). I enjoyed programming, algorithms, and formal languages, and was particularly excited by algorithms. During the same year, in Math I took courses at Paris VII university, a mix of easy courses that bored me to death, and of more advanced courses that seemed to me too abstract and meaningless (Differential geometry come to mind - a course I only barely managed to pass). At the end of the year, I decided to switch to computer science and signed up for a DEA (Masters') in computer science at Orsay.

In retrospect, it is clear that Cours de Sevres was designed to lure would-be mathematicians into computer science by focusing exclusively on theoretical topics (I never understood why graph theory was not one of the topics taught), and provided an obviously biased image of computer science. Nevertheless it has had a lot of impact in forming many people who are now computer scientists in France.

So, I would say that deciding to study theoretical computer science was not a reasoned choice on my part, but largely a coincidence due to context. I never stopped to think about a profession as a way to contribute to society. I never considered how to best fit my talents and tastes to the potential needs of society in the coming decades. I simply picked a field in the same way that one picks a hobby: do what you enjoy, and if you succeed, continue. It is only a few years later, when I heard that I was recruited to CNRS and realized that I now had a job for life, that suddenly the question occurred to me: "What's the point?"

There is an inconsistency in this: I am against mandatory courses. Students only learn what they are interested in. You cannot take an ass who is not thirsty and force it to drink. Yet I would not have taken Cours de Sevres if it had not been mandatory, so my own experience goes against my own opinion!

Welcome To France

After a few days of uninterrupted bliss, yesterday I had my first Welcome To France moment. That's the term American expats use in France when something happens that, in their opinion, defies common sense and is thoroughly unAmerican. As I am now American as much as French, I, too, am now at risk of reacting in that way.

Yesterday a technician came to my place to install an internet and phone connection. Unable to find the very easy Parisian address, he called me twice on the way; parked his car illegally, got it towed away, had to go to the car pound to get it back, and finally showed up at my place two hours later, in a rotten mood. He then told me that he needed to change a plug that was hidden behind the TV and hard to access. The TV had to come off, but he wouldn't touch it, because he did not want to be responsible if anything happened. After calling my landlady, locating the instruction manual, and examining the TV, I realized that all I needed to do was remove a bolt, unscrew a single screw, and the TV would come off. I had no tools, but what about the technician? No such luck: he declared firmly that he had no tools, that the appointment would have to be rescheduled, and I signed a piece of paper that said that he had come to my place and that the result had been "echec": failure.

A technician comes to set up an internet connection but has no tools, not even a monkey wrench? Welcome To France.

Harvard: a model for French universities?

Yesterday's issue of Le Monde newspaper had a full page article on everything that is admirable about Harvard, the "best university in the world" according to the Shanghai ranking, that the French seem to pay close attention to.

The person interviewed, Stephanie Grousset-Charriere, first points out that she was hired as a lecturer after four half-hour meetings with members of the department faculty (she's in Sociology). This comes in sharp contrast with the French system and its extremely short interviews, every applicant giving one talk each, scheduled back to back on the same day, resulting in tenured hires.

The French hiring system seems almost incredible in its lack of seriousness in hiring, until one realizes that a lot goes on behind the scenes. It is normal for serious candidates to arrange to give an hour-long seminar some time during the previous months. Phone calls are given, opinions are discreetly sollicited, and there is an unspoken expectation of thorough background work that culminates with the final formal interview, whose role is mostly to confirm opinions, clarify lingering doubts and resolve remaining questions about the applicant. At least, that is my impression, but I don't know for sure. Part of the reason is that compared to the US, France is a relatively small country, so promising candidates can be identified early on. But at a time when the process is becoming more international, the lack of transparency is a major obstacle for foreign applicants: it is hard for them to know what is expected of them. For example, would their calling the chair of the hiring committee be considered a breach of ethics or lack of good manners, or would their not calling the chair of the hiring committee be considered a sign of disinterest or lack of good manners? They don't know, and for them, applying is a little bit like walking a minefield. At a time of increasing internationalization, I think that the French system is a handicap (not to mention the risk of manipulation).

The article then points out that Harvard provides new faculty with pedagogical resources. The first lecture is filmed and criticized, and there is a training camp for new faculty. In my experience in various institutions in the US, the pedagogical resources available are not very important in themselves, but their existence signals a commitment. When I was a professor at Orsay and at X, my teaching issues were discussed around the coffee machine. At Brown, my teaching issues have also typically been discussed around coffee. Colleagues help colleagues identify the reasons of their problems and give shape to possible responses that they can then try out. The main difference was that at Brown, more faculty are interested and willing to spend more time fine-tuning their teaching. Why is that? I think that it is because of the low teacher-student ratio. As mentioned in the Le Monde article, at Harvard (and other similar institutions) there is a very low ratio: the number of students enrolled is about 10 times the number of faculty. That naturally implies that the faculty teach fewer courses to fewer students, and therefore have more time to devote to making their teaching effective. I think that in places with a low student-teacher ratio, the instructors have almost a duty to teach outstanding courses, and, perhaps, their courses can serve as models for similar courses in other institutions.

The article also mentions Harvard expectations that the faculty will be well dressed, smiling and polite. That made me laugh; obviously they have not looked at computer scientists! Unless Harvard stands out in a unique way, in computer science the instructor's clothes are completely nondescript.

The article points out that in Management, the instructors know a lot about real life applications, but it does not give a reason for it. I would agree that faculty in the US have more connections to the world outside academia (in industry, for computer science), and that it is a good thing. I have a conjecture as to the reason: in France professors are paid 12-month salaries, but in most universities in the US, they are paid 9-month salaries, and for the other three months, are expected to find funding on their own: typically by getting grants, but also by consulting with industries. It's a strong incentive to keep a link with the outside. At the same time, it guarantees that the university chores will not encroach into the summer months: in June, July and August, the faculty owe nothing to their university, and no one has any grounds for complaints if they are away.

The article talks about the generosity of Harvard alumni. Why are former students so generous in their giving? One reason is the tax structure: I believe that those donations can be for extremely large amounts and are entirely tax deductible. Another reason is that Harvard (or Brown, or most other schools in the US) develops a loyalty to the institution, by promoting events that serve to celebrate Harvard. Ceremonies start and end the university school year, speeches are given, traditions such as distinctive university colors, a motto, a mission statement, a song, are encouraged. Famous former students are celebrated. Anecdotes about life at the university are preciously kept, and an image of the institution develops, like a nation. In the same way that people might say: "We the French particularly care about human rights (or about food)", they might say "At Brown, students are into social justice". In a similar way that there is a pride of being French, students develop a pride of being from Brown, not necessarily because it is the "best" place in some absolute way, but because of its distinctive features. How does that help generous giving? Making a donation is a way to give back to the institution. Donors remember what they learned while at Brown and all the good things that they received from Brown during their education, and later in life, if they become rich, they may want to offer similar opportunities to future generations by giving to Brown. Fostering such sentiments requires giving students a good experience during their education, and making sure that the school has a strong enough identity that the student associates their experience specifically with their school. In contrast with that, I remember talking to a former student from Ecole Normale Superieure right after I was admitted. She said: "Being accepted at ENS gives you three things: first, a label that will help you in the next few years; second, a salary during your studies; third, cheap subsidized housing in Paris. That's it." How depressing it was to hear that! I think that her assessment was incorrect, but such was her experience. How could someone like her ever be tempted to make a donation?

How to ask questions

Mike Mitzenmacher said once that I ask lots of questions. In teaching I always ask lots of questions, because the students are the ones who build the lectures. When I meet some well-known computer scientists I sometimes take the chance to interview them on research and life. Recently I have also pursued a project outside work that involves interviewing academics. How to go about asking questions, especially from strangers? First, I am interested in what they have to say. Seeing what is in other people's minds is always a thrill. Second, I have no interest in boiler-plate answers. In class, I want to hear how students think about a problem, not a repetition of what the textbook says. In interviews, when I ask someone, for example, why he or she decided to become a researcher in theoretical computer science, what I'm hoping to hear is their story, not the answer that they think they're supposed to be saying. (That's why it works better with senior people: they have more freedom of speech, because they have no worries about jobs or tenure.) Third, if they seem open to questions, I try to see how far I can go, and it can sometimes go to the limits of people's comfort zone (or beyond if I misjudge). It is a way to try to learn about people, in a fashion similar to when trying to learn about a scientific problem: to understand it, ask a variety of questions about it, aiming not for the trivial nor for the unanswerable, but for the zone at the threshold. The downside is that it's not very polite. In British culture, it can come across as downright rude. The movie "A room with a view" starts with a scene where a man offers to trade his hotel room with a woman he does not know, after hearing her complain about the lack of view from her room. He means well and shows common sense, but is perceived as insufferable. No sense of proper reserve! How incredibly ill-mannered! I have heard that academics in general have the reputation of lacking good manners. Could that be related? Could the willingness to ask hard questions about open problems, if it is unchecked, correlate with a tendency towards bad manners in society?

Base case trouble

The entirety of my silverware is packed in boxes on their way across the Atlantic. It only took me a few hours to realize my mistake. As backpackers know, one cannot survive long without a knife, so I quickly bought a knife at the nearest store. There is a world of a difference between having one knife and no knife at all! However, good, sturdy knives come in good, sturdy packaging, a mixture of cardboard and of hard plastic. How do you open such packaging? With a knife. Thus, in order to get a knife, you need to already have a knife! So, how can one go from the knife-less state to the state of having one knife? After that initial knife it is easy to get a second one, a third one, etc., but getting started with the first one is a challenge. (Today's solution used a lengthy mix of the following ingredients: twisting, turning, hitting, pulling, and a dash of swearing.)

Models for evolving structures

How do you model a structure that evolves over time?

How do you keep track of an approximately sorted order with few probes, when the true underlying order evolves over time? Agnastopoulos, Kumar, Mahdian and Upfal designed an algorithm assuming the following model for an evolving order: at any time, there is a ground truth order, and the next change will consist in a swap of an adjacent pair, where the choice of the pair to swap is made uniformly at random.

How do you keep track of the minimum spanning tree of a weighted graph that evolves over time? Agnastopoulos, Kumar, Mahdian, Upfal and Vandin designed an algorithm assuming the above model for the evolving set of edge weights.

How do you keep track of an unweighted graph that evolves over time? Agnastopoulos, Kumar, Mahdian, Upfal and Vandin designed an algorithm assuming the following model for an evolving graph: at any time, there is a ground truth, and the next change will consist of swapping out an edge and swapping in a non-edge, where the choice of the edge to swap out and the edge to swap in are made uniformly at random.

Those models that are simple enough to be amenable to analysis. They are combinatorial, independent of the distribution of the numbers themselves. That makes them quite elegant.

More generally, if one has a static distribution of structures, a local operation to modify the structure such that the set of structures is connected under that operation, and an associated Markov chain such that the asymptotic distribution is the desired status distribution, then that naturally suggests a model for the evolving structure: simply run the Markov chain.

Other examples that fall into that category: random binary trees evolving by rotations; random planar triangulations evolving by edge flips; etc.

The challenge of knapsack in practice

Every item in my house has to be placed in one of three categories: (1) moving to France, (2) going into storage, and (3) to be disposed of. For each item, there is a cost for (1), another smaller cost for (2), and possibly a profit from (3). Each item has a value if it is in France and another value if it is in the US.

This is an instance of combinatorial optimization that is very close to research problems I have worked on, so one would expect that I would be an expert at handling this.

Yet I am paralyzed by indecision. Why? Because every information is "soft". I don't know how to evaluate each item! I don't have a hard bound on the maximum cost of moving! There are too many items for me to be able to ponder carefully the value of each object! In addition, that value depends on the unknown future, and I cannot model it with scenarios and probabilities. That's not how life works.

There will be only a single execution of that algorithm that is my life. Only one future, many unknowns on which it depends, and no probabilistic model to represent it.

Course conclusion

Simone Weil (sister of mathematician Andre Weil), about teaching and research in the sciences.

On science: “The true definition of science is ... the study of the beauty of the world.” “Joy ... is the feeling of reality. Beauty is the manifest presence of reality.”

On problem-solving: “Whenever the intelligence is brought up against a contradiction, it is obliged to conceive a relation which transforms the contradiction into a correlation, and as a result the soul is drawn upwards.”

On searching for what is true: Before we start writing or reading anything, we should always ask ourselves, “Am I in line with truth?” or “Am I going to find truth in here?”

Intellectual intimacy - not!

The other day, in class, I asked a hard question. I had one specific answer in mind. Suggestions came forth, but not in the direction that I wanted.

Finally one student raised his hand, and started to phrase his answer as I looked at him expectantly. I could tell he had precisely the right idea in mind, the one that would make everything come through beautifully. He had a ghost of a smile as he talked, and I smiled back: I knew the suggestion he had in his mind, it was the same as the one in my mind, and he knew that I knew, and I knew that he knew that I knew. But none of the other sixty or eighty people present had any clue. Yet there had been no communication between us that all the others had not been party of. Sweet moment of intellectual closeness! Normally, that sometimes happens in one-on-one research, but not in class.

Then the student said one more word, and everything came crashing down: he actually had the wrong idea. Oh, no! I had imagined extra sensory communication of brain waves, but it was all a fantasy!

Slang

I enjoy using American slang. As soon as I learn a new word or idiom, I wait impatiently for an opportunity to use it. I find those words often colorful and vivid, and trying them out gives me great pleasure.

Unfortunately using slang is a tricky matter. Context is crucial. Once, when I was visiting elderly American relatives, we were playing bridge together, when, looking at my hand, I commented: "What a pile of crap!" - A stunned, dismayed silence followed. Oops!

It's particularly difficult because slang is used a lot more in French than in English. To viz, the infamous: "Casse toi, pauv' con!" At faculty meetings at Brown, I virtually never hear slang. But at faculty meetings in France, well-chosen (not all) slang words are a natural part of the vocabulary.

So how can I know when slang is or is not appropriate, and what is the scope of a particular word that I am itching to try out? The answer is: the online slang dictionary. It gives not only the meaning of a word, but also its degree of "vulgarity". Very useful! That might save me from other embarrassments in the future. (example.)

From that website, after certifying that you are over 18 years old (!?), you can even access a list of the 100 most vulgar slang words. I was able to check that I do not use any of them, and in fact, there are many whose meaning I do not know. I love the internet!

Podcast assignments

I went to a talk on Friday advocating the use of podcasts or webcasts instead of written assignments. Instead of a written algorithm and proof, the student could turn in a Khan academy style proof, at most 2 minutes long.

I think of the number of times that a student has come to my office to question his or her grade. I would ask them: "Can you read to me what you wrote? Just read it aloud to me." They would start reading, then stop and say: "Well, I didn't write xxx, but of course that was what I had in mind". They would continue, then stop in some embarrassment at the lameness of their style. The lack of precision in their writing would be painfully obvious, and sometimes they couldn't help but laugh at themselves. I wouldn't need to explain why they didn't get full credit: once they read aloud, the reasons became obvious.

A webcast might be the answer!

The process of discovery

The other day I taught a reduction from 3SAT to Independent Set, and I learnt a lot from the lecture. I asked the students who had not seen reductions before to come up with it themselves, but I actually had no idea how they could go about it. My question was more like an act of faith than like a lecture plan. I thought to myself as I asked them to find the reduction: "What do I say next if no one has any suggestion? I have no idea." When, as a student, I learned that reduction, it was given to me as if by fiat, and I did not understand how one could come up with such a reduction with no knowledge of gadgets and without having seen any non-trivial reduction before.

But I was wrong to worry. I was delighted to hear many ideas spring up from the room, was careful, to save time, to prune the suggestions that I knew would lead to a dead end, and was very impressed that my class, with no prior experience and in a truly collaborative effort, was able to create all the pieces that combine to make the reduction. I hope that, like me, the students who had seen the reduction before (and who were primarily bystanders in that part of lecture) learned from watching their peers at work.

The first observation that started the discussion was that each variable in a 3SAT assignment is either true or false, with exactly two possibilities, and each vertex in a graph is either in the independent set or not, so, "by analogy", one could try to create one vertex per literal, and, for each variable x, connect the vertex "x is true" to the vertex "x is false" by an edge. The student who suggested that told me that he had never seen it before. It was not reconstructed but created ab nihilho. Impressive! I am singling out that comment because it was the first one and broke the ice, but there were several other equally insightful and creative suggestions from all different students.

The process of discovery is fascinating to watch.

Walking out of class

Students sometimes walk out of the room during my lectures.

I know that it is considered not polite. Once in the room they should suffer through the lecture until the end, advocate proponents of good manners. But why? If they are bored, if they know the material already, if they are hopelessly lost, if they are suddenly taken by a bout of sleepiness, or if, for whatever reason, they are not getting anything out of attending class, why should they stick around?

In the room where I teach, it is easy for people near the side alley to leave discreetly without, I think, distracting anyone. I see out of the corner of my eye the figure of someone leaving, but it does not interrupt the lecture in any way. Of course I hope that students are benefiting from lectures, but if not, isn't it slightly hypocritical for them to stay?

I pretend to teach, they pretend to learn, and it becomes a charade.

The destiny of the professor's wife

Daniil Kharms wrote a story about a professor's wife. Here is the beginning.

Once a professor had something to eat, and you could not say a little something, and he began to feel sick. His wife approached him and said: "What's wrong with you?" And the professor said: "Nothing." The wife went back to the kitchen.

The professor lay down on a divan, stayed there for a while, got some rest, and went to work.

And there, a surprise awaited him: They had cut down his salary, instead of 650 rubles now he made only 500. The professor tried everything, but nothing would help. He went to the director, but the director wanted to strangle him. He went to the bookkeeper, and the bookkeeper said: "You should go see the director." The professor got on a train and went to Moscow.

On the train the professor caught the flu. When he got to Moscow, he was so sick he could not get off the train.

He was put on a stretcher and taken to a hospital.

He stayed there no longer than four days and died.

The professor was cremated, and his ashes were put in a little jar and sent off to his wife.

So here is the professor's wife, sitting and drinking coffee. Suddenly the doorbell rings. What's going on? "You got a parcel." The wife is very happy, she is smiling, tipping the mailman with 5 rubles, and quickly opens the parcel.

She looks, and inside the parcel are a little jar with the ashes and a note: "This is all that is left of your husband."

Reductions

Today I was teaching reductions. I found a relevant quote on wikipedia:

Q: How do you shoot a blue elephant?
A: With a blue elephant gun.
Q: How do you shoot a yellow elephant?
A: Have you ever seen a yellow elephant?
Q: How do you shoot a red elephant?
A: Hold his trunk shut until he turns blue, and then shoot him with the blue elephant gun.
Q: How do you shoot a purple elephant?
A: Paint him red, hold his trunk shut until he turns blue, and then shoot him with the blue elephant gun.

Spring school heaven

This past week, during Brown's Spring break, I gave a couple of lectures at a Spring school in France on theoretical computer science.

It took place on an island off the Atlantic coast, in a campground about a mile from lovely beaches of fine sand. There were slightly more than 40 students, postdocs, and researchers there to learn from the lectures, and a half-dozen lecturers, a ratio of about 7 to 1. The weather was amazing, with bright sun and exceptionally high temperatures every day, and so, instead of observing the usual lecture format, the school improvised ad hoc Socrates-like discussions: every morning we split into small groups, with one instructor per group, got on our bikes and headed to the beach. On the beach, we formed small circles and had learned conversations about algorithms, graphs, and randomness. But how can one teach without a screen, one might ask? The answer has been known since Antiquity at least: wet sand and a stick are the perfect writing medium. I only got into trouble once on the first day, when, half way through the analysis of the Goemans-Williamson maxcut algorithm, a wave came in and erased my calculation, as well as accidentally getting me wet all the way to my knees. Instead of erasing the board when we needed more writing space, we simply walked along the shore to find the next fresh spot of unwritten wet sand. At lunch time, the staff from the compound brought us picnic lunches and some wine (two bottles for every 6 people, usually one of local wine from the island, and the other one from the Bordeaux region). After going through the presentation of an exciting result, we cooled off by running in and out of the water (everyone had brought a swimming suit, of course). In the early afternoon, we took a leisurely walk back to our bungalows, walking our bikes and discussing exercises and puzzles as we went, then took a pleasant nap (or tried to use the flaky internet connection) before heading back to the beach for the late afternoon work session and evening swim. On the last day, we switched roles: the students became the instructors, the instructors became the students, and we got acquainted with the tricks of riding bicycles in the sand, juggling torches of fire (if you get petrol on your clothes, dive into the sand and other will quickly cover you with sand to extinguish the flames), getting into cold water without effort, body-surfing the waves, and biking in the woods by night without a light. At one point Ronald de Wolf commented: "We look like a bunch of hippies!", but I could not tell whether his tone was one of approval or of disapproval.

I taught a bit of optimization, and we practiced steepest descent by rolling down the sand dunes. Someone else presented an analysis of the dynamics of the famous sandpile model, and we had a lab session testing the fit of the model with reality (it's a poor fit). But the main theme of the week was randomness and probability in algorithms, and we used waves as our random coin flips, checking how long it took to get wet as a practical instance of geometric distributions. We studied random walks by biking into the confusing salt marshes area, where an unhappy landowner once threatened to keep me as a hostage for intruding on private property. We learned the similarity between having a creative idea and seeing a shooting star: both require much patience, skill in knowing where to look, and a little bit of luck. In both cases, two persons can both be star gazing at the exact same time with the same dedication, and one will see the shooting star but the other one won't. We tested our students' ability to greet new ideas with an open mind, by giving them oysters for dinner. We suffered the predictable consequences of our hard work all week: sun burns, sore muscles, and a big pile of unread emails. But all in all, I would not complain.

Email and dirty dishes

The ever-repeated quandary: is time better spent dealing with emails or actually doing work? When email exceeds my bandwidth I have a depressing accumulation mounting in my inbox, making the start of each day an ordeal. When I give priority to email, the day is spent doing small routine tasks and there is no sense of doing anything of actual value. It's a recurring problem. The problem that will not go away and that only gets worse with delays! It's like dirty dishes piling up in the sink.

It's all about notation

When designing an algorithm, one often critical step is to find a good representation for the problem input and output, that will help us think about it clearly.

When writing a proof, one often critical step is to find the right notation. Once you have decided what objects are worth having an independent notation, that will direct (or mislead) the proof.

The morale of today's lecture

Before designing an algorithm: find a good visual representation for the input and output helps you think about the problem.

Case in point: Viterbi's algorithm. Input includes so much data that it's messy to think about, until the right graph is drawn (with colors, too.)

For when the input is a permutation: represent it as a collection of points (i,sigma(i)), and hope that the output of the problem can be interpreted visually.

James Q. Wilson on liberal education

James Q. Wilson, whose existence I just learned about upon the event of his death, authored a thought-provoking essay about liberalism and liberal education. He writes:

A liberal education is at its best when it strikes this balance: when it makes one aware that principles must ultimately be justified by something more than mere utility, that liberty is as worth preserving when it is attacked by a group one admires as it is when assaulted by a group one detests, and that the bonds of civility upon which the maintenance of society depends are more fragile than we often admit.

This reminded me of the unsightly celebrations in the US a few years ago, when Saddam Hussein was executed. Sure, many people are against the death penalty... except for loathsome criminals like Saddam Hussein!

Currently, it brings to mind the preparation of the presidential campaign in France, where putative candidates must obtain the "signature" of 500 mayors before they can officially pose their candidacy (there are about 35000 mayors in the country and each mayor can give their signature to exactly one candidate.) One current question is whether the candidate for the extreme right party (the party of all prejudices) will get 500 signatures. There may be some lobbying to pressure mayors not to give her their signature, even though, in the upcoming election, it appears that she would get the votes of roughly 20 percent of the population. What is more important: to preserve the liberty of presenting candidates for all significant political parties, or to prevent the development of ideas that one detests? That is close to the dilemma presented by Wilson.

Lecturing on meta-topics

One primary goal of the Algorithms course that I am currently teaching is to teach problem-solving. That is normally done by example, going through a diverse array of algorithmic problems that come up in computer science. However, my way of teaching that has changed a little bit in recent years, with a shift to the meta-level.

Many methods I use to attack problem come without thinking. Through taking courses, reading papers, and collaborating with other researchers, I have absorbed certain ways of going about solving problems, and now I reproduce them in the hope that students will absorb them in turn. However, one of my former PhD students, Warren Schudy, systematically tried to bring out the meta-principle behind our discussions. He would be very explicit about it, reflecting aloud: "So, to no longer be stuck on this question, you are suggesting to try out some small concrete examples; that's your guiding principle" - and I would think: "Yes, of course he's right, that's what I'm doing!" Eventually I started to see the value of making explicit the guidelines that guide how we try to solve problems.

That adds a new element to my teaching: in class, I now try to not only solve the problem of the day, but also add a parenthetical comment to be more explicit about the path we took to problem-solving, the "guiding principle". It does not come naturally, since it can feel like pontificating, but it seems to have some value. Perhaps it helps demystify the "creative" steps and show that much can be achieved simply by systematically following a natural path of exploration - natural, once you have acquired enough experience to know what you're doing. I do not always remember to do it, but, following Warren's example, I try, at the end of each piece of algorithmic design or analysis, to reflect back on how we achieved it, and on the meta-tools that led us to the solution.

The New York review of books on absolute versus relative error

We usually evaluate approximation algorithms by the ratio of the output value to the unknown optimal value. Although it is almost a dogma at this point that this is the most reliable way to evaluate an algorithm, the last issue of the New York Review of Books gives an outstanding counterexample.

The article is debunking a disinformation piece published by 16 scientists in the Wall Street Journal on January 27. The WSJ misleading article was a piece of global warming skepticism.William Nordhaus establishes the fallacy of their arguments one by one. The point that caught my attention was the one about economic analysis. Nordhaus writes: The sixteen scientists argue, citing my research, that economics does not support policies to slow climate change in the next half-century, then moves on to offer the following, which can be interpreted as a beautifully clear argument against making a dogma out of approximation ratios.

The authors cite the “benefit-to-cost ratio” to support their argument. Elementary cost-benefit and business economics teach that this is an incorrect criterion for selecting investments or policies. The appropriate criterion for decisions in this context is net benefits (that is, the difference between, and not the ratio of, benefits and costs).

This point can be seen in a simple example, which would apply in the case of investments to slow climate change. Suppose we were thinking about two policies. Policy A has a small investment in abatement of CO2 emissions. It costs relatively little (say $1 billion) but has substantial benefits (say $10 billion), for a net benefit of $9 billion. Now compare this with a very effective and larger investment, Policy B. This second investment costs more (say $10 billion) but has substantial benefits (say $50 billion), for a net benefit of $40 billion. B is preferable because it has higher net benefits ($40 billion for B as compared with $9 for A), but A has a higher benefit-cost ratio (a ratio of 10 for A as compared with 5 for B). This example shows why we should, in designing the most effective policies, look at benefits minus costs, not benefits divided by costs.

The winds of change

My adult life so far has been split almost exactly 50-50 between France and the US. Now things are changing once again: I am shortly going to move back to France. While I plan to still spend a couple of months per year at Brown, in the foreseeable future I will be primarily based at Ecole Normale Superieure, in the Latin quarter in Paris.

Should anyone wish to come to Paris for a work visit, it would be a pleasure to welcome foreign visitors, collaborators, and interns.

Blogging will be light for a while, as I am occupying my time with various tedious tasks related to my move.

The year of the TSP

When I was at ITCS, last month, I talked to Huyng-Chan An who told me about his recent work with David Shmoys and Bobby Kleinberg (to appear in STOC 2012).

They study the s-t path variant of TSP, that asks for the shortest path going from a pre-specified start vertex s to a pre-specified end vertex t while visiting all other vertices along the way. What is the motivation for this problem? Well, imagine that you are a postman delivering letters. You pick up letters at the post office, deliver them, and when you're done, you go home: you have just built an s-t path, with the post office as s and your home as t. Or, imagine that your building is on fire, it is early in the morning, and the fire alarm is not working. You want to leave your office, visit all offices in the building as quickly as possible to tell anyone who might be there already that they must leave, and then you want to get out. No way you want to go back to your starting point in the end!

Christofides' algorithm, adapted to that variant, is not a 3/2 but a 5/3 approximation in the metric setting. An, Kleinberg and Shmoys have a very simple algorithm that improves the 5/3=1.66… to 1.61… The funny thing is that I did not know about the 5/3 approximation until An told me that they had improved upon that twenty years old bound! For that reason, I am hesitant to call it a breakthrough, and also because it comes along with several recent papers making progress on special cases of TSP. As a friend recently suggested, this is shaping up as "the year of the TSP"! But I looked at their result in more detail, and it is a clean, more or less self-contained, clever application of modern techniques. That's what makes it appealing.

What's the algorithm?

Nothing special, really:
(1). Solve the natural variant of the Held-Karp linear programming lower bound for TSP
(2). Express the solution as a convex combination of spanning trees (that's known to be possible by polyhedral combinatorics)
(3). Pick a random such tree T* according to the distribution given in (2), and
(4). use it in an execution of the natural variant of the Christofides heuristic.
The fact that it is "nothing special", in my view, is a good thing. It means that it can be implemented at little additional cost. (The difficulty is in the analysis.)

What's the "natural variant" of the Held-Karp constraints? Some constraints are different: every s-t cut must be crossed by a minimum of just one edge (instead of a minimum of two edges, in the usual version).

What's the "natural variant" of the Christofides heuristic? Instead of finding a perfect matching of the odd degree vertices of T*, it finds a perfect matching (T-join) of the "off-degree" vertices of T*, that is, the vertices whose degree has the wrong parity: the difference with the usual setup is that now, vertex s has the wrong parity if its degree in T* is even, and similarly vertex t has the wrong parity if its degree in T* is even.

So, that's the algorithm.

What's the analysis?

First, they present an elegant proof of the 5/3 approximation result, then modify it. Because of that, we first have to understand why the algorithm is a 5/3 approximation. The tree T* from step 3 has expected cost bounded by OPT, so the sole focus is on bounding the cost of the T-join. That is achieved by bounding the value of a particular fractional T-join. What's a fractional T-join? It's a feasible solution to the following LP:
* for every edge e, variable y(e) must be between 0 and 1
* for every proper cut (S,V-S), if S contains an odd number of "off-degree" vertices, then at least one edge crosses the cut - or in other words, fractionally, the sum, over every edge e crossing the cut, of y(e), must be at least 1.
As it happens, that polytope has integer vertices, so the optimal (integer) T-join is also an optimal fractional T-join, and so the cost of the T-join built by the algorithm in step (4) can be bounded by the cost of any fractional T-join. The proof exploits this freedom to carefully choose a particular fractional T-join whose expected cost is less than 2/3 OPT. How can it prove that the cost is less than 2/3 OPT? By proving that it's less than the 2/3 times the Held-Karp lower bound. So, the proof has now neatly moved to the realm of polyhedral analysis, and the rest is now a matter of manipulating vectors y=(y(e)).

The 5/3 result is proved by choosing, for our fractional T-join, a scaled version of an average of two solutions that each achieve the Held-Karp lower bound, namely: the fractional solution x* obtained in step (1), and the tree T* obtained in step (3). Indeed, x* satisfies all the fractional T-join constraints, but in addition, observe that there are some constraints where it has slack: for some cuts, the T-join constraint requires a weight of 1 across the cut, but x* guarantees a weight of 2 across the cut. The tree T* also satisfies all the fractional T-join constraints, but in addition, observe that there are also some constraints where it has some slack: for some cuts, the T-join constraint requires a weight of 1 across the cut, but T* guarantees a weight of 2 across the cut. Really? Well, yes: if S separates s from t and contains an odd number of "off-degree" vertices, then a straightforward counting argument shows that at last 2 edges of the tree must come out of S. Now, the funny thing is that T* has slack precisely for every constraint where x* does not have slack! So if we take the average of x* and of T*, for each constraint of the fractional T-join, we'll have (1+2)/2=3/2 edges crossing at least, and so, if we scale by 2/3, it's still feasible! That shows that y=(2/3)(x*/2+ T*/2) is a feasible fractional T-join. To recap, its cost is at most 2/3 times the average cost of x* and of T*, which is at most 2/3 OPT. The T-join built in step (4) has cost less than that, and that's how they get a 1+2/3=5/3 approximation.

How do they improve on this analysis? By fiddling with the factors cleverly. To get a fractional T-join with cost slightly better than 2/3, instead of x*/3+T*/3, they pick y=(1/3-2c)x* + (1/3+c)T*+(correction vector for the fractional T-join constraints that are now violated), and hope that the cost of the correction vector is less than c OPT. Realizing that hope requires a careful analysis of the violated constraints. They observe that
* even if constraints are violated, they're not violated by much: the sum across the cut is still at least 1-O( c). The deficiency is O( c).
* given that T* is drawn at random in step (2), those cuts are rare: an elementary argument uses Markov's inequality to show that their probability is O( c).
So the correction vector z will simply have z(e)=deficiency times Pr(e in cut where the constraint is violated) times x*(e)=O(c^2)x*(e).
Then the cost of the fractional T-join y is (2/3 - c + O(c^2))OPT, which is less than 2/3 for c small enough constant.

There's an additional technicality: the above reasoning is buggy when the violated constraints correspond to non-disjoint cuts, but they show that they can make the cuts disjoint up to introducing another small factor 1-O( c). And with that, they beat the 5/3 approximation. (There's more to the analysis to refine it and get further improvements, but that's beyond my attention span...)

What's the take-home message from that proof? Perhaps, it is a hymn to the power and flexibility of LP feasibility. The technique seems general. They pushed it through for the s-t path TSP problem, but why not use it for other problems, whenever there's an integer polytope behind the scenes?

2=1, 1=2

Two people in love: when in a romantic mood, one is tempted to think of them as two persons united by love into a single being. 2=1: a small miracle!

A woman giving birth: for those of us who don't have enough imagination to think of a child in the womb as a completely real person, what we see is that, one moment there was one person, and the next moment there were two. 1=2: another small miracle!

The Murphy's law approach to grading

Say that the assignment that you are grading is ambiguous, so that you are not sure what the students meant. One interpretation leads to a correct solution, the other one, to an incorrect solution. What to do then?

The Murphy's law approach: if something can go wrong, then it will be wrong. The student kept the writing ambiguous because he or she was not sure which specific interpretation was correct. Then, it should be counted as wrong.

But doesn't that contradict the mustard seed approach? Which approach will be taken then depends on ... on the grader's philosophy? on the grader's mood? on what he or she had for lunch? on some random coin flip, but decided consistently across all graders?

The mustard seed approach to grading

Today I learned a new thing about grading.

What do you do if a student presents an algorithm in two ways, at a high-level and with pseudo-code, and if the two versions are different, one correct and one incorrect? Should one count the answer as correct or incorrect?

The "mustard seed" response: there's some good in there, so focus on what's good and count it as correct.

The fate of retired professors in Greece

rue89.com has an article about the impact of the Euro crisis on the daily life of people in Greece. A student interviewed 10 people and wrote a paragraph about each of them. One is a recently retired university professor.

Nikos, 65 ans, professeur d'université à la retraite
Retraité depuis août, Nikos n'a reçu aucune pension au début du mois de janvier. Il dit qu'il pourra peut-être recevoir une retraite dans six mois – et encore : « D'un mois sur l'autre, nous ne dépensons que l'essentiel car nous ne savons pas si on nous donnera le mois prochain une retraite. Nous qui appartenions à la classe moyenne riche, ma femme étant professeur à la retraite, nous devenons pauvres. Avant, nous partions en vacances chaque Pâques, chaque Noël : en Norvège, en Egypte. Aujourd'hui, cela est impossible ; nous n'achetons que ce qui est nécessaire : plus de vêtements, plus de voyages. Que de la nourriture. [...]


Nikos, 65, retired university professor
Having retired this past August, Nikos received no pension at the beginning of January this year. He says he may be able to receive a pension in six months - but: "From month to month, we do not spend that much because we do not know if we will receive our pension next month. We, who belonged to the wealthy middle class - my wife is a retired professor - we are becoming poor. Before, we left on vacation every Easter, every Christmas, to go to Norway or Egypt. Today that is impossible; we buy only what is needed: no more clothes, no more trips. Only food."

In the midst of a great depression, it may seem ironical to sympathize with people whose biggest problem is that they can no longer travel for vacation, but this is a retired professor: in other words, one of our colleagues, so it hits close to home. Barring a war, it is hard to imagine that a day might come when financial problems would cause me to go hungry, but who knows what the future has in store?