Current Trends in Computer Science (Conference)

I participated in a two-day conference organized by the Institute of Theoretical Computer Science in Prague entitled "Current Trends of Theoretical Computer Science" (STTI 2009). The presentations were invitation-only, which was mainly based on the criterion that the invitee had a publication at a well-established conference. The presentations were carried out in Czech and Slovak, which was a common source of amusement as few were used to that.

Talks

The number of talks was rather large so let me mention some representatives. The main talk was given by Viliam Geffert on finite state automate minimization. Minimization of standard DFAs is a well-known problem, this talk has addressed minimization modulo introducing finitely-many errors in the output of the result of the minimization. The motivation for such types of reduction is that if a certain device is running for an unbounded period of time, a finite number of errors at the beginning does not pose a problem.

Matus Mihalak presented a nice algorithmic problem in which a number of cops are guarding a certain region of a graph against a robber. Some complexity results were presented. For instance that the problem is NP-complete when the graph is a tree.

Another nice algorithmic problem was solved by Pavel Surynek: how to move a group of robots to desired destinations in a graph; with the additional objective to find minimal plans. This problem is motivated by traffic or warehouse organization. Pavel has targeted a special case when the graph is 2-connected. For intuition, Lloyd's 15 puzzle is a special case of this problem.

A problem from the bio-informatics was presented by Brona Brejová. Given a Hidden Markov Model (HMM) and a chain of transitions, one is to find the most probable sequence of states in the model that would correspond to the sequence of transitions. The classical algorithm solving the problem uses memory proportional to the length of the transition-sequence and number of states in the HMM. This is too much for the examples coming up in bio-informatics and thus Brona and her coauthors devised an online algorithm discarding unneeded memory.

Several talks were on complexity classifications. Stanislav Živný presented some of his results on so-called submodular polynomials. These are pseudo-boolean polynomials satisfying an additional constraint called submodularity. Minimization of these polynomials can be done in cubic time for quadratic polynomials. Stanislav has been investigating for which polynomials can minimization be translated into minimization of quadratic ones.

Jiri Srba gave an overview of recent complexity results for Visibly pushdown automata. Those are such pushdown automata where each operation must always push/pop a fixed number of symbols from the stack. These automata are interesting for program verification as equivalence is decidable (in program analysis the stack models the callstack). One of the mentioned results of Jiri was that deciding bisimulation for visibly pushdown automata is EXPTIME-complete.

Eva Jelínková has presented a problem from the graph realm. Eva has investigated the complexity of deciding whether a clustered graph can be drawn nicely in a plane. A clustered graph is graph in which nodes may be contained in clusters; clusters are either disjoint or one is a subset of another. By nicely I mean that the clusters can be drawn as closed curves that do not intersect.

Rastislav Královic presented a problem from the networking domain. Rastislav has investigated how strong of an opponent can we have when the game is that we need to send a message in a network and the opponent is allowed to discard certain number of messages. One of the presented results was that a message can still be delivered even if the opponent can discard all but one message in each step.

Problem Section

An interesting part of the conference was the Problem Section, where whoever wanted presented a small (open) problem. I have presented a problem that I've bumped into recently and Radu wrote up here (I was a bit surprised that I haven't got an answer or pointer (yet)).

Martin Klazar has presented a so-called Skolem's problem which was is it decidable that a recurrent sequence hits a 0?

Libor Barto has presented a hard-core question, what is the minimal tree for which H-coloring is NP-complete?

Summary

All in all, I would like to say that it was a nice experience. All participants came neither for fame nor for money and still the talks were given in an excellent quality. I'm glad that I went as I enjoyed the overall spirit of the conference and not only I learned about the result of my countrymen but about theoretical computer science in general.

P.S. apologies to those whose names are not spelled properly but my patience is quite limited when it comes to diacritical problems :)

P.P.S. Mr. Nesetril, the program chair, told me that it is not correct that anybody could have participated in the Problem Section as he filtered the topics beforehand.