Department of Informatics: Nye registreringer
Viser treff 21-40 av 981
-
FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges
(Journal article; Peer reviewed, 2023)We study the α-Fixed Cardinality Graph Partitioning (α-FCGP) problem, the generic local graph partitioning problem introduced by Bonnet et al. [Algorithmica 2015]. In this problem, we are given a graph G, two numbers k,p ... -
An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL
(Journal article; Peer reviewed, 2023)In general, a graph modification problem is defined by a graph modification operation ⊠ and a target graph property 𝒫. Typically, the modification operation ⊠ may be vertex deletion, edge deletion, edge contraction, or ... -
Kernelizing Temporal Exploration Problems
(Journal article; Peer reviewed, 2023)We study the kernelization of exploration problems on temporal graphs. A temporal graph consists of a finite sequence of snapshot graphs 𝒢 = (G₁, G₂, … , G_L) that share a common vertex set but might have different edge ... -
An Optimal Universal Construction for the Threshold Implementation of Bijective S-Boxes
(Journal article; Peer reviewed, 2023)Threshold implementation is a method based on secret sharing to secure cryptographic ciphers (and in particular S-boxes) against differential power analysis side-channel attacks which was proposed by Nikova, Rechberger, ... -
On the Parameterized Complexity of the Structure of Lineal Topologies (Depth-First Spanning Trees) of Finite Graphs: The Number of Leaves
(Journal article; Peer reviewed, 2023)A lineal topology T = (G, r, T ) of a graph G is an r-rooted depth-first spanning (DFS) tree T of G. Equivalently, this is a spanning tree of G such that every edge uv of G is either an edge of T or is between a vertex u ... -
Combing a Linkage in an Annulus
(Journal article; Peer reviewed, 2023)A linkage in a graph 𝐺 of size 𝑘 is a subgraph 𝐿 of 𝐺 whose connected components are 𝑘 paths. The pattern of a linkage of size 𝑘 is the set of 𝑘 pairs formed by the endpoints of these paths. A consequence of the ... -
Approximating Long Cycle Above Dirac's Guarantee
(Journal article; Peer reviewed, 2023)Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit "natural" guarantees bringing to algorithmic questions whether a better ... -
Living without Beth and Craig: Definitions and Interpolants in Description and Modal Logics with Nominals and Role Inclusions
(Journal article; Peer reviewed, 2023)The Craig interpolation property (CIP) states that an interpolant for an implication exists iff it is valid. The projective Beth definability property (PBDP) states that an explicit definition exists iff a formula stating ... -
Visual Ensemble Analysis of Fluid Flow in Porous Media Across Simulation Codes and Experiment
(Journal article; Peer reviewed, 2024)We study the question of how visual analysis can support the comparison of spatio-temporal ensemble data of liquid and gas flow in porous media. To this end, we focus on a case study, in which nine different research groups ... -
Differentiating between malicious events and natural events in an Operational Technology (OT) environment
(Master thesis, 2024-06-03) -
On Logical Deduction in Large Language Models
(Master thesis, 2024-06-03) -
Polyhedral approach to weighted connected matchings in general graphs
(Journal article; Peer reviewed, 2024)A connected matching in a graph G consists of a set of pairwise disjoint edges whose covered vertices induce a connected subgraph of G. While finding a connected matching of maximum cardinality is a well-solved problem, ... -
Low-Rank Parity-Check codes : Generalization and Improved Decoding for Low-Rank Parity-Check Codes
(Doctoral thesis, 2024-08-23)I 1978 foreslo McEliece en kryptografisk nøkkelforankringsmekanisme basert på kodeteori. Det underliggende matematiske problemet med å dekode en tilfeldig lineær kode ble bevist å være NP-fullstendig av McEliece og Berlekamp ... -
Two new algorithms for error support recovery of low rank parity check codes
(Journal article; Peer reviewed, 2023)Due to their weak algebraic structure, low rank parity check (LRPC) codes have been employed in several post-quantum cryptographic schemes. In this paper we propose new improved decoding algorithms for [n, k]qm LRPC codes ... -
Computing Complexity Measures of Degenerate Graphs
(Journal article; Peer reviewed, 2023)We show that the VC-dimension of a graph can be computed in time n^{⌈log d+1⌉} d^{O(d)}, where d is the degeneracy of the input graph. The core idea of our algorithm is a data structure to efficiently query the number of ... -
Generalized low rank parity check codes
(Journal article, 2023)In this work we propose a family of Fq-linear lowrank parity check (LRPC) codes based on a bilinear product over Fmq defined by a generic 3-tensor over Fq. A particular choice of this tensor corresponds to the classical ... -
Type Theory with Explicit Universe Polymorphism
(Journal article; Peer reviewed, 2023)The aim of this paper is to refine and extend proposals by Sozeau and Tabareau and by Voevodsky for universe polymorphism in type theory. In those systems judgments can depend on explicit constraints between universe levels. ... -
Learning Horn envelopes via queries from language models
(Journal article; Peer reviewed, 2024)We present an approach for systematically probing a trained neural network to extract a symbolic abstraction of it, represented as a Boolean formula. We formulate this task within Angluin's exact learning framework, where ... -
Runtime Enforcement Using Knowledge Bases
(Journal article; Peer reviewed, 2023)Knowledge bases have been extensively used to represent and reason about static domain knowledge. In this work, we show how to enforce domain knowledge about dynamic processes to guide executions at runtime. To do so, we ... -
Towards prediction of CML Treatment Outcomes with Machine Learning and CyTOF Data
(Master thesis, 2024-06-03)Predicting responses to therapy for patients with Chronic Myeloid Leukemia (CML) is crucial for optimizing treatment strategies. This study utilizes machine learning models with mass cytometry (CyTOF) data from samples ...