Archive for May, 2011

Announcing ThRaSH 2011

To quote Jan L. A. van de Snepscheut: In theory there is no difference between theory and practice, but in practice there is.

The upcoming Workshop on Theory of Randomized Search Heuristics, located in Copenhagen, is an effort to do something about the fact that there is a gap between provably efficient methods for NP-hard problems (as investigated in our group) and methods that seem efficient in many practical cases. Free registration. (Note to PhD students: If you are interested in attending the workshop, you may get ECTS points by presenting some of the results from the workshop at a group meeting.)

Papers, and a challenge

I finally found time to do what I have wanted to do for years, namely updating my papers page to be in a consistent, organized, and user-friendly state. I ended up making my own Python script that generates the HTML based on information about the papers, so this means that I should be able to easily maintain, or even improve, the page. Of course, I’m happy to share the script if someone wants it.

On a different note, I have been thinking for a while about what makes a data mining problem hard. In particular, the problem of finding frequent itemsets is equivalent to finding, in a 0-1 matrix, large submatrices with only 1s. At the bottom of the papers page I have added what I believe is a hard such instance. Even though the instance can be encoded in 450 bytes (or 62 bytes compressed), and the answer sought in just 7 bytes, I believe that solving it will require algorithmic advances and/or use of massive parallelism. Of course, I will be happy to hear from anyone who solves it, or tries to.

The Art of Convincing, 10 years later

For some reason I was looking at some popular articles that I wrote for the Danish-language magazine Aktuel Naturvidenskab, and realized that it is the 10th anniversary of my debut as a popular science writer! One of the articles, Overbeviselsens kunst (The Art of Convincing), is about mathematical proofs, especially probabilistically checkable ones.

Though I did not write much popular science since then, I think that I have needed many times the art of convincing: When talking to journalists, family members, colleagues within a different research area, or addressing multi-disciplinary research councils, you need to explain clearly why they should care about your work (or the work done in one’s peer community). This is challenging because you need to put yourself in the place of the person you are addressing, but also fun!

I am happy to learn from group members such as Thore and Philippe who, with complementary approaches, excel at doing this kind of communication. In case you didn’t see it yet, ask Thore about how he illustrated data mining using decks of cards to ITUs vice chancellor. Or ask Philippe why we should care about smart grids.

PS. My other popular articles are here, here, and here.