Archive for February, 2011

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.