Kim's Very Occasional News and Blog

During the month of May, Joan and I visited the Department of Computer Science at the University of Toronto. While there, we both gave talks on recent work on online algorithms with predictions, dealing with scheduling and paging, to be presented at WADS and ICML this summer. We worked with Faith Ellen and Allan Borodin. In addition, Shahin Kamali came in from York University and Denis Pankratov came in from Concordia University to collaborate on new projects.

I am very excited to be the main supervisor of Ph.D. student Magnus Berg. He comes with an MS in mathematics and a side topic in computer science. Magnus will work on the project Online Algorithms with Predictions, as part of the national undertaking of Digital Research Centre Denmark (DIREC), under the Innovation Fund Denmark. The project is carried out in collaboration with ITU. As the main advisor, Kim Skak Larsen is joint by Lene Favrholdt and Melih Kandemir. Joan Boyar will also function as an advisor for the online part on equal terms with Kim and Lene, while Nutan Limaye from ITU and Melih will advise on connections to machine learning from different points of view. Magnus made a very positive impression at the job interview and I am certain advising him will be a pleasure!

I am very excited to be co-supervisor of Ph.D. student Simon Skjernaa Erfurth. The topic is Trust and News Authenticity which is somewhat different from topics I am normally involved with. I normally advise theoretical computer science topics with a theorem/proof tradition. Simon's topic is interdisciplinary, also involving web programming, security, and media/communication. Fortunately, Simon has excellent co-advisors who can help with these challenges: Joan Boyar, Ruben Niederhagen, and Claes de Vreese. Simon is very competent and I am certain advising him will be a pleasure!

Thanks to FNU for granting us 770,400 DKK to cover conference travel, research visits, and guests for the coming three years. We applied for a larger project, but it was nice to get this smaller grant to at least get started on this exciting project.

We are very pleased with the research council, which has funded our research activities continuously since 1999. This time the success rate was 11%.

My partner, Joan, and I reclaimed the club championship title after losing the title last year. ツ Out of 18 pairs, we became club champions of the Wednesday Club in Læseforeningen.

I still think you should start playing; see an earlier entry, where I try to convince you.

We have enjoyed conference travel this summer, participating in SWAT - the Scandinavian Symposium and Workshops on Algorithm Theory in Malmö, June 18-20, and in MOLI - Modern Online Algorithms in the picturesque old Charles University in Prague, July 9, 2018. The workshop was a satellite workshop of ICALP. Joan gave a talk on joint work with Kim and Faith Ellen (University of Toronto) entitled "The Scheduler is Very Powerful in Competitive Analysis of Distributed List Accessing" and Lene gave the talk "Upper and Lower Bound Techniques for Advice Complexity" based on joint work with Joan and Kim, as well as former students Christian Kudahl and Jesper W. Mikkelsen. Several talks at the workshop cited results by our online algorithms group.

I don't know any researchers who work as little as the number of hours we are supposed to work. Nobody takes all their vacation - they do officially, because the university insists, since they would otherwise have to pay us extra, but people still work. Nobody thinks about that we're really working extra when traveling to a conference and often using the weekends. Thus, everyone works more than 100% (some much more), compared to the official hours. Despite of that, nobody gets everything done. There is always too much work if research should take up just an acceptable fraction of the time.

In such a set-up, it's hard to see that anyone could be busier than someone else. How can one be more busy than working all the time? Some people still make comments about a person being really busy. I wonder if it measures the amount of work a person does not get done, i.e., the more you don't get done, the busier you are?!

Sometimes students remark on busyness. I've often talked to students who have tried to get help from someone else before approaching me. They would say things such as "I emailed NN, but he never replied, and when I found him, he said he didn't have time and I should make an appointment - I guess he's really busy!"

I must admit that I'm thinking "No, he doesn't care much about servicing the students and have prioritized his own research or some other career-advancing activity" while I'm responding "I think we're all pretty busy - what can I help you with?". I try to pretend to have time to listen while the reality, of course, is that every minute this takes, there is some (additional) research or other thing that will not get done.

Another frequent student comment is "Why don't you just let the ones teach who want to and like it!" I don't ever even begin to explain why this doesn't work. Nobody wants to teach more and most would like to teach less. This is the case even for those of us who like to teach. We also want to teach less; to a large extent because we're always too busy with many other tasks.

Some professors simply don't spend enough time preparing, are not timely when it comes to posing and grading assignments, do not answer student questions promptly, and thereby convey the message that they really don't care (sometimes generously interpreted by students as being too busy).

On the other hand, some of us respect the students' time, always prepare and announce in a timely manner, and try to answer questions and address the students' concerns. In addition, when we teach the same (seen from our perspective) trivial material once again, we try to pretend that we find it interesting, show some enthusiasm, and try to relate to the circumstance that some of this material is hard when you're at a beginner's level.

I guess this performance is sometimes so successful that students get the wrong impression and think we actually want to teach (as much as we do or more). That's probably good, and the truth of the matter is that when I get responsibility for a class, I genuinely care and want the students to learn. I would just prefer not to get that responsibility quite as often. And I actually like the lecturing and student interaction in connection with that - which is also the least time-consuming. It's the preparation, administration of the course and home page, notes, assignments, grading, exams, etc. that's the real pain.

Whereas I can appreciate that students prefer not to be taught by someone who doesn't care much, punishing the faculty members who do care by giving them extra teaching is not the right incentive.

This is my first blog entry in Danish, necessitated by my urge to complain about grammar in Danish media.

Nu er jeg ikke ekspert i dansk grammatik, så det kan da være, jeg selv laver fejl i nedenstående. Ret mig gerne!

"Almindelige" mennesker på Facebook etc. kan simpelt hen ikke finde ud af, hvornår noget skrives som ét ord. Det kan være lidt morsomt, når folk reklamerer for deres nye butik med bland-selv-slik og kalder den "Slik Torvet", hvilket i mine ører lyder som et temmeligt ulækkert forslag, men generelt er det ret irriterende.

Engelsk har fået en stor plads i Danmark, hvilket er fint, og jeg taler selv mere engelsk end dansk, men det har betydet, at folk begynder at bruge de engelsk ord, der også findes på dansk, i den engelske betydning. F.eks. er der mange, som nu refererer til en musiker, maler, eller lignende som en "artist", som om vedkommende arbejdede i et cirkus! Det hedder selvfølgelig "kunstner".

Politikere har fået for vane at bruge en "både/men" form. De siger f.eks. "Både landbruget, men også industrien skal forurene mindre". Det er en ny mode-anvendelse af "både" og "men", der ikke giver mening (selv om indholdet selvfølgelig er klart nok). Ordet "men" giver ingen mening, når man allerede har sagt "både". Sig "Både landbruget og industrien skal forurene mindre". Hvis det er noget helt særligt, man gerne vil fremhæve med sidste del, så kan man evt. bruge "men" - dog forudsat at man ikke har brugt "både". Dvs. "landbruget, men også industrien, skal forurene mindre".

Fyldord er virkelig irriterende. Ind i mellem hører man folk, der hele tiden bruger "som der" i f.eks. "planen som der blev udarbejdet af regeringen".

Mest irriterende er nok TV2 News, hvor værterne skal vise, at de kan henvende sig til folk uden at læse direkte op fra teleprompteren (eller hvad sådan noget nu hedder). Prisen er, at de tillægger sig vaner for at købe sig selv mere tid ved at bruge fyldord. Den værste af slagsen er indsættelse af pronominer, når subjektet allerede er i sætningen! Nogle værter gør dette i mere end hver anden sætning: "Statsministeren han udtalte i dag...", "Vejret det bliver solrigt...", "Det græske parlament de stemmer om...". Læs dog op fra skærmen! Vi ved godt alligevel, at I ikke sidder sammen med os i vores stue, og at der ikke er tale om en samtale.

It was enjoyable giving a talk on generally-applicable analysis techniques in online algorithms for the Theory Group in the Computer Science Department at the University of Toronto. It was an exquisite audience, including Allan Borodin, Joan Boyar, Stephen Cook, Faith Ellen, and Charles Rackoff, as well as a number of brilliant students.

Thanks to FNU for granting us 1,382,962 DKK to cover conference travel, research visits, and guests for the coming three years.

Joan and I are very pleased with the research council, which has funded our research activities continuously since 1999. This time the success rate was around 12%.

My partner, Joan, and I reclaimed the club championship title after coming in second last year. ツ Out of 24 pairs, we became club champions of the Wednesday Club in Læseforeningen.

I still think you should start playing; see an earlier entry, where I try to convince you.

On April 4, 2016, the algorithms group arranges the ARCO workshop — a small, informal, biannual meeting for algorithms researchers in the nearby geographic area, which includes parts of Denmark and Sweden. However, if you happen to be around and would like to join, drop me an email.

I write this triggered by yet another student request for a deadline extension, but it applies equally well to the research world. I'll start with the student scenario.

First of all, there are situations, such as illness affecting one individual as well as more major events affecting many people, where extending a deadline could be the right decision. Similarly, very shortly after a deadline has been announced, one may be alerted to problems with the given date due to holidays, other deadlines, etc. Such circumstances may also be reasonable grounds for changing the deadline and I don't think of such decisions as extensions.

However, the common situation is that students run out of time because they have too high a workload, are not administering their time well, have personal problems, or something similar. Some students silently accept the consequences by dropping my course, dropping a course given by somebody else to make my deadline, skipping their sister's wedding, or something else. Other students come by my office and explain their hardships to me to get an extension. Finally, a very small number of students lie to obtain what they want.

I feel sorry for students when they explain their difficult situation to me and it's very tempting to give in and extend their deadline. However, is that really fair to the students who believe that a deadline is final and who do not approach the professor? Giving in seems to reward students who are good at presenting their cases favorably, or, in extreme cases, good at lying. Additionally, it potentially leads to forms of nepotism, rewarding students you like, students who look cute, students who performed well before, etc. Some professors, wanting to be fair, decide to extend the deadline for everyone in such a case. But even that solution doesn't seem fair to students who already dropped another course or missed out on their sister's wedding to make my deadline.

These issues are not restricted to the student world. Also scientific conferences often extend deadlines. The excuse is usually that the program committee wants to increase the quality of the scientific program by letting more people submit. And who can be against increasing the scientific quality?

However, this suffers from all the same problems. There's the nepotism issue, since people known to the program chair/committee have better access. In fact, you sometimes here people boasting that if they, together with this and that friend, contact the program chair, then they almost always get an extension.

There are the same unfairness issues. If you were dumb enough to believe the deadline and moved meetings, grading, and all sorts of other things to just after the deadline, you will not be able to take advantage of an extension to improve your submission and you are at greater risk of loosing in the competition to people obtaining the extended deadline.

Is the scientific quality then at least improved? Maybe a little, considering the conference in question in isolation, since the people who can usually get an extension count on it, but if you made it clear from the beginning that there would be no extensions, the difference would probably be minor.

At any rate, if a paper is not submitted to a conference because somebody didn't make the deadline, the paper does not disintegrate! The science is still there and will be accepted into another conference. So it's really just stealing good papers from the next conference. That conference, in turn, will have to extend the deadline to steal papers from their successor, etc. In this community, in particular, we should know enough game theory to conclude that it's better if we all play fair.

I have been so fortunate to be appointed Knight of the Order of Dannebrog (Ridder af Dannebrog) by Her Majesty Queen Margrethe II of Denmark. The order was instituted in 1671 by King Christian V and is awarded people who by virtue, loyal service, and manly accomplishments have made themselves ahead of others renowned. ツ I will have an opportunity to thank Her Majesty in person.

I thought I was done taking exams, but then again, I also thought that before finding out that I needed to take a California driver license some years back. This year, the university decided that all staff with teaching responsibilities should be certified to teach in English. Fortunately, the experience was not all that unpleasant and I was certified C2. This is the highest rating according to the Common European Framework of Reference (CEFR), where the ratings A1, A2, B1, B2, C1, C2 cover beginner, intermediate, and advanced levels, with C2 being "mastery or proficiency".

If you send me an email and decide to end one of your sentences with an exclamation point, I will take that to mean that you are trying to communicate a message of major significance. This is the meaning of an exclamation point as I understand it. If you end a sentence with 17 exclamation points, I'm at a loss, and will have to try to guess the meaning. It's probably some measure of importance, but if you don't tell me if it's 17 out of a maximum of 20 or 17 out of a maximum of a 100, I have no way of assessing it, so I will simply ignore them. On the other hand, if you inform me it's 17 out of a 100, I will interpret that to mean that the message is of minor importance. If I'm informed that it's 17 out of a maximum of 17, I will interpret that as I would interpret one exclamation point from a person who does not apply exclamation point repetition. I have similar views regarding statements from people being strictly more than 100% certain of something...

Michal Kotrbčík joins the online algorithms group as postdoc for one year, starting September 1, 2015. Until now, he has been a postdoc at Masaryk University. We look forward to our collaboration with Michal.

My partner, Joan, and I managed to defend our club championship title from last year. ツ Out of 24 pairs, we became club champions of the Wednesday Club in Læseforeningen.

The bridge club is the only place where people still occasionally ask me: "So, how are you doing, young man?" In other words, the average age is up there... However, young people, not least people with a background in Math or CS should enjoy this game. Here's a repeat of my attempt from last year at convincing you:

Competition bridge is a fast-paced game. You have around 7 minutes for each hand, including bidding, playing, and scoring. Then you move on to a new problem - not like chess where you get stuck in the same bad position for hours. Basically, it's applied probability theory. Every time a bid is made - or not made, a card is played, etc., you get more information and must update your estimate of the probability distribution.

One problem with getting started is the initial somewhat steep learning curve. There are classes, but one can also just read, learn, and practice in some social setting before entering into competitions.

A one year postdoc position in online algorithms is available in our group starting around September 1, 2015. The application deadline is April 15, 2015. See the university page for the full announcement and how to apply. Drop me an e-mail if you have any questions.

One of my favorite topics again: How to avoid wasting each others time! This time about doodles... More and more appointments are scheduled using doodle.com. This is how to do it my way. ツ

Give a 24 hour deadline for filling-in a doodle

Most people have a really hard time remembering to do things. Giving them too long time will make them postpone and forget. If not, they will fill it in immediately. People who prefer to get little things done right away (me!) will also prefer to do it immediately. If the deadline is several days away, nobody will keep track of all the options in the calendar to avoid clashes and nobody will want to update the doodle every time they schedule something new. These are strong arguments against long deadlines. How short can we make them then? One can of course be occupied all day or all evening, but my claim is that during a 24 hour window, one can almost always find a couple of minutes for this; and it should not take longer! Put "24 hour deadline" in the subject of your e-mail. Occasionally, when external people are involved or over holidays, a longer deadline could be relevant.

Time your announcement

The important issue here is not to collect the information, but when you "release" everybody's calendar. Thus, set your deadline so that immediately when it expires, you can tell everybody the result, and then they're free to schedule other things again. If your scheduling is dependent on room availability or similar, you should schedule the deadline such that these issues can be resolved fast at that moment and a decision can be announced. If you take more than a day announcing the result, I will certainly start scheduling other things and will feel no obligation to keep updating the information in the doodle.

Give few and realistic options

Doodle has made the mistake of making it way too easy to create lots and lots of options by copying the first row. This is very similar to the ease of which one can send e-mail to lots of people. In my opinion, people should pass a test and be certified conscientious users before being allowed to send e-mail to more than 10 people or allowed to make a doodle with more than 10 options! ツ Choose sensibly! This includes not listing options that are known not to work because most or key people for the meeting cannot make it. Also, know your environment; in a university environment, for instance, where all lectures have a duration of 2 hours and start at an even hour (such as 8-10, 10-12, 12-14, etc)., don't schedule a possible meeting from 9-11! Very occasionally one might miss a possible meeting time option in this way, but that small margin of error is vastly outweighed by the saved time in filling-in doodles and by the accuracy of the information which is due to the fast turn-around enabled by the small processing time for each individual. I consider it a polite practice that the creator of the doodle also fills it in; not least if it's a doodle with many options where you impose a lot of calendar-checking on your colleagues.

Choose carefully - you cannot correct

Finally, announcing a meeting time and sending out a correction later is bound to fail. People probably handle this in many different ways, but while I have an undetermined doodle event scheduling, I queue many other requests for meetings. As soon as I get the announcement of the meeting time, I flush my queue, sending out confirmations and meeting times suggestions for requests that I've queued. Thus, the information I gave in the doodle is out-of-date almost immediately after the announcement was sent out.

Professors Leah Epstein (University of Haifa) and Asaf Levin (Technion) are visiting us for two weeks, and so far it has been most enjoyable and productive. Given how quiet it is at the university in the middle of the summer, we're working in the coffee room most of the time. Drop by if you would like to meet our guests! They are here until July 25.

The workshop Trends in Online Algorithms that we arranged as a satellite workshop of ICALP attracted about 50 researchers. This is a really large number of participants for such an informal and specialized arrangement. It's always hard to know in advance how these things turn out, so it was great to find that the interest was greater than we had hoped. The talks were good and we had interesting discussions with people working on these problems as well as people who were developing an interest.

It was not a large crowd at the online session at CiE, but an audience of very high quality, so I really enjoyed giving my 45 min. invited presentation on Beyond Competitive Analysis - why and how.

We're organizing the workshop Trends in Online Algorithms as a satellite workshop of ICALP. Join in!

Anders and Jan had their Master's defense today. They did well, and it's been fun to advise a quite unusual project entitled European Football Placement Problems - Complexities and Exact Solutions, where we considered the complexity of deciding placement possibilities for teams in ongoing tournaments, and despite of the hardness results, actually managed to compute them.

My partner, Joan, and I ended the season well. Out of 24 pairs, we became club champions of the Wednesday Club in Læseforeningen.

As opposed to how it's often portrayed, competition bridge is a fast-paced game. You have around 7 minutes for each hand, including bidding, playing, and scoring. Then you move on to a new problem - not like chess where you get stuck in the same bad position for hours. Basically, it's applied probability theory. Every time a bid is made - or not made, a card is played, etc., you get more information and must update your estimate of the probability distribution.

As of April 1, I've accepted the position as chairman of the national External Examiners in Computer Science (formand for censorkorpset i datalogi). I felt a responsibility to accept and hope it will not be an administrative burden to the extent that I'll regret it.

I was allocated a substantial amount money to have a programmer make the home page, but decided that given the number of times I've told students that this is easy, I ought to try it myself. I've spoken html almost fluently for a couple of decades of course, but this was my first attempt at creating a dynamic web page using substantial elements of PHP, Javascript, jQuery, CSS, MySQL, etc. It wasn't quite as easy as I had thought, but an interesting experience. I think the end result is acceptable for a first attempt, where my focus was functionality over design.

Marie's Ph.D. defense was today, and she did well! This is one of the times where I feel I've accomplished something, when I can send another highly qualified person out in the world to do good for society.

FNU granted us a bit more than one million DKK yesterday! This means that there's no problem travelling to conferences, having research visitors, etc. the next three years. It's getting increasingly hard to get this funding (a 12% success rate this time, I believe), so we're very pleased that we succeeded. We like FNU!

It's of course ridiculous that we should apply for this money, since it's necessary to do a good job as a researcher. As I see it, it's quite similar to asking us to apply for pen & paper. An enormous amount of time (and therefore money) is wasted applying for these relatively modest grants.

This will probably not be a very active blog, but ever so often I need to feel that I'm telling people my opinion on something - or maybe just announcing some news on a topic that means something to me. I'll pretend that some people are occasionally reading this - which may be in Danish if appropriate.