Monthly Archives: June 2011

Exponential Time Algorithms at ESA 2011

The list of accepted papers for ESA 2011 is online. Below is my own quick take on which papers are about exponential time algorithms.

ESA 2011 is colocated with IPEC under the ALGO 2011 umbrella, so there will be plenty of exciting results that week.

  • Dimitrios Thilikos. Fast sub-exponential Algorithms and Compactness in Planar Graphs.
  • Gwenaël Joret, Christophe Paul, Ignasi Sau, Saket Saurabh, Stéphan Thomassé, Hitting and Harvesting Pumpkins, arXiv:1105.2704.
  • Fedor Fomin, Ioan Todinca and Yngve Villanger, Exact algorithm for the maximum induced planar subgraph problem, Todinca’s slides from Worksh. Graph. Decomp. 2010.
  • Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk and Jakub Wojtaszczyk, Scheduling partially ordered jobs faster than 2n.

I’m probably missing some results, but without online abstracts it’s hard to tell. I cannot judge a paper from its title alone. Comments and corrections are welcome, in particular links to online manuscripts.

Filter Bubble in Weekendavisen

I managed to excite Danish weekly Weekendavisen about the societal impacts of internet personalisation, along the lines of Eli Pariser’s recent book The Filter Bubble. This resulted in a nice, meaty two page article starting on the front page of the paper’s science section Idéer.

This is part of my ongoing effort to unleash the meme of the Algorithmic Lens in the public discourse. Two years ago I initiated an article about the algorithmic lens on the sciences in the same paper.

The Social Science Filter Bubble

The creation of such an article is a give-and-take between me and the journalist. I’d collaborated with him previously on the production of a TV programme about how Google’s page rank algorithm works, so we had established a level of common trust. Still, we come from vastly different epistemological backgrounds.

Here’s a detail that made me smile.

I originally suggested a formulation along the following lines:

Dewey and Habermas are fine, but today the public sphere is shaped by algorithmic processes, and we’re just in the beginning of that development. And just like we turn to Newton to understand gravity, we must turn to Turing and his disciples to understand some of the forces that influence the behaviour of individuals and groups in the information society.

Plenty of dropped names, and it was rejected for being too opaque. Consequently, in the final version, the references to philosophers Dewey and Habermas remain, but Newton and Turing have been removed. So, the readership of Weekendavisen is of course expected to know the public sphere and the civil society (as rightly they should). But they are protected from having to google who the other two guys are.

This is an example of the “old” filter bubble, where media through self-selection and editorial policy shape a common frame of reference, an understanding of what a Citizen is supposed to educate herself about.

In the Brave New World to come, an algorithm would have processed my quote. It would perhaps have replaced “Dewey and Habermas” by “Philosophers” or “Some social scientists” or “Dead White Males” on a per-reader basis, based on the epistemological priors, background knowledge, and ideological preferences of the reader.

Further reading

If you came here from Weekendavisen because you googled my name – provided your personalisation settings allowed me to burst your filter bubble –, and want to read more, check out That’s Eli Pariser’s blog, including links to his book, his TED talk video, and a list of 10 ways to pop your filter bubble.

Alternatively, check out my recent (Danish) TV production How Google works, which explains the PageRank algorithm. Now, the Good Olde Days.

Or you can hire me to give a talk; I have several ready, such as Hvordan Google virker or The Algorithmic Lens. See the full list at Popular Science talks.

Update: I also appeared on Danish public radio about this: P1 Morgen 4 Jun 2011, 7m45s, around 9:30.

Update: And even the the local paper Sydsvenskan: De digitala skygglapparna (4 July 2011) (in Swedish).

Update: And even in Svenska Dagbladet:
Isolerade i nätbubblan (15 August 2011) (in Swedish).

Image source: Wikimedia Commons