Monthly Archives: January 2012

Journées Nationales du GDR 2012

Leave a reply

Illustration of Yates’s algorithm from my talk. I finally found a way to simultaneously depict the lattice structure and the symmetries of the circuit.

I spent a few nights in lovely Paris last week, attending the Journées Nationales d’Informatique Mathématique at Paris Diderot university.

Many computer science fields in France are organised in national, cross-institutional groupes de recherches, not completely unlike the ACM SIGs in the US. The TCS group (“Mathematical Informatics”) encompasses some 400-500 people, as far as I understand.

As in most of Europe, theoretical computer science in France includes many more fields more than US-style theory of computation. Amazingly, they meet once a year for two days, and give well-attended talks to each other. The 2012 meeting had 170 registrants, an impressive number.

This struck me as particularly noteworthy after just attending SODA, where the various subfields of algorithms become increasingly fragmented and estranged, to the point of hostility and mutual incomprehensibility.

At the Paris meeting, a steering committee selects a number speakers from the various working groups in the GDR IM, who give meaty, 45-minutes talks to a general TCS audience: Computational logic, computational geometry, distributed systems, process calculi, extremal graphs, ….

In addition, the meeting includes two 1-hour invited talks recruited outside of the French GdR. Ashwin Nayak talked about communication complexity, and I used to opportunity to present an overview of zeta transform algorithms and applications, culminating in our SODA 2012 result from last week. [slides]

Thanks to everybody who attended, and to the nice organisers for putting me into a disarmingly charming hotel in the middle of the Latin quarter, where you couldn’t swing a dead Marsipulami without hitting a comic store. I had a splendid time.

More Algorithms in Svenska Dagbladet

Leave a reply

“Coded cultural choice” on the cover of SvD’s Arts section, illustrated by badly indented Java code.

My quixotic attempts to insert computer science into the memetic space of the literati continue to bear fruit. Today’s score is 3 pages in Sweden’s major newspaper Svenska Dagbladet. Of course, this only works on a day where the entire cultural elite is still hung over from actually having a life at New Years’s Eve, so there is a narrow window of opportunity where no other culture is being produced.

The article is about the effect of algorithms on the consumption of culture. One of the arguments that I’ve been trying to make for a while is that (a) the human condition is increasingly determined by access to information (b) the main force affecting information is algorithms. Thus algorithms are a worth understanding for other reasons than (a) intellectual curiosity or (b) technological progress.

The web version of the article is online at svd.se.

Such an article are the result of an interview that takes over an hour, and where I say a lot of things about a lot of things, and some subsequent emails. What ends up in the final article is a bit of hit and miss. This time, I’m pretty happy with the outcome.

Some highlights and comments:

  • My physics envy is in full display: “We teach 1960’s science like physics and chemistry in school, but you don’t learn more about algorithms now than 20 years ago.” This statement is of course not universally true; many countries do have programming and other computer science as part of the high school curriculum. But even with that proviso I think it’s safe to say that “what science should be thought in school” has changed relatively little since Sputnik. But the point of the article is of course something else: algorithms have an effect on culture (and democracy and whatnot), so the bold claim is that algorithmic thinking should be part of the Social Science curriculum. (It goes without saying that recursion ought to stand proudly next to Pascal’s law in the Science and Maths curriculum as well.)
  • The article contains a nice-looking attempt at actually Explaining What’s Going On. You can see some pseudocode in the web version, where nice-looking brand icons serve as objects that are polled for various signals about previous user behaviour. There is even a collaborative filtering aspect (since the hypothetical Facebook object is queried about what your friends like). Given the constraints under which such a page is produced, I think this came out well. The real point is of course that this code is not written by a human, but by another algorithm, so “the algorithm” performs at a meta-level. I did not find a good way to communicate that, so I didn’t try.
  • The code on the section’s front page is from the very nice data mining research done at ITU: Andrea Campagna and Rasmus Pagh, Finding Associations and Computing Similarity via Biased Pair Sampling, The Ninth IEEE International Conference on Data Mining, Miami, Florida, USA, 6-9 December 2009 pp 61-70. Proper indentation or choice of a non-proportional font is not something the newspaper graphics guy cares about. (Hell, my own students don’t.) I proudly showed this to ITU’s vice chancellor Mads Tofte, but he “would have been more impressed if it had been in ML.”
  • Lest somebody misattributes pithy quotations to quotable me, the phrase “program or be programmed” is from Douglas Rushkoff.