[Facets-of-complexity] Invitation to Monday's Lecture & Colloquium Dec.13 ! - online via Zoom.

["I.Brunke" <i.brunke@fu-berlin.de>]

Dear all,

next Monday's Lecture and Colloquium will take place online via Zoom on December 13.

Please find link to Zoom Meeting here:

https://hu-berlin.zoom.us/j/66440063420?pwd=VkhwYytqNHJBZW83b3hUL1g4cTV5Zz09

A password is required this time!

Meeting ID: 664 4006 3420
Password: 961144

You all are cordially invited!

Location:

Online via Zoom.

Monday's Lecture: Florin Manea (Universität Göttingen)

Time: Monday, December 13 - 14:15 h

Title: Combinatorial String Solving

Abstract:

We consider a series of natural problems related to the processing of textual data, rooted in areas as diverse as information extraction, bioinformatics, algorithmic learning theory, or formal verification, and see how they can all be formalized within the same framework. In this framework, we say that a pattern $\alpha$ (that is, a string of string-variables and letters from a fixed alphabet $\Sigma$) matches another pattern $\beta$ if a text $T$, over $\Sigma$, can be obtained both from $\alpha$ and $\beta$ by uniformly replacing the variables of the two patterns by words over $\Sigma$. In the case when $\beta$ contains no variables, i.e., $\beta=T$ is a text, a match occurs if $\beta$ can be obtained from $\alpha$ by uniformly replacing the variables of $\alpha$ by words over $\Sigma$. The respective matching problems, i. e., deciding whether two given patterns match or a pattern and a text match, are computationally hard, but efficient algorithms exist for classes of patterns with restricted structure. In this talk, we overview a series of recent results in this area.


Break

Monday's Colloquium: Markus Schmid (Humboldt-Universität zu Berlin)

Time: Monday, December 13 - 16:00 h s.t.

Title: Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number

Abstract:

We investigate the locality number, a recently introduced structural parameter for strings (with applications in pattern matching with variables), and its connection to two important graph-parameters, cutwidth and pathwidth. These connections allow us to show that computing the locality number is NP-hard, but fixed-parameter tractable, if parameterised by the locality number or by the alphabet size, which has been formulated as open problems in the literature. Moreover, the locality number can be approximated with ratio O(\sqrt{log(opt)} log(n))$.
An important aspect of our work --- that is relevant in its own right and of independent interest --- is that we identify connections between the string parameter of the locality number on the one hand, and the famous graph parameters of cutwidth and pathwidth, on the other hand. These two parameters have been jointly investigated in the literature (with respect to exact, parameterised and approximation algorithms), and are arguably among the most central graph parameters that are based on "linearisations" of graphs. Most importantly, we relate cutwidth with pathwidth via the locality number, which results in an approximation preserving reduction that improves the currently best known approximation algorithm for cutwidth.
[This is based on joint work with Katrin Casel, Joel D. Day, Pamela Fleischmann, Tomasz Kociumaka, and Florin Manea, published in Proc. ICALP'19.]

You all are cordially invited!

Virenfrei. www.avast.com