Wednesday, May 29, 2013
"à 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.
Monday, May 27, 2013
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?
Tuesday, December 18, 2012
Applying for a job in France, part 2
Friday, December 7, 2012
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.
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.
Wednesday, October 31, 2012
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/
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!
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.
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.
Thursday, September 27, 2012
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.
Wednesday, September 26, 2012
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".
Subscribe to:
Posts (Atom)