Posts
December 18, 2012
+
3:29 PM | 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.
December 07, 2012
+
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
[…]
October 31, 2012
+
7:48 PM | 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
[…]
+
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 […]
+
10:30 AM | 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
[…]
September 27, 2012
+
3:11 PM | 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
[…]
September 26, 2012
+
8:18 AM | Poincaré and dynamical systems
Etienne Ghys, a famous French mathematician in dynamical system, 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 […]
July 07, 2012
+
8:39 AM | 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 […]
July 06, 2012
+
11:17 AM | 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
[…]
July 05, 2012
+
8:25 AM | 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
[…]
July 01, 2012
+
9:20 PM | 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 […]
June 29, 2012
+
11:47 PM | 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
[…]
June 28, 2012
+
10:29 PM | 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.
[…]
June 27, 2012
+
11:13 PM | 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
[…]
June 26, 2012
+
10:49 AM | 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 […]
June 24, 2012
+
2:56 PM | 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
[…]
June 23, 2012
+
3:24 PM | 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?
[…]
June 22, 2012
+
3:14 PM | 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. TheoremThe internal edges of a planar triangulation can be partitioned into
[…]
June 21, 2012
+
1:19 PM | 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]
[…]
June 20, 2012
+
10:14 AM | 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
[…]
June 18, 2012
+
9:14 PM | An interview with 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
[…]
June 07, 2012
+
9:25 AM | What is ENS?
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 ENS, whose full name is "Ecole Normale Supérieure de la rue d'Ulm", quite a mouthful! (Also called "ENS Ulm", "rue d'Ulm", or "Ulm" for short.) It is old,
[…]
May 28, 2012
+
2:17 PM | 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
[…]
May 21, 2012
+
4:37 PM | 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
[…]
May 20, 2012
+
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
[…]
May 19, 2012
+
10:14 AM | 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
[…]
May 18, 2012
+
10:17 PM | 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
[…]
May 13, 2012
+
4:46 PM | 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 […]
May 10, 2012
+
1:47 AM | 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 […]
May 08, 2012
+
12:29 PM | 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
[...]
