Colloquia and Seminars

To join the email distribution list of the cs colloquia, please visit the list subscription page.

Upcoming Colloquia & Seminars

  • Parameterized Automata Constructions and Their Applications

    Ran Ben-Basat, M.Sc. Thesis Seminar
    Monday, 22.9.2014, 15:30
    Taub 701
    Prof. Hadas Shachnai

    Parameterization is a useful tool for handling NP-hard problems in the real world. It aims to reduce the running times of algorithms for such problems, by confining the combinatorial explosion to some parameter k. As this parameter is often significantly smaller than the input size, it allows to develop practical algorithms for non-trivial classes of instances for these problems. In this talk we present a novel framework for developing parameterized algorithms, using constructions of automata for the corresponding languages. Our automata-based framework gives a different view of the parameterized versions of several classic problems, including Traveling Salesman and 3D-Matching. We show that many of the previously used techniques for solving these problems imply automata constructions for some implicitly related regular languages. We use automata tools also to infer lower bounds for these techniques. Finally, we note that our framework allows clean and simple design of algorithms for a family of problems, where the design of a single automaton for a specific problem yields deterministic, randomized and approximate witness counting algorithms for the problem.