Publications

Hybrid Approach to Twin-width by Taming Red (HATTER): A heuristic solver for finding twin-width of an undirected graph

Under Review: Latin American Theoretical Informatics (LATIN), 2024

Twin-width was introduced by Bonnet et al. in 2020. The graph parameter twin-width intuitively measures the distance of a graph to a co-graph. In this paper, we propose “Hybrid Approach to twin-width by Taming Red (HATTER)”, a novel heuristic solver for computing the twin width of an undirected graph. The solver can be accessed through this link. We use preprocessing and divide-and-conquer techniques in HATTER. In the preprocessing phase, we first apply a reduction technique on the degree one vertices of the input graph based on some property. Later, we decompose the preprocessed graph into several components and compute the contraction sequence for each of these components independently. Finally, we identify vertices until the graph is reduced to a single vertex.

Recommended citation: Talika Gupta, Srinibas Swain, “Hybrid Approach to Twin-width by Taming Red (HATTER): A heuristic solver for finding twin-width of an undirected graph”, Latin American Theoretical Informatics (LATIN), 2024

Coreference in Long Documents using Hierarchical Entity Merging

Published in SIGHUM Workshop on Computational Linguistics for Cultural Heritage, Social Sciences, Humanities and Literature (LaTeCH-CLfL), 2024

Current top-performing coreference resolution approaches are limited with regard to the maximum lengths of texts they can accept. We explore a recursive merging technique of entities that allows us to apply coreference models to texts of arbitrary length. In experiments on established datasets we quantify the drop in resolution quality caused by this approach. Finally we use an under-explored resource in the form of a fully coreference annotated novel to illustrate our models performance for long documents in practice. On this novel we achieve state-of-the-art performance, outperforming previous systems capable of handling long documents.

Recommended citation: Talika Gupta, Hans Ole Hatzel, Chris Biemann, “Coreference in Long Documents using Hierarchical Entity Merging”, SIGHUM Workshop (LaTeCH-CLfL), EACL 2024 https://www.inf.uni-hamburg.de/en/inst/ab/lt/publications/2024-gupta-et-al-sighum.pdf