tag:blogger.com,1999:blog-40681836987476231132016-04-03T04:17:16.136-04:00A CS Professor's blogClaire Mathieunoreply@blogger.comBlogger373125tag:blogger.com,1999:blog-4068183698747623113.post-7794944085775069372013-05-29T10:18:00.002-04:002013-05-29T10:18:45.987-04:00"à Pâques ou à la Trinité"There is a French expression that I have been thinking of lately, "<i>à Pâques ou à la Trinité</i>". 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.Claire Mathieunoreply@blogger.com0tag:blogger.com,1999:blog-4068183698747623113.post-48476740097178427912013-05-27T15:37:00.002-04:002013-05-27T15:37:29.749-04:00Blog 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. Claire Mathieunoreply@blogger.com7tag:blogger.com,1999:blog-4068183698747623113.post-13179367514625479302013-05-27T08:00:00.000-04:002013-05-27T15:43:18.979-04:00Blog presentationHow 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?Claire Mathieunoreply@blogger.com1Europe55.379110448010472 9.14062523.286916448010473 -73.4765625 87.471304448010471 91.7578125tag:blogger.com,1999:blog-4068183698747623113.post-921969065853677142012-12-18T10:29:00.000-05:002012-12-18T10:31:04.940-05:00Applying for a job in France, part 2For CNRS, good informal advice can be found in this text written by Bruno Durand a few years ago: <a href="http://www.lirmm.fr/~bdurand/cn7/conseils10.html">here</a>. In French, more recent information (for the year 2012) is <a href="http://www.lirmm.fr/~bdurand/cn7/2012.html">here</a> and <a href="http://www.lirmm.fr/~bdurand/cn7/index.html">there</a>, with pointers to the current two sections in computer science, <a href="http://www.labri.fr/perso/gimbert/cn6/conseils.html#Advices">6</a> and 7. Claire Mathieunoreply@blogger.com0tag:blogger.com,1999:blog-4068183698747623113.post-39809828114203093522012-12-07T09:27:00.003-05:002012-12-07T09:27:20.480-05:00The diameter of the flip graph of triangulationsConsider 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. <br><br>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. <br><br>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. <br><br>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 <a href="http://perso.efrei.fr/~pournin/associahedraENS.pdf">here</a> 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. <br><br>Anyone interested in the problem really should spend a few minutes pouring over those slides. <br><br>Claire Mathieunoreply@blogger.com2tag:blogger.com,1999:blog-4068183698747623113.post-31859631323452218632012-10-31T15:48:00.000-04:002012-10-31T15:48:21.125-04:00Sandy delays STOCJUST IN: <br><br>The deadline for ACM STOC 2013 submissions has been <b>extended</b> to Monday, Nov 5 2012 5:00 p.m. EST. The change has been announced on the STOC website. <br><br>OLD NEWS: <br><br> 1) Please read the Call for Papers carefully and pay special attention to length and formatting requirements, which have changed since last year: <br> a) Submissions must be no more than 10 pages in two-column ACM Proceedings format, including the bibliography. <br> b) Length and formatting requirements will be enforced strictly and literally; submissions that don't conform will be summarily rejected. <br> Note that you have the option of uploading a full-paper version, along with your 10-page extended abstract. <br><br> 2) The online submission process will take more time than it has in the past for at least two reasons: <br> 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. <br> 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. <br><br> Note that this and all other information about STOC 2013 can be found at http://theory.stanford.edu/stoc2013/ Claire Mathieunoreply@blogger.com0tag:blogger.com,1999:blog-4068183698747623113.post-15827428744036324672012-10-31T10:03:00.000-04:002012-10-31T10:03:47.745-04:00A probable "maître de conférences" job opening at ENSPour 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! <br><br>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! Claire Mathieunoreply@blogger.com7tag:blogger.com,1999:blog-4068183698747623113.post-39420863215557375882012-10-31T06:30:00.000-04:002012-10-31T09:50:36.596-04:00Applying for a job in FranceIf 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.) <br><br>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. <br><br> 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. <br><br> 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. <br><br> 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. <br><br> <b>1. Informal contacts.</b> 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. <br><br> <b>2. Written application</b>. 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. <br><br> <b>3. Interview</b>. 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. <br><br> <b>Outcome</b>. 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). <br><br> 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. <br><br> Claire Mathieunoreply@blogger.com11tag:blogger.com,1999:blog-4068183698747623113.post-3411997736242557182012-09-27T11:11:00.000-04:002012-09-27T11:11:02.769-04:00Counting permutations: an open questionNati 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. <p>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 <p>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}. <p>Conjecture: in d dimensions, it's [(1+o(1))(n/e^d)]^{n^d} <p>Linial and Zur Luria proved the "less than or equal to" side. The "greater than or equal to" is still open. Claire Mathieunoreply@blogger.com2tag:blogger.com,1999:blog-4068183698747623113.post-24178599293706577302012-09-26T04:18:00.000-04:002012-09-26T04:40:32.248-04:00Poincaré and dynamical systemsEtienne 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é: "<i>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</i>." Poincare proves that if the cause is distributed according to some diffuse probability measure, then the result is an equidistribution. He says: "<i>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</i>". Claire Mathieunoreply@blogger.com0tag:blogger.com,1999:blog-4068183698747623113.post-25004847193915554632012-07-07T04:39:00.000-04:002012-07-07T04:39:00.344-04:00Urban pedestrian projectsWalking 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. <p>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. <p>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. <p>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.Claire Mathieunoreply@blogger.com1tag:blogger.com,1999:blog-4068183698747623113.post-72441727139636727932012-07-06T07:17:00.000-04:002012-07-06T07:17:00.971-04:00A tradition that deserves to dieHow do you know whether you have been accepted to your dream college or university? <p>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! <p> 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. <p>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?Claire Mathieunoreply@blogger.com3tag:blogger.com,1999:blog-4068183698747623113.post-8833931249854703342012-07-05T04:25:00.000-04:002012-07-05T04:25:44.066-04:00DeadlinesDays 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. <p>Day after the conference deadline: goofing off. <p>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. <p>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. <p>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.Claire Mathieunoreply@blogger.com5tag:blogger.com,1999:blog-4068183698747623113.post-37389130448148317302012-07-01T17:20:00.002-04:002012-07-01T17:20:26.075-04:00The small world phenomenonRecently 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...Claire Mathieunoreply@blogger.com1tag:blogger.com,1999:blog-4068183698747623113.post-88402880395679805352012-06-29T19:47:00.001-04:002012-06-29T19:47:31.751-04:00Homeless in Paris: a survival guideIt is estimated that about 80 homeless people live in my immediate neighborhood. <p>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. <p>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. <p>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. <p>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!Claire Mathieunoreply@blogger.com0tag:blogger.com,1999:blog-4068183698747623113.post-45857912154572568002012-06-28T18:29:00.002-04:002012-06-28T18:29:59.642-04:00PrioritiesToday the people on the streets in my neighborhood are expressing their joy: Italy won the Euro semi-final. <p>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. <p>To each their own priorities.Claire Mathieunoreply@blogger.com4tag:blogger.com,1999:blog-4068183698747623113.post-600015369356851452012-06-27T19:13:00.000-04:002012-06-27T19:49:10.448-04:00Find the intruderToday is the start of summer sales in Paris, and the stores have been busy preparing their displays. <p>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"? <p>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.Claire Mathieunoreply@blogger.com0tag:blogger.com,1999:blog-4068183698747623113.post-75116684808238675462012-06-26T06:49:00.000-04:002012-06-26T07:07:19.667-04:00Travel woes: how the mighty fallFlying 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! <p><strike>Morale</strike>Lesson: after a red eye, take a day off.Claire Mathieunoreply@blogger.com3tag:blogger.com,1999:blog-4068183698747623113.post-57938887854160153742012-06-24T10:56:00.000-04:002012-06-24T10:56:00.304-04:00Numbering floors in buildingsBuildings 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. <p>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? <p>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.Claire Mathieunoreply@blogger.com3tag:blogger.com,1999:blog-4068183698747623113.post-37726845088675787422012-06-23T11:24:00.000-04:002012-06-23T11:24:00.139-04:00Turing and the Turing awardAccording 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. <p>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?Claire Mathieunoreply@blogger.com3tag:blogger.com,1999:blog-4068183698747623113.post-45787436391519467362012-06-22T11:14:00.000-04:002012-06-22T11:14:00.428-04:00One triangulation = three treesAt 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. <p><b>Theorem</b>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. <p>The proof is elementary and algorithmic, by induction on the number of vertices. <p>Algorithm <br>If G is a single triangle, <br>Then we are done. <br>Else <br>  Find an edge {u,v} with u on the outer boundary, v internal, and exactly two paths of length 2 from u to v. <br>  Contract edge {u,v} into a vertex u', creating a contracted graph G'. <br>  Recursively solve the problem for G', obtaining three trees, blue, white and red, where, say, the blue tree is rooted at u'. <br>  Uncontract edge {u,v}, color it blue; other edges inherit the color of the corresponding edge of G'. <br> <p>Analysis <br>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.Claire Mathieunoreply@blogger.com0tag:blogger.com,1999:blog-4068183698747623113.post-88593613865322077902012-06-21T09:19:00.000-04:002012-06-22T08:20:30.523-04:00Tom Trotter's view of Combinatorics<i>Other mathematicians compete about the complicated theorems that they are<b> able</b> to prove; combinatorialists like to compete about about the simplicity or self-evidence of statements they are <b>unable</b> to prove, i.e., ``I can't even prove ...''</i><br>   [As recalled and paraphrased by Mike Saks]Claire Mathieunoreply@blogger.com4tag:blogger.com,1999:blog-4068183698747623113.post-30027876630812600182012-06-20T06:14:00.000-04:002012-06-20T06:30:30.110-04:00Avi at AofA: population recoveryFans 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? <p>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.) <p><b>The population recovery problem</b>: 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. <p>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).<br> <p>Here is the algorithm: <br>(0) Take a few queries. <br>(1) Find, for each vector v, a small set Sv of coordinates, such that the following condition holds: <br>   (*) Sv uniquely distinguishes v from every vertex u such that |Su|≤|Sv|. <br> Let Ambiguous(v) be the set of vectors u that are indistinguishable from v by looking at just the coordinates in Sv. <br>(2) Label the vectors 1,2,..,k by order of non-increasing |Sv| <br>(3) For v = 1 to k <br>   Let zv = the restriction of v to the coordinates in Sv. <br>   Compute qv, the fraction of the queries whose Sv coordinates are (roughly) zv. <br>   Let (**) estimate(pv)= qv- ∑ estimate(pu), <br>    where the sum is over every u in Ambiguous(v), other than v itself, of course <br>Output (estimate(p1),estimate(p2),…,estimate(pk)).<br> <p>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? <br>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. <p>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. <p>The main remaining difficulty is how to achieve (*) while maintaining sets Sv of cardinality at most log(k). Here is how to do it. <br> <p>Algorithm for Step (1): <br>Start with the empty set for every Sv <br>Repeat <br>   While there exists an Sv and a coordinate i such that adding i to Sv decreases |Ambiguous(v)| by a factor of 2 <br>     Add i to Sv <br>   If condition (*) is violated by some u and v, <br>   then replace Su by Sv <br>Until condition (*) holds. <p>Why does that work? By some elementary magic.Claire Mathieunoreply@blogger.com0tag:blogger.com,1999:blog-4068183698747623113.post-65402108403259101112012-06-18T17:14:00.000-04:002012-06-20T06:14:53.790-04:00An interview of Avi WigdersonQ: Do you consider yourself a Mathematician or a Computer Scientist? <br>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.<br>Q: How did you get interested in this?<br>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.<br>Q: Why did you decide to do a PhD? <br> 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.<br>Q: What was your first research project?<br>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.<br><br> Q: How do you work with your graduate students?<br>A: In the last decade I have been working mostly with postdocs, so I'll talk mainly about my time at the Hebrew University.<br> 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.<br>Q: Would you have advice for first year graduate students?<br>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.<br>Q: How do you get your beginning students started with research?<br>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.<br><br> Q: What makes a question a "good" research question?<br>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.<br>Q: What is your favorite result in your own work?<br>A: Zero-knowledge. It's so much fun explaining it to people. It's very rewarding.<br>Q: Practical impact. What would you say about that?<br>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)<br><br> Q: How much time do you spend reading papers?<br>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.<br>Q: Do you have role models?<br>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.<br><br> Q: You've been in the field for roughly 30 years. How has it changed?<br>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...<br> 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.<br> Q: So, students have to be much more mathematicaly sophisticated?<br>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.<br>Q: I actually find it a bit intimidating. How to advise students who are so talented?<br>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.<br>Q: Concretely, how did you go about attracting students to theoretical computer science?<br>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.Claire Mathieunoreply@blogger.com4tag:blogger.com,1999:blog-4068183698747623113.post-77472887647059354212012-06-07T05:25:00.000-04:002012-06-07T05:54:45.965-04:00What is Ecole Normale Supérieure?<p>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). <p> 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.) <li> 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. <li> 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). <li> 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. <li> It teaches academic subjects covering the spectrum of arts and sciences. No preeminence is given to science over the humanities. <li> It is tiny: only 2200 students! ENS Cachan and ENS Lyon are similarly small. <li> 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.) <li> 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) <li> Many of the students are very, um, aware that they "are the best"... <p> 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.) <p> 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.) <p> 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.Claire Mathieunoreply@blogger.com30