TheKro’s Nest

The last week of August I was in London for two workshops. The first workshop was the “small conference” type of workshop – the International Workshop on Combinatorial Algorithms (IWOCA). The second was the “break-away groups and problem-solving” type of workshop – StringMasters. Both workshops were held at King’s College in London, with the first running all the proceedings in the Strand Campus Great Hall.

In this hall, they did the registration, put up the posters, had tea and coffee breaks, and also did the presentations of the various papers. Fortunately, we did get out of the building for lunch, which was held at a place called Smolensky’s. The menu was handled cleverly, in that everyone ordered in the morning tea break, thus saving time at the restaurant. The downside was that the waiters hadn’t taken our orders, so they spent lunch wondering between tables shouting “one beef burger”, etc.

The conference organization was, in my opinion, very good, with everything we needed being dished out on arrival. The conference dinner was held on a boat which cruised up and down the Thames, which is a great way to combine sightseeing with a conference when you’re just popping in! At the dinner, which we ate sat in somewhat cramped quarters (we were on a boat, after all), I ended up having a discussion on aspects of apartheid, mistreatment of aborigines, and the caste system, with a woman from Australia and two Indians (one of whom emigrated to USA many years ago).

This was the first conference I’ve been at where I’ve attended all of the talks. Some of the talks I found interesting was work by Karim Douïeb on a data structure called a skip lift (I worked further with Karim at StringMasters), work by Colin Cooper on chains-into-bin processes, and Mohammad Zubair’s presentation on I/O bounds using pebbling strategies.
Alan Frieze’s invited talk on refinements of the Karp-Sipser matching algorithm interested me because it was a new area employing concentration arguments I was not aware of, and Gregory Kucherov’s invited talk was fascinating, since I had previously had no idea how BLAST performs its searches.

In terms of criticism, I think the chairs used were very uncomfortable for tall people: the top of the chairback digs in below the ribcage, which is quite unpleasant if you are supposed to spend most of 3 days sitting on the chairs. The other thing I found (once again) quite mysterious is why we academics continuously surround ourselves with all the ritualism of presenting papers, which just wastes everybody’s time:

1. Session chair introduces the speaker and topic – despite it being on the program, and presumably already projected up on the screen
2. Speaker comes up and again tells us who he is and what the topic will be
3. Speaker notes it’s joint work with X and Y. Again, this is on the program, and usually projected on the screen.
4. Speaker gives a talk overview, telling us he will “present background”, and that he “will conclude”
5. Speaker gives talk
6. Speaker ends talk with something like “unless there are any questions”
7. Session chair pops up asking people to thank the speaker.
8. People clap politely
9. Chair in turn asks if there are any questions
10. Some questions are asked and answered (possibly zero)
11. Chair asks people to thank the speaker again
12. People clap politely

As fairly educated people, we should be able to navigate some of these things safely as a group. How about, for example:

1. When it’s the speaker’s turn to speak, he loads his powerpoint slides and gives everyone a moment to see the title page.
2. Speaker gives overview of the main portion of his talk.
3. Speaker gives talk
4. Speaker ends talk with something like “unless there are any questions”
5. Some questions are asked and answered (possibly zero)
6. People clap politely
7. Session chair only intervenes in case of (a) technical problems, (b) speaker/questions going over time, (c) large groups clamouring to ask questions, and (d) severe medical emergencies.

StringMasters was quite different: in the (late) morning, we all had coffee in Costas’ office (Jackie – I’m siding with Costas on the apostrophe today, I’m afraid) before breaking away into groups to tackle problems brought by various of the attendees. Most of the StringMasters attendees were at IWOCA, but some others arrived just for StringMasters, including another South African, Bruce Watson. I believe Bruce and I were the only Africans at IWOCA or StringMasters this year. After a bit of working on problems, we were interrupted for a great lunch somewhere close to the college. Although the food was excellent, and I know that conference/workshop meals are important networking events, I found them a bit long – I felt we could have achieved more with a slightly earlier start and shorter meals.

Speaking of achieving something: what did I do at StringMasters? One of the people presenting problems at StringMasters was Zsuzsanna Lipták, who I’d met on the IWOCA 2010 conference dinner boat. She’d worked in South Africa before (at SANBI, as well as at Wits – collaborating with Scott Hazelhurst), and had a string problem with bio-informatics applications. I joined a break-away group to work on the problem, along with Karim Douïeb, amongst others. The problem is basically trying to find an order-complexity improvement on an existing (obvious) quadratic-time algorithm. We have managed two improvements: one reparametrizes the order complexity into something usually better, but still worst-case quadratic, while the other (due primarily to Karim) yields a slightly sub-quadratic algorithm (only a logarithmic factor improvement, unfortunately) using (min,+)-convolution (which I’ve got to read more on).