The opposite of Math/CS

When I read a book, regardless of topic I often find some parts of it that resonate with my understanding of Mathematics and computer science. One book that I read recently is a glaring exception: "Washington rules" by Bacevich, presenting an interpretation of American military operations in recent history. The book was interesting in laying out its theory that American leaders, regardless of political party, believe that the US have a mission to assure world wide order and peace via their military power. But none of it made me think of any Math/CS issue.

So, I think that political history is the opposite of theoretical computer science.

Student evaluations

The nastiest student evaluation I ever got was while visiting Berkeley, teaching an undergraduate summer course on Algorithms:

"Why does Berkeley always have to hire incompetent foreign immigrants who can't speak English to teach its summer courses?"

------------------------------------------------------

The most memorable student evaluation I ever got was in France, the following (anonymous, of course):

"The lectures are quite interesting, but they would be even more interesting if the instructor dressed better."

It was a mid-semester evaluation. At the following lecture, I read the comment aloud to the class and saw one student in the back turning bright red. So much for anonymity!

------------------------------------------------------

Once at Brown, being away at a conference, I asked a TA to teach a lecture for me. After my return, I asked the students to fill out evaluations of and feedback on his lecture. Here is the most remarkable comment he got (anonymous, of course):

"X. is so great. I want to have a child from him."


------------------------------------------------------

How students are annoying

In the comic book "Le chat du rabbin", the rabbi's cat gets into an argument with the rabbi's rabbi about whether he should be allowed to have a bar-mitzvah. Then the cat tells the rabbi's rabbi that he, the cat, is God who has taken the appearance of a cat as a challenge for him. The cat proceeds to tell the rabbi's rabbi that he is very dissatisfied with his behavior, that he has been as dogmatic and closed-minded with him as some Christians are with Jews. The rabbi's rabbi kneels before the cat and asks for forgiveness. The cat then answers that it was just a joke, that he is not really God but just a cat after all, and that the rabbi's rabbi can stand back up from his knees. The rabbi's rabbi gets angry and says that the cat should be drowned. The cat's rabbi asks the rabbi's rabbi whether a rabbi ought not to systematically accept contradiction from his students, and whether that is not the very principle of Talmudic teaching.

I like that principle but I'm not sure how much contradiction I can deal with.

Once I was teaching a freshman class in France. Some students were not paying attention. The atmosphere grew increasingly chaotic. Paper airplanes were flying around the amphitheater. I heard a couple of pieces of chalk being thrown as I was writing on the board. Then, inexplicable muffled laughter broke behind my back. And again. I looked sideways, and saw the red light of a laser pointer shining on the board next to me. Someone was acting up with a laser pointer! More laughter every time I turned to write on the board. My temper started rising (it is usually slow to trigger but, once awakened, is quick to rise). Finally I turned around quickly, just in time to see the source of the merriment.
-"You!"
-"Who, me?"
-"Yes, you. Get out of here."
-"Me? Why?"
-"Just get out. I have had enough of you for today. You have been distracting the entire class and preventing other people from paying attention to the lecture. Enough! Pick up your stuff and leave, right now. You can ask one of your friends to explain the material of the rest of today's lecture to you."
I had no idea what I would do next if he didn't leave, but I was angry enough that I didn't care. Fortunately the student got up, slowly, and left reluctantly.

The ordinary miseries of traveling

- Have to either pay $75 to check a second piece of luggage, or (my choice) accept to have several bulky carry-ons
- As a result of the quantity of my carry-ons, forget cellphone at security. It's probably lost forever, and some of the phone numbers stored in it will be hard to recover
- The usual discomforts of flying a red-eye
- Red wine (complimentary, thanks to Air France) spilled on my clothes while flying
- Slowed by the new arrangement of a renovated train station, barely miss a connection to a commuter train, then incur delays for the next one, hence a missed lqter connection to a bus: ordinary mishaps that lengthen the airport-to-destination part of the trip by a couple of hours.

Nothing out of the ordinary, but every time I travel by air, I remind myself that I don't want to do it anymore.

Skype is the way of the future.

The invisible button

I am still using a very old laptop that I am reluctant to give up. For the last few months, it has stopped showing any images.

Today I am at Logan airport, near Boston. Computer scientists hang out at airports all the time. Sometimes it seems that we travel just for the benefit of spending a few hours in airport noise, breathing airport air, and watching airport urban decor. Several times already, I have had chance encounters at airports with people I knew.

Logan has free wifi. To connect, you just need to click on the relevant button on the screen. However, having no images, I do not see the buttons. How, then, can I connect?

The first time it happened, I used trial and error, and spent a long time moving my mouse around the mostly blank screen. Occasionally, it went over something invisible that was clickable. I tried clicking on it, saw what happened next. After a few tries, I found the right place to click on my screen.

The second time, I was with someone else who also had a laptop, and watched on her laptop to see the approximate location of the button I wanted to click. That made it much easier.

Today, the third time, the presentation appeared to have changed (at least, judging from the non-blank parts of the screen), but I simply took my time: whenever the mouse went over something clickable, I left it to hover in place, until, after a moment, a label appeared with a brief description of the functionality of the invisible button. Thus I explored the screen much more efficiently, and only had to click once. It is the first time that I have ever seen those labels to be any good for anything!

How pure scientists are annoying

Literalism. Logic pushed to the extreme, in a narrow way, ignoring the broader context.

A few examples taken from my own life, off the top of my head:
---------------------------
A1: "Does anyone have the time?"
I: "No, sorry"
A2: "Did anyone answer A1?"
I: "Yes, I did"
... (pause) ...
I:"...and I answered that I didn't have the time"
---------------------------
B1: "Can I count on you for this task?"
I: "I can't promise"
B1: "Do you not want to do it?"
I: "Well, an earthquake might strike, or the end of the world might arrive, or something. So I can't promise."
---------------------------
C1: "How to solve world hunger?"
I: "Let's see. One fairly clear way could be to kill the weak and old, to reduce overpopulation."
---------------------------
D1: "Child, don't put your bare feet on the table!"
I: "Why shouldn't he put his feet on the table?"
D1: "Come on. Because it's dirty."
I: "If that's the reason, then does it mean that, if his feet are clean, then he'll be allowed to put them on the table?"
---------------------------
E1: "I'm off to the store. Do you want to come along?"
I: "Sure, I'll be happy to."
E1: "But beware, I am paying for everything. I don't want you to pay. Is that clear?"
I: "All right, I won't pay for everything."
E1: "(after hesitating a moment and parsing my answer:) Oh, you mathematicians! One always has to listen carefully to every word to avoid being tricked. You twist meaning."
---------------------------

Dreams and academics

What dreams are specific to the academic life?

I have had a dream in which I was giving a lecture or a seminar but realized as I was about to start that I knew nothing about the topic which I was supposed to cover. Huge embarrassment. Of course, some approximation of that has happened to me in real life too, so the amount of fantasy in that dream is quite small, but it is a dream that I never had before becoming a professor, and that I have had several times since then.

Several friends have dreams that as they are giving a talk they suddenly realize that they are naked. Not very original, for sure. People who speak in public know that they must be willing to say something a little bit personal to make their talk interesting, so they are revealing a bit of themselves publicly, thus exposing themselves to possible attack from an unfriendly audience, and the decision to let oneself be vulnerable is scary even if it is by choice. That dream makes perfect sense.

But here is a unique researcher's dream. A friend has had a recurring dream in which he is trying to find a tantalizing error in a proof. He proves a big theorem, but the proof would imply something false, for example, that pi equals three, so he knows that there must be an error somewhere, but where? The dream consists of the frantic search.

And of course, there is the very common, possibly universal dream that happens when we become absorbed in a problem: we start dreaming about it a wake up in the middle of the night with the perfect proof, rush to turn on the light and jot down the main points before they vanish in the fog of dreams of the past, only to find a scribble of vacuous nonsense by our bedside when we wake up the next morning.

Elchanan Mossel on life, counting, and comparisons.

Elchanan Mossel has been visiting Microsoft Research for the past few days. In his work, he particularly likes reversible Markov chains. I missed an opportunity to ask him for his views on research, but, instead, the other day, as a spin-off of the topic "To hike, or not to hike", he offered me his opinion on life.


He is against counting people's age as the number of years elapsed since they were born. Instead, he wants to count in reverse, starting from the time when they will die and going back in time until the current date. Why? Because that's what really matters if you want to use that number as a gauge of how much deference to show someone. If the person is only a few hours or days from dying, of course you will most of the time yield to their wishes: it's their last chance to enjoy life, whereas you will get other opportunities later, after they are gone. Similarly if someone has only a year or two to live, whereas you have twenty or thirty years.


Of course the problem is that we do not know in advance exactly when someone will die. So, a natural solution is to use the person's current age as a proxy: the more years have elapsed since their birth, the closer they are to death, on average. Elchanan maintains that it's just a proxy, and that when other knowledge gives more information on the unknown date of future death, one should take it into account.


What's the upshot of this theory? The result is that, in spite of our age difference (I am his senior by 9 years), because of the difference in our respective physical health, he claims, or at least he implies, that I legitimately ought to show him respect and deference.


I think that that's right in line with yesterday's post on "Math madness".

Math Madness

Richard Schwartz, my neighbor in Rhode Island, is a Math Professor who also writes children's books. He wrote "You can count on Monsters", an Amazon best-selling book about tilings, numbers up to one hundred, primes, and monsters.

On his web page, there are also illustrated children's stories that seem to draw a mixture of raving and furious reviews. His very particular sense of humor is called "madness" by some, yet I instantly recognize it. I think that it's a distinctive mathematician's humor that has to do with playing with the absurd.

Sometimes I make a comment that is patently absurd. If I am in the company of computer scientists and mathematicians, all instantly recognize it as humor and naturally reply in like manner, for a moment of delightful freedom from common sense. If I am in other company, people look at me uncertainly and start avoiding me, I'm not sure why.

There are no taboos in pure science. Everything could and should be questioned, and belief can always be suspended just as well as disbelief. When I now read Alice in Wonderland, I can recognize the unmistakable marks of a mathematician's mind.

Subscribing to Arxiv

Many years ago, friends in physics told me that every day they looked at the preprints uploaded on the Arxiv website on that day. A few days ago, a friend in probability and combinatorics told me that he was doing the same. This week, I followed my sheep instincts:
--------------------------------------
email cs@arxiv.org
Subject: subscribe Claire Mathieu
add DS
----------------------------------------
Now, every day I receive an email from arxiv listing all "preprints on the topic of Data Structures and Algorithms" published in the past 24 hours, along with their abstracts. From now on I will be able to keep up with current research, not with a lag of a couple of years as happens to people who read journal articles, not with a lag of six months as happens to people who read conference proceedings, not with a lag of three months as happens to people who study lists of accepted papers to conferences and immediately search for papers of interest (which is what I had been doing), but with a lag of just a couple of days: as soon as authors are ready to claim a result, they publish their preprint on Arxiv, and I hear about it on the next day.

If this catches on -- and it seems to be spreading -- it will change the way we do research. A friend physicist described their way of life: "There is a constant race to be ahead. People rush to publish partial results, putting unpolished drafts on the Arxiv. The pressure to publish is enormous. The number of preprints is large, but the quality is low. There is no vetting for quality, and there are often mistakes." That sounds like the complaints that computer scientists have about conferences, raised to another level of unpleasantness.

Yet I can't deny a certain pleasure in reading abstracts from the previous day's uploads to Arxiv. It feels like I am on the cutting edge of research, no matter where I am physically located anywhere in the world.

A global warming algorithm

I saw the following comment there and thought it was funny in its deadpan style presentation.

So, is there any plausible case where the following is NOT going to happen during this century:

1. Rapidly warming arctic melts the sea ice.

2. Melting sea ice exposes more and more open ocean.

3. Open ocean absorbs more solar energy, thereby accelerating the warming and the melting, and exposing more open ocean, which absorbs even more solar energy.

4. Steps 1-3 continue until Arctic warms sufficiently to thaw permafrost/tundra and to destabilize underwater clathrates, thereby releasing vast amounts of methane.

5. Game over; PETM extinction looks like a picnic by comparison.

Lift-and-project and odd cycle constraints

Lift-and-project has been studied during the last 10 years in the theoretical computer science community as a systematic way to strengthen linear programs. As an introduction, let's consider the independent set problem.

Start from the usual LP relaxation for independent set: one variable x(i) for each vertex i, such that
0 ≤x(i) ≤1 for each vertex i
x(i)+x(j)≤ 1 for each edge {i,j}.

Algebraically, one round of lifting leads to the following LP in the Sherali-Adams variant: each initial constraint leads to 2n new constraints. For each k, one new constraint is obtained by multiplying by x(k) and the other by multiplying by 1-x(k), and then substitute y(i,k) for x(i)x(k). We have variables x(i) for each vertex and y(i,j)=y(j,i) for each pair of vertices, with y(i,i)=x(i). The constraints obtained by this automatic process are thus:
(1) 0≤ y(i,k) ≤x(k) for each pair of vertices i and k
(2) 0≤x(i)-y(i,k)≤ 1-x(k) for each pair of vertices i and k
(3) y(i,k)+y(j,k) ≤x(k) for each edge {i,j} and each vertex k
(4) x(i)-y(i,k)+x(j)-y(j,k) ≤ 1-x(k) for each edge {i,j} and each vertex k.
That's the automatic algebraic definition.

To understand this intuitively, note that each variable x(i) of the basic LP can be interpreted as a distribution over vertex i: x(i)=.3 means that with probability .3 vertex i is in the independent set and with probability .7 it's not in the independent set. Similarly, each {x(i),x(j),y(i,j)} of the lifted LP can be interpreted as a distribution over the pair of vertices i,j: x(i)=.35,x(j)=.6,y(i,j)=.2 means that with probability .2, both i and j are in the set, with probability .35-.2=.15, only i is in the set, with probability .6-.2=.4, only j is in the set, and with the remaining probability .25, neither i not j are in the set.

Let us focus on the lifted LP for independent set. First, notice that y(i,j)=0 for every edge {i,j}: to prove this algebraically, apply (3) to k=i, substitute y(i,i)=x(i) and simplify to get y(i,j)≤ 0. Together with (1) that implies y(i,j)=0. To understand this intuitively: the constraint x(i)+x(j)≤ 1 means that i and j cannot simultaneously be in the set, so in a joint distribution over i and j, the probability that both i and j are in the set should be zero.

Now, here's a more interesting fact about the lifted LP for independent set. I want to prove that constraints (1)-(4) imply every odd cycle constraint: for every cycle C of odd length, the sum of the x(i)'s for i in C is at most (length(C)-1)/2. At first sight, that is a bit surprising, because the lifted LP still merely consists of local constraints (with a bunch more variables), whereas the odd cycle constraints are long-range global constraints. I will prove this for a cycle of length 9, consisting of vertices 1,2,...,9.

Note that since 1 and 2 are neighbors, y(1,2)=0
Apply (4) for k=1 and {i,j}={2,3}: x(2)+x(3)-y(1,2)-y(1,3)≤ 1-x(1)
Apply (3) for k=1 and {i,j}={3,4}: y(1,3)+y(1,4)≤ x(1)
Apply (4) for k=1 and {i,j}={4,5}: x(4)+x(5)-y(1,4)-y(1,5)≤1-x(1)
Apply (3) for k=1 and {i,j}={5,6}: y(1,5)+y(1,6)≤ x(1)
Apply (4) for k=1 and {i,j}={6,7}: x(6)+x(7)-y(1,6)-y(1,7)≤1-x(1)
Apply (3) for k=1 and {i,j}={7,8}: y(1,7)+y(1,8)≤ x(1)
Apply (4) for k=1 and {i,j}={8,9}: x(8)+x(9)-y(1,8)-y(1,9)≤1-x(1)
Note that since 9 and 1 are neighbors, y(1,9)=0
Sum everything: after cancellations, we get x(1)+x(2)+...+x(9) ≤4.
That's the odd cycle constraint.

What miracle just happened? Instead of going all the way around the cycle, let's just go through the path from 1 to 9 (ignoring the edge between 9 and 1) and sum those inequalities. We obtain:
x(1)+x(2)+...+x(9)≤ 4+y(1,9).
Normally, we know that the independent set can only have at most 5 vertices of a path consisting of 9 vertices, and that can easily be proved from the basic LP, but this tells us more. The variable y(1,9) captures the joint distribution of x(1) and x(9): it tells us that the sum can only be more than 4 when x(9) and x(1) are simultaneously equal to 1. This additional information is what comes into play when we close the cycle: because there is an edge between 9 and 1, x(1) and x(9) can never be 1 together, so we're stuck at 4.

Stronger versions of lift-and-project add positive semi-definite constraints. Why do we care about lift-and-project? Ten years ago, it seemed like a promising venue to reduce the integrality gap of linear programs. That promise has not yet been fulfilled, and it is not so easy to manipulate those complicated, higher dimensional objects, but we are slowly making progress. For example, in the upcoming FOCS Barak, Raghavendra and Steurer use lift-and-project for an algorithm for unique games.

In a graduate course on approximation algorithms, I would want to spend a lecture or two talking about lift-and-project. The above would be a preliminary introduction, but after that, I would want an example of application of lift-and-project that would be simple enough to present in about one lecture. I am wondering: what is the least technical interesting example of using lift-and-project?

How to choose sub-reviewers

When I am on a conference program committee or editor of a journal, here is how I choose a sub-reviewer who I ask to read and evaluate the submission.

First, I carefully read the part of the introduction that talks about "related work" and about "techniques", looking up every reference. Then, I quickly look through the body of the paper, checking whether some paper is referenced inside the proofs. Then I know that that paper is probably important and the authors of that papers would probably have a well-informed opinion on the submission.

Once I have my list of relevant or very relevant references, I restrict attention to recent papers, discarding anything older than 10 years old, because I assume that, absent other information, the authors of those papers are probably no longer interested in the subject. I look at redundancy, giving higher priority to authors who have written several of the relevant cited papers. I look at conflicts of interest, giving lower priority to people who have recently co-authored papers with the authors of the submission. Then, I give higher priority to authors of papers that have been published in similar venues, because I assume that they will be better able to evaluate the quality threshold. Finally, I try to pick a mix of junior people, who have more time and may be more interested in the submission, and senior people, who may have more perspective and more of a long view on the results submitted.

Uri Feige on important research questions

Uri Feige popped in for a brief visit of the Microsoft Research Theory group. After lunch on Thursday, Yossi Azar, Nikhil Devanur, Uri and myself stood in the hallway of Building 99 chatting. Here is my recollection of our conversation.

Claire: Why do you do research?
Uri: Because I get paid for it.
Yossi: Come on, we all know the real answer to that question. We do research because we enjoy it, of course. It's fun.

Claire: How do you pick research problems?
Uri: There are two ways. Some problems I pick because I think that they are good problems, that the questions are important, that they have lasting value. The other way is opportunistic. There are problems that I work on because I can. They come up, and I know how to solve them.

Claire: Can you give an example of a paper of yours that was opportunistic?
Uri: I have many papers that are opportunistic. It would be a better question to ask me which papers are not opportunistic.

Yossi: for example, your result on the hardness of approximation of set cover
Uri: My own contribution to that paper was opportunistic. It's not one of my favorite papers, actually, in terms on my personal investment into it. I had the right skills at the right time, for a problem that begged to be solved, so, for me, it was a matter of applying the techniques that I already had available at that time. Atthe time there was a different question I really cared about: parallel repetition. That was quite important to me even before it started having impact. I was interested in understanding it and willing to invest a lot of time into it.
Claire: Do you wish you were Ran Raz?
Uri: I am happy being myself, thank you.

Claire: Tell us more about questions that have lasting value.
Uri: I am not so sure what people will think, in one hundred years, about the distinction between polynomial and exponential time. Maybe they will think it was an exotic topic that researchers in the late 20th century and early 21st century got stuck in, some odd topic temporarily in fashion.
Yossi: I'm not sure I agree.
Uri: Also, our evaluation of running time is based on asymptotics. How can you be sure that asymptotics have lasting value? It all depends on how large n has to be. If n is more than something like 2^50, or, let's say, 2^100 (just to be on the safe side), then no one cares whether an algorithm takes polynomial or exponential time.
Claire: No one cares about anything at all when n is 2^100
Uri: No, that's not true. 2^100 may come up, for example, if you are manipulating implicitly defined subsets of objects. Then, what you want is a sublinear algorithm.

Nikhil: Approximation I think is more of a weak point in our models. Why we care about approximation ratios: I am not sure it's so fundamental. Between approximation ratios of log(n) or log(n)^2, I don't know that it really matters.
Uri: Also, consider the area of algorithmic game theory. There, many questions come up that have to do with people's behavior. How good the questions are depends on how faithfully our models capture the behavior of human beings. But it is not clear whether our questions are the right questions, whether that's the way in which people think. It's not like physics.
Nikhil: There is nothing similar to the law of thermodynamics.
Uri: So we don't really know whether what we do has any lasting value.
Nikhil: what do you prefer, algorithms or lower bounds?
Uri: I prefer algorithms. Then there are some problems, for example some "hat" problems, that are unrelated to algorithms or to lower bounds, but that I personally care about, although solving them won't make a STOC or FOCS paper. As for computation, I am not sure how fundamental, long-lasting it is. Some integrality gaps results have lasting value, more than the corresponding NP-hardness proof. The hardness result may matter more right now at the present time, but in the future, gap results might have a more lasting impact. They do not depend on any Turing machine or computation model.

A Theory of Bugs, or: a New Model for Proof-Checking

Yuval Peres, who was the secret influence behind the recent shift of
Computer Science conferences towards mandating that full proofs be
included in the appendix of submissions, has a theory about bugs. He
likes to say that, more often than not, mistakes lie in the parts of
a proof that have been given less attention than the rest, and that
in the manuscript, such parts are often prefaced by wording such as:
"It is easy to see that...". Those words are like a red flag.

Such a theory makes for interesting lunch time conversations, but, as
creationists like to say about the theory of evolution with a
dismissive, contemptuous tone of voice: "It's just that, a mere
theory" - implying that it therefore has no value.

Very recently Yuval's Theory of Bugs was validated by real events. An
exciting new result came out. Yuval was interested, but suspicious
(as one always should be with exciting results), but too busy to
check the proof for correctness line by line. So, he applied his
theory, and searched for the sentence: "It is easy to see". No luck.
Then he searched for: "It is easy to verify", and found one instance.
He focused on that claim, and, sure enough! The claim was flawed --
in fact it was easy for him to verify, not that the claim was true,
but that the claim was false.

Value

On the afternoon after the SODA deadline, my office mate asked me:

- Are you working right now?
- No, just putting together receipts for getting refunded from trips
- Oh, doing that counts as work
- Not really. It doesn't have any value except monetary
- Well! What has value if not money!?

But as we know, money does not have any value in itself. Then, what does have value? In our work, I think it's knowledge. When we read a paper, understand a new lemma or algorithmic idea, we learn something, and no one can take that away from us. That has value. When we discuss a problem with a student and he or she acquires some of the techniques, they learn, and that has value. When we teach a class and students get acquainted with some computer science topic, after that, they know more. That has value. When we make progress in research and discover some new structure or have an insight, we learn something new that no one knew before. That has value. Knowledge has intrinsic value.

A puzzle

(From Omer Tamuz)

Basic puzzle:

A prisoner escaped from prison, and, starting from some n on the positive integer line, jumps k steps to the right at each step. An adversary tries to catch him by landing a the same place as the prisoner at the same time. The adversary chooses one place at each time step, and all choices are possible. For example: 3,10,5,2,58,9,... But the adversary knows neither k nor n.

How can he or she catch the prisoner?

Extension:

What if the prisoner takes his basic calculator and uses some elementary function of time (using addition, substraction, multiplication, division, logarithms, exponentials, sine and cosine - rounded to the nearest integer) to compute where to go at time t?

Further extension:

What if the prisoner takes his laptop and writes a program that will, for each t, determine where he goes at time t?

Bastille day

Today is Bastille day in France, the national holiday, commemorating the 1789 uprising of the population that opened (and later destroyed) the hated Bastille prison in which the monarchy used to put political prisoners, and also the 1790 feast of the federation. From now on until Assumption day on August 15 (a Catholic holy day that it also a French public holiday), it is peak vacation time.

It was declared the national holiday in 1880, and then the official report to the Senate said: "Le 14 juillet 1790 est le plus beau jour de l’histoire de France, et peut-être de toute l’histoire. C’est en ce jour qu’a été enfin accomplie l’unité nationale, préparée par les efforts de tant de générations et de tant de grands hommes, auxquels la postérité garde un souvenir reconnaissant. Fédération, ce jour-là, a signifié unité volontaire.
Elles ont passé trop vite, ces heures où tous les coeurs français ont battu d’un seul élan ; mais les terribles années qui ont suivi n’ont pu effacer cet immortel souvenir, cette prophétie d’un avenir qu’il appartient à nous et à nos fils de réaliser."

My quick-and-dirty translation: July 14, 1790, was the most beautiful day of French history, and maybe of all of history. On that day was finally accomplished the national unity prepared by the efforts of many generations and of many great men, to whom we are grateful. Federation, on that day, meant consensual unity. Those hours when all French hearts beat together passed by too fast, but the terrible years that followed could not erase that immortal memory, that prophecy of a future that is now our duty, for us and for the next generations, to transform into reality.

Now it sounds so quaint, and a little bit ridiculous. Were they really so naive? So idealistic? One wonders what 19th century politicians would think of the style of 21st century political speeches.

Why do research?

One day, when I was a student, I asked Andy Yao why he was doing research. As best as I remember, this is what he answered:
-"I need a long-term goal to drive my interest in the field. If the P vs. NP question was resolved tomorrow, I would probably change fields."
I insisted: what did he enjoy the most about doing research?
-"I enjoy the moment right after I have discovered something new. At that time, there is something that I know and that no one else knows yet. It's like being the first person ever to get to the top of a mountain. I spend a few days savoring the feeling."

What to teach students their first day/week/month studying CS

[07/08/11] Claire Mathieu: Hi Cora! Hi Val! Would you like to talk about what to teach students their first day/week/month studying CS? Any ideas on this?
[07/08/11] Glencora Borradaile: sadly, not really - other that they should see some algorithmic ideas early on. i liked Phil Klein's intro-cs course - that is really the only intro-cs class I've seen
[07/08/11] Glencora Borradaile: I've been handed a CS orientation class that needs work. 3 hrs/week for 10 weeks plus 1 hr of lab per week, but the labs are pretty set. we assume they know nothing and there is no requirement that they learn any programming
[07/08/11] Claire Mathieu: Really! So you're all free.
[07/08/11] Glencora Borradaile: Yes. Which is nice, but also too much freedom.
[07/08/11] Valerie King: There's an interesting course at CMU. It's "Great Ideas in Theory". It doesn't presume any previous knowledge
[07/08/11] Claire Mathieu: What kind of things do they teach? Computation? Godel's incompleteness theorem? Recursivity?
[07/08/11] Valerie King: some complexity some randomization, some algorithms. I think Rudich developed it
07/08/11] Glencora Borradaile: 15-251: Great Theoretical Ideas in Computer Science (Spring 2011)
This course is about how to use theoretical ideas to formulate and solve problems in computer science. It integrates mathematical material with general problem solving techniques and computer science applications. Examples are drawn from Algorithms, Complexity Theory, Game Theory, Probability Theory, Graph Theory, Automata Theory, Algebra, Cryptography, and Combinatorics. Assignments involve both mathematical proofs and programming. https://colormygraph.ugrad.cs.cmu.edu/
07/08/11] Claire Mathieu: But really, Cora's talking about, not just Theory, but all of CS I think.
[07/08/11] Glencora Borradaile: Yes.
[07/08/11] Claire Mathieu: At Orsay we used to have a mini-programming language with a mini-lab in which you could visualize an architecture and an execution step by step at the level of registers. You go from some basic-like piece of code to mini-assembly to a bunch of 0's and 1's, then we see it executed. It was an eye-opening experience for me to see how computers can actually do what they are told. Then Turing machines made a lot more sense. So we see the concept of programming and of computer. That, I thought, was brilliant.
[07/08/11] Glencora Borradaile: huh. I wonder if something like that is still available.
[07/08/11] Valerie King: In the old days we had a course like that, without programming but with a card board "computer" which had 10 instructions. I found it very interesting.
[07/08/11] Glencora Borradaile: So you think they should have some experience with seeing how a computer should work - computer architecture. (And they want *me* to teach it?) But is that computer science? Or just something that computer scientists should know?
07/08/11] Claire Mathieu: Well, it helps make sense of everything else for me. For example, what is an algorithm? Those formal definitions - sequence of instructions that you know how to do, etc. With a little bit of an intro to architecture, it's just so much more real.
[07/08/11] Valerie King: I think from our point of view it makes sense.
[07/08/11] Glencora Borradaile: one of the course learning objectives for this course is to be able to explain what computer science is.
[07/08/11] Valerie King: Well many people today would say it involves HCI, graphics, applications, etc.
[[07/08/11] Claire Mathieu: But those topics (HCI etc.), they are not core CS.
[07/08/11] Glencora Borradaile: what is core cs?
[07/08/11] Claire Mathieu: Computation
[07/08/11] Glencora Borradaile: That's difficult for me. It's a study of how to solve problems computationally. So, programming languages and algorithms are core. CA and OS - are they computer science or computer engineering? and then there are, perhaps topical areas - ML, graphics
[07/08/11] Valerie King: I looked at what others had written. There is something Jeanette Wing calls computational thinking. This includes algorithmic thinking. Which involves abstraction and recursion. There is also the ability to think about concurrency for example
[07/08/11] Valerie King: Ah, I've been writing up a description of that for our VPAC (Vice president Academic. that's standard Canadian.)
[07/08/11] Claire Mathieu: What is NOT CS? Prove the existence of an object by the probabilistic method, then ask students to find it. There is no algorithm. They are helpless. Then the difference between constructive and non-constructive problem-solving appears.
[07/08/11] Valerie King: CS is about what can be computed and what can't be. I'm not sure the probabilistic method is about computing, by itself.
[07/08/11] Claire Mathieu: Well, I mean precisely that the probabilitstic method enables you to prove things without giving you any handle on how to compute it, so it shows examples of what is NOT computer science.
[07/08/11] Valerie King: Here is my definition: Computer science is a relatively young, diverse and changing field, evolving as the use of computers evolve. Unlike electrical engineering, computer science deals not with the physical level of transistors and devices, but with a level of abstraction above this, where the computer's operations are idealized. Thus, on-off switches store information; information is manipulated by other information representing programs, programs are run by other programs known as systems, and so on. Understanding and designing for these complex processes requires skills which computer scientists sometimes call "computational thinking".
It includes ``algorithmic thinking," the ability to specify a step by step procedure by which the problem can be solved with the goal of minimizing time and computational resources. Algorithmic thinking also includes knowing which kinds of problems are infeasible for any computer to solve, how information can be communicated efficiently, and how it can be kept secret. Computational thinking also includes the ability to reason about large systems of interacting networks of computers and users, and large amounts of data, and how to represent this complexity to users. Computer scientists draw on diverse skills: mathematics and logic, psychology and sociology, engineering, linguistics, art and music.
In the last 20 years, scientists with large amounts of data, e.g., from the Hubble telescope or DNA sequences, have recognized the centraility of computation in their research. The analysis of the human genome was made possible by the development of speedier algorithms developed by computer scientists working with biologists. Today we are seeing researchers from the humanities. social sciences, and the arts working with computer scientists to analyze information and create knowledge in ways never considered before. New forms of electronic media, like Facebook, exhibit sociological connections between millions of people on a global level. The advent of online advertising and auctions have created a new subfield of computer science and economics.
An economist may be able to show a market equilibrium exists; a computational economist may show that it is computationally infeasible, in terms of computing resources, for anyone to determine the equilibrium point. Computational thinking is becoming ever more important, to a wider range of areas.
[07/08/11] Claire Mathieu: So what's different about CS? What makes it unique? Now it looks as though it's all over the map."in ways never considered before"?
[07/08/11] Valerie King: I believe it applies everywhere, but it's viewing everything through a particular lens, that of computation.
[07/08/11] Glencora Borradaile: math of the 21st century
[07/08/11] Valerie King: Re ways never considered before: I think of how we can now view millions of connections between people, we have all sorts of data we can analyse.
[07/08/11] Claire Mathieu: Kind of like statistics? (devil's advocate) Statistics apply everywhere: Analyzing data, huge amounts = statistics
[07/08/11] Valerie King: The question is whether CS gives a different view from statistics. Does data mining differ from statistics? I think CS has evolved some new perspectives, like the PAC learning model which can involve the notion of feasibly computation.
[07/08/11] Claire Mathieu: There is certainly a different flavor (emphasis on worst case vs. distribution assumptions for example), but in essence,...? I guess statistics is only trying to say things about data - analyze it and make observations, infer structure -- but we are solving problems involving data. That's a little bit different,m isn't it?
[07/08/11] Valerie King: I don't know, I think the difference is the notion of poly time computable, maybe

[07/08/11] Glencora Borradaile: what if you went backwards - what would a high school class learn about CS? my problem with (high school) cs classes - and math classes - is they don't reflect cs (or math). cs is "just programming"
[07/08/11] Claire Mathieu: "Just programming" is what they think after high school, and that is wrong.
[07/08/11] Glencora Borradaile: yes. maybe compare to physics or chemistry or biology
[07/08/11] Valerie King: They also have boring intro classes sometimes
[07/08/11] Glencora Borradaile: sure, you learn experimentation, but lab courses are a minority in what you study, from what I remember
[07/08/11] Claire Mathieu: Stil, I think that programming is central. Computability, undecidability, induction, abstraction etc. are best understood with some programming skills. You could have a course centered on problem-solving.
[07/08/11] Valerie King: Or some easy programming language.
[07/08/11] Glencora Borradaile: that's true - it is nice to see the ideas in action
[07/08/11] Claire Mathieu: One thing: I think that the notion of polynomial-time is probably too advanced for a first course. First they need to internalize the idea that we're dealing with asymptotics - large size data sets
[07/08/11] Glencora Borradaile: sure - that's fine
[07/08/11] Claire Mathieu: It might be good for them to see that (program Hanoi towers, say)
[07/08/11] Glencora Borradaile: but you could show them the difference between a bad design (exponential) and a good design (polynomial) for the same problem
[07/08/11] Valerie King: In our classes here, the other profs get the students to act out the algorithms. Like quicksort
[07/08/11] Glencora Borradaile: or median finding
[07/08/11] Claire Mathieu: What do you mean, act out? QS - I tried once to get them to sort themselves. That was rather awkward.
[07/08/11] Valerie King: I can't bring myself to do it.
[07/08/11] Glencora Borradaile: why not?
[07/08/11] Claire Mathieu: It's weird, and you need students who are good-natured
[07/08/11] Valerie King: It seems so silly. And if I were in the audience, it would have seemed so easy anyhow
[07/08/11] Claire Mathieu: When I was in elementary school we acted our computation in binary. Each student was 1 bit. Arm up (1), arm down (0).
[07/08/11] Glencora Borradaile: heh
[07/08/11] Valerie King: That's good. My daughter learned to count binary with her fingers
[07/08/11] Claire Mathieu: She has only 2 fingers?
[07/08/11] Valerie King: Each finger is a digit
[07/08/11] Glencora Borradaile: the number 4 is always amusing for kids
[07/08/11] Claire Mathieu: Oh, right. Some numbers had best be avoided though
[07/08/11] Claire Mathieu: jinx
[07/08/11] Valerie King: I guess games would be fun.
[07/08/11] Claire Mathieu: It can be fun, but what does it show? What concepts get taughts?
[07/08/11] Valerie King: Recursion maybe
[07/08/11] Glencora Borradaile: abstraction
[07/08/11] Claire Mathieu: Example of abstraction? Can you be more concrete?
[07/08/11] Valerie King: Cora, they tell us here when we design a class we should think of learning outcomes first
[07/08/11] Glencora Borradaile: yes, we have a similar thing here. the learning outcomes for this course are pretty minimal. i could do what I want, so long as I hit them
[07/08/11] Claire Mathieu: hit your students??
[07/08/11] Glencora Borradaile: very funny.
[07/08/11] Claire Mathieu: What are the "outcomes" for that course?
[07/08/11] Glencora Borradaile: "what is CS", "data representation", I think, I would have to find the list .... I remember them not being so ... specific or deep
[07/08/11] Claire Mathieu: "data representation": what would be good for that? In terms of what concepts to convey
[07/08/11] Glencora Borradaile: i think they have 'just' been doing binary representation. of course, you could go much deeper than that
[07/08/11] Valerie King: you could add huffman coding
[07/08/11] Claire Mathieu: Crypto. Code each letter with another letter. Ask students to decode a text that you have encoded.
[07/08/11] Glencora Borradaile: that's true. that would be good actually - hitting on some areas of cs
[07/08/11] Claire Mathieu: Manipulating data that's poorly represented: adding numbers written with Roman numerals -- the progress of mathematics with Al-Kowarizmi, thanks to symbol 0 and base 10 representation of numbers. Plus a little bit of implicit fighting anti-Moslem prejudices
[07/08/11] Valerie King: abacas
[07/08/11] Claire Mathieu: logarithms with those instruments that people used to have - they could ask their grandparents?
[07/08/11] Glencora Borradaile: slide rules?
[07/08/11] Claire Mathieu: yes. Except I don't even know how those work
[07/08/11] Valerie King: Didn't you have one? I did
[07/08/11] Claire Mathieu: no
[07/08/11] Glencora Borradaile: wow! Even I know how to use one, Claire! :) (or, at one point, I was shown and may be able to reproduce it)
[07/08/11] Valerie King: I'm the last of a time. Oh, my father was a chemist, very proud of his slide rule
[07/08/11] Claire Mathieu: Although maybe not such a good example because a lot of the difficulty is in the Math rather than in the computation itself, at least, that's my impression?
[07/08/11] Claire Mathieu: Do you thin slide rules are good for teaching data representation?
[07/08/11] Valerie King: I think an abacas might be more interesting.
[07/08/11] Claire Mathieu: How about the various representations of Catalan numbers? I don't know how to use an abacas either -- unlesss it's obvious
[07/08/11] Valerie King: I knew once, I forgot.
[07/08/11] Valerie King: You could go over the history of computation
[07/08/11] Claire Mathieu: That could be fun. Astronomy. The earth at the center of the world, or not. Copernicus. Religion. Taking square roots by hand
[07/08/11] Valerie King: Euclid's algorithm. methods for computing pi
[07/08/11] Claire Mathieu: Oh, pi, that is good! But they'd have to program something too
[07/08/11] Glencora Borradaile: do you think this would turn off a group of students? a group of students that probably are not fond of math (something I don't understand) (that people would major in CS when they 'hate' math)
[07/08/11] Claire Mathieu: They don't like math because they think it's purely symbolic
[07/08/11] Glencora Borradaile: you could have a competition to see who could compute the most digits of pi
[07/08/11] Valerie King: you can look it up
[07/08/11] Claire Mathieu: Teach them reasoning, problem-solving, puzzles, finding each other's mistakes in logical inferences and they'll love it, I think...?
[07/08/11] Valerie King: Most of what students do now is look up answers
[07/08/11] Claire Mathieu: Counter-intuitive answers are such fun. They destabilize the students. Make them unsure of previous certainties. It's a good way to start college
[07/08/11] Valerie King: Well there are those logic puzzle books. Like "what is the name of this book?"
[07/08/11] Claire Mathieu: Also, when the teacher teaches things that are wrong. You know, prove something, they nod, then tell them there's a mistake in your argument. Or write a program, tell them "find the error". Like Where's Waldo
[07/08/11] Glencora Borradaile: what can you ask students that they can't look up the answers to?
[07/08/11] Claire Mathieu: In class, in real time
[07/08/11] Glencora Borradaile: (a case for in-class tests and quizzes - I am thinking of not having any true assignments) without their laptops open
[07/08/11] Valerie King: Right, I give quizzes
[07/08/11] Claire Mathieu: Just thinking about the possibilities, though, it's exciting. Of course it's hard to make these concrete. And not lose sight of the goals.
[07/08/11] Claire Mathieu: I'm sorry but I have a meeting coming up
[07/08/11] Glencora Borradaile: thanks for all the ideas - this was really helpful for me
[07/08/11] Valerie King: Look at Rudich's course
[07/08/11] Valerie King: bye
[07/08/11] Claire Mathieu: bye
[07/08/11] Glencora Borradaile: later!

Post-SODA submissions

On Tuesday around 2pm, the SouthSouthWest corner of Microsoftt building 99 breathed a collective sigh of relief: the SODA submission deadline was past. Altogether, the members and visitors of the Theory research group have submitted a good dozen of papers, and the last couple of days have been quiet and busy.

On Monday Allan Borodin joked that since our submissions were all in competition with one another, we should try to prevent other people from finishing up their last touches, but in reality, the studious atmosphere helped people work. Certainly, I remember that from when I visited Berkeley or Princeton. Five minutes after the deadline, everyone is dawdling in the hallways, and if this was at different times, we would all be having a smoke or at least a drink. For that atmosphere to exist, there needs to be a critical mass of people working in theoretical computer science. Only a few research groups are like that.

That sense of reaching a (temporary) goal all at the same time, that collective breathing in and out of the research community three times a year (SODA, STOC, FOCS) is unique to our field. In Mathematics, it is unknown. It is part of our tradition and it makes us more of a community.

How not to take decisions

This weekend I went on a hike with three PhD students visiting the Theory group at MSR, Alice, Bob and Charlie. At the trailhead, we met hikers who recommended a trail that they were going to follow, different from the one we had planned. We didn't have a map but looked at theirs, tried to memorize it, and decided to follow their suggestion.

They had said that after a creek crossing, the trail would go up and get covered with snow. The creek would have been a fine stopping point for a moderate and very pretty hike, but we were not ready to turn back, so, in spite of the knowledge of the difficulties that lay ahead, we kept going.

To gather information, we asked every hiker we met what the trail would be like ahead of us (is there a model for that in TCS?). None of them had continued very far, so we could have taken the cue and turned back, but the uphill path in the forest would have been such a boring, disappointing place to stop, that of course we kept going.

Then snow appeared, and walking started to require attention. We could have turned back, but we were still able to follow the trail and see footsteps of the people who had gone before us, so we stubbornly kept going.

Then the trail disappeared. We kept going a little ways, but, worried about getting lost, were just about to turn back, when we heard hikers above us. Two men appeared, one with an ice axe, and informed us that, equipped with a GPS, they had made it up to the ridge, a thousand feet above; they seemed to find it no big deal, so we decided to follow their footsteps. Adventure! Exciting! So we kept going.

Walking up steep snowfields between the trees was hard going, particularly for those wearing sneakers. We considered turning back, but the view kept getting better and better. Finally, the voice of reason:
"-[Alice:] I think we should turn back".
"-[me:] How about if we just keep going for another 45 minutes?"
"-[Alice:] I think that's too long. How about 15 more minutes?"
"-[me:] Ok, sounds good."
Thus was common sense neatly silenced by me, and we kept going.

15 minutes later -- only Bob had a watch, he didn't say anything, and no one asked him about it. Oh, the pride! So we kept going.

Worries were expressed by Alice and Bob about how we would get back down, but I peremptorily declared that we should defer discussing such non-constructive thoughts until we had to face them, and so, with that problem temporarily solved in that expeditious manner, we could keep going.

No more objections were raised. To prevent other non-constructive thoughts, Charlie entertained us with the story of Lord Shackleton's expedition. Another 30 minutes -- suddenly the ridge was in sight, only a short distance away! In no way were we going to stop at that point. We enthusiastically kept going.

Success!

Nothing is more beautiful than a hard-earned view. No wine is sweeter than on a wide ledge with a steep ravine down in front and a vertical cliff down in the back. No food tastes better than up in the heavenly solitude of the high mountains. There is no wind, the late afternoon sun dries our sweat, and life is good.

Unfortunately, what goes up must come down. But how?

Off we went reluctantly. Down steep snowfields among the trees. Slow, careful, yet slightly hazardous. I worried that it might be a harrowing experience for those wearing sneakers. Then - the incident I feared: Bob slipped, fell, and started sliding on the snow. I heard the sound, turned back, tried and failed to grab his hand as he passed me, but didn't have the presence of mind to put myself squarely in his way, and he ominously continued towards the trees. Then - he managed to stop himself after just a few yards. Phew! It had all happened in an instant. But really, now that it was over, it was as though nothing had happened: all was well, no big deal. Still, that'll be an interesting memory from his time at Microsoft Research!

We resumed our slow descent, retracing our footsteps with much care. We managed not to fall again, and not to get lost in spite of a couple of brief false alarms. Back on the trail, back across the creek, back down the mountain, and finally back at the car, with at least 20 minutes of daylight to spare. Perfect!

What a great hike!

In hindsight, although the hike was fun and beautiful, going all the way to the ridge of the mountain was not a wise decision. But making such decisions online in real time is extremely difficult, if not impossible. Who can fight the irresistible urge to keep going? How can the longing to reach the goal not cloud one's judgement? At some point, part of me knew that we ought to turn back, but I could not bring myself to let that thought quite emerge into my consciousness. How do mountain guides know when to stop, I wonder? How does one learn that kind of wisdom?

And that is how MSR visitors and interns spent their weekends.

Allan Borodin on Theoretical Computer Science

Allan Borodin is vising the Microsoft Research Theory group this week, and this morning we are sharing the same office. I took that opportunity to ask him a few questions.

[Claire:] I saw on a blog that you were the only attendee at FCRC who was already present at the first STOC conference. Of course there are many other active researchers whose work also spans the same time interval, but they were not at FCRC this year, and they are not in my office right now. So, for you, who have perspective on the evolution of the field over its entire history, what do you think of it?

[Allan:] We (the field) still work on the same fundamental problems, but the field has diversified a lot. There are some things we don't do any more, such as some work on formal languages, but there are also many new exciting directions. You know for example, all the work on social networks, and links with economics. It is much, much more diverse field.

[Claire:] How about your own work?

[Allan:] I have moved away from complexity theory. It's become too difficult. For example, consider the algebraic geometry agenda to resolve the P versus NP question. I currently prefer to focus on developing a bettter understanding of conceptually simple combinatorial algorithms such as greedy algorithms, local search, dynamic programming.
For example, in mechanism design, if you design an algorithm that people cannot understand, then they're simply not going to use it.

[Claire:] Is there some recent progress that particularly interested you?

[Allan:] In terms of understanding simple algorithms, in the last SODA conference there was a paper by Poloczek and Schnitger giving a simple 3/4 algorithm for Max Sat, using randomization. In the upcoming ESA 2011 conference Poloczek proves in some strong sense that the algorithm cannot be de-randomized. But this is just the most recent result I am thinking of. The field has been continuously vibrant with great impact (e.g. complexity based cryptography).

Ambiguity in scientific writing and in literature

In our scientific writing we often make statements that could be interpreted as ambiguous. Just as operator overloading (using the symbol "+" both for the addition of numbers and of matrices, for example) simplifies and actually clarifies writing, leaving some parts of our statements not spelled out in detail can sometimes improve writing. It presents ideas at a higher level, preventing the reader from being side-tracked by minor points.

However there is an underlying assumption, that the reader is at the level of maturity that will permit them to reconstruct the unsaid without effort. The writer wants to convey something very specific, and, if both reader and writer took the time to spell out the missing pieces in full detail, they would both come up with the same interpretation. I cannot think of any instance where it is desirable that the reader come up with several interpretations of what the writer really meant. There is no such freedom. The text and its meaning belong to the writer, and the reader is not at liberty to go at variance with what the writer intended to convey.

That is not true in literature. For example, "The Raven" poem by Poe. What is that bird really about? Why does it say "Nevermore" repeatedly? The answers can vary from reader to reader. Once the poem is released, it escapes from the poet, and other people are free to give it meanings that Poe never intended. They read the poem in the context of their own experience, and interpret it in radically different ways. The multivalence is not a fault but a richness. The stand-alone poem is incomplete, and it only achieves meaning when the reader's perspective is incorporated into it. The poem is ambiguous in a way that a mathematical text never is.

How to quiet a classroom

How does one start a lecture? Usually at Brown I try to arrive a little bit early, and the students slowly gather, chatting merrily as they get out their notebooks and laptops. When I am ready to start, how do I bring about some silence?

As a singer, I refuse to raise my voice and risk hurting my precious vocal chords. As a believer in democracy, I am reluctant to force people to shut up by drowning them out with my microphone. Imposition is not fun. I prefer to make people do what I want because they want to, not because I force them.

Once at Mass I remarked how the priest asked the congregation to sit down. Since it is not one of the rubrics, to avoid disrupting the flow of the liturgy he used a nonverbal cue: he looked at the congregation, extending his arms forward, palms facing down, and moved his hands downward, as if he was pushing on an invisible cushion hanging in the air in front of him. Immediatly people sat down.

At my next class, when I found myself ready to start lecturing, I stood in front of the class, looked at my students, extended my arms, palms facing down, and silently moved my hands downward, as if I was pushing on an invisible cushion hanging in the air. The majority of students stopped talking right away, and the few who had not seen my gesture noticed the change in noise level, looked up, saw me repeat the gesture, and made silence. Complete silence. Magic!

I started teaching my class as though that was the most natural thing in the world and as if I had never expected anything different, but inwardly I was thrilled by the aura of natural authority that had suddenly enveloped me. In later weeks I repeated the gesture occasionally, always with great effectiveness. No stole or chasuble needed!

The Online Parking Game

I have been living in Seattle for a week, with a car but with no reserved parking space, and have therefore been playing a game with parking enforcement officers, similar to "Mister X", a board game where all players but one gang up on the last player, "Mr. X", and try to catch him as he moves stealthily around Manhattan.

If I lived here, I would know what to expect: the patterns of the routes and schedules, the amounts of the fines. My decisions would be stochastic. But as I am new here, it's an online game in which every day I learn a little bit more about my adversaries. The streets near my flat require paying to park on the street between 8am and 6pm. Getting back from Microsoft after 6pm is no problem, but in the morning, being out and on the road by 8am is a challenge, so every morning I take a few more minutes, hoping that no parking enforcement officer will come and give me a ticket between 8 and 8:10. Then it's too early to fight traffic across the bridge to Redmond, so instead I head to a cafe. If I go to a cafe on First Hill, I park on some small street, hoping that parking is not reserved to residents, or that parking officers would be lenient with a car with a California license plate. If I go to a cafe down below, REI has free parking for the first hour, but only opens at 9am, so what is one supposed to do between 8:15 and 9am? Once I did pay to park on the street between 8:15 and 9, but I have a strange, almost Freudian reluctance to slipping money into the parking meter coin slot. So, today I am leaving the car across the street from the cafe, simply hoping to get lucky. At 9am I will move the car to REI (of which I am a frequent customer), and then I just need to make sure that I am on my way by 10am. Will these various online choices spare me a ticket? How much is the ticket, if I get one? Is the game worth playing? Only future will tell.

That's the Online Parking Game. So far, I am ahead.

In Berkeley, near campus, parking is limited to 2 hours, and during the day while we discuss research work is regularly interrupted by people saying: "Let's take a break: I need to move my car". The policy thus plants breaks from work throughout the day in a natural manner. Very healthy!

In Providence, it's definitely worth playing the game, since tickets are only twenty dollars. In addition, whenever I get a ticket, I have a feeling of righteousness as I pay it: by being such a good citizen in my prompt payments, I am helping the city deal with its deep budget problems. In addition the police officers are mean -- they're clearly out to get you -- so the game is irresistible. There can be unexpected twists: once I parked to run a quick errand, leaving my son in the car and not putting money in the parking meter. A police officer showed up, and when my son explained that I would be right back, the officer reacted by suggesting a compromise, asking him if he had any money on him. Unfortunately he didn't, so when I got back to the car there was a ticket on my windshield.

In Manhattan I don't play the game. I am afraid. It's a vast and dangerous world out there. I am scared that if a police officer finds me parked five minutes overtime, he will send me to rot in jail for twenty years. So I go to a parking garage and pay the attendant whatever amount he asks for.

Here is what I wish google or bing provided: a detailed map of the city, with the block-by-block parking rules. For all I know, if I went a few blocks away from my flat I would be able to park in a side alley with no constraints. But I do not know that, and exploring takes time. Why can't our online resources help with that?

Focs 2011 accepted papers...

I just looked at statistics about this blog.
This week, what is the most common keyword search leading to it?
"Focs 2011 accepted papers".

Ha!

Here is a link to the FOCS web page that currently says that the list is "not yet available".
When the list is officially out, the link will take you to it.

Alternative title for this post:
How to disappoint your readers.

Cafes old and new

Cafes used to be a place for people unhappy at home to come and find a temporary escape with a bit of company and of alcohol; for friends or dates to meet in a neutral space; for tourists to rest after long walks; for anyone who wanted some time alone sheltered from the elements to read the newspaper in peace; and for anyone who wanted to socialize to sit a a table, do some people-watching, and interact with friendly strangers. It was a very special place at the frontier between private and public life, playing a unique role in society: where else would you go EITHER if you wanted to be left alone OR if you wanted some company? I used to overhear heated conversations about sports, politics, and how to change the world.

Last summer I was passing through a village in central France on the day of the final of the World Cup, and stopped at the cafe to watch the game on their TV. The place was packed with people of all ages who had gathered there to watch the game together instead of each in their own home. It was the nexus of the village's social life. How old-fashioned!

Now, at least in the US, newspapers and books have all but disappeared, and in cafes interaction between people has gone down drastically. People still come to cafes for the illusion of socializing, but laptops are the new companions, and the place is full of individuals each focused on their own screen, some with headphones. The bodies are at the same location, but the minds are each in their own world, and contacts are minimal. The cafe has been reinvented as a variant of one's office.

A 4/3 algorithm for TSP for a special case

Here is a special case that illustrates the main idea of the Moemke-Svensson algorithm (after receiving an email from Ola Svensson with comments). The result in that special case was already known (Boyd, Sitters, van der Ster, Stougie, IPCO 2011) but by different methods; the point of this post is to explain the deletion/addition/removable pairs idea.

Input: shortest path metric in a 2-edge-connected unweighted graph G in which every vertex has degree 3.
Output: 4/3 approximation to TSP

Algorithm:
1) Let T be any depth-first-search tree.
2) Define removable pairs as follows: each back edge goes into some vertex, call it v, and (if v is not the root) is paired with a tree edge from v to the child of v. ("the" child, because the graph is cubic).
3) Take M, a random perfect matching of G such that each edge is in M with probability 1/3 (known from some 1980's discrete math publications).
4) For each edge e of M that is in a removable pair, remove e from G. For each edge e of M that is not in a removable pair, add e to G, creating a duplicate edge.
5) Output an Eulerian tour of resulting multigraph.

Analysis of correctness: in the multigraph, every vertex has even degree, 2 or 4, and, given the definition of removable pairs, it is not hard to convince oneself that it is still connected, so it's Eulerian.

Analysis of cost: G has (3/2)n edges. T has n edges. (Almost) every back edge is in a removable pair, so there are (n/2) removable pairs, each pair with 2 edges, for a total of (n/2)*2=n removable edges. The other (n/2) edges are unremovable. The expected size of the output is:
(#edges of G)+(# unremovable)*prob(in M) - (# removable)*prob(in M)=(3/2)n+(n/2)*(1/3)-(n)*(1/3)=(4/3)n,
give or take a few.

This is so simple that it could probably be taught at the senior undergraduate level.

And that concludes my posts about TSP, for now.

Better than 3/2 for TSP, take two

In April Tobias Momke and Ola Svensson published a beautiful paper on Arxiv about an(other) better-than-3/2 approximation algorithm for the traveling salesman problem when the input is the shortest path metric in an unweighted undirected graph G. It's a 1.461 approximation. Here's a summary of the algorithm, without the analysis.

The algorithm first solves the Held-Karp linear programming relaxation, which in this presentation is written using one variable x(e) per graph edge e, and whose objective is to minimize the sum of x(e), subject to having at least 2 edges between S and V-S for every nontrivial subset S of vertices. It drops from the graph all edges not used by the LP solution.

From the LP solution, they construct a depth-first-search tree starting from some arbitrary root, where ties when choosing what vertex to visit next are always broken in favor of traversing the edge e with maximum value x(e). They can then view the graph as directed, with every tree edge directed away from the root and every back edge directed towards the root, and solve a circulation problem to find a minimum "cost" collection of cycles covering all tree edges. Here the "cost" is the number of back edges, except that for each vertex v and each child-subtree of v, the first back edge into v out of the subtree is free. (The fact that the tree is not just any DFS tree, but one that has been guided by the LP solution, helps bound the "cost" of the circulation.) Then the algorithm drops from the graph all edges not used by the circulation. Consider the result G'.

The algorithm will then make this graph into an Eulerian multigraph by making all the degrees even. In the Christofides heuristic specialized to unweighted graph metrics, one first takes an arbitrary spanning tree T and then makes it Eulerian by adding a set M of edges forming a min cost collection of paths in G connecting odd degree vertices.

Here, in the first phase the authors construct G' instead of T, so a priori they seem to doing worse than Christofides: the graph G' is not a tree but something with more edges, hence more costly. In the second phase they choose edges M forming those paths based on edges in G' only instead of G, thus depriving themselves of possibilities, so it's also a source of additional cost a priori. But they have a brilliant idea to make up for it: how about if, instead of adding all the edges of M to G', one removed some of them from G'? Indeed, if adding duplicate copies of some of the edges adjacent to a vertex v makes the degree of v even, then removing some of them instead of duplicating them also makes the degree even. That's the key new observation: x-1 is congruent to x+1 modulo 2. One wonders why it took 30 years to realize that!

The problem, of course, is that when one starts deleting some edges instead of adding them, then the graph risks becoming disconnected. To prevent that from happening, the authors define local constraints that suffice to ensure that connectivity is maintained: consider the structure of the graph G'. If, for each vertex v and each child-subtree of v, the algorithm makes sure to either preserve the tree edge from v into the subtree or preserve the first back edge from the subtree into v, then connectivity is maintained. These are called "removable pairs" of edges. Other edges of M will always be added if they are tree edges and will always be deleted if they are back edges.

So, now the authors want to choose M, a collection of paths connecting odd-degree vertices, in such a way that many of these edges can be deleted of the graph instead of being added to the graph. To that end, they just do it the stupid way, so to speak, i.e. without using any further structural property of their graph: it is not hard (via a reduction to matchings in cubic graphs) to pick a random M whose one-dimensional marginal is uniform, such that every edge is present with probability 1/3.

In total, some parts of the algorithm make it worse than the Christofides heuristic, some parts make it better, and there did not seem to be any way to predict a priori how those pros and cons would work out. It's a lucky coincidence that the resulting algorithm beats 3/2!

July 4th

I recently spoke to a relative who just started an internship and is delighted by one feature of the job: after she gets home from work, in the evening, her day's work is over and she is free to turn her mind to other things with no nagging thought in the back of her mind of what she should be doing for work.

I answered that, except when backpacking, I do not really know that feeling. I was just a little bit envious. In our profession, we always have one more thing to do, there is always one more theorem that needs to be proved, one more paper that needs to be finished, one more review that needs to be written. In what other profession would I, of my own volition, be spending most of the day of July 4th working?

The upside of course is that our job is interesting, and, we like to think, vastly more interesting than 9-to-5 jobs. But as a lifelong academic, I have no way of knowing that for sure. One hint that that might be true: once I was with a group of about 10 people in their thirties. One said that if he came into a large sum of money, he would retire from his job. Another answered: "Of course. We all would!" I looked around, surprised to see everyone nodding, while the only other academic in the room and I simultaneously answered: "No we wouldn't!" --- at least we would hesitate, weigh the pros and cons, the exciting aspects of our job versus what we are missing out on in life by spending so much of our energy focused on generally arcane topics; it would not be the obvious decision that it seems to be in other professions.

So, that's the upside.

The downside is that I find myself at my desk on the morning of July 4th.

How to talk to non-scientists

Yesterday on a hike someone named Sara, who is not a mathematician nor a scientist, asked me what I do. I said I worked on theoretical computer science, that is, the mathematics of computer science. She asked: "What is it that you people do, exactly? I can understand what a musician, say, does in his work, but I have no idea what mathematicians do."

I started trying to answer her: "You like games. You enjoy puzzles. Consider the Rubik's cube, and think about what your brain does as it is trying to figure it out. That is very similar to what a mathematician does while he or she is working on solving a problem. In addition, instead of working with a physical object, it's as though they had a picture of the Rubik's cube in their head, and they work with their representation of the mathematical world inside their head, so it's a bit more abstract." Omer Tamuz intervened: "yes, abstraction is very important. Here is an example. For every group of six people, if you look at which pairs are friends and which are not, there always exist either three who are all friends or three, none of which are mutual friends." He tried to explain it more clearly, I criticized that choice of an example, he asked me what would be a better example of abstraction, I suggested commutativity of addition and of multiplication, he suggested that removing three apples from eight apples leaves five apples, just in the same way that removing three oranges from eight oranges leaves five oranges, I criticized those examples for not being impressive enough, suggested the probabilistic method, it reminded him of Noga Alon's simple and beautiful first lecture in a course, which, upon my request, he proceeded to tell me about in full detail, and suddenly we came upon the others, including Sara, who had stopped for a break.

Sara had long since left Omer and me to join the others, but we had not even noticed her absence. She commented how amazing it was that after she had asked just one simple question, we took off with it, started discussing math, and an hour later we were still going at it. I was a little embarrassed. That doesn't seem like quite the right way to talk to a non-scientist about what we do, does it?

I am afraid that it reminds me of the 19th century cartoon L'idée fixe du savant Cosinus -- a must-read for all French-speaking mathematicians.

How to pick research problems (UPDATED)

(Scroll down to the end for update with Valerie King's contribution.)

[07/01/11] Glencora Borradaile: Hi Claire
[07/01/11] Claire Mathieu: Hi Cora!
[07/01/11] Claire Mathieu: Today we are meeting on skype to discuss how one picks research problems. There are two categories of problems I work on: the problems that I come up with, and the problems that are given to me. When a problem is offered to you, how do you gauge whether it's a "good" problem?
[07/01/11] Glencora Borradaile: If the problem given to you is already a theory problem - distilled to a clean problem - then it should be easier. Have you worked on any problems that weren't already in that form?
[07/01/11] Claire Mathieu: Sometimes but not with great success. Modeling a problem is not my forte.
[07/01/11] Glencora Borradaile: Well, there are problems like the planar PTASes we've worked on - there was a good deal of evidence to believe that the result was possible.
[07/01/11] Claire Mathieu: I would say that it has to catch my interest, so that I happily spend time mulling over it; that I have to have some skills suited to it so that I have a good chance of making progress; and that some other people have to be interested in my solution afterwards, so that I get positive feedback from the community.
[07/01/11] Glencora Borradaile: What makes it catch your interest? Interest must go beyond your second two points, yes?
[07/01/11] Claire Mathieu: It has to be clean and mathematically simple, most of the time. But it has to be not purely recreational. It has to fit in some kind of context where I have a sense that it makes sense. Typically, some long-term hypothetical application... I get impatient with pure combinatorial mathematical problems.
[07/01/11] Glencora Borradaile: Really? You think what we work on has some long-term application?
[07/01/11] Claire Mathieu: I have the sense that combinatorial optimization problems on planar graphs is a subject that matters.
[07/01/11] Glencora Borradaile: I'm certainly arguing as much in my proposal ...
[07/01/11] Claire Mathieu: Now, a PTAS developed for one of those, maybe not so much a priori, but it fits in -- it gives insight into the complexity of the problem.
[07/01/11] Claire Mathieu: Also, I forgot an important criterion!
[07/01/11] Glencora Borradaile: Someone interesting to work with?
[07/01/11] Claire Mathieu: It has to be a problem that some colleagues around me are interested in, so that we can collaborate
[07/01/11] Claire Mathieu: Jinx
[07/01/11] Glencora Borradaile: I remember you talking about not caring to work alone.
[07/01/11] Claire Mathieu: I can't push myself to work on a problem alone
[07/01/11] Claire Mathieu: Jinx
[07/01/11] Claire Mathieu: How about you?
[07/01/11] Glencora Borradaile: A challenge I'm becoming very familiar with at OSU. So it's interesting - I'm not sure of the criterion of what would be a "good" choice. Right now I (know, ill-advisedly) am hung up on "good for career" as opposed to "good for self". Where sometimes those things are different.
[07/01/11] Claire Mathieu: As in... do you have some specific example of a problem which you would like to work on if, say, you were in heaven, with not a care in the world? And infinite time
[07/01/11] Glencora Borradaile: I would go in one of two extremes - much more theoretical or much more applied
[07/01/11] Claire Mathieu: Would you work on P vs. NP? You'd have infinite time to get acquainted with the existing literature
[07/01/11] Glencora Borradaile: I don't think I would work on that - I think I don't want to know the answer to that. I think the field is made interesting by the fact that we don't know it. I might work on things like the 4-colour theorem (a simple proof for it, I mean). Or anything where I didn't have to worry about publishing for a while. *or* I would go and try to solve a real traffic engineering problem, say - propose a good (mathematically sound) solution and see it through to completion.
[07/01/11] Claire Mathieu: The problem is that, even if you don't have to worry about it, if you don't publish, you have no feedback to encourage you, and how do you stay self-motivated? One thing that helps a lot, that I learned from Karp, is to always keep the rate of progress positive. That is, always have an interesting example, or observation...
[07/01/11] Glencora Borradaile: Hmmm. Well, I think that for the "puzzle" aspect, I don't need external motivation.
[07/01/11] Claire Mathieu: Really? For me it quickly becomes sterile if I don't have something else to keep me at it: progress, collaborators, or outside feedback. For planar graphs, I guess I am piggy-backing on Phil Klein's enthusiasm. He provides the fuel, the energy that keeps us going.
[07/01/11] Glencora Borradaile: Perhaps people like you are more likely to be successful in the community. I mean: if you are driven (at least partly) by problems that will be accepted by the community - so as to get that feedback - then you're more likely to get that positive feedback (which we need for accolades and reference letters, etc.)
[07/01/11] Claire Mathieu: Right, on the other hand the researchers who revolutionize our field do not work that way.
[07/01/11] Glencora Borradaile: risk v. reward
[07/01/11] Glencora Borradaile: Do you think that's true?
[07/01/11] Claire Mathieu: Well, there's something to be said about being a problem-solver. Conceivably such a type of researchers could bring in techniques from other areas, their flexibility would make it easy for them to adjust to several fields and then see connections that might have escaped the people who are more driven in a single direction.
[07/01/11] Claire Mathieu: One thing I don't do is attack a big open problem upfront. If people have failed at it for a long time, then it's probably a waste of time to go at it directly. On the other hand changing perspective might make the problem doable and, since it would still be close to a recognized big question, still could be very interesting.
[07/01/11] Glencora Borradaile: But isn't that the opposite of working on problems that are not necessarily accepted by the community? If it's big and open, then there is a history to it?
[07/01/11] Glencora Borradaile: How about open v. new? How do you introduce a new problem to the community?
[07/01/11] Claire Mathieu: If it's not big and open, how do you know it's any good?
[07/01/11] Claire Mathieu: I'm not sure. I'm very tentative on those grounds. Last year Adrian Vladu worked with me on online ranking. It was new - no one had ever worked on that before, although plenty of people had worked on ranking. The reviews for our submission said that it was a "natural" question. What made it natural? I'm not sure. We were in some kind of void where I have to rely on such vague things as "taste" and I have no confidence that I have good "taste".
[07/01/11] Glencora Borradaile: natural = "well studied area A" + "well studied area B"?
[07/01/11] Claire Mathieu: + "putting A and B together makes sense"
[07/01/11] Glencora Borradaile: game theoretic network flows
[07/01/11] Claire Mathieu: A=game theory, B=network flows, A+B="people make decisions with themselves in mind when choosing traffic routes?"
[07/01/11] Glencora Borradaile: ah yes, that's true ... why didn't I think of that? That was the price of anarchy example too ... so much for being funny
[07/01/11] Claire Mathieu: and complexity of Nash equilibrium, A=equilibrium, B=computational complexity, A+B=computing equilibrium
[07/01/11] Glencora Borradaile: i've been grant writing and there are some problems which I would like to know the answer to, and would even like to work on, but can't list them because I don't have the background for it
[07/01/11] Claire Mathieu: I had my first grant proposal summarily rejected because I didn't know a basic bibliographical reference. I think it reflects very poorly on the applicant when she does not have the background and it shows. I would say that you need to have already one paper in an area before you can apply for a grant with a good chance of being funded (but what do I know)
[07/01/11] Glencora Borradaile: I had a confidence boost when myself and a colleague here at OSU got a grant from Google to work on a theoretical problem that I modelled (with my colleague's expert input). So, I guess that external motivation was nice.
[07/01/11] Claire Mathieu: Yes. What was your problem funded by google?
[07/01/11] Glencora Borradaile: The modelled version is a 2D analogue of string edit distance. It models the problem of comparing two spreadsheets. We have an unanalyzed algorithm that does very well when the two spreadsheets (arrays) have a common parent.
[07/01/11] Claire Mathieu: you want a fast algorithm? Good data structure? Average case analysis on some input model?
[07/01/11] Glencora Borradaile: Aiming for correct with high probability. Using a planted model.
[07/01/11] Claire Mathieu: I see. Nice. You might need some probability for that, though.
[07/01/11] Glencora Borradaile: Um. Yes.
[07/01/11] Claire Mathieu: And on work funded by google, you can't come to the MSR Theory group to leverage their expertise!!
[07/01/11] Glencora Borradaile: Maybe that's true.
[07/01/11] Claire Mathieu: Are you excited about it? It sounds like it might fit my description of a "good" problem.
[07/01/11] Glencora Borradaile: I am. I had an REU implement it last summer and it was great seeing this algorithmic idea exceed expectations. And beating the software engineer's solution (more external feedback ... I'm such a liar!). She (the REU) is back with me as an M.Sc. student. We have some theoretical explanations of simple cases ...
[07/01/11] Claire Mathieu: Sounds great. Now all you need is some nice mathematical structure
[07/01/11] Glencora Borradaile: It's a definite case of trying to design an algorithm with a view to an analysis.
[07/01/11] Claire Mathieu: But you already implemented it before knowing how to analyze it
[07/01/11] Glencora Borradaile: Yes. That's true. Well, *I* did not implement it. But, had it performed terribly, it would have saved me a lot of time.
[07/01/11] Claire Mathieu: "You" includes your students, Professor Borradaile. (Your undergrads, at least)
[07/01/11] Glencora Borradaile: Heh. The royal "you".
[07/01/11] Claire Mathieu: Ok. How about wrapping it up? I have that SODA submission to prepare...
[07/01/11] Glencora Borradaile: Likewise.
[07/01/11] Claire Mathieu: ok. Bye!
[07/01/11] Glencora Borradaile: Enjoy the long weekend. Bye!

UPDATE

Valerie King couldn't participate in our last discussion because she was in Europe, but sent her part of it afterwards. Here it is.

Hi Claire and Cora

I liked Karp's comment about always making positive progress. It's really saying keep a positive perspective. Little obervations can be useful. Hamming says: Plant acorns. I like to go for big problems that don't require a lot of background, because I like the stimulation of trying to come up with a completely new approach but I'm lazy. I like the spreadsheet problem, but it seems fundamentally different from string edit distance since there usually is a well understood structure in a spreadsheet. Or it's string edit distance where a structure is understood on the strings. I've seen some stuff like that. Software engineers look at program evolution and reengineering,trying to determine a common ancestor., especially in my CS dept (Hausi Muller, Margaret Storey). And I love working with people. When it reaches the point when you're together in this space creating something--very in tune with each other's thoughts. Last time I experienced this was a year ago, and it doesn't come frequently enough for me. And then I actually enjoy presenting the work, finding the right words and pictures to convey this new thing..

But every now and then I wonder why anyone is doing this. Whether the work is valuable at all. How one can stay focussed on a problem like the Dynamic Optimality Conjecture for decades without getting bored or losing faith in its importance.

Time for a break: Peter Winkler's 60th birthday limerick

Jim Propp wrote the following limerick in honor of Peter Winkler's 60th birthday a few years ago:

A mathematician named Pete
Found that math swept him off of his feet
Mere mention of DIMACS
Would cause him to climax
In ways colleagues found indiscrete.