Archive for August, 2009

ALGO Algorithms for everyone at ITU

From 7 September to 11 September 2009, ITU hosts ALGO 2009, the largest European algorithms conference. The invited talks on Monday, Tuesday, and Wednesday mornings, from 9AM to 10AM, are open to employees and students at ITU.

“Algorithms are everywhere today, not just in your car navigation system or your web search engine,” says organizer Thore Husfeldt. “Algorithmic thinking has become as important outside of computer science as inside. Modern biology is an example that everybody knows about, but the algorithmic lens is useful in many other areas as well.

“Since we’re hosting ALGO at ITU, we’ve tried to attract keynote speakers that have something to say about each corner of ITU’s triangle.”


On Monday, Michael Mitzenmacher from Harvard University talks about open problems in cuckoo hashing. Cuckoo hashing is a fundamental data structure that was discovered by ITU’s Rasmus Pagh, and many ITU students have been exposed to it. Mitzenmacher is a leading expert on randomness in computation and known for his ability to apply techniques from algorithmics to make strong impact on other fields such as network communication protocols, and coding theory.

Michael’s blog: My Biased Coin

The Arts

On Tuesday, Erik Demaine from MIT talks about algorithms in arts, puzzles, and stage magic. Among his many research activities is computational origami, and his creations are on permanent exhibition at the New York Museum of Modern Art. Demaine is a MacArthur Fellow, started university as a 12-year old, go this Ph.D. at age 16, and was the youngest ever professor in the history of MIT.

Erik’s webpage:


On Wednesday, Noam Nisan talks about Google’s auctions for TV advertising. Algorithmic thinking has transformed many areas of economics such as game theory, a highly visible application is the auction-based pricing mechanism that Google uses to place advertisements on its search results page. Nisan, on of the world’s leading researchers in computational complexity, is on leave from Hebrew University of Jerusalem and works at Google Tel Aviv.

Noam’s blog: Algorithmic Game Theory

See the full programme at

LaTeX support

We now have \LaTeX support up and running! To make it work, I needed to enable the WP latex plugin, specify the paths /usr/bin/latex and /usr/bin/dvipng, and the default colors 000000 and ffffff. Now you can just write

$latex e^2$

… and out comes beautifully typeset e^2. Try it for yourself!

ALGO 2009

ITU campus
The next big thing going on here is ALGO 2009. Arrangements are taking a lot of effort - especially Thore, Nhi, and Darryl have done a lot of work. Stay tuned for inside information!

Position(s) announced

ITU has position(s) announced at associate/assistant professor levels. Some of the possible research backgrounds fit our group. If you are interested in applying, feel free to contact Rasmus Pagh to learn more.

Popular science talk at Fantasticon 2009

Thore Husfeldt will give a popular science talk at the Copenhagen Science Fiction convention Fantasticon 2009 on Sunday, 30 August, at 12.

From the abstract:

[...] as a technologically curious person, you want to understand the role played by computation in current society:

  • Why do Google, genome sequencing, and car navigation systems work? These are computationally feasible tasks with astounding consequences for society.

  • Why can’t I use natural language to talk to my computer, like in Star Trek? This computational task is routinely solved by our brains, but we don’t seem to be able to automate it, to our great annoyance.
  • Why can’t my neighbour break my home banking cryptosystem? A seemingly computationally infeasible task, to our great pleasure.

[...] as a consumer of speculative fiction, you want to understand the questions that permeate your genre. In general, the nature of our computational world determines the possibility of strong artificial intelligence, a trope of Science Fiction. In particular, writers such as Charles Stross make the transition between these computational worlds a central world-building or plot element. [...]

Charles Stross is Guest of Honour at Fantasticon.

Recent activities

Since we are moving our announcement of activities to this blog, here is a list of past activities, for future reference:

* September 7-11, 2009. We are hosting the ALGO 2009 conference.

* May 14, 2009. Mini-workshop on "Data Processing on Modern Computer Architectures".

* April 27, 2009, 11-12: Talk by Jelani Nelson, MIT: Revisiting Norm Estimation in Data Streams.

* April 6, 2009, 11-12: Talk by Mark Greve, MADALGO: Online Sorted Range Reporting

* February 23, 2009, 12-13. Talk by Philip Bille, DTU: Fast Searching in Packed Strings

* December 17, 2008, 13-14: Talk by Jeremy Barbay, Universidad de Chile: Compressed Representations of Permutations, and Applications

* December 2, 2008, 12-13: Talk by Rasmus Pagh: Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes

* October 14, 2008, 11-12. Talk by Thore Husfeldt: Computing the Tutte Polynomial in Vertex-exponential time (to appear at FOCS 2008)

* September 18, 2008, 13-14. Talk by Milan Ruzic on Near-Optimal Sparse Recovery in the L_1 Norm (to appear at FOCS 2008)

* September 30, 2008, 11-12. Rasmus Pagh talks about “Bee Trees, and Searching a Sorted Table with O(1) Accesses”

* September 4, 2008, 11-12. Milan Ruzic gives an introduction to compressed sensing.

* September 2, 11-12. Talk by Mikkel Thorup: Efficient Cuts via Greedy Tree Packing (appeared at STOC 2008)

* June 9 - 12, 2008. AFAPA summer school