Talk given at the GoCAS workshop Existential Risk to Humanity, Gothenburg, 7 Sep 2017.
Talk given at the GoCAS workshop Existential Risk to Humanity, Gothenburg, 7 Sep 2017.
I spent a splendid week at Schloss Dagstuhl for Dagstuhl Seminar 14451: Optimality and tight results in parameterized complexity. As usual, this was intellectually extremely stimulating and very exhausting.
My head is full of tempting research ideas that I immediately need to pursue. Instead, I finalised a small cryptic crossword about parameterized complexity. If you are in the tiny demographic targeted by this puzzle, enjoy!
7 Freethinker Nelson hides a smaller problem. (6)
8 Mr No is crazy for graphs like K5 and K3,3. (6)
9 Remote application for algorithm rejected initially. (4)
10 Uppermost parts of perennial Unix command for displaying acyclic graph in PostScript? (8)
11 Peer pressured? (8)
13 Gadget for viewing booty in the mirror. (4)
14 Leaders of Japanese universities lament yearly when ICALP is. (4)
15 The German left room before Erik Demaine briefly blushed. (8)
16 Holger Dell, perhaps, to date teen in disguise. (8)
19 At the start of reduction, apply a trick. (4)
20 Rod is covered in soft hair, reportedly. (6)
21 Importance of mean and variance, for instance. (6)
1 Important concept in exponential time complexity is belittling to slave. (4-9)
2 A connected, bridgeless cubic graph with chromatic index equal to 4 expresses “I love you” in a sharply critical fashion. (8)
3 Leaf lattice contains a set whose closure equals itself. (4)
4 Aunt had intercourse, as represented on a surface. (8)
5 Sounds like you mend one. (4)
6 Unix filesystem in important kernelization. (13)
12 Ask wordy drunk when Dagstuhl seminars take place. (8)
13 Robertson and Seymour’s results maybe confused me and others. (8)
17 Blow nose for very long running times. (4)
18 At first, Eppstein liked minimum spanning trees. (4)
Many computer science fields in France are organised in national, cross-institutional groupes de recherches, not completely unlike the ACM SIGs in the US. The TCS group (“Mathematical Informatics”) encompasses some 400-500 people, as far as I understand.
As in most of Europe, theoretical computer science in France includes many more fields more than US-style theory of computation. Amazingly, they meet once a year for two days, and give well-attended talks to each other. The 2012 meeting had 170 registrants, an impressive number.
This struck me as particularly noteworthy after just attending SODA, where the various subfields of algorithms become increasingly fragmented and estranged, to the point of hostility and mutual incomprehensibility.
At the Paris meeting, a steering committee selects a number speakers from the various working groups in the GDR IM, who give meaty, 45-minutes talks to a general TCS audience: Computational logic, computational geometry, distributed systems, process calculi, extremal graphs, ….
In addition, the meeting includes two 1-hour invited talks recruited outside of the French GdR. Ashwin Nayak talked about communication complexity, and I used to opportunity to present an overview of zeta transform algorithms and applications, culminating in our SODA 2012 result from last week. [slides]
Thanks to everybody who attended, and to the nice organisers for putting me into a disarmingly charming hotel in the middle of the Latin quarter, where you couldn’t swing a dead Marsipulami without hitting a comic store. I had a splendid time.
Based on my quick perusal of list of accepted papers [PDF], here’s a list of papers related to exponential time computation, together with references to online version — I’m probably missing some. Updates are welcome.
An amazing number of kernelisation (and, I presume non-kernelisation) papers. And lots and lots of exciting papers in many other fields as well.
Usually I’m not a big fan of conference merchandise—university branded ball point pens, T-shirts, bags, notepads… But boy, did I change my mind after ICALP 2010!
I saw little reason to unpack the coffee mug we got at the registration desk, and stuffed it in the conference bag. As did everybody else, I think. Only when I came home did I realise that the cup rattled. Was it broken? Intrigued, I opened the box, only to find a piece of chalk! The mug was a blackboard! We could have spent every coffee break eagerly scribbling proofs on our mugs.
The Presburger Award was awarded for the first time in at the Bordeaux ICALP. The award goes to a young scientist, and the 2010 recipient is Mikolaj Bojanczyk from Warsaw for his work in automata theory, logic, and algebra.
The EATCS awards session at ICALP included this award and two more: The Gödel prize and the EATCS award. Each recipient gave a talk, and young Mikolaj faced the thankless task of appearing in a session with some of the best speakers in our field, Sanjeev Arora, Joe Mitchell, and Kurt Mehlhorn, who all gave splendid presentations.
Well, Mikolaj’s speech blew me away. Instead of explaining his research contributions, he devoted the talk to the life and work of fellow Varsovian Mojzesz Presburger (1904–1943).
Not only was this graceful, interesting, and moving, it was also extremely well presented. I say this as somebody who obsesses about presentations.
Mikolaj’s visual aids break the slides metaphor we are used to, no matter which medium—35 mm, overhead transparency, computer projector. You can see Mikolaj’s Presburger Award presentation at his website. Check out his other ICALP 2010 presentation as well: his “slides” pan and zoom about on a single, huge, dynamic canvas. I’ve tried to do something similar a few times, but this is better by orders of magnitude.
I’m at ICALP 2010 in sunny Bordeaux. I have been very busy working on two papers with colleagues who happen to attend ICALP as well, so I have missed a bunch of interesting talks on the first two days already.
I did, however, attend the business meeting, an event that combines various reports from ICALP committees with the general assembly of EATCS, the “European SIGACT.”
I normally enjoy business meetings, but ICALP business meetings are relatively stiff and mind-numbingly boring, with no discussion and no free beers. Still, let me give an incomplete and skewed summary of some of the issues that were mentioned.
EATCS views ICALP as its flagship conference, and ICALP has published with Springer’s LNCS proceedings series for many years – if DBLP is to be trusted, the proceedings from the 4th ICALP (Turku, Finland, 1977) appear as LNCS volume 52. Since a few years ago, Springer has started an LNCS subline called ARCoSS (Springer page about ARCoSS) “in cooperation with” EATCS and ETAPS. These have a nicer cover.
However, it has been unclear in which sense this publication model coincides with the current preferences of the members of EATCS. Just to mention an alternative, the STACS conference now publishes with the LIPIcs series, which is Open Access in the sense that they are available on line and free of charge.
Very commendably, and to my pleasant surprise, EATCS actually implemented a member poll in the Spring of 2010 to determine our opinions on open source publication models, and in particular the outlet for ICALP’s proceedings. The results are online ([poll results at EACTS website]), but for mysterious reasons only accessible to EATCS members. It’s fair to say that there is a large majority of members that would prefer another publication model. For example, only 10% want EATCS to “Publish the proceedings of ICALP as before in a traditional print publication?” To the question “What is the publication model for scientific papers in theoretical computer science that you would prefer to see gain prominence in the near future?”, 83% respond “Open access publication as for LMCS, LIPIcs and EPTCS”
EATCS chairman Burkhard Monien reported that the EATCS Council has now approached Springer about the ICALP proceedings. According to him, Springer has made substantially better offer “very close to open access. We have discussed this carefully in the council.”
I think this is good news. However, I am less than impressed about the speed with which the process will continue. According to Monien, the result of the May 2010 poll were not sufficiently conclusive, so “We’ll ask your opinion again.” This time, there will be mercilessly concrete choices about either (1) going with LIPIcs, or (2) staying with Springer, under specific (and, I assume, new) terms. Monien explained the EATCS council wants to get this right, ICALP is a big steamer, should not go in zig-zag course, and stick to its decisions. He was unsure if the next poll will be implemented in the Fall, but promised “beginning of next year, at the latest.” I’m not holding my breath.
Still, all in all I think this is splendid news, and I’m particularly happy to the the EATCS council involving its members in an important decision process.
ICALP 2010 Organization
The report from the ICALP 2010 organizers was the usual list of statistics. I have become increasingly interested in these details after arranging ALGO 2009 myself. In total, ICALP 2010 has 292 participants, including 55 locals (the latter strikes me as a high number). 200 of these are registrants for ICALP itself, rather than one of the affiliated workshops, 147 pay the full registration fee. Only 3 Swedes and 1 Dane are registered, I wonder which I am.
This ICALP is held in the conference facilities of a large, soul-less hotel in down-town Bordeaux. I’m not a big fan of this kind of conference, and the contrast in atmosphere to the locally organised SWAT I attended in June is enormous. There’s a small lobby to hang out in, with few chairs or tables (let alone blackboards), interaction between attendees is minimal, except for the cliques one is already in. Furthermore, ICALP provides no lunches, so people scatter into small groups and look for a place to eat. Pretty much like the large US conferences.
Also, the Friday banquet is included only for full participants, meaning that many students will not be able to get the 90 Euro dinner ticket reimbursed, and consequently won’t attend. In my experience, this decision is de rigeur for Southern European ICALPs, but I think it is fundamentally misguided. The food better be spectacular.
On the other hand, the proceedings are included in the registration, which is another mistake. Many people never even remove the shrink wrap anymore, paper proceedings are just ballast. Moreover, proceedings are easy to reimburse, even for those students who honestly prefer to pay for the privilege to read the absurdly formatted 12 page LNCS amputated paper rather than reading the full version on the web.
The budget for the whole event is slightly over 100,000€, and the organizer received 2,500 emails. Apparently, EATCS maintains some for of organizer’s manual for ICALP; I’d like to see that. (I have seen the ESA/ALGO manual.) These things should be on-line, and allow for feed-back.
The reports from ICALPs various programme committees included the usual absurd statistics, which were useless even by the low standards we are used to. The best paper award (Track A) went to Leslie Goldberg and Mark Jerrum’s result about about Approximating the partition function of the ferromagnetic Potts model. This is, of course, utterly splendid work. In total ICALP Track A received 229 submissions (6 were withdrawn) and accepted 60. Denmark submitted 3.33 papers, 1.17 accepted. Sweden submitted 1.83 and accepted 1.17. Again, I wonder which I am.
The programming for ICALP’s Track A has left me, and many others, completely puzzled, and looks as if it’s the result of a grep script based on paper titles. For example, ICALP had two strongly related results about Cuckoo hashing; but the results appeared in different sessions:
Michael Hoffmann presented the ICALP 2011 organisation in Zürich. icalp11.inf.ethz.ch . This seems to be an ICALP model closer to my preferences. The conference will be held in in university facilities, at something called CAB from late 19th century, with several large lecture rooms for workshops or parallel tracks, an even larger lecture hall, WLAN, and plenty of working space.
Also, there is no banquet, but rather a number of receptions with plenty of finger food and drinks. As an added benefit, registration fees are expected to be low. Of course, Zürich is “not among the cheapest places”, and prices are even higher than shown last year, because of the exchange rate between Swiss Franc and Euro, which shows high variance.
I will certainly attend, as I am one of the invited speakers. Apparently, I’m speaking on the 5th.
Artur Czumaj presented the plans for ICALP 2012, which (somewhat unusually) is already fixed two years in advance. The dates are July 9–13 2012 in Warwick, for the centenary of Alan Turing’s birth. Thus, ICALP is one of many events in the UK for the Alan Turing year, see the list of events. ICALP will be held on Warwick’s campus, including accommodation and lunches. Satellite events were said to include Wimbledon right before ICALP and the London Olympic games somewhat later.
Possibly this is the right time to start thinking about what we in the greater Copenhagen area (e.g., Sweden and Denmark, or all of Scandinavia) should be doing for the Turing year. Computer Science has far from the pop-sci clout that biology enjoys, but shouldn’t we be able to drum up at least one hundredth of the attention that Darwin got? Ideas are welcome.
For example SWAT 2012 is in the Turing year. We should start branding all our CS-related activities in 2012 as Turing-related, and hopefully concoct some more.
The SWAT conference dinner involved a boat trip to an island near Bergen, with a spectacular seafood dinner of Halibut and Wolffish. Also, initiated by Fedor Fomin, SWAT reverted back to its tradition of pressuring attendants to sing (partitioned into small groups by nationality or country of residence) after the main course. Again, the organisers managed to get the atmosphere exactly right.
I am attending SWAT in surprisingly sunny Bergen.
The biannual SWAT is the oldest European conference devoted to algorithms. (ICALP is a lot older, and STACS slighly, but both have a wider focus.) It rotates around the Scandinavian countries (with a single exception in 2006) and in 2010 Bergen is, again, the host.
Bergen has a large algorithms group with a bunch of postdocs and graduate students, and this makes a large difference for organising a successful conference. A lot of heart and energy has gone into this, and the atmosphere is absolutely splendid. Even the weather in Bergen seems to, so far, play along.
The Sunday evening reception was on a roof terrace, with live music, wine, and snacks. Several activities were arranged for Monday evening, and I was lucky to be among the handful of people who went sailing on a small sailing boat, late in the evening, under the Northern sun, with a view of beautiful Bergen and the surrounding coastline. Brilliant.
At the business meeting, Magnus Halldorson reported on the steering committee’s thoughts about SWAT. Four changes have been implemented at SWAT 2010:
I think these decisions represent a very welcome re-alignment of how SWAT views itself. The attendees of the business meeting seemed to be happy as well.
PC chair Haim Kaplan gave a short overview of the work of the programme committee. The most interesting point is that SWAT 2010 attracted 78 submissions this year, which is markedly less than for previous SWATs. This year, the SWAT submission deadline was before the notification of SOCG 2010 because of the June time slot, which may account for a decrease of the number of submissions in computational geometry, traditionally a thematic focus of SWAT.
A brief discussion was devoted to publication models for contributed SWAT papers; currently the conference is published in Springer’s LNCS series.
Petteri Kaski successfully invited SWAT 2012 to Helsinki.
This is part 3 in a series of 3 posts on ALGO 2009, largely repeating the organiser’s report from the business meeting. This is the least serious part.
One of the small details that I tried to micro-manage are name tags. For some reason, name tags at many conferences display the attendee’s name in very small letters, and leave most of the tag’s area either white, or taken up by the logo of the conference or venue. (Professional name tag designers typically optimise something else than ease of identification of the attendee. That’s their job, and they are good at it. But it’s not the job I want done.) ALGO had nice, legible name tags, and we also tried to double-check various diacritics.
One the other hand, the batch-driven production from a spreadsheet to the final tag messed up some affiliations, for reasons that remained a mystery. Incidentally, I don’t really understand the value of displaying the affiliation on the tag anyway, they seem to serve mostly as an ice-breaker for conversations. (Maybe we should put people’s hobbies on the tags instead.) From that perspective, a wrong affiliation works at least as well.
Closely related to the layout of the name tag are the mechanics of the badge holder. After obsessing over this for many years I have concluded that the pin–clip combo is the way to go, so that’s what we got. We even told people to not clip the badge to their trousers. It was perfect, nothing could go wrong, everything was prepared for the one conference where you wouldn’t have to squint or use x-ray vision to read the name of whats-his-name-I-think-we-met-at-ICALP-last-year.
Alas, it was not enough. A seemingly unrelated decision destroyed all my careful planning: We decided to hand out multi-ride ticket to the Copenhagen subway system, attached to ITU-branded key bands. (This was to prevent the tickets from being accidentally lost in the pile of written material we handed out to attendees.)
Driven by their desire to remain anonymous, and a perverse predilection for craftsmanship, many enterprising attendees carefully removed the ticket from the key band, and attached their name tag instead, thereby constructing the mothership of all that is evil about name badges: they dangled at belly button height, typically obscured behind tables or under jackets, and they swivelled around their single, ill-constructed joint, displaying the badge’s empty back side more often than the laws of probability theory predict.
Next time I’ll tatoo the name on people’s forehead.
The etiquette about open laptops during talks is very much unclear in the CS community. We politely asked people to avoid accessing the internet during sessions, and if so, to do it from the back row so as to annoy the speaker and the rest of the audience as little as possible. Several attendees told me they were happy about this decision; the auditoriums were certainly relatively free of open laptops. I remain uncertain about how to handle this – I can get a lot of work done while half-way listening to a talk, and the alternative is to stay out of the lecture room…
One thing I decided against, for fear of committing a social mistake, was to send instructions to the speakers about how we would have liked the talks at ALGO. Namely, more accessible.
Talk quality at our conferences is generally high: clear, readable, well-presented, entertaining. However, most of the speakers vastly overestimate the audience’s level of familiarity with the subject. This makes it very difficult to attend a presentation to learn something, in particular about a field in which you aren’t an expert already.
One of the problems is that talks are grouped into thematically related sessions. This seems to imply that everybody in the room is already an expert about “latest derandomisation tricks in quantum I/O kernelisation,” so why bother explaining the basics again? An earlier rumination of Michael Mitzenmacher about the STOC 2009 schedule already touched on the bold idea of mixing sessions at random. (But this may introduce more problems than it solves.)
The smaller events at ALGO, such as WAOA and IWPEC, are technically highly specialised workshops in the first place, pitched at an expert audience. So how do we turn this around? It would be great if ALGO attendees could “stay for IWPEC” to finally find out what “this FTP-stuff” is all about – but the atmosphere has the exact opposite effect. Similarly, I talked to a WAOA attendee who was frustrated about the O-part being largely incomprehensible. (The attendee was there for the A-part.) How do we solve this? Clearly, not every IWPEC talk can define treewidth again, but my ambition with ALGO was to reduce balkanisation, not contribute to it.
Many of the “too difficult” talks are given by students. There are a number of reasons for this – students assume that everybody knows what they do (I did), students need to demonstrate that they’re smart and did a difficult thing, some students lack the broad overview to be able to place their subfield into a broader ensemble, previous talks have been given only at departmental seminars, where everybody else is equally interested in derandomising quantum I/O kernelisation, etc. Maybe for this target audience, a “Here’s what we’d like your talk to be”-letter could have done a lot of good.