Manuel Cáceres
Best Student Paper Track A:
Abstract: A minimum chain cover (MCC) of a $k$-width directed acyclic graph (DAG) $G = (V, E)$ is a set of $k$ chains (paths in the transitive closure) of $G$ such that every vertex appears in at least one chain in the cover. The state-of-the-art solutions for MCC run in time $\tilde{O}(k(|V|+|E|))$ [M\"akinen et~at., TALG], $O(T_{MF}(|E|) +...
Ruiwen Dong
Best Student Paper Track B
Abstract: We consider semigroup algorithmic problems in the wreath product $\mathbb{Z} \wr \mathbb{Z}$. Our paper focuses on two decision problems introduced by Choffrut and Karhum\"{a}ki (2005): the \emph{Identity Problem} (does a semigroup contain the neutral element?) and the \emph{Group Problem} (is a semigroup a group?) for finitely generated...
Tsun-Ming Cheung, Hamed Hatami, Pooya Hatami and Kaave Hosseini
Best Paper Track A:
Abstract: In many practical learning problems, the learning task is tractable because it is only required to predict the labels of the data points with specific properties. For example, in large-margin classifiers, one seeks to classify only the data points bounded away from the decision boundary by a...
Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks and Karol Węgrzycki
Best Paper Track B:
Abstract: Seminal results establish that the coverability problem for Vector Addition Systems with States (VASS) is in EXPSPACE (Rackoff, '78) and is EXPSPACE-hard already under unary encodings (Lipton, '76). More precisely, Rosier and Yen later utilise Rackoff's bounding...
Miguel Bosch Calvo, Fabrizio Grandoni and Afrouz Jabal Ameli
Abstract: The 2-Vertex-Connected Spanning Subgraph problem (2VCSS) is among the most basic NP-hard (Survivable) Network Design problems: we are given an (unweighted) undirected graph $G$. Our goal is to find a subgraph $S$ of $G$ with the minimum number of edges which is $2$-vertex-connected, namely $S$...