IT University of Copenhagen

Thore Husfeldt

News

New apartment

My family moved apartments to a wonderful building next to Stadsparken in Lund. Currently it’s a huge mess with moving boxes, hard-working builders, and lots of dust. Also, currently no phone and (worse) no internet, so I’m off the radar.

Tue, 14 Apr 2009 | Category: News | Permanent link

Spring School on Exact Algorithms

I will be teaching at Spring School on Fixed Parameter and Exact Algorithms in May 2009. Exciting stuff, and a great set of lecturers. See you there!

Tue, 24 Mar 2009 | Category: News | Permanent link

At IT University of Copenhagen

As of June 2008, I have accepted a permanent position at IT University of Copenhagen. I retain my position in Lund and remain available for make-up exams in courses that I’ve been responsible for, and thesis advice in algorithms and related fields.

Tue, 03 Jun 2008 | Category: News | Permanent link

New paper on the Tutte polynomial

I loved this the moment I saw it: the Tutte polynomial, an amazing structure in algebraic graph theory that can be used as a unifying framwork for lots and lots of science from other fields: models from statistical physics, graph colouring, knot theory, network theory. And now we have a paper on it!

We look at algorithms for computing the Tutte polynomial, and we even do what we claim to be interested in: compute the Tutte polynomial! So if you always wondered about the coefficient of x2y2 in Loupekine’s Second Snark: it’s 991226, found by our new, exact algorithm that runs in time roughly 2n.

The paper continues a very pleasant research collaboration with Andreas Björklund, Petteri Kaski, and Mikko Koivisto. Preprint at the ArXiv.

Update (April 2008): Now in polynomial space! And the paper covers the cover polynomial as well.

Tue, 15 Apr 2008 | Category: News | Permanent link

Summer school on algorithms for advanced processor architectures

With Philip Bille I am organising a summer school on algorithms for advanced processor architectures (AFAPA) for June 2008. We have been able to attract some extremely attractive lecturers for this; check out the course web page.

Tue, 15 Apr 2008 | Category: News | Permanent link

New paper at ICALP 2008

We found a way of analysing the classical dynamic programming solution to the TSP of Bellman and Held–Karp using a beautiful lemma of Shearer. This leads to running times (slightly) faster than within a polynomial factor of 2n. The ICALP committee was so kind as to accept this to the forthcoming Iceland ICALP; you can find the submitted manuscript among my on-line papers. This is joint work with Björklund, Kaski, and Koivisto.

What makes this extra fun is that the xkcd web-comic just ran a strip on the dynamic programming algorithm, so I hasten to supply an alternative final frame for it.

Wed, 09 Apr 2008 | Category: News | Permanent link

Paper on STACS 2008

The STACS 2008 committee just accepted our submission Trimmed Moebius Inversion and Graphs of Bounded Degree. This is joint work with Andreas Björklund, Petter Kaski, and Mikko Koivisto.

In some earlier work we showed that the graph colouring problem can be solved in time 2npoly(n); which punctuated a decades-long story of incremental improvements of the base of the exponent, from the obvious-by-dynamic-programming 3 via 2.4423, 2.4151, 2.4023, and 2.3236.

Our new papers shows that the story doesn’t end with 2, as tempting as this number looks. At least not for bounded-degree graphs. Specifically, we show that every bounded-degree graph can be coloured in time cnpoly(n) for some constant c strictly less than two, depending on the degree but not on n.

The techniques involve some manipulations “inside” Yates’s algorithm for Moebius inversion, and some neat combinatorics about families of intersecting sets based on a result of Chung et al..

Fri, 14 Dec 2007 | Category: News | Permanent link

Not fired yet!

I made the local paper: Slutet nära för Lunds datavetare, which (besides calling me Thore Husman) also makes it sound as if I am already fired. This, at least so far, has not yet happened: I’m certainly immensely frustrated; but I’m not yet fired. (In case my bank is reading this…)

What is true is that Lund will no longer have a Computer Science education. (There are several Computer Engineering programmes, and a programme in Information Systems, however.) As far as I know, that’s unique for a large university (or just a medium one). There has been one analysis of the consequences of this decision, by former dean Bertil Holmberg. Two quotes at least are interesting from a university perspective:

Ur ett övergripande universitetsperspektiv förlorar Lunds universitet möjligheten att ge en allsidig och djup programmerarutbildning på solid vetenskaplig grund
Om utbildningen elimineras ur fakultetens utbud försvinner universitetets möjlighet att erbjuda en genomarbetad CS-utbildning – allt under förutsättning att inte LTH bygger upp ett motsvarande program eller programvariant.
The latter would be a great solution, but it does not seem to happen. Bertil’s report is public, [PDF].

Confused about Computer Science (datavetenskap) and Computer Engineering (datateknik) and Information Systems (systemvetenskap)? I recently tried to explain what it all means on another blog. In Swedish (kind of).

Fri, 16 Nov 2007 | Category: News | Permanent link

Journal version of paper with Björklund and Koivisto

I’m happy to announce that Andreas Björklund, Mikko Koivisto, and myself have merged our contributions to the IEEE Foundations of Computer Science conference (FOCS) 2006 into what I consider a very, very nice journal paper. The result was invited and accepted to the SIAM Journal on Computing special issue for FOCS, which of course makes us extra proud.

The two original conference papers that appeared at FOCS had very different styles, and basically we had to rewrite most of it from scratch. But it turned out that the final, merged version is at least as good and consitent as any of them. You can check out the final submission among my on-line papers.

Thu, 01 Nov 2007 | Category: News | Permanent link

Lund University Student Unions Teaching Award

I still haven’t quite absorbed the fact that the natural science students found me worthy of their pedagogical prize 2007, but now it seems I get the university-wide prize as well: Lunds Universitets Studenkårer (Lund University’s Student Unions) will be honouring me with their prize for outstanding teaching on Oct 19.

Nomination

Part of the nomination is now on-line at the University webspace. Translating that into English gives something like this:

In his role as Computer Science teacher, Thore Husfeldt has proved that enthusiasm actually can be contagious. Like no other he manages to create motivation for learning and enthusiasm for the topic in his students. This may hinge the fact that he really is a fiery spirit and has stated he sees teaching as the most fun thing he does at University.

Pedagocial development is an issue that lies close to Thore’s heart. Apart from being a driving force in development Thore has also shown enthusiasm and participation in the development of quality measures, models that depend on the central role of examination for learning.

Thore makes time for his students. His door is seldom closed. It’s never a problem if students need an extra seminar or explanation, Thore is always there for them.

What can I say? First, I need to express my enormous gratitude to whatever students fought for my nomination in whatever covens these things are decided. I have always tried to take the right people seriously, and engage politically able and rational students in honest and well-reasoned debate. This costs a lot of easy points, but has made me popular with some other fiery spirits who throw some weight around. It’s supremely satisfying to see this strategy validated.

Second, there are a lot of teachers better than me who don’t get recognised. Students: do you bloody job and nominate the right people. They need you.

Third, I’m happy to see myself awarded for things that are really important to me, and not so trivial. (I’m pretty sure you can be a terrible teacher while being available and enthusiastic. I understand why these criteria are on the list, since they are necessary. But they don’t make you a good teacher.) But the nomination does mention my stubborn insistence on Good Exams, a topic that is really important to me. The fact that the student union recognises this is great, and verifies one of my dogmas: the idea that students prefer fuzzy exams is a myth.

I have never ever taken a pedagocial course, and most of those I’ve looked at disgusted me. But I have copied all the best teachers I’ve ever met, and anything I do right I have shamelessly stolen from them: from people who derive pleasure from explaining difficult things really, really well.

Update: Full nomination

I just received the text of the full nomination.

Lunds Naturvetarkår (LUNA) nominerar härmed Thore Husfeldt, institutionen för datavetenskap, till Lunds universitets pedagogiska pris 2007.

Thore Husfeldt har i sin gärning som lärare i datavetenskap visat att entusiasm faktiskt kan smitta av sig. Som ingen annan förmår han skapa inlärningsvilja och intresse för ämnet hos sina studenter. Detta beror kanske på att han verkligen är en eldsjäl och att han uttalat ser undervisningen som det roligaste han gör på universitetet.

Att undervisa i datavetenskap är svårt, om detta kan många vittna. Dåligt undervisad datavetenskap blir obegriplig p.g.a. sin extremt tunga teoretiska bas. Här har Thore en enorm förmåga att förklara svåra teoretiska resonemang på ett begripligt sätt. Mycket av detta beror på att han gärna sätter teorin i sitt sammanhang. De datavetenskapliga teoretiska modellerna har en avgörande betydelse för alla vetenskaper som behandlar stora statistiska underlag, bland annat inom naturvetenskap, samhällsvetenskap och ekonomi. Detta klargör Thore i sin undervisning på ett utmärkt sätt. Detta betyder inte att Thore trivialiserar sin vetenskap och dess teori, tvärtom. Ärlighet är ett nyckelord i Thores undervisning. Om ett kursmoment är svårt så säger han det. Om ett kursmoment är tråkigt säger han det. Thore anser att detta är en betydligt bättre motivationsteknik än att trivialisera svåra och tråkiga moment. Enkelhet och tydlighet är andra viktiga begrepp i Thores pedagogik.

Det har sagts att Thores kurser inte liknar varandra från termin till termin. Detta beror på att Thore kontinuerligt utvecklar kursinnehållet och sin egen pedagogik. Han har varit drivande i arbetet med bolognaanpassning av utbildningen och grundutbildningens upplägg. Thore har även hållit i utbildning för laborationsassistenter och forskningsassistenter. Det pedagogiska utvecklingsarbetet är något som ligger Thore varmt om hjärtat.

Förutom att ha varit drivande i utvecklingsarbetet har Thore också visat entusiasm och engagemang i att utveckla kvalitetssäkringsmodeller för utbildningen. Kvalitetssäkringsmodeller som tar fasta på examinationens centrala roll för lärandet.

Thore har länge påpekat att utbildning ges för lite utrymme och status i förhållande till forskning, men att forskning och utbildning går hand i hand. Det är särskilt tydligt inom datavetenskapen där utvecklingen går hejdlöst snabbt, och en lärare som är borta från forskningen en tid förlorar möjligheter att hänga med i utvecklingen. Thore för en “kamp för att höja nivån på undervisningen” vilket bland annat innebär att forskande lärare aktivt deltar i undervisningen. Thore har bland annat arrangerat “algoritmseminariet”.

Thore tar sig tid för sina studenter. Hans dörr är sällan stängd. Om studenterna har behov av ett extra seminarium eller en genomgång till är det aldrig ett problem utan Thore ställer upp.

Att Thore uppskattas av sina studenter har bland annat manifesterats i att han har mottagit datalogernas pedagogiska pris “Golden Keyboard Award” samt LUNAs pedagogiska pris.

Detta sammantaget gör att vi rekommenderar varmt att Thore Husfeldt tilldelas Lunds universitets pedagogiska pris för 2007.

I especially like the third paragraph. English translation will follow.

Wed, 17 Oct 2007 | Category: News | Permanent link

SWAT 2008 Committee

I am on the Programme Committee for SWAT 2008, to be held at Gothenburg next Summer, chaired by Joachim Gudmundsson. The Call for Papers is now on-line at the SWAT 2008 conference website.

Mon, 15 Oct 2007 | Category: News | Permanent link

Pony trecking and fishing, Oct 9–12

I’ll be visiting Finland this week (Oct 9–12), to work with Mikko Koivisto and Petteri Kaski in Helsinki. Email works.

Mon, 08 Oct 2007 | Category: News | Permanent link

LUNA Pedagogical Prize 2007

I am very proud to have received 2007 pedagogical prize awarded by the student federation at the Natural Science faculty, LUNA. Teaching is the part of my job that I do best and enjoy the most, and it is supremely satisfying to have this recognized. I am grateful to whoever nominated me.

The Prize

Apart from a nice diploma that will be decorating my office wall, the prize is a wandering trophy in the form of an apple, I assume the reference is Biblical or Newtonian. The whole thing is huge and very, very heavy. The trophy comes with a smaller copy that I get to keep. [LUNA]

A metal plaque displays the previous winners, which I decipher to be:

1998
Sven-Olle Nilesen
1999
Anders Ahlberg
2001
Eric Warrant
2002
Tomas Brage
2003
Lennart Jönsson
2004
Per Nyström
2005
Olof Berglund
2006
Jep Agrell
2007
Thore Husfeldt

Mon, 28 May 2007 | Category: News | Permanent link

Plans for late Spring 2007

In June, I plan to attend STOC 2007 in San Diego, California; I will stay from Sunday to Sunday, 10th to the 17th.

I am also honoured to participate as a committee member in a number of Ph.D. defences in the next few months. Topics include overloading web servers, exact satisfiability, and graph theory. Lovely stuff.

On June 6 I will give a general audience talk (an algorithmic perspective on phylogenetics) in Lund’s Botanical Gardens in connection with the Linné celebrations on that day.

Wed, 09 May 2007 | Category: News | Permanent link

Docent

I finally levelled up and am now a lvl 3 academic, called docent. Go me!

Wed, 25 Apr 2007 | Category: News | Permanent link

Docent lecture

As part of the requirements to obtain the Swedish docent degree (often translated to associate professor) I will be giving a public lecture on Friday, 16 March, 2007 at 15:15 in E:1406. As Sweden is celebrating Linneaus this year, the title is A Linnean Journey from Computation of Taxonomies to Taxonomies of Computation. The lecture is public, and supposed to be accessible to beginning graduate students of science.

Mon, 26 Feb 2007 | Category: News | Permanent link

New paper on subset convolution

Joint work with Björklund, Kaski, and Koivisto on how to compute general subset convolutions faster than by dynamic programming. Especially, it gives a fast algorithm for the minimum Steiner tree problem. Update: To appear at STOC.

Fri, 16 Feb 2007 | Category: News | Permanent link

Lecture notes on inclusion-exclusion in combinatorial optimisation

For Andrzej Lingas’ course I produced lecture notes about using inclusion-exclusion in combinatorial optimisation. The audience is advanced undergraduates, and the prerequisites are minimal. [PDF].

Fri, 22 Dec 2006 | Category: News | Permanent link

Journal version of ICALP 06 paper

Andreas and I finished a draft of the journal version of our ICALP paper on exact algorithm for exact satisifability and number of perfect matchings. Comments are welcome.

Fri, 22 Dec 2006 | Category: News | Permanent link

New Paper with Björklund

“Inclusion-exclusion algorithms for counting set partitions”: [PDF]. To appear at FOCS 2006. Comments are welcome. A preliminary version appeared as “Inclusion-Exclusion Based Algorithms for Graph Colouring” at ECCC TR06-44

Mon, 30 Oct 2006 | Category: News | Permanent link

Travel plans autumn 2006

Here are my travel plans for the 2nd half of 2006. 19 September I am at ITU Copenhagen. 4-6 October I visit Aarhus University. 20-26 October I will in sunny California (and inside airplanes) for FOCS.

Tue, 03 Oct 2006 | Category: News | Permanent link

Conferences Summer 2006

In July, I will attend SWAT, ICALP, and iETA. See you there!

Fri, 16 Jun 2006 | Category: News | Permanent link

Email trouble

People continue to have big problems sending me email at my cs.lu.se address. Try cs.lth.se instead, that seems to work if the other doesn’t. (Or why not use the phone?)

Thu, 30 Mar 2006 | Category: News | Permanent link

Sukoku (in Swedish)

I samband med fakultetens studiedagar för gymansister har jag pratad om sudoku. Tack till alla som kom och lyssnade.

Det är en kul föreläsning och ett härligt ämne där jag även kan smuggla in riktigt mycket naturvetenskap. Om man missade studiedagarna kommer jag gärna och ger den i andra samband, till exempel för andra gymnasieklasser i regionen. Ring eller skriv och fråga.

          Här borde det finnas in Quicktime film  

Material:

Fri, 10 Mar 2006 | Category: News | Permanent link

New Paper with Björklund

“Polynomial space algorithms for exact satisfiability and chromatic number”:

Abstract: We provide simple algorithms using polynomial space and O(cn) time for variants of n-element set cover problems, based on divide-and-conquer and on inclusion–exclusion characterisations.

We show that the Exact Satisfiability problem of size l with m clauses can be solved in time lO(1) 2m, and that the Chromatic Number of an n-vertex graph can be found in time O(2.4423n). Both these algorithms require only polynomial space and admit efficient parallelizations, answering open problems in the literature.

We also argue that some weighted versions of the problems can be solved in polynomial space, still only using time singly exponential in m and n, respectively.

Finally we show that if we allow our Chromatic Number algorithm to use exponential space, the chromatic number of an n-vertex graph is found in time O(2.3236n), an improvement over the previously best algorithm running in time O(2.4023n).

A draft can be found under On-line papers. Comments are welcome.

Update: Some rewriting, extension, and improvement. And a title change to Exact algorithms for exact satisfiability and number of perfect matchings.

Update: To appear at ICALP 2006.

Tue, 20 Dec 2005 | Category: News | Permanent link

Note on priority queues with Alstrup, Rauhe, and Thorup

We present a simple black box that takes a priority queue Q which supports find-min, insert, and delete in x-time at most t. Here x-time may be worst-case, expected, or amortized. The black-box transforms Q into a priority queue Q* that supports find-min in constant time, insert in constant x-time, and delete in x-time O(t). Moreover, if Q supports dec-key in constant time, then so does Q*.

Extended abstract under On-line papers.

Mon, 12 Sep 2005 | Category: News | Permanent link

Vacation Time

Here are my preliminary plans for when I will be vacationing this summer, or be away at conferences. If you need to contact me, please check this list first. Below are the days in which I won’t be in my office. You can still send me e-mail (especially when I am at conferences) but don’t count on getting a quick reply.

Jul 1–2
I will take these two days off, possibly the 5th as well.
Jul 8–10
Attending the SWAT conference in Denmark.
Jul 12–16
Attending the ICALP conference in Finland.
Last week of July
Vacation in Germany.
Aug 3–10
Camping on Bornholm. Not quite sure about when I’ll be back; depends on the weather.

Mon, 28 Jun 2004 | Category: News | Permanent link

Cryptic Crosswords (in Danish)

I know it’s silly, but I have been toying with the idea of producing cryptic crosswords in Danish, a tradition sadly lacking in what is an otherwise educated nation. My efforts a linked from the sidebar.

Thu, 27 May 2004 | Category: News | Permanent link

SWAT 2004

I will be attending this year’s SWAT July 8–10 (often not an option because of family birthdays). I’ll stay at the hotel (rather than commuting back to Lund), hoping to catch up with friends and colleagues.

Thu, 06 May 2004 | Category: News | Permanent link

New Paper with Björklund and Khanna

“Approximating longest directed paths and cycles,” to be presented at ICALP 2004.

Abstract: We investigate the hardness of approximating the longest path and the longest cycle in directed graphs on n vertices. We show that neither of these two problems can be polynomial time approximated within n1-ε for any ε>0 unless P=NP. In particular, the result holds for digraphs of constant bounded outdegree that contain a Hamiltonian cycle.

Assuming the stronger complexity conjecture that Satisfiability cannot be solved in subexponential time, we show that there is no polynomial time algorithm that finds a directed path of length Ω(f(n)log2 n), or a directed cycle of length Ω(f(n)log n), for any nondecreasing, polynomial time computable function f in ω(1). With a recent algorithm for undirected graphs by Gabow, this shows that long paths and cycles are harder to find in directed graphs than in undirected graphs.

We also find a directed path of length Ω(log2 n/log log n) in Hamiltonian digraphs with bounded outdegree. With our hardness results, this shows that long directed cycles are harder to find than a long directed paths. Furthermore, we present a simple polynomial time algorithm that finds paths of length Ω(n) in directed expanders of constant bounded outdegree.

Extended abstract under On-line papers.

Thu, 29 Apr 2004 | Category: News | Permanent link

New paper with Alstrup and Rauhe

“Dynamic nested brackets,” to appear in Information and Computation.

Abstract: We consider the problem of maintaining a string of n brackets ‘(’ or ‘)’ under the operation reverse(i) that changes the ith bracket from ‘(’ to ‘)’ or vice versa, and returns ‘yes’ if and only if the resulting string is properly balanced. We show that this problem can be solved on the RAM in time O(log n/loglog n) per operation using linear space and preprocessing. Moreover, we show that this is optimal in the sense that every data structure supporting reverse (no matter its space and preprocessing complexity) needs time Ω(log n/loglog n) per operation in the cell probe model.

Full paper under On-line papers.

As a related curiosity, note this Perl regex:

/^(?{local$d=0})(?:\((?{$d++})|\)(?{$d—-})(?(?{$d<0})(?!))|(?>[^()]*))*(?(?{$d!=0})(?!))$/

Mon, 12 Jan 2004 | Category: News | Permanent link

It’s a girl!

Tony gave birth to a beautiful daughter in the wee hours of Wednesday. 3100g, 51cm, all are well and proud.

Wed, 07 Jan 2004 | Category: News | Permanent link

Visit in Oxford

I’ll be in Oxford December 10–12, attending the RAND/APX workshop, spending money at Thornton’s, and brushing up the old accent.

Mon, 03 Nov 2003 | Category: News | Permanent link

Visit a BRICS

I’ll be visiting Aarhus University Monday, November 11.

Mon, 03 Nov 2003 | Category: News | Permanent link

Room With a View

I switched offices. My new room is E:2416—smaller but with a view. Oh, and it’s closer to the coffee machine.

Fri, 15 Aug 2003 | Category: News | Permanent link

Talks

(This list is not complete.)

General audience talks

Från sociala nätverk till kvantmekanik – ett algoritmiskt perspektiv på vetenskaperna
27 november 2007. Hallands nation, Lund.
Om algoritmiskt tänkande i andra vetenskaper än datavetenskap.

Naturvetenskaperna under den algoritmiska linsen
2 september 2007. Kårhuset, Lund.
Introduktion till naturvetenskaperna för novischer på Lund universitets naturvetenskapliga program.

En linneansk resa från taxonomiberäkning till beräkningstaxonomi
6 juni 2007. Botaniska trädgården, Lund; del av en serie sk “linnéföredrag” i samband med linnéfirandet på nationaldagen.
Om beräkningsbiologi med utgångspunkt i linneansk taxonomi.

Varför har du inte fler vänner?
2007. Lunds universitet. Naturvetenskap, medicin, och teknikdagar för gymnasieelever.
Om sociala nätverk, främst “världen är liten”-fenomener.

Sudoku
2005. Lunds universitet. Naturvetenskap, medicin, och teknikdagar för gymnasieelever.
Introduktion till algoritmer och beräkningskomplexitet med utgångspunkt i sudoku.

Origami, presentinslagning, och hur man viker en bilkarta
9, 10, 11 mars 2004. Lunds universitet, Naturvetenskap och teknikdagar för gymnasieelever.
3 mars 2005. Arbetslag Bästa formen, SVT Malmö.
Kombination av föredrag och pyssel (klippa! vika! pussla!) om beräkningsgeometri från leksaksproblem till industriell produktion.

Kan fyra atombomer slå ut internet?
9, 10, 11 mars 2004. Lund Universitet, Naturvetenskap och teknikdagar för gymnasieelever.
Om modeller, mått och algoritmer för nätverk.

Scientific presentations

Trimmed Moebius Inversion and Graphs of Bounded Degree
21 February 2008. Bordeaux, France. Paper presentation at 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008).
8 February 2008. Institut für Informatik, Humboldt-Universität Berlin. Mitarbeiterseminar Logik in der Informatik. (In German! “Gestutzte Möbiusinversion und Graphen begrenzten Grades.”)

Computing the Tutte polynomial in vertex-exponential time
7 December 2007. Fredercia, Denmark.
Workshop “Graph Theory 2007”.

A new algorithm for Steiner trees with applications to signaling pathways and phylogenetic trees
5 November 2007, Dept. of Theoretical Physics, Lund University.
Computational Biology and Biological Physics seminar.

Inclusion–exclusion in combinatorial optimisation
12 October 2007, Helsinki University.
Helsinki Institute for Information Technology seminar.

A new algorithm for phylogenetic trees and protein interaction networks
20 September 2007, Dept. of Cell and Organism Biology
COB biology seminar.

Fourier meets Möbius: Fast subset convolution
11 June 2007, San Diego, California.
Paper presentation at 39th Annual ACM Symposium on Theory of Computing (STOC).

Sat, 01 Jan 2000 | Category: News | Permanent link

Travel plans

October 26–28, 2008
FOCS 2008, Philadelphia, PA, USA.
October 21–24, 2008
Moderately exponential time algorithms, Schloss Dagstuhl, Wadern, Germany
September 15–17, 2008
ESA 2008, Karlsruhe, Germany
July 6–13, 2008
ICALP 2008, Reykjavik, Iceland
July 2–4, 2008
SWAT 2008, Gothenburg, Sweden.
May 21, 2008
Visiting Stuttgart University
May 9, 2008
Committee member for Jakob Nordström’s Ph.D. defence at KTH Stockholm.
February 20–24, 2008
STACS 2008, Bordeaux, France.
February 8, 2008
Visiting Institut für Informatik at Humboldt-Universität, Berlin
December 6–9, 2007
Graph Theory 2007, Fredericia, Denmark.

Sat, 01 Jan 2000 | Category: News | Permanent link

Papers

The Travelling Salesman Problem in bounded degree graphs
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
35th International Colloquium on Automata, Languages and Programming (ICALP 2008), Part I, LNCS 5125, Springer, 2008, pp. 198–209. submitted manuscript

Trimmed Moebius inversion and graphs of bounded degree
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), Dagstuhl Seminar Proceedings 08001, IBFI Schloss Dagstuhl, 2008, pp. 85–96. [Proceedings version (PDF)]

Computing the Tutte polynomial in vertex-exponential time
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
Proceedings 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2008. [PDF]
Preprint at [arXiv.org].

Fourier meets Möbius: fast subset convolution
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), San Diego, CA, June 11–13, 2007, Association for Computing Machinery, New York, 2007, pp. 67–74. Preprint at [arXiv.org].

Set partitioning via inclusion–exclusion
Andreas Björklund, Thore Husfeldt, and Mikko Koivisto
SIAM J. Comput., Special Issue for FOCS 2006, to appear. [PDF]
The results were announced in two (independent) conference papers at 47th FOCS 2006: Koivisto, An O*(2n) algorithm for graph colouring and other partitioning problems via inclusion-exclusion, pp. 583–590; and Björklund and Husfeldt, Inclusion–exclusion algorithms for counting set partitions, pp. 575–582 [PDF], which began its life as ECCC TR06-44.

Exact algorithms for exact satisfiability and number of perfect matchings
Andreas Björklund and Thore Husfeldt
Algorithmica, Volume 52, Number 2, October 2008, pp. 226–249. (DOI 10.1007/s00453-007-9149-8)
Prelim. version in Proc. 33rd ICALP 2006, Springer LNCS 4051, pp. 548–559 [PDF]

Black box for constant-time insertion in priority queues (note)
Stephen Alstrup, Thore Husfeldt, Theis Rauhe, and Mikkel Thorup
ACM Transactions on Algorithms, Vol. 1:1 (July 2005), pp. 102–106. [PDF]

Approximating longest directed paths and cycles
Andreas Björklund, Thore Husfeldt, and Sanjeev Khanna
31st ICALP 2004, Springer LNCS 3142, pp. 222–233. [PDF]

Dynamic nested brackets
Stephen Alstrup, Theis Rauhe, and Thore Husfeldt
Information and Computation, Vol. 193 (2004), No. 6, pp. 75–83. [PDF via ScienceDirect]
Preliminary version: [PDF]

Finding a path of superlogarithmic length
Andreas Björklund and Thore Husfeldt.
SIAM J. Computing. Vol. 32 (2003), No. 6, pp. 1395–1402. [PDF]
Announced at Proc. 29th ICALP 2002, Springer LNCS 2380, pp. 985-992. [DVI, PS, PDF]

Lower bounds for approximate polygon decomposition and minimum gap.
Joachim Gudmundsson, Thore Husfeldt, and Christos Levcopoulos.
IPL 81(3), 2002, pp. 137-141. [PDF]

A cell probe lower bound for dynamic nearest-neighbour searching.
Stephen Alstrup, Thore Husfeldt and Theis Rauhe.
Proc. 12th SODA 2001, pp. 779-780. [PS.GZ]

Marked Ancestor Problems.
Stephen Alstrup, Thore Husfeldt and Theis Rauhe.
Proc. 38th FOCS 1998, pp. 534-543. [PS.GZ]

New lower bound techniques for dynamic partial sums and related problems.
Thore Husfeldt and Theis Rauhe.
SIAM J. Computing. Vol. 32 (2003), No. 3, pp. 736–753. [PDF]
A preliminary version appeared as Hardness Results for Dynamic Problems by Extensions of Fredman and Saks’ Chronogram Method in Proc. 25th ICALP 1998, Springer LNCS 1443, pp. 67-78. [.dvi], [.ps.gz], [.pdf]

Lower Bounds for Dynamic Transitive Closure, Planar Point Location, and Parentheses Matching.
Thore Husfeldt, Theis Rauhe, and Søren Skyum.
Nordic Journal of Computing 3(4):323-336, Winter 1996. Prelim. version in Proc. 5th SWAT 1996, Springer LNCS 1097, pp. 198-211. [PS.GZ]

Fully Dynamic Transitive Closure in Plane Dags with One Source and One Sink.
Thore Husfeldt.
Proc. 3rd European Symposium on Alorithms (ESA), 1995, Springer LNCS 979, pp. 199-212. [PS.GZ]

Dynamic Algorithms for the Dyck Languages.
Gudmund Skovbjerg Frandsen, Thore Husfeldt, Peter Bro Miltersen, Theis Rauhe, and Søren Skyum.
Proc. 4th Workshop on Algorithms and Data Structures (WADS), 1995, Springer LNCS 955, pp. 98-108. [PS.GZ]

A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth.
Gerth Stølting Brodal and Thore Husfeldt.
BRICS Report RS-96-1, 1996. [PS.GZ]

Sat, 01 Jan 2000 | Category: News | Permanent link

Kryptiske Kryds-og-tværser

Nogle forsøg på at producere kryds-og-tværser på dansk i den “krypiske” tradition, som kendes fra engelske aviser. Alle er PDF-dokumenter. God fornøjelse!

Nummer 1

Nummer 2

Nummer 3

Nummer 4

Nummer 5

Sat, 01 Jan 2000 | Category: News | Permanent link

Teaching materials

Inclusion-exclusion in combinatorial optimisation. [PDF]

Sat, 01 Jan 2000 | Category: News | Permanent link