"à Pâques ou à la Trinité"

There is a French expression that I have been thinking of lately, "à Pâques ou à la Trinité". It means "at some indeterminate time, and possibly never". That seems to me an adequate description of the date at which journal submission reviewers turn in their reports. The expression comes from an 18t century song about Lord Malborough who went to war, his lady is waiting for him to return, he never comes back, then is heard to have died at war, and she changes her clothes to black mourning. A manuscript gets sent to a reviewer like a soldier gets sent to war: we hope that one day it will come back, in not too long, but we can never be entirely sure.

Blog revival?

After getting settled in Paris and adjusting to my new department at Ecole Normale Superieure, I may now be ready to resume blogging. I will give it a try and see how it goes.

Blog presentation

How large should the font be for a blog? How many characters per line? Should comments be nested or chronological? Should they be numbered? What should be the design of the background? Each blog designer has his own preferences and sets parameters to fit them, but none of those questions should be answered by the blogger. Instead, the user is the one who should dictate the appearance of a blog. Why do current websites hosting blogs not transfer those decisions from the blog owner to the blog reader?

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?