Archive Page 2

LATA paper

My paper, Restarting Automata with Auxiliary Symbols and Small Lookahead, has been accepted for LATA 2011, a relatively new but increasingly important conference in theoretical computer science, especially for researchers in formal languages, computability, logic and automata. 

Here’s my abstract:

We present a study on lookahead hierarchies for restarting automata with auxiliary symbols and small lookahead.  In particular, we show that there are just two different classes of languages recognised by RRWW automata, through the restriction of lookahead size.  We also show that the respective (left-) monotone restarting automaton models characterise the context-free languages and that the respective right-left-monotone restarting automata characterise the linear languages both with just lookahead length 2.

Current Trends in Exponential Time Algorithms (Ph.D. Course)

Ph.D. Course at ITU Copenhagen in exponential time algorithms, including parameterised computation.

When: We meet Thursdays at 10 AM, starting 3 March 2011.

Who: This course is organised by Thore Husfeldt, ITU and aimed at Ph.D. students and advanced graduate students. Send Thore an email if you plan to attend or have questions.

Format: Weekly meetings (1-2 hours) of informal seminar-style presentation of selected recent papers. Participants are encouraged to discuss their own research, including open problems, partial progress, and half-baked results. 10-12 meetings during the Spring term 2011.

Prerequisites: This is a research-level course. Prerequisites correspond roughly to the monograph F. Fomin and D. Kratsch, Exact Exponential Algorithms, Springer 2010.

ECTS: Active participation in this course yields 2.5 ECTS.


  • 3 Mar at 11 AM in 4A05: Konstantin Kutzkov about bicliques. Relevant papers:
    1. Reduction between Maximum Frequent Itemsets(k1, k2) and Biclique(k1, k2): Gunopulos, D., Khardon, R., Mannila, H., Saluja, S., Toivonen, H., Sharm, R.S.:
      Discovering all most specific sentences. ACM Trans. Database Syst. 28(2), 140–174
    2. Biclique(k1, k2) is NP-complete: David Johnson, The NP-Completeness Column: An Ongoing Guide, J.Algorithms, 1987
    3. Inapproximability of Biclique(k1, k2): Khot, S.: Ruling out ptas for graph min-bisection, densest subgraph and bipartite clique. In: FOCS, pp. 136–145 (2004)
    4. Biclique(k1, k2): In FPT or W[1]-hard: Open Problems from Dagstuhl Seminar 07281:
      ( page 4: The problems proposed by Mike Fellows and Daniel Marx.
    5. A parameterized algorithm for Bipartite VC: H. Fernau and R. Niedermeier. An efficient exact algorithm for constraint bipartite vertex cover. Journal of Algorithms, 38(2):374–410, 2001.
    6. Exact non-parameterized algorithm for Biclique(k1, k2): Daniel Binkele-Raible, Henning Fernau, Serge Gaspers, Mathieu Liedloff: Exact exponential-time algorithms for finding bicliques.
      Inf. Process. Lett. 111(2): 64-67 (2010)
    7. The paper showing that Minimum Infrequent Set is W[2]-hard: Mario Boley. On Approximating Minimum Infrequent and Maximum Frequent Sets. Discovery Science, page 68-77. 2007 (Section 2)
  • 10 Mar at 10AM, in 409: Thore Husfeldt presents Imagliazzo, Paturi: On the Complexity of k-SAT. J. Comput. Syst. Sci. 62(2): 367-375 (2001). [PDF]. (note change!)
  • 17 Mar at 11AM, in 4A05: Nina Taslaman presents Calabro et al.: On the Exact Complexity of Evaluating Quantified k-CNF. From proceedings of IPEC 2010
  • 24 Mar at 11AM, in 4A09: Andreas Björklund on Hamiltonicity detection in cubic graphs.
  • 31 Mar at 10AM, in 4A09: Thore Husfeldt on algorithms for the permanent, based on arxiv0904.3251 (also Inf. Process. Lett. 110(20): 867-870 (2010)).
  • 7 April at 10AM, in XXXX: Natalie Schluter presents (part of) Golovach et al.: Colorings with Few Colors: Counting, Enumeration and Cominatorial Bounds.  From proceedings of WG 2010.
  • 14 April at 11AM, in XXXX: Thore Husfeldt presents Kawarabayashi’s paper on an algorithm for the k-cycle problem.
  • 28 April at 10AM, in 4A05: Natalie Schluter presents Grigni: A Sperner Lemma Complete for PPA.  In Information Processing Letters, 77(5-6): 255-259 (2001).
  • 5 May at 10AM in 2A05: Søren Bøg presents “Planning over chain causal graphs for variables with domains of size 5 Is NP-hard” af O. Giménez og A. Jonsson, abstract.
  • 12 May: No meeting
  • 19 May, 11 AM in 4A05: Thore Husfeldt presents arxiv1103.0534.


The ALGOSENSORS 2011 call for papers is out. The interesting thing about this event is that it somehow spans the research themes represented in the Efficient Computation group. I’m not sure if there will be any submissions from us this time around, but the event is definitely worth keeping an eye on to spot developments of broad interest within the group.

Leaps of human civilization

Human civilization has made a number of leaps in development that allowed people to travel longer and longer distances without the need to spend several nights on the way. What few people realize is that a recent invention dramatically increased the length that families with children can travel.
Nintendo DS
On Thursday, I will leave for a 5-month stay at Carnegie Mellon University, and will remember to put two gadgets in the hand luggage for sure!

Open position

A position as assistant/associate professor has just been announced here. It is a general call for computer science, but preference will be given to candidates doing research related to (1) programming, logic and semantics, or (2) computer systems. Candidates in the latter category are potential members of the efficient computation group. If you know of excellent candidates, encourage them to apply!

NP-hardness in first grade

Math education is changing (slowly, but changing). I was pleased to see that my 1st grade daughter is asked to solve (weakly) NP-hard problems at school! Look at the below page, with many instances of the subset sum problem:

Hard problems in first grade

When asking her about the solution strategy it sounded like brute force search. Perhaps the dynamic programming solution will come later. I wonder in what grade they start posing strongly NP-hard problems!? And what this will mean for our teaching 20 years from now.

Visit by Ninh Dang Pham

Today Ninh Dang Pham from Faculty of Computer Science and Engineering, HoChiMinh City University of Technology, Vietnam, will speak on “Mining Patterns in Time Series Data” in room 2A05 from 11-12. All are welcome. Ninh will be visiting our group Monday-Wednesday.

Upcoming PhD defense

Rasmus Resen Amossen will defend his PhD thesis on Friday January 14 in Aud. 2, starting at 1 PM with a 1-hour presentation of his work. A reception will be held after the defense. Hope to see many people there!

10th IEEE International conference on data mining - ICDM2010

Today is raining. Usual.
I am in Sydney, Australia, where I attended ICDM2010. This conference is a bit unusual, at least
for me. The reason why I say so, is that the people attending the conference come from various
sectors of the economical world. Better: not only there are people from academia, like professors,
phd students and the like, but also many people from private companies that are not only the
usual famous computer science connected ones, and also freelances and people from state
agencies, including the DOD it seems.
It definitely sounds like data mining is getting a huge interest in the world of applied informatics.

I attended a bunch of nice and interesting talks, mainly concerning streaming and association
rules. However, these two topics seem to get less attention than in the former years, while
clustering and social networks mining are an ever green the former and an emerging strong
topic the latter.

Tomorrow I will be flying over Mongolia and the Gobi desert again. No Himalaya though.

Vector Rally World Record

What do efficient computation people do when they have time to spare? Well, it depends, but some of them set out to be #1 on the Vector Rally world rankings. Also a good teaching showcase for BFS!

Happy holidays!

« Previous PageNext Page »