Department of Informatics
Recent Submissions
-
On decoding additive generalized twisted Gabidulin codes
(Journal article; Peer reviewed, 2020)In this paper, we consider an interpolation-based decoding algorithm for a large family of maximum rank distance codes, known as the additive generalized twisted Gabidulin codes, over the finite field Fqn for any prime ... -
Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth
(Journal article; Peer reviewed, 2020)The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time 2^𝒪(tw)n^𝒪(1), for Feedback Vertex Set and connected versions of ... -
Finite and Confident Teaching in Expectation: Sampling from Infinite Concept Classes
(Frontiers in Artificial Intelligence and Applications;325, Chapter, 2020)We investigate the teaching of infinite concept classes through the effect of the learning prior (which is used by the learner to derive posteriors giving preference of some concepts over others and by the teacher to devise ... -
Measures in Visualization Space
(Chapter, 2020)Measurement is an integral part of modern science, providing the fundamental means for evaluation, comparison, and prediction. In the context of visualization, several different types of measures have been proposed, ranging ... -
The directed 2-linkage problem with length constraints
(Journal article; Peer reviewed, 2020) -
GAPGOM—an R package for gene annotation prediction using GO metrics
(Journal article; Peer reviewed, 2021)Objective Properties of gene products can be described or annotated with Gene Ontology (GO) terms. But for many genes we have limited information about their products, for example with respect to function. This is ... -
The Parameterized Complexity of Guarding Almost Convex Polygons
(Journal article; Peer reviewed, 2020)The Art Gallery problem is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k; the task is to decide ... -
A (2 + ε)-Factor Approximation Algorithm for Split Vertex Deletion
(Journal article; Peer reviewed, 2020)In the Split Vertex Deletion (SVD) problem, the input is an n-vertex undirected graph G and a weight function w: V(G) → ℕ, and the objective is to find a minimum weight subset S of vertices such that G-S is a split graph ... -
The differential spectrum of a ternary power mapping
(Journal article; Peer reviewed, 2020)A function f(x)from the finite field GF(pn)to itself is said to be differentially δ-uniform when the maximum number of solutions x ∈GF(pn)of f(x +a) −f(x) =bfor any a ∈GF(pn)∗and b ∈GF(pn)is equal to δ. Let p =3and d =3n−3. ... -
Fault tolerant subgraphs with applications in kernelization
(Journal article; Peer reviewed, 2020)In the past decade, the design of fault tolerant data structures for networks has become a central topic of research. Particular attention has been given to the construction of a subgraph H of a given digraph D with as ... -
On the parameterized complexity of deletion to H-free strong components
(Journal article; Peer reviewed, 2020)Directed Feedback Vertex Set (DFVS) is a fundamental computational problem that has received extensive attention in parameterized complexity. In this paper, we initiate the study of a wide generalization, the H-SCC Deletion ... -
Development and validation of a universal blood donor genotyping platform: A multinational prospective study
(Journal article; Peer reviewed, 2020)Each year, blood transfusions save millions of lives. However, under current blood-matching practices, sensitization to non–self-antigens is an unavoidable adverse side effect of transfusion. We describe a universal donor ... -
Approximation in (poly-) logarithmic space
(Journal article; Peer reviewed, 2020)We develop new approximation algorithms for classical graph and set problems in the RAM model under space constraints. As one of our main results, we devise an algorithm for d–Hitting Set that runs in time nO(d2+(d/ε)), ... -
Quick separation in chordal and split graphs
(Journal article; Peer reviewed, 2020)In this paper we study two classical cut problems, namely Multicut and Multiway Cut on chordal graphs and split graphs. In the Multicut problem, the input is a graph G, a collection of 𝓁 vertex pairs (si, ti), i ∈ [𝓁], ... -
A Polynomial Kernel for Paw-Free Editing
(Journal article; Peer reviewed, 2020)For a fixed graph H, the H-free Edge Editing problem asks whether we can modify a given graph G by adding or deleting at most k edges such that the resulting graph does not contain H as an induced subgraph. The problem is ... -
Type theoretical databases
(Journal article; Peer reviewed, 2020)We show how the display-map category of finite (symmetric) simplicial complexes can be seen as representing the totality of database schemas and instances in a single mathematical structure. We give a sound interpretation ... -
Building large k-cores from sparse graphs
(Journal article; Peer reviewed, 2020)A popular model to measure network stability is the k-core, that is the maximal induced subgraph in which every vertex has degree at least k. For example, k-cores are commonly used to model the unraveling phenomena in ... -
ETH-tight algorithms for long path and cycle on unit disk graphs
(Journal article; Peer reviewed, 2020)We present an algorithm for the extensively studied Long Path and Long Cycle problems on unit disk graphs that runs in time 2O(√k)(n + m). Under the Exponential Time Hypothesis, Long Path and Long Cycle on unit disk graphs ... -
Application of quantitative transcriptomics in evaluating the ex vivo effects of per- and polyfluoroalkyl substances on Atlantic cod (Gadus morhua) ovarian physiology
(Journal article; Peer reviewed, 2021)Because of their global consumption and persistence, per- and polyfluoroalkyl substances (PFASs), are ubiquitously distributed in the environment, as well as in wildlife and humans. In the present study, we have employed ... -
On equivalence between known families of quadratic APN functions
(Journal article; Peer reviewed, 2020)This paper is dedicated to a question whether the currently known families of quadratic APN polynomials are pairwise different up to CCZ-equivalence. We reduce the list of these families to those CCZ-inequivalent to each ...
RSS 2.0