The prisoners dilemma

A few weeks ago Taso (new fancy homepage), Tony and I organised the Sydney Theory Day. Among the invited speakers were Peter Bro Miltersen who gave a talk on "Names in boxes". The abstract of the talk can be found here. The short version is:

"The names of one hundred prisoners are placed in one hundred wooden boxes, one name to each box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room; they may look into up to fifty of the boxes to try to find their own name but must leave the room exactly as it was. They are permitted no further communication after leaving the room. The prisoners have a chance to plot a strategy in advance and they are going to need it, because unless they all find their own names they will all be executed. There is a strategy that has a probability of success exceeding thirty percent - find it"

If each prisoner examines a random set of 50 boxes, their probability of survival is close to zero. It turns out that there is a very simple schedule that gives the prisoners a 30% chance of surviving. It sounds almost impossible but there's a simple proof that anyone can understand in "7 Puzzles You Think You Must Not Have Heard Correctly" by Peter Winkler.

This semester I've been teaching computational geometry at USyd and I find it hard to get them to properly understand the beauty of expected running times. However, this year I started the lecture by discussing the "Prisoners dilemma" for 20 minutes before I talked about the expected running time of low dimensional LP. And I really believe it had a positive effect. The students seemed to appreciate the simplicity of the arguments a bit more than usual.

Now the challenge is to find a puzzle like this for each lecture. Any tips?

ESA accepted papers

I'm about two weeks late, but better late than never.

The list of accepted papers at ESA is out. I was in the PC for the applied track where we got 53 submissions out of which 16 were accepted. As a whole the papers were of high quality and even though I was pretty tired of reviewing papers I enjoyed reading many of them (well at least a few).

In the theory track there were a some papers that look interesting, for example: "Fitting a step function to a point set" by Fournier and Vigneron, "An optimal dynamic spanner for doubling metric spaces" by Gottlieb and Roditty (finally an optimal algorithm!) and "Deterministic Sampling Algorithms" by van Zuylen.

Our group also got a paper accepted, "Detecting Regular Visit Patterns" by Bojan Djordjevic, Anh Pham, Thomas Wolle and me. I quite like this paper. As the title suggests the original motivation comes from detecting regular visit patterns. However, the problem boils down to a nice little problem on bitstrings.

Given a bitstring S and a constant 0 < c < 1 find the longest substring of S containing at least a fraction c of 1's. We give a linear time algorithm and then we apply it to our original problem.

ISAAC deadline approaching

Call for Papers

The 19th International Symposium on Algorithms and Computation
(ISAAC 2008) December 15 - 17, 2008, Gold Coast, Australia
http://www-or.amp.i.kyoto-u.ac.jp/isaac08/

The 19th International Symposium on Algorithms and Computation (ISAAC 2008) will be held in Gold Coast, Australia, December 15-17, 2008. The symposium is intended to provide a forum for researchers working in algorithms and theory of computation. Papers presenting original research in the areas of algorithms and theory of computation are sought. Papers in relevant applied areas are also welcome.


Topics

The topics include, but are not limited to:
- Algorithms and data structures
- Approximation algorithms
- Combinatorial optimization
- Computational biology
- Computational complexity
- Computational geometry
- Cryptography
- Experimental algorithms
- Graph drawing
- Graph algorithms
- Internet algorithms
- Online algorithms
- Parallel and distributed algorithms
- Quantum computing
- Randomized algorithms


Important Dates

Submission deadline: June 25, 2008 (12pm, US Pacific Time)
Notification of acceptance: August 18, 2008
Camera-ready submission: September 15, 2008


Invited Speakers

Prof. Tetsuo Asano (JAIST, Japan)
Prof. Peter Eades (University of Sydney, Australia)
Prof. Robert Tarjan (Princeton University, HP, USA)


Paper Submission

The submission should contain a scholarly exposition of ideas, techniques, and results, including motivation and a clear comparison with related work. The length of the submission should not exceed twelve pages in LNCS style.
If the authors feel that more details are essential to substantiate the main claim of the paper, they may include a clearly marked appendix that will be read at the discretion of the program committee.
Only electronic submission (pdf) will be allowed.
Submitted papers must describe work not previously published.
They must not be submitted simultaneously to another conference with refereed proceedings or a journal. At least one of the authors of accepted papers is expected to present their work at the conference.


Publication

The symposium proceedings will be published by Springer-Verlag in Lecture Notes in Computer Science (LNCS) series. Selected papers will be invited to special issues of Algorithmica and International Journal on Computational Geometry and Applications.


Awards

The Best Paper and the Best Student Paper will be awarded.
The Best Student Paper Award will be given to the best paper written solely by one or more students. A paper is eligible if all authors are full-time students at the time of submission.
To indicate that a submission is eligible, please add the phrase "Eligible for best student paper" as the last sentence in the "Abstract" field in the web form on the submission server as well as in the paper. The program committee may decline to make the award, or may split it among several papers.

Sydney weather

Rain, more rain and then some more rain these days in sydney.
Here are some interesting "facts" about sydney weather:

1. Sydney has almost the same number of wet days per year as London UK
   (152 wet days for sydney, 153 for london. a wet day has 0.25mm rain or more)
   
   
2. Sydney is the "wettest" city i have ever lived in
   (i have lived in athens-greece, princeton-NJ, toronto and sydney)
   
   
3. Sydney has only 100 sunny days per year. Las vegas has over 200.
   (ok my stats for sydney and las vegas are from different sources using different definitions for sunny-ness: sunny day for sydney has average cloud cover less than 25%, for las vegas it is up to 1/3 cloud cover.)
   
   
4. In april 2008 we had 12 continuous days of rain in sydney. plus some more (non-continuous) days of rain. feb-march were just as bad.

maybe sydney weather has somewhat better reputation than what it really deserves. at least my impression of sydney weather was far better, before moving to sydney.

For me the definition of good weather is simple: sun. Temperature is not very important, as long as you have sun. Having lots of sun implies that you cannot have terribly wet weather, you cannot have tropical weather etc.

The definition and most statistics for wets days comes from BBC.co.uk/weather website. For example here are some links, for the averages for sydney and here for toronto. Or you can look up other cities starting here. The source for the number of sunny days in sydney is the Australian Bureau of Meteorology.

The following is a list of cites and their average number of wet days per year:

• phoenix arizona: 39 (source)
• athens greece: 103 (source)
• NYC: 125 (source)
• ottawa: 139 (source)
• toronto: 145 (source)
• sydney: 152 (source)
• london UK: 153 (source)
• stockholm: 164 (source)

And a list of some nice, sunny, good-weather places in the US:

sunniest US cities (source):

City	% Sunshine	Clear Days
Phoenix, Arizona	85	211
Las Vegas, Nevada	85	210
Tucson, Arizona	85	193
El Paso, Texas	84	193
Fresno, California	79	194
Sacramento, California	78	188
Albuquerque, New Mexico	76	186
Los Angeles, California	73	167
Denver, Colorado	69	115
San Diego, California	68	146
Oklahoma City, Oklahoma	68	139
San Francisco, California	66	160

[% sunshine is the percentage of time between sunrise and sunset that sun reaches the earth's surface. Clear days is the number days a year when clouds cover less than one-third of the sky on average.]