Department of Informatics
Recent Submissions

A Polynomial Kernel for Line Graph Deletion
(Journal article; Peer reviewed, 2020)The line graph of a graph G is the graph L(G) whose vertex set is the edge set of G and there is an edge between e,f ∈ E(G) if e and f share an endpoint in G. A graph is called line graph if it is a line graph of some ... 
Transversals of longest paths
(Journal article; Peer reviewed, 202003)Let lpt(G) be the minimum cardinality of a transversal of longest paths in G, that is, a set of vertices that intersects all longest paths in a graph G. There are several results in the literature bounding the value of ... 
Reconstructing ribosomal genes from large scale total RNA metatranscriptomic data
(Journal article; Peer reviewed, 20200313)Motivation Technological advances in metatranscriptomics have enabled a deeper understanding of the structure and function of microbial communities. ‘Total RNA’ metatranscriptomics, sequencing of total reverse transcribed ... 
A complexity dichotomy for critical values of the bchromatic number of graphs
(Journal article; Peer reviewed, 2020)A bcoloring of a graph G is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The bColoring problem asks whether a graph G has ... 
Reducing Graph Transversals via Edge Contractions
(Journal article; Peer reviewed, 2020)For a graph parameter π, the Contraction(π) problem consists in, given a graph G and two positive integers k,d, deciding whether one can contract at most k edges of G to obtain a graph in which π has dropped by at least ... 
Statistical considerations for the design and interpretation of proteomics experiments
(Doctoral thesis, 20210610)The methods to study proteins are continuously improving, making it possible to identify and study increasingly more proteins. It is important to keep studying and improving the way experiments are designed, performed, and ... 
Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes
(Journal article; Peer reviewed, 2020)Given a vertexcolored graph, we say a path is a rainbow vertex path if all its internal vertices have distinct colors. The graph is rainbow vertexconnected if there is a rainbow vertex path between every pair of its ... 
Geometric Planar Networks on Bichromatic Points
(Journal article; Peer reviewed, 2020)We study four classical graph problems – Hamiltonian path, Traveling salesman, Minimum spanning tree, and Minimum perfect matching on geometric graphs induced by bichromatic ( Open image in new window and Open image in new ... 
Metagenomeassembled genome distribution and key functionality highlight importance of aerobic metabolism in Svalbard permafrost
(Journal article; Peer reviewed, 2020)Permafrost underlies a large portion of the land in the Northern Hemisphere. It is proposed to be an extreme habitat and home for coldadaptive microbial communities. Upon thaw permafrost is predicted to exacerbate increasing ... 
Classification of quadratic APN functions with coefficients in F2 for dimensions up to 9
(Journal article; Peer reviewed, 2020)Almost perfect nonlinear (APN) and almost bent (AB) functions are integral components of modern block ciphers and play a fundamental role in symmetric cryptography. In this paper, we describe a procedure for searching for ... 
A New Family of APN Quadrinomials
(Journal article; Peer reviewed, 2020)The binomial B(x) = x 3 +βx 36 (where β is primitive in F 2 2) over F 2 10 is the first known example of an Almost Perfect Nonlinear (APN) function that is not CCZequivalent to a power function, and has remained unclassified ... 
Partially APN functions with APNlike polynomial representations
(Journal article; Peer reviewed, 2020)In this paper we investigate several families of monomial functions with APNlike exponents that are not APN, but are partially 0APN for infinitely many extensions of the binary field F2. We also investigate the differential ... 
Making the BKW Algorithm Practical for LWE
(Journal article; Peer reviewed, 2020)The Learning with Errors (LWE) problem is one of the main mathematical foundations of postquantum cryptography. One of the main groups of algorithms for solving LWE is the BlumKalaiWasserman (BKW) algorithm. This paper ... 
On the Distance Between APN Functions
(Journal article; Peer reviewed, 2020)We investigate the differential properties of a vectorial Boolean function G obtained by modifying an APN function F . This generalizes previous constructions where a function is modified at a few points. We characterize ... 
Macroscale mesenchymal condensation to study cytokinedriven cellular and matrixrelated changes during cartilage degradation
(Journal article; Peer reviewed, 2020)Understanding the pathophysiological processes of cartilage degradation requires adequate model systems to develop therapeutic strategies towards osteoarthritis (OA). Although different in vitro or in vivo models have been ... 
Efficient hash maps to G2 on BLS curves
(Journal article; Peer reviewed, 2020)When a pairing e:G1×G2→GT, on an elliptic curve E defined over a finite field Fq, is exploited for an identitybased protocol, there is often the need to hash binary strings into G1 and G2. Traditionally, if E admits a ... 
Attacks on IntegerRLWE
(Journal article; Peer reviewed, 2020)In 2019, Gu Chunsheng introduced IntegerRLWE, a variant of RLWE devoid of some of its efficiency flaws. Most notably, he proposes a setting where n can be an arbitrary positive integer, contrarily to the typical construction ... 
Bifurcation and sensitivity analysis reveal key drivers of multistability in a model of macrophage polarization
(Journal article; Peer reviewed, 2020)In this paper, we present and analyze a mathematical model for polarization of a single macrophage which, despite its simplicity, exhibits complex dynamics in terms of multistability. In particular, we demonstrate that an ... 
Some grouptheoretical results on Feistel Networks in a longkey scenario
(Journal article; Peer reviewed, 2020)The study of the trapdoors that can be hidden in a block cipher is and has always been a highinterest topic in symmetric cryptography. In this paper we focus on Feistelnetworklike ciphers in a classical longkey scenario ... 
On the EAclasses of known APN functions in small dimensions
(Journal article; Peer reviewed, 2020)Recently Budaghyan et al. (Cryptogr. Commun. 12, 85–100, 2020) introduced a procedure for investigating if CCZequivalence can be more general than EAequivalence together with inverse transformation (when applicable). In ...