Homeless in Paris: a survival guide

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

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

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

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

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

Priorities

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

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

To each their own priorities.

Find the intruder

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

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

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

Travel woes: how the mighty fall

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

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

Numbering floors in buildings

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

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

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

Turing and the Turing award

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

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

One triangulation = three trees

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

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

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

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

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

Tom Trotter's view of Combinatorics

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

Avi at AofA: population recovery

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

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

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

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

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

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

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

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

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

Why does that work? By some elementary magic.

An interview of Avi Wigderson

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

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

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

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

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

What is Ecole Normale Supérieure?

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

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

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

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

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

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

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

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

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

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

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

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

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