Do you know someone who knew someone who knew someone who knew someone who knew someone who knew someone who knew someone who knew George Washington personally?
We could imagine trying to run Milgram's experiment: give a message to someone who we think might lead to Washington; that person thinks of someone they used to know, to whom they could have given that message, and who might lead closer to Washington, etc. But it is impossible to implement: we cannot run an experiment into the past. The social networks of the past are gone. They have disappeared forever. They seem inaccessible.
Then, how could you estimate the number of degrees of separation between you and George Washington?
Wednesday, January 11, 2012
Tuesday, January 10, 2012
Gossip from a hundred years ago
Last week I visited Marie Curie's birth house in Warsaw. Talking about it with relatives, I learned a piece of gossip from a hundred years ago. My grandmother was a physics student at the Ecole Normale Superieure de Jeunes Filles (ENSJF), where a few years earlier she would have had classes with Marie Curie, but instead, was taught by her replacement Paul Langevin.
As the family story goes, Langevin was a terrible teacher. He was also sexist, and claimed that the only good thing about teaching women was that it did not require any preparation. But one day, when my grandmother arrived at the school, she found a group gathered in great excitement around one of her friends, who had bought the newspapers: "Look! They are talking about our teacher! Look at what they are saying about Langevin!" - the newspapers were saying that Langevin had an affair with (then widowed) Mme Curie. That much I knew from wikipedia, but the little additional bit that I did not know was that it was not only the journalists who spread the rumor but also Langevin's wife who made a big scandal about it - so perhaps there was some truth behind the tabloids' stories.
Had I not visited Curie's house, I would not have heard that anecdote. How many stories about the past are sleeping in our elderly relatives' memories, I wonder?
As the family story goes, Langevin was a terrible teacher. He was also sexist, and claimed that the only good thing about teaching women was that it did not require any preparation. But one day, when my grandmother arrived at the school, she found a group gathered in great excitement around one of her friends, who had bought the newspapers: "Look! They are talking about our teacher! Look at what they are saying about Langevin!" - the newspapers were saying that Langevin had an affair with (then widowed) Mme Curie. That much I knew from wikipedia, but the little additional bit that I did not know was that it was not only the journalists who spread the rumor but also Langevin's wife who made a big scandal about it - so perhaps there was some truth behind the tabloids' stories.
Had I not visited Curie's house, I would not have heard that anecdote. How many stories about the past are sleeping in our elderly relatives' memories, I wonder?
Monday, January 9, 2012
ITCS Graduating bits: a big hit
As I am typing students and postdocs looking for jobs are giving 5 minute presentations. It was absolutely great for the first hour. For each speaker I quickly checked
- their web page (if they kept their name on the screen long enough for me to catch it),
- the DBLP page for their publications,
- their Facebook page,
- checked whether they were applying for a job at Brown,
and jotted down for myself a few notes on their presentation and on whether I thought their interests might be a fit.
What a great way to get a quick first impression! Also a great way to get a quick sense of the pool of theory-inclined applicants this year. If I see other applicants in our database, then, even if they are not here today, this session will make it easier for me to evaluate them.
The room is full and I saw some people standing in the back.
If only this had been split into two sessions, it would be easier to pay attention. As it is, early speakers had a big advantage. If I was staying around, I would compare impressions with other Brown people and try to corner a few of those applicants to chat with them. Unfortunately I've about had it with traveling (I've logged close to 80 hours traveling in the past 22 days and only spent 12 hours at home since getting back from France), so I am not taking full advantage of this great opportunity to get a first look at job candidates; but it is a great, great idea.
- their web page (if they kept their name on the screen long enough for me to catch it),
- the DBLP page for their publications,
- their Facebook page,
- checked whether they were applying for a job at Brown,
and jotted down for myself a few notes on their presentation and on whether I thought their interests might be a fit.
What a great way to get a quick first impression! Also a great way to get a quick sense of the pool of theory-inclined applicants this year. If I see other applicants in our database, then, even if they are not here today, this session will make it easier for me to evaluate them.
The room is full and I saw some people standing in the back.
If only this had been split into two sessions, it would be easier to pay attention. As it is, early speakers had a big advantage. If I was staying around, I would compare impressions with other Brown people and try to corner a few of those applicants to chat with them. Unfortunately I've about had it with traveling (I've logged close to 80 hours traveling in the past 22 days and only spent 12 hours at home since getting back from France), so I am not taking full advantage of this great opportunity to get a first look at job candidates; but it is a great, great idea.
Models
It is a paradox that reality can be better apprehended by thinking, not about the real world directly, but about simple, pure models that are not real themselves but that capture one dimension of reality better than the messy and confusing real objects.
The Turing machine is not a real computer but a model for real computers. It's a computer in "hyperbolic form". It is not real, yet it is a tool to help us think about some essential aspects of reality. We can understand reality better by starting from that model. The Genesis is not a real account of the start of humanity but a model. It is not real, but it helps us think about some essential aspects of the start of humanity such as all human beings forming a family-like community. Polynomial runtime is not a real execution time but a model. It is not real, but it helps think about the design of efficient computations. Ensoulment at conception is not a real account of the beginning of personhood but a model. The Ising model. The state of nature. Classical mechanics. The free market. Alice and Bob.
All models.
All those models enrich our understanding, but they're also limited. When we use one and are led to exciting insights, it is tempting to give that model a broader scope and view everything through the lens of that particular model, but that's a mistake. We must not lose sight that they are not a catch-all substitute for reality. The risk is that asking the wrong questions about them leads to nonsensical answers or to sterile quests. How is Turing computation affected by the presence of several tapes? How does one make archeological and paleontological finds fit the story of the Creation? Can you reduce runtime from n^{1000} to 2^{100000}n^{999}? What happens to the soul during twinning with late separation or for conjoined twins? Such questions are close to vacuous: by and large, they do not produce new understanding of the real world but only serve to show the limitations of our models. Any question that exploits the aspects of a model that diverge from the real world is of lesser interest at best: it's only about the model, not about the phenomenon that the model is aiming to describe.
The Turing machine is not a real computer but a model for real computers. It's a computer in "hyperbolic form". It is not real, yet it is a tool to help us think about some essential aspects of reality. We can understand reality better by starting from that model. The Genesis is not a real account of the start of humanity but a model. It is not real, but it helps us think about some essential aspects of the start of humanity such as all human beings forming a family-like community. Polynomial runtime is not a real execution time but a model. It is not real, but it helps think about the design of efficient computations. Ensoulment at conception is not a real account of the beginning of personhood but a model. The Ising model. The state of nature. Classical mechanics. The free market. Alice and Bob.
All models.
All those models enrich our understanding, but they're also limited. When we use one and are led to exciting insights, it is tempting to give that model a broader scope and view everything through the lens of that particular model, but that's a mistake. We must not lose sight that they are not a catch-all substitute for reality. The risk is that asking the wrong questions about them leads to nonsensical answers or to sterile quests. How is Turing computation affected by the presence of several tapes? How does one make archeological and paleontological finds fit the story of the Creation? Can you reduce runtime from n^{1000} to 2^{100000}n^{999}? What happens to the soul during twinning with late separation or for conjoined twins? Such questions are close to vacuous: by and large, they do not produce new understanding of the real world but only serve to show the limitations of our models. Any question that exploits the aspects of a model that diverge from the real world is of lesser interest at best: it's only about the model, not about the phenomenon that the model is aiming to describe.
What to do with FOCS rejected papers?
What to do with rejected FOCS submissions? Many people say that the conference should accept many more papers, but there is strong resistance to doing that.
How about creating a conference that would be reserved for presenting rejected FOCS papers? The only criterion for acceptance would be that the paper would have to have been rejected from FOCS. The format would depend on the number of people who wish to present their work in spite of the submission having been rejected from FOCS. This new conference could be co-located with FOCS, and could happen on the day just before, the day just after, or as poster sessions in the evenings during the same days. Then the two communities could mingle. Imagine the conversation in the hotel elevator:
"-What is your research area?
- Arbitrary analysis. What's your research area?
- Forgetful algorithms.
- That sounds interesting.
- I'd like to hear more about your arbitrary analysis. Are you going to present a paper?
- Yes, I am giving a FOCS talk tomorrow. How about you, are you going to give a talk on forgetfulness?
- Yes, I am giving a FOCS Rejected talk tonight.
- Great! I look forward to hearing it!"
How about creating a conference that would be reserved for presenting rejected FOCS papers? The only criterion for acceptance would be that the paper would have to have been rejected from FOCS. The format would depend on the number of people who wish to present their work in spite of the submission having been rejected from FOCS. This new conference could be co-located with FOCS, and could happen on the day just before, the day just after, or as poster sessions in the evenings during the same days. Then the two communities could mingle. Imagine the conversation in the hotel elevator:
"-What is your research area?
- Arbitrary analysis. What's your research area?
- Forgetful algorithms.
- That sounds interesting.
- I'd like to hear more about your arbitrary analysis. Are you going to present a paper?
- Yes, I am giving a FOCS talk tomorrow. How about you, are you going to give a talk on forgetfulness?
- Yes, I am giving a FOCS Rejected talk tonight.
- Great! I look forward to hearing it!"
Sunday, January 8, 2012
The computational society
The best way to fly across the Atlantic: with a good book that keeps you occupied from beginning to end. Having two flights, I had two books. The first one had nothing to do with computer science. The second one, "The empire of the lesser evil" by Michea, contains the following footnote (my translation).
"It is probably this obsessive fear of civil war that explains why 17th and 18th century philosophers […] almost always describe the "state of nature" as a state of inevitable […] war of all against all. This obviously consists of a transposition into philosophy of the situation of civil wars of that period, pushed by assumption - as in all thought experiments - to their imaginary limit […]. This is a hyperbolic formulation […]. Similarly, at a metaphysical level, the cartesian doubt takes a hyperbolic form to create the possibility of cogito. Note that modern solutions must always be deduced of philosophical situations that are not merely negative or even hopeless (absolute doubt, absolute violence) but also fictive (the hypothesis of the dream and the genie with Descartes, the state of nature with Hobbes, the fable of original trade of goods with economists). That is not the least paradox of a society […] claiming to be entirely "realist" and procedural - that is, founded on the purely mechanical protocols of Law and of Market - that it thus generates its own foundational myths."
"It is probably this obsessive fear of civil war that explains why 17th and 18th century philosophers […] almost always describe the "state of nature" as a state of inevitable […] war of all against all. This obviously consists of a transposition into philosophy of the situation of civil wars of that period, pushed by assumption - as in all thought experiments - to their imaginary limit […]. This is a hyperbolic formulation […]. Similarly, at a metaphysical level, the cartesian doubt takes a hyperbolic form to create the possibility of cogito. Note that modern solutions must always be deduced of philosophical situations that are not merely negative or even hopeless (absolute doubt, absolute violence) but also fictive (the hypothesis of the dream and the genie with Descartes, the state of nature with Hobbes, the fable of original trade of goods with economists). That is not the least paradox of a society […] claiming to be entirely "realist" and procedural - that is, founded on the purely mechanical protocols of Law and of Market - that it thus generates its own foundational myths."
Saturday, January 7, 2012
The Sorbonne at war
This month is appearing a book entitled "La Sorbonne en Guerre (1940-1944)", followed by the short "Journal de la Liberation de Versailles". It is a primary historical document from a manuscript written by my grandfather Georges Mathieu about life as a professor (of ancient Greek) at the Sorbonne during the Occupation. My father typed, edited, prefaced and indexed the text.
In there, you read about such topics as faculty meetings discussing how to deal with new laws restricting Jewish students and faculty. If a Jewish professor goes into hiding, should the department hire someone to fill the prestigious position, or should they make do with temporary replacements? If loudly voicing disagreement with the laws means that you will be fired and arrested, then what is the best way to react to unjust measures? How do you work with a colleague whose collaborationist attitude you despise? How does one deal with anonymous letters at such a time? The book is not a guide of what one ought to do, but a report of what happened.
The Liberation of Versailles is a thrilling account of the Allied forces arriving in Versailles in 1944 and being greeted with great rejoicing by the ecstatic population.
http://www.editions-harmattan.fr/index.asp?navig=catalogue&obj=livre&no=35756
In there, you read about such topics as faculty meetings discussing how to deal with new laws restricting Jewish students and faculty. If a Jewish professor goes into hiding, should the department hire someone to fill the prestigious position, or should they make do with temporary replacements? If loudly voicing disagreement with the laws means that you will be fired and arrested, then what is the best way to react to unjust measures? How do you work with a colleague whose collaborationist attitude you despise? How does one deal with anonymous letters at such a time? The book is not a guide of what one ought to do, but a report of what happened.
The Liberation of Versailles is a thrilling account of the Allied forces arriving in Versailles in 1944 and being greeted with great rejoicing by the ecstatic population.
http://www.editions-harmattan.fr/index.asp?navig=catalogue&obj=livre&no=35756
Friday, January 6, 2012
Push-pull
I just saw a talk by Thomas Sauerwald analyzing the push-pull protocol for broadcasting in graph-theoretical models for social networks. If you ask your search engine for push-pull, many answers come up, related to aviation, physics, flirting, and marketing. But this is different.
To broadcast information, in the push protocol, at every round every node that has the information rudely shares it with a random neighbor, whether that neighbor wants it or not. In the pull protocol, at every round every node that does not yet have the information extracts it from a random neighbor, if that neighbor has the information. In the push-pull protocol, both behaviors occur.
Q: How many rounds before 99% of the nodes are informed?
A: log log n if the network is a Chung-Lu random graph model for social networks (parameterized such that the average distance between two nodes is log log n.) That's the result.
Q: What's the Chung-Lu model?
A: each node i has a weight w(i), and edge {i,j} is in the network independently with probability min(1,w(i)w(j)/W), where W is the sum of all weights. w(i) is such that the distribution of degrees follows a power law (with parameter beta).
Q: How about informing not just 99% but 100% of the nodes?
A: the diameter is roughly logarithmic, so, there is no way that you can inform 100% of the nodes in time log log n. In a social network, when something goes viral, 1% of the crowd will remain clueless in spite of your efforts. The solution: just forget abut them. We're the 99%!
Q: What's the rough idea of the proof?
A: Partition nodes into classes according to (the log log of) their degree, (rounded to the nearest integer.)
0. The information initially belongs to a random node.
1. After log log n rounds it reaches a node in the highest class.
2. After a few more rounds it reaches (50% of) the nodes in the highest class.
3. After another log log n rounds it goes from there to almost all network nodes.
Step 2 contains some intuition: In the Chung-Lu model, two nodes x and y of high class (i.e. high degree) are probably connected by a path of length 2 via an intermediate node z of degree 2. If x has the information, then z will pull it from x after a couple of steps, and then z will pass it on to y after a couple more steps, so nodes of degree 2 transmit information in a constant number of rounds. In other words, small degree nodes are good for passing on information quickly to everyone they know. So what matters in the large degree nodes is really their degree-2 neighbors: those will immediately pull the information and share it across to their other neighbor, thus roughly reducing the GOSSIP mode of communication to a LOCAL mode of communication.
Q: Is the push-pull protocol realistic?
A: It's not inconceivable. Pushing corresponds to, say, sending an email to a single (or a few) recipient(s) to share information: "Have you heard? Abe and Amy broke up!". Pulling corresponds to asking your friend: "How are Abe and Amy doing? I haven't seen them lately" or checking their Facebook page, and then, if you find the piece of information which you were waiting for "Status: single", adding a note about it on your own Facebook wall: "Hey everyone, look, Abe is no longer in a relationship. He's single! How exciting!". (I am having trouble imagining why someone seemingly so interested in that piece of information would want to broadcast it to the rest of the world, but if that's the only reason why the protocol is not perfectly realistic, I'll give it a pass.)
Q: Is the Chung-Lu model realistic?
A: Maybe since it's a reasonably good fit with reality according to several statistics. But there is no way to know for sure, is there?
Q: Is the above log log n result robust? Does it still hold if the push-pull protocol or the Chung-Lu network is replaced by something similar but different?
A: The proof presumably breaks down. The result might still be true if the graph has small average distance and if it has some small degree nodes adjacent to large degree nodes.
Q: Is the synchronous assumption realistic?
A: In the asynchronous model in which each node has a Poisson clock, the log log n becomes a 1. That's because x and y don't just have a path of length 2 going through node z: they have many such paths going through z1, z2, …, and one of them goes through a node whose Poisson clock rings twice in rapid succession: "Zap! Get that info from x! Zap! Tell y about it, quick, to be the first one!" and transmits information almost instantaneously. So we don't mind if synchronicity does not hold, quite the opposite!
Q: What about other graphs?
A: In general graphs, the idea of reducing GOSSIP to LOCAL has been explored by Kelner, Censor-Hillel, Haeupler and Maymounkov. The two modes differ by at most an additive polylog(n).
To broadcast information, in the push protocol, at every round every node that has the information rudely shares it with a random neighbor, whether that neighbor wants it or not. In the pull protocol, at every round every node that does not yet have the information extracts it from a random neighbor, if that neighbor has the information. In the push-pull protocol, both behaviors occur.
Q: How many rounds before 99% of the nodes are informed?
A: log log n if the network is a Chung-Lu random graph model for social networks (parameterized such that the average distance between two nodes is log log n.) That's the result.
Q: What's the Chung-Lu model?
A: each node i has a weight w(i), and edge {i,j} is in the network independently with probability min(1,w(i)w(j)/W), where W is the sum of all weights. w(i) is such that the distribution of degrees follows a power law (with parameter beta).
Q: How about informing not just 99% but 100% of the nodes?
A: the diameter is roughly logarithmic, so, there is no way that you can inform 100% of the nodes in time log log n. In a social network, when something goes viral, 1% of the crowd will remain clueless in spite of your efforts. The solution: just forget abut them. We're the 99%!
Q: What's the rough idea of the proof?
A: Partition nodes into classes according to (the log log of) their degree, (rounded to the nearest integer.)
0. The information initially belongs to a random node.
1. After log log n rounds it reaches a node in the highest class.
2. After a few more rounds it reaches (50% of) the nodes in the highest class.
3. After another log log n rounds it goes from there to almost all network nodes.
Step 2 contains some intuition: In the Chung-Lu model, two nodes x and y of high class (i.e. high degree) are probably connected by a path of length 2 via an intermediate node z of degree 2. If x has the information, then z will pull it from x after a couple of steps, and then z will pass it on to y after a couple more steps, so nodes of degree 2 transmit information in a constant number of rounds. In other words, small degree nodes are good for passing on information quickly to everyone they know. So what matters in the large degree nodes is really their degree-2 neighbors: those will immediately pull the information and share it across to their other neighbor, thus roughly reducing the GOSSIP mode of communication to a LOCAL mode of communication.
Q: Is the push-pull protocol realistic?
A: It's not inconceivable. Pushing corresponds to, say, sending an email to a single (or a few) recipient(s) to share information: "Have you heard? Abe and Amy broke up!". Pulling corresponds to asking your friend: "How are Abe and Amy doing? I haven't seen them lately" or checking their Facebook page, and then, if you find the piece of information which you were waiting for "Status: single", adding a note about it on your own Facebook wall: "Hey everyone, look, Abe is no longer in a relationship. He's single! How exciting!". (I am having trouble imagining why someone seemingly so interested in that piece of information would want to broadcast it to the rest of the world, but if that's the only reason why the protocol is not perfectly realistic, I'll give it a pass.)
Q: Is the Chung-Lu model realistic?
A: Maybe since it's a reasonably good fit with reality according to several statistics. But there is no way to know for sure, is there?
Q: Is the above log log n result robust? Does it still hold if the push-pull protocol or the Chung-Lu network is replaced by something similar but different?
A: The proof presumably breaks down. The result might still be true if the graph has small average distance and if it has some small degree nodes adjacent to large degree nodes.
Q: Is the synchronous assumption realistic?
A: In the asynchronous model in which each node has a Poisson clock, the log log n becomes a 1. That's because x and y don't just have a path of length 2 going through node z: they have many such paths going through z1, z2, …, and one of them goes through a node whose Poisson clock rings twice in rapid succession: "Zap! Get that info from x! Zap! Tell y about it, quick, to be the first one!" and transmits information almost instantaneously. So we don't mind if synchronicity does not hold, quite the opposite!
Q: What about other graphs?
A: In general graphs, the idea of reducing GOSSIP to LOCAL has been explored by Kelner, Censor-Hillel, Haeupler and Maymounkov. The two modes differ by at most an additive polylog(n).
Thursday, January 5, 2012
An algorithm
The other day a 5-year old child was showing me her kindergarden work. I saw the instructions: "follow the pattern and color the beads", and a necklace with a sequence of pearls carefully drawn along the curving line: red, blue, purple, red blue purple, red, blue, purple, etc. I said to her: "I see that you're doing Math in school". She answered: "No, that's not Math. It's an Algorithm."
This is how I discovered the French kindergarden curriculum: drawing, singing, writing letters, alphabet, math, and algorithms.
So: "Math" means numbers and arithmetic, while "Algorithms" means logical reasoning. What a conquest!
This is how I discovered the French kindergarden curriculum: drawing, singing, writing letters, alphabet, math, and algorithms.
So: "Math" means numbers and arithmetic, while "Algorithms" means logical reasoning. What a conquest!
Sunday, January 1, 2012
A new year challenge: life as in the 20th century
As you read this, I am off the internet.
I have nothing with me that connects to the internet.
No laptop.
No iPhone.
I am disconnected. I challenge you to be able to do it for 24 hours!
What happens to your email correspondents when you disconnect?
Do disasters and catastrophic events suddenly start happening?
Does hell break loose?
Do you lose your job?
I will know in a few days, when I get back online.
I have nothing with me that connects to the internet.
No laptop.
No iPhone.
I am disconnected. I challenge you to be able to do it for 24 hours!
What happens to your email correspondents when you disconnect?
Do disasters and catastrophic events suddenly start happening?
Does hell break loose?
Do you lose your job?
I will know in a few days, when I get back online.
Subscribe to:
Posts (Atom)