ARCO workshop

Algorithms researchers in the broader Øresund area are meeting once again for the revived ARCO meeting series. The program includes three talks from our group.

There’s a supercomputer in my office!

Due to a generous donation from nVidia I now have a 1 Teraflop computing device, a Tesla C2075. It will be used for thesis projects, and perhaps future research.

The world’s first teraflop computer, ASCI red, was finished less than 15 years ago. It remained the only teraflop computer in the world until the year 2000. Its energy usage is around 4000 times higher than the Tesla card.

With such parallel computing capability becoming affordable, the range of potential applications will increase dramatically. There are great challenges for algorithms researchers to create algorithms that fit these architectures. Perhaps it is time to find better theoretical models for doing this?

PhD defense

Andrea Campagna will defend his PhD thesis, Sampling implicit sets: a new data mining technique on Thursday October 27, 3 PM, in auditorium 2. Committee members are Thore Husfeldt (ITU), Gerth Brodal (AU), and Piotr Indyk (MIT). Hope to see many people interested in algorithms and data mining there!

Andrea Campagna

Danish success at SODA 2012

SODA is the largest, and one of the most prestigious venues for algorithms research. Again in 2012, Denmark is a strong contributor with 6 papers co-authored by researchers at Danish institutions:

  • Distance Oracles with Near-Linear Preprocessing Time for Undirected Graphs, Christian Wulff-Nilsen
  • I/O-Efficient Data Structures for Colored Range and Prefix Reporting, Kasper Green Larsen and Rasmus Pagh
  • Fast zeta transforms for point lattices, Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof and Pekka Parviainen
  • Shortest Cycle Through Specified Elements, Andreas Björklund, Thore Husfeldt and Nina Taslaman
  • Fully Persistent B-trees, Gerth Stølting Brodal, Spyros Sioutas, Konstantinos Tsakalidis and Kostas Tsichlas
  • Competitive Routing in the Half-ϑ6-Graph, Prosenjit Bose, Sander Verdonschot, Rolf Fagerberg and Andre Van Renssen

I am proud that three out of these 6 have authors from our group. Well done!

Algorithms seminar fall 2011

Don’t miss this exciting activity. The seminar page has all the details!

Pointers worth following

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.

Minwise independence in the news

Thore and I are quoted in an article (in Danish) on the popular science website This includes a nontechnical explanation of minwise independent hashing! Time will tell if other Danish media will pick this up…

Next Page »