## Thursday, March 31, 2011

### Defining the reading level of a text

How does one estimate the accessibility of a text? What leads to labels such as "This is at the 9th grade reading level"?

Apparently one big factor is the distribution of the number of syllables in the words. Another factor is the length of sentences. Here's a typical formula:
You can use a formula to calculate Flesch-Kincaid reading level on your own. This is a good tool to determine whether a book is going to challenge you.
1. Select a few paragraphs to use as your base.
2. Calculate the average number of words per sentence. Multiply the result by 0.39
3. Calculate the average number of syllables in words (count and divide). Multiply the result by 11.8
4. Add the two results together
5. Subtract 15.59

More on http://www.micropowerandlight.com/rd.html

I have reservations about these tools, at least as applied to material for adults. A text is difficult if it contains many unknown words, of course. One of the tools proposed maintains a database of words; perhaps they are ranked according to frequency in the English language, and one reasonable measure of difficulty would be the frequent occurrence of rare words.

But a text is also difficult if its structure is convoluted. Doing a grammatical analysis and parenthesizing relative clauses, one could compute the levels of nested parentheses, thus measuring the number of partial sentences that the reader must simultaneously keep in mind as he or she is reading. That should be an important factor in readability.

Examining vocabulary is similar to examining the number of notations that the reader of a scientific paper must familiarize himself with and must memorize as he is reading. Studying the nested structure is similar to studying the number of assumptions that the reader must keep in mind while processing a proof ("This is a proof by contradiction, with a case-by-case analysis, and we are in the "else" part of the "if" statement of case 2"...). Shouldn't there be a rigorous way to measure and analyze those parameters in readability?

## Wednesday, March 30, 2011

### Ehud and Avi on Fukushima

Avi Wigderson: "-Why tolerate errors [in outputs of randomized algorithms]?
-We tolerate uncertainty in life."

Ehud Friedgut: "You have to realize that, when people say: "This is very tiny", sometimes they mean 1/100 and sometimes they mean one over ten billion."

Neither realized it at the time, but they could have been commenting on the Fukushima nuclear plant accident!

## Monday, March 28, 2011

### Newton Institute: Monday

The people who are here at the Newton Institute (Cambridge, UK) this week are largely the same ones who were in Paris last week, or at Dagstuhl earlier, or in Jerusalem last year. Why do we go from place to place like a flock of migratory birds? What instinct prevents us from settling down anywhere in particular?

Here is what Christopher Lasch writes in his book "The revolt of the elites":
"Ambitious people understand that a migratory way of life is the price of getting ahead. It is a price they gladly pay, since they associate the idea of home with intrusive relatives and neighbors, small-minded gossip, and hidebound conventions. [...] Those who covet membership in the new aristocracy of brains tend to congregate on the coasts, turning their back on the heartland and cultivating ties with the international market [...] Patriotism, certainly, does not rank very high in their hierarchy of virtues. "Multiculturalism", on the other hand, suits them to perfection, conjuring up the agreeable image of a global bazaar in which exotic cuisines, exotic styles of dress, exotic music, exotic tribal customs can be savored indiscriminately, with no questions asked and no commitments required. The new elites are at home in transit, en route to a high-level conference, to the grand opening of a new franchise, to an international film festival, or to an undiscovered resort. Theirs is essentially a tourist's view of the world -- not a perspective likely to encourage a passionate devotion to democracy."
"Their loyalties -- if the term is not itself anachronistic in this context -- are international rather than regional, national, or local. They have more in common with their counterparts in Brussels or Hong Kong than with the masses of Americans not yet plugged into the network of global communication."

Ouch. Thankfully, I cannot possibly fit that description since I am staying in a dorm with a shared bath!

## Sunday, March 27, 2011

### The beggars of Paris

During my visit to Paris my two offices and my studio were all essentially on the same block, that I got to know by heart.

By the bakery on rue Gay-Lussac, there is a beggar, not always the same one. One day there was a woman and child, who I noticed looked at the chocolate bun that I had bought for breakfast. I gave the child half of my bun, whereupon the adult immediately said: "She is thirsty, too." I answered: "I can't give her that" and went on my way, annoyed for some obscure reason.

By the sea and water institute, there sometimes is a man begging and looking sad. After emptying the tiny fridge in my studio and checking out, as I walked by him with my bag of leftover groceries, his eye caught mine and I was compelled to offer him some of my extra food. But he refused my offer of a box of microwavable lentils and bacon dish: "I have no way to reheat it", he explained. I looked again in my bag, but there was nothing edible without cooking. "Sorry, I don't have anything else", I said regretfully. "It's all right, never mind. Have a nice day!", he answered gracefully. I continued on my way, wondering about the one thing that I could have given him but chose not to take out of the bag and offer him: a bottle of wine...

On rue Pierre et Marie Curie, there are often traces of a presence on the street: empty beer bottles, a sleeping bag drying on a railing, and sometimes an indistinct human form buried in layers of cloth. When I stayed late in the office, once or twice I heard loud drunken noises coming from the street.

At the corner of rue d'Ulm, there is a phone booth that was inhabited last January, but that is currently available. On the other hand, a woman seems to be spending many of her days sitting on a heat grate on the sidewalk. Late one night, I saw a shape in a sleeping bag, set up in the middle of the street, on the piece of pavement off limits to traffic that marked the middle of the intersection! Was it her? Was that her way of setting up some boundaries?

Further down rue d'Ulm, there is a university whose main entrance cuts off the first floor of the building diagonally, providing a shelter. A beggar is set up there. Sometimes he is sleeping. Other times, some large pieces of cardboard are set out and dozens of books are on display, as an improvised streetcorner bookstore. I wish I had looked at it more closely.

Closer to the RER, by the side entrance of the church of St Jacques d Haut Pas, there is a beggar, usually but not always an older woman. One day she was selling daffodils and I bought a bunch, happy with that creative way to generate an income. But she was indifferent to my presence and never raised her eyes to my face. She is only there during the day: perhaps she has a home to go back to at night.

The main entrance of that church also has occasional beggars, two men, but they're not regulars. Maybe they're only there at night and to ask for charity at Mass time.

The beggars in Paris are diverse. Men and women, young and old, with dog or child. I have seen an old woman reading a prayer book, oblivious to her environment. I have seen a young woman, her hair carefully covered with a scarf, in a silent kneeling posture, full of dignity. Her body is there, but her mind seems absent. According to statistics 17 percent of homeless people in Paris are women.

I often wonder what kind of beggar I would be.

### Wigderson against Pharisaism

Avi Wigderson taught a mini-course on expanders in Paris last week. I spent some time there learning about expanders, and some time learning about teaching.

When I present an algorithm or proof in a talk, in order to convey the main ideas, I sometimes ignore side concerns, which sometimes makes me take liberties with correctness stricto sensu. Avi takes that approach and carries it to an extreme: when briefly presenting a research direction, he may choose to briefly outline the prettiest algorithm, while briefly citing only the most important paper on the subject, even if there is a mismatch between the result outlined and the paper cited! I would not dare do that (at least not on purpose), for fear of catching hell from authors. But it is morally doing the right thing: giving a pointer to the one paper interested students ought to look at, while attracting them with hints of the most elegant results.

It's sacrificing accuracy in the details, so as to better get the essential ideas across. In fact, it's also sacrificing some accuracy to beauty. It's an anti-Pharisee stance: Pharisees, I am told, were so obsessed with rules and with following every detail of every ritual in exactly the right way, that those regulations obscured the overall purpose of their religious practice.

## Friday, March 25, 2011

### "P < > NP is a fact of nature"

That was the message from Avi Wigderson's pop talk on Wednesday in Paris.

Consequently, an open question: how does nature know how to efficiently fold proteins? Is it that our theoretical models are wrong (so that the problem is not really NP-hard)? Or is it that there is additional structure that gives it structure that makes it amenable? Either way, the answer would be interesting.

In Avi's world "interesting" is a word loaded with meaning. He does not employ it to mean a polite lack of dissent, but to mean that something like "revealing a deeper truth".

## Wednesday, March 23, 2011

### Philippe Flajolet

Claude Puech was my PhD advisor, and his own PhD advisor was Philippe Flajolet, so I am a proud to count myself as an academic grandchild of Philippe. In 2007, he gave a great invited talk at the SODA conference in New Orleans, with his usual charisma, enthusiasm and clarity, and we had a "French-speaking lunch" in the New Orleans French quarter, together with a small group of other francophone attendees. Our research tastes are somewhat different, but I have always looked up to him with great admiration.

Today I hear some sad news. http://en.wikipedia.org/wiki/Philippe_Flajolet

## Monday, March 21, 2011

### Trust and Authorities

Rather than hearing only a few voices from traditional media, I much prefer the cacophony of internet articles, news and reports about the Fukushima nuclear power plant accident, yet the array of more or less informed opinions is bewildering. It would be nice to have a quick way to recognize authorities on an emerging topic. Here is what I have noticed. Some media:

- are not up to date and keep reports that are more than 24 hours behind
- do not date the events they report ("This morning" quickly gets old as a way to date events!)
- do not give quantitative information, confuse legal limit with safe limit, confuse or perhaps intentionally try to confuse short-term risk with long-term risk, confuse individual risk with a population's risk (if an individual now had an additional 3% risk of dying from cancer, that might be acceptable for some individuals under some circumstances; if the Tokyo agglomeration was going to have an excess 1 million deaths from cancer, that would be a major, major public health issue.)
- confuse units (micro versys milli), confuse reactors, confuse reactors with plants, confuse core with spent-fuel pools, confuse containment vessel with outer shell, confuse kilometers with miles, etc.
- do not specify where measurements were taken ("at the plant": 1 km from reactor, at reactor, inside reactor? That's different by orders of magnitude.)
- focus on the future at the expense of description of the present
- when asked to make a prediction, only give a best case description, or only give a worst-case description
- do not put their quantitative information in context. What is safe? How safe is safe?

I found that interviews of scientists and experts do not actually yield a more level-headed assessment. The main effect seems to be to give more confidence to whatever assessment the newspaper is aiming for, but the resulting article is more biased than it would otherwise be. Just because scientists are able to avoid basic mistakes does not mean that they do not emphasize only the information that goes the way they want it to go! On the contrary, I am afraid that they come off looking not very good. One can definitely not consider them to be trustworthy authorities.

I found that the wikipedia website on the nuclear accident was one of the best sources of information. Sometimes a useful information appeared and later disappeared, but not often. That's a little bit mysterious: how can something as loosely controled as wikipedia give such reliable information?

## Tuesday, March 15, 2011

### UPDATED- “The past was erased, the erasure was forgotten, the lie became truth.” - Trust the experts!

UPDATE- Apparently Dr. Josef Oehmen, an MIT specialist in risk management, is the author of the essay “Why I’m not worried about Japan’s nuclear reactors”. It was an email that he sent to his family in Japan and that went viral.

That changes a lot of things. A private message to try to reassure one's family is very different from a report posted for the general public. Even though the writer is being reassuring, he could be having reservations that he preferred not to voice: "The large amount of cooling water that has been used is sufficient to take up that heat [in petto: at least, I hope so]. ... Boric acid is "liquid control rod". Whatever decay is still going on, the Boron will capture the neutrons [in petto: I hope so!] "...

Isn't it ironical that I have to correct a post in which I complained about other people's updates to their own posts!

-------------------------- Original post ----------------------------

On the day before yesterday, in a comment, Neal linked to a detailed guest post there
from a nuclear expert presenting the technology behind the design of the Fukushima muclear power plant and explaining that there is no reason to worry.

Today the post has been moved to an MIT nuclear physics website (were the original contributors from there? I did not pay attention), but it's been vastly edited. Now it is purely factual, the claim that the containment vessels are impossible to damage has disappeared, and the confident assessment of an evolution where everything is under control has totally disappeared. The rewriting of history has started!

Suddenly I am sorely missing our old-fashioned paper media. The shameless removal of erroneous expert predictions that I am witnessing here is reminiscent of 1984. The proper thing to do would have been to leave in place the piece that was already there, while adding an update. Perhaps, cross out some sentences so that the reader can see what statements made on day x are rescinded in day x+2. How else can we make accountable the scientists who inform public opinion and who serve as advisors for political decisions? How else can we restore the credibility of scientists among the general public?

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

Meanwhile the journalists reports of radioactive measurements are showing some confusion between microsieverts and millisierverts. Not in any intentional way, I think. I do not see a pattern of deception but genuine mistakes.

## Monday, March 14, 2011

### More on rare events

AP Paris -- "“Europe has to wake up from its Sleeping Beauty slumber” about nuclear safety, Austria’s Environment Minister Nikolaus Berlakovich told reporters in Brussels. He suggested an EU-wide stress test for nuclear plants, much like European banks have been tested for their ability to cope with financial shocks. Yet some experts and officials say those fears are overblown, given the exceptional nature of Japan’s earthquake and ensuing tsunami. The Japanese blasts may slow the push for more nuclear plants, but appear unlikely to stop it, given the world’s fast-growing energy needs."

"exceptional" = roughly one-in-twenty-five odds, in the present case, according to historical records of natural disasters in Japan.
How many once-a-millenium events are dismissed in various countries when designing nuclear power plants, because of their "exceptional" nature?

What Yuval Peres was telling me today: that people cannot distinguish between odds of one-in-one-hundred and of one-in-one-million. That's why there is every reason to be worried about current safety measures everywhere. The last sentence of the AP article reminds me of a XIVth century French proverb: "Il n'est pire sourd que celui qui ne veut pas entendre" [No one is deaf like the one who does not want to hear].

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

When I go into the mountains with my son, sometimes we go to exposed locations. At this point he is more nimble than me and I cannot protect him physically; but I always remind him: "Here, you must not fall. Don't go there if you're not sure you'll make it. Don't go, even if you think that the odds are 9 in 10 that you'll be fine. Even 99 out of 100 is not good enough, since that would mean that you would fall after we've gone mountaineering for a hundred times or so. In this instance (say, walking on top of a cliff with a tremendous drop all but guaranteeing death in case of a fall, for example), I don't want you to fall, not even once." --- of course the safer option would be not to go mountaineering at all, but life would be pretty dull if we could not do the things that bring us the most joy; so there's some amount of risk that we're willing to take. I know that there is a risk, I hope that it is minuscule, and I trust that my son knows how to gauge it. Mountain guides: that's one profession where they have to know how to assess risk if they want to grow old.

Meanwhile, a few proponents of nuclear energy are admiringly drawing attention to the 50 Japanese plants that did not cause any trouble in spite of the earthquake and tsunami. That argument does not inspire trust but misgivings, raising doubts about the competence of those "experts" in risk assessment. Maybe nuclear power companies should recruit mountain guides for consulting!

## Sunday, March 13, 2011

### Assessing the risk of rare events

Some time ago I had a discussion with, I think, a probabilist (maybe it was Yuval Peres), who advanced the opinion that humans are really bad at understanding the odds of rare events. Even probabilists don't really understand rare events, he said.

I saw a report of an interview of a Japanese professor saying that Friday's events were "literally" a "once a millenium" event: in 869 there was an earthquake of this scale, with a tsunami that went 3 miles inland. At first, once a millenium sounds pretty low... until you realize that, for a plant with a lifetime of 40 years, it's an unacceptable 1-in-25 odds!

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

Coincidentally, on Thursday evening I happened to be chatting with a mathematician friend about the Japanese's amazing ability for reconstruction from scratch; the specific topic of our conversation was their rise as international mathematicians in every major area of mathematics since WW2.

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

At Notre-Dame de Paris cathedral, there was a Mass for the people of Japan. Standing room only. Many Japanese, including the ambassador of Japan in France. As it happened, the day's first reading was on Adam and Eve's banishment from Eden, so the archbishop talked about the meaning of death; but I found it academic more than sympathetic. Anecdotically, in the procession at the end, I saw Sarkozy walk right by me, just a couple of yards away!
Here is what some Christians have been using to pray this weekend:
The waves of death rose about me;
the torrents of destruction assailed me;
the snares of the grave surrounded me;
the traps of death confronted me.
The earth reeled and rocked;
The mountains were shaken to their base.
The bed of the ocean was revealed;
The foundations of the world were laid bare.
From on high he reached me and seized me;
He drew me forth from the mighty waters.
From Psalm 18
Psalms are amazing. Thousands of years old, yet there's always one appropriate for every circumstance!

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

SODA will be in Japan in 2012.

## Friday, March 11, 2011

### The Arora-Barak-Steurer paper on unique games

I am finally slogging through the Arora-Barak-Steurer paper on a subexponential algorithm for unique games, almost a year after it first came out. I have written a summary of the algorithm and the lemmas that state the structural properties achieved at each step of the algorithm (no proofs). It's not that hard, after all. Teaching it, I think, would require a few lectures:
- one lecture to present the problem, the conjecture, and put it in context (why people care).
- one lecture on expanders (for the preprocessing step)
- one or two lectures on spectral graph methods, proving Cheeger's inequality
- two lectures to present the algorithm and analysis in the Arora-Barak-Steurer paper, including the proof of the variant of Cheeger's inequality.

## Wednesday, March 9, 2011

### Gaps in my knowledge

If I was starting over with my education... here are some courses I wish I had had when I was a student:

- Probability and random walks, "a la" Yuval Peres
- Spectral graph theory.

## Friday, March 4, 2011

### Dagstuhl Thursday night

On Thursday night, in the cheese room, we had an informal discussion on the future of scheduling. A list of open-ended questions had been prepared, several people had been told in advance to think about it, and I moderated the discussion in the same way as I do in the classroom when I teach. Much of the discussion was about the relation between theory and applications. Some directions that were proposed: robust scheduling, stochastic scheduling, scheduling a sequence of similar instances, behavioral scheduling, inapproximability, etc. Many other things were brought up. Miraculously, someone - Alexander Souza - came to me afterwards and, without being prompted, volunteered to write up a report of the discussion! He instantaneously became my hero of the day.

Talking about applications of theoretical work, several people said they had heard that Niv Buchbinder had designed some algorithm that had had practical impact while he was a postdoc at MSR; but Niv adamantly refused to acknowledge the possibility that he might have done something actually useful. He's funny! It's a measure of how informal the atmosphere was that people, instead of trying to show how important their work was, may have downplayed its importance.

The last question was: what drives you to work on scheduling problems? Baruch Schieber talked eloquently about the gratification that comes from doing work that is useful for others. David Johnson mentioned the pleasure of working on problems that one can explain to Beotians. Fritz mentioned the value of our results, as measured by society's feedback. Kirk, down to earth as always, said that it's good to work on topics for which you can get funding. I brought up the importance of beauty, but Neal Young said, essentially, that beauty is in the eye of the beholder.

But doesn't our work have intrinsic value? If I found a solution to, say, the k-server problem, it would make me very happy and I would think that the solution has value even if no one else cared or knew about it.

## Thursday, March 3, 2011

### Dagstuhl Thursday fatigue

With tutorials to ponder, open problems to think about, and a paper to work on while my coauthor and myself are in the same place, my interest in talks has waned, and most of it is going above my head while I am taking stock of what I learned during the first three days of the workshop. I have therefore changed my seat, farther from the board and closer to the window where I can bask in the sun and enjoy the view.

Something during this morning's tutorial caught my attention, though.
- Baruch Schieber: "This notion that you use in your proof, I call it the red point's shedow."
- Magnus Haldorsson (the speaker), puzzled: "Shedow? Is that yiddish?"
- Person in audience: "No: when you hear him say "shedow", he really means "shadow"."
I am so glad that someone else has an unapologetically strong accent in spite of having lived in the US for many years! I am grateful for the tolerance of Americans for us immigrants with our imperfect English. They realize that the simplified English that we use in our international interactions is the modern Esperanto.

I also listened to Seffi Naor's tone during his talk. His voice goes up and down gently like ripples lapping the sea shore at night after the wind has died down. It is a pleasant, soothing sound. The content is surely very interesting (the title contains the exciting terms "small set expansion"!), but I am out of energy, and the long introduction listing previous work tried out my patience and quickly wore it out.

Obviously, other people are more resilient than me: they are still participating actively, asking questions during the talks. I don't know how they manage it!

## Wednesday, March 2, 2011

### Dagstuhl, Wednesday afternoon

The traditional Wednesday afternoon hike took us to a chapel where one could view Dagstuhl from a distance. During the hike Daniel Marx gave me a lightning-speed overview of techniques for FPT algorithms - one example for each algorithmic technique. Now, whenever I see an FPT algorithm, I will remember the sun-filled scenery of green hills, quiet ponds and small streams! David Johnson thinks that, rather than studying this or that more or less artificial theoretical model, our research time would be better spent trying to understand why integer programming works so well. He's had good experiences with it recently. I liked the idea. Neal Young criticized my wish to go back to the Plotkin-Shmoys-Tardos paper and try to understand it: now that I have heard his tutorial, I no longer need to read that paper, he says! (Except for examples of applications). Etc. This is why hiking is such a good thing to do during workshops. The blood flow stimulates the brain, conversation flows easily, and, in a natural environment, informal discussions on topics related to research happen in an organic manner.

The traditional stop of Dagstuhl hikers at a restaurant for coffee and cakes no longer exists. The reception tried to make a reservation for us, but got turned down. Rumor has it that, once, an order of seventy cakes was placed for one group, but nobody showed up at the restaurant. Since then, as the story goes, neighborhood restaurants refuse to take reservations for Dagstuhl people.

I also broke with tradition at meal time: I arrived early, found that Kirk Pruhs and I were going to be seated at the same table for at least the fourth time in a row, and quietly exchanged his name tag with one on the next table. When Kirk arrived, a few minutes later, he took a look at me, at the name tags, and commented: "Not today, eh?"

I have made one convert to tablets: Samir Khuller. He started using his yesterday to take notes during talks (had had it for a while but had never used the tablet features!). Today he asked me how to share a document with other people on the internet, so that we could all edit it at the same time. That would obviously be extremely useful for long-distance collaborations. One would think that that has to exist - the technology is there, there is no reason why that shouldn't be possible. But I don't know.

### Dagstuhl, Tuesday afternoon and Wed morning

The afternoon talks were somewhat less well attended, because the weather is so beautiful that some people just can't resist the sun and stay outside beyond the specified time.

Baruch Schieber talked some more about busy time problems. He spent some time on motivation. It's about having the minimum number of computers turned on, so, like in Kirk Pruhs' talk, it's also about minimizing power usage. It would have been nice if his talk had been before Samir's talk!

Lisa Fleischer talked about flows over time. I have heard talks about this several times, but this was the first time that I understood the problem definition before the talk was over. There's a picture of a pitcher pouring some red or blue stuff into the network. Actually, the rate at which it is pouring matches the maximum "capacity" of the edge on which things start. Also, I always think of "capacity" as a static quantity, but in this setting it's actually a rate- say, the maximum rate at which a highway can route cars without getting jammed. And time, as well as the stuff being routed, are all continuous quantities. Capacity reduction can help increase the flow. I keep thinking of those lights that regulate the rate at which cars can enter the acceleration ramp on highways at rush hours in the US. Those lights don't exist in France. I think that the French, being rational people, would not believe that you can get better overall flow by reducing input, and would therefore ignore such traffic lights. But in the US people are law-abiding enough that they stop at red lights even if it seems unreasonable.

Leah Epstein talked about online clustering problems in one dimension.

Asaf Levin talked about an asymptotic fully polynomial PTAS for bin packing with various bin sizes and costs. The techniques were a bunch of rounding/shifting/DP stuff, but the result was surprisingly strong!

In the evening we had an open problem session in the cheese room. I can't say that there was one problem that really captured my fancy, but they varied from puzzle-like to broad and ambitious questions. Then there was mafia, bridge, beer, wine, poker, and even one of the open problems was solved along the way! By a PhD student, of course: only they have the stamina to continue working at the close of the day. I noticed several people were wearing slippers.

Wednesday morning Neal Young gave a black board tutorial on Lagrangian relaxation and presented one algorithm applied to several different settings. Now it seems that I might finally be able to go back and read the Plotkin-Shmoys-Tardos paper, and it might even be easy. We'll see. Then Grigoriadis talked about non-linear approximation.

### Dagstuhl, Tuesday morning

Ola Svensson gave two talks about hardness of approximation for job shop and (unique games dependent) hardness of precedence-constrained scheduling on parallel machines. The reductions were simple and we had a black-board talk, so that we were able to follow (almost) everything. What a great pleasure! I love slow talks. Otherwise I cannot listen to 5 hours of talks a day. I showed off how to use a tablet - borrowing someone else's tablet and writing notes for the talk, that will be uploaded to the Dagstuhl website shortly, so that everyone can use them as if they were the slides for the talk.

Niv Buchbinder gave a linear-programming approach to the secretary problem and variants. Let pi be the probability that the ith arrival is hired, qi be the probability that he is hired given that he is the best of all, fi be the probability that he is hired given that he is best aong the first i. Since the problem is online, qi=fi. We can write a few constraints that must be satisfied, then a feasible solution suggests an algorithm, and exhibiting a matching dual feasible solution proves optimality. Simple and classic LP approach to online problems, that nicely unifies several s of the secretary problem. Elegant. Open: take that approach for the knapsack variant.

Before talking about the underlying LP, Niv started by showing an algorithm, then had to fight a rebellion from the room: he wanted to move on to the analysis, but instead was attacked by rapid-fire questions, all of which he answered with: "Wait, it'll come in a couple of slides!" - a good teaser talk. Fun!